14
$\begingroup$

In my research, I've recently started to play with Voronoi tessellations. I currently have a Python code that creates the tessellation and I am trying to color the polygonal regions according to their regularity. The best-case scenario would be to have a color scale (let's say from red to blue) where regions in red would be the "most irregular" (in some sense) and regions in blue would be the "most regular" (in some sense). It is not strictly necessary to have a scale; I would happily settle to color regions by range, e.g., if the region is "very irregular" I color it red, if it is "sort of regular" I color it yellow and if it is "regular" I color it green.

What I am looking for is a way to associate a number to say how regular a polygon is (for now, I am more interested in hexagons, but it wouldn't hurt to have something for a general polygon).

For example, the first idea that came to mind was taking the average of the angles and measuring the difference from this average to the expected internal angle of the hexagon (which is $2\pi/3$), but this does not work because the average is always $2\pi/3$ since the polygons I'm working with are always convex.

Some ideas that I have discussed with my advisor are

  • looking at $\bar{D}/\sigma(D)$, where $D$ is the set of distances from the vertices of the polygon to it's center, $\bar{D}$ is the average of $D$ and $\sigma(D)$ is the standard deviation of $D$. This ratio ranges from 0 ("maximum" irregularity) to $\infty$ ("maximum" regularity);
  • looking only at $\sigma(D)$, which ranges from 0 ("maximum" regularity) to $\infty$ ("maximum" irregularity).

If possible, I would like to work only with angles due to the way the code I have produces the Voronoi tessellation. However, my intuition says that either

  1. I'll have to forget angles altogether and look only at distances;
  2. I'll have to look at angles and at distances.

Therefore, my question is: is there such a metric for characterizing the regularity of a polygon that involves only the internal angles? If not, is there a more interesting metric that involves distances than the ones I listed above?

I would be more than happy to share more information about the problem if need be.

Edit: this picture it a prototype to what I am trying to do. The green regions are hexagons (regular or not), the white ones are the infinite regions of the tessellation and the red ones are the finite regions that are not hexagons.

$\endgroup$
8
  • $\begingroup$ Too short for a full response: but the space of polygons of fixed length (up to rotation and translation) is double covered by the Grassmanian of planes which has a metric on it that you can use for measuring distance from a given polygon of fixed length to a regular polygon of the same length…but this is maybe not applicable to your setting as lengths can be variable $\endgroup$
    – guest
    Dec 7, 2022 at 11:51
  • 1
    $\begingroup$ A few thoughts which may not be applicable to your situation. One may want notions which are scale invariant, so that dilations of the polygon don't change how irregular it is. In which case $\sigma(D)/M$ where M is the maximum length of a side may be a useful metric. If one wants one that talks about angles, one option is to look at how big the standard deviation of the angles is (although this will be zero for all rectangles). Combinations (linear, products etc.) of these also make sense. $\endgroup$
    – JoshuaZ
    Dec 7, 2022 at 12:04
  • 1
    $\begingroup$ Some more geometric options: The center always exists, and if a polygon is regular, then the angle bisectors and perp bisectors both go through it. Take center of mass and measure how far it is from these segments (either set or both). Another geometric option is to draw a "potential" incircle and circumcircle of the correct radius based on area, with the center of mass, and then somehow measure how much they fail to be the actual incircle and circumcircle (possibly by having the wrong amount of area left over.) For all these metrics, inequalities between them may be interesting. $\endgroup$
    – JoshuaZ
    Dec 7, 2022 at 12:08
  • 2
    $\begingroup$ Side note: Please don't use red/green to distinguish features, use some colorblind friendly coloring scheme instead $\endgroup$ Dec 8, 2022 at 7:19
  • 2
    $\begingroup$ @CaioTomás If you can see what's going on when printed on a monochrome printer, then you're ok. $\endgroup$ Dec 8, 2022 at 20:02

2 Answers 2

13
$\begingroup$

Internal angles are not enough to determine the regularity of a polygon. E.g., angles of $2\pi/3$ between sides of length $1,1,4,1,1,4$ make an irregular hexagon.

For a metric of regularity, I suggest $$A \ / \ \sum d_i^2$$ where $A$ is the area of the hexagon and the $d_i$ are the side lengths.

Using this metric:

  • regular hexagons have a regularity of $\sqrt{3}/4 \sim 0.433$;
  • irregular hexagons have lower regularity;
  • the hexagon with six unit lengths along a $1\times2$ rectangle has a regularity of $1/3$;
  • the hexagon with six unit lengths along a $0\times 3$ rectangle has a regularity of $0$.

The area is easy to calculate as $\sum (x_i y_{i+1}-x_{i+1}y_i)/2$. So the metric should be good for getting a stable optimization, since the numerator and denominator are both simple quadratic functions of the coordinates, not requiring any square roots.

$\endgroup$
10
  • 2
    $\begingroup$ Huh… I first misread your metric as $A \mathbin/ \left(\sum d_i\right)^2$ and thought "yeah, that makes perfect sense, it's measuring the area-to-perimeter ratio," but of course that's not what you actually wrote. Now I'm trying to figure out some geometric intuition for your actual metric. $\endgroup$ Dec 7, 2022 at 20:28
  • 2
    $\begingroup$ If you construct a square outside each edge of the hexagon, then this metric of regularity is the ratio of area inside the hexagon to the sum of the six areas outside the hexagon. (Using the square of the perimeter in the denominator might also work, but that has square roots, so sometimes it may not have a nice derivative, and that can make optimization more awkward.) $\endgroup$
    – user44143
    Dec 7, 2022 at 21:34
  • 2
    $\begingroup$ This is what @IlmariKaronen and I were discussing: $A/(\sum d_i)^2$ is the inverse of the isoperimetric ratio, but I suggested $A/\sum(d_i)^2$ as a more stable (if somewhat less intuitive) alternative. Either could work well depending on the goal of the research. $\endgroup$
    – user44143
    Dec 8, 2022 at 0:16
  • 2
    $\begingroup$ @IlmariKaronen, another way to see it is that in an irregular hexagon with consecutive vertices at $(0,0),(a,b),(1,0)$, you can make the regularity increase by replacing $(a,b)$ with $(\frac12,b)$, since this keeps the area constant and reduces $\sum d_i^2$. Doing that repeatedly and taking the limit will give a regular hexagon as the unique option with maximal regularity. $\endgroup$
    – user44143
    Dec 9, 2022 at 0:02
  • 2
    $\begingroup$ For that last step, if $PQRSTU$ has maximal area among hexagons with unit sides, then $PQRS$ must maximize area among quadrilaterals with $PQ$, $QR$, $RS$ of unit length. If we let $y$ and $z$ be the distances from $Q$ and $R$ to $PS$, then the area of $PQRS$ is $(y\sqrt{1-y^2}+(y+z)\sqrt{1-(y-z)^2}+z\sqrt{1-z^2})/2$, which is uniquely maximized with $y=z=\sqrt{3}/2$, i.e. by half a regular hexagon. wolframalpha.com/input/… $\endgroup$
    – user44143
    Dec 10, 2022 at 16:17
7
$\begingroup$

All indices are in $\mathbb Z\bmod6$.

Let $z_k=\frac{\ell_{k,k+1}}{\ell_{k-1,k}}e^{i(\pi-\theta_k)}=\frac{v_{k+1}-v_k}{v_k-v_{k-1}}$, where $\ell$ is edge length, $\pi-\theta$ is vertex exterior angle, and $v_k\in\mathbb C$ is the $k$th vertex of the polygon. So the complex number $z_k$ scales and rotates one edge at $v_k$ to the other edge, maintaining orientation. (Note that $\prod_kz_k=1$, and $\sum_k\prod_{m=0}^{k-1}z_m=0$.) One measure of irregularity is $\sum_k|z_{k+1}-z_k|^2$.

Another approach is to take the Discrete Fourier Transform of the vertices, i.e. represent the polygon as a $\mathbb C$-linear combination of regular polygons (allowing overlapping vertices or self-intersection): $v_k=\sum_mc_me^{i2\pi mk/6}$. The coefficient $c_0$ encodes the polygon's centre, which we don't care about. The polygon is regular when only one other coefficient $c_m$ is non-zero; however, it's non-convex unless $m=1$ (or maybe $m=-1$, but that has the wrong orientation). So you can use $\sum_{m\neq0,1}|c_m|^2$ as a measure of irregularity. (And for scale invariance you can divide this by $\sum_{m\neq0}|c_m|^2$.)

$\endgroup$
1
  • $\begingroup$ Thank you also for taking the time to answer my question! I think your metric is a good theoretical one, but the area-to-perimeter ratio variation suggested by Matt is easier for me to apply in my code. I think I would never have thought of using DFT, nice! $\endgroup$ Dec 8, 2022 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.