Mean polygons

What does a triangle look like? It is easy to give an answer, but harder to find the best answer: the triangle closest to all others; the mean triangle. The same can be asked of more sided polygons.

Here's my best effort at calculating the mean polygons:

tri: 31, 0.46, 31, 0.27, 118, 0.27. quad: 61, 0.32, 69, 0.32, 61, 0.18, 170, 0.18. pent: 233, 0.08, 70, 0.19, 83, 0.30, 83, 0.24, 70, 0.19.

We can also find the mean of just the convex polygons:

tri: 31, 0.46, 31, 0.27, 118, 0.27. quad: 63, 0.35, 79, 0.20, 109, 0.20, 108, 0.25. pent: 92, 0.32, 91, 0.16, 116, 0.19, 124, 0.18, 117, 0.16.

The asymmetry of two of these is interesting. There are of course two mean shapes in this case, one being the reflection of the other. But whenever you take the mean of this shape with its reflection, the best alignment must on average, create a new mean that looks like the mean shape again (or its reflection). That is what I assume is happening anyway.

If we allow the equivalence class of shapes to include reflections, then we get more asymmetric results:

tri: 16, 0.47, 42, 0.16, 122, 0.37. quad: 32, 0.39, 70, 0.23, 74, 0.16, 184, 0.22. pent: 78, 0.06, 244, 0.22, 57, 0.30, 70, 0.29, 91, 0.12.

And finally, the convex only mean polygons:

 

 
tri: 16, 0.47, 42, 0.16, 122, 0.37. quad: 91, 0.12, 97, 0.22, 135, 0.24, 38, 0.41. pent: 63, 0.36, 110, 0.10, 112, 0.14, 126, 0.22, 129, 0.17.

In order to find these mean polygons, we have to decide what the space of polygons is. 

In my opinion a polygon is defined by a set of interior angles from 0 to 360, and a set of edge lengths. We pick from the set of all such values which produce a valid closed polygon. In practice, we do this by choosing a random set of bearings (from 0 to the expected sum for that polygon), then ordering them and using the adjacent differences as the set of angles. This gives a uniformly distributed set of angles such that they add up to the expected total. We do the same thing for edge lengths. We then check whether the resulting polygon is close to being closed. If it isn't, we throw it out. If it is then we adjust the edge lengths to pull it together (this should only introduce a tiny error if any).

Now we can generate random polygons, we need to decide how to average them. We shouldn't just average the parameters (angles and lengths) because these are shapes, and shapes are an equivalence class. Usually, shapes remain the same shape under Euclidean transformations and scaling. So I average each pair of n-sided polygons together by comparing against all n relative rotations and taking the sum of the products of the interior angles, and multiplying it by the sum of the products of the edge lengths. This is a form of cross correlation, and the greatest match defines how one polygon is rotated relative to the other. We take the mean of the polygon parameters once they are matched (shifted around the loop to be as close as possible). We therefore take the mean of pairs, then take the mean of pairs of these, and so on. The reason I don't just accumulate a running mean, is that I don't want symmetry breaking, where a particular bias then is strengthened.

 

Since people talk about polygons all the time, it is nice to have an actual shape to represent them. The above are arguably the best such 'archetypes'.

But that's not the main reason I made these. I was reading an article recently, which made some overblown claims about cut objects averaging to a topological cube (which is believable, and not really surprising). However, the article gives the impression that the average shape of gravel and other objects is a cube, or cuboid. 

The above results should show that being topologically square does not mean that the average shape is square, far from it. The same goes for cubes.

To be more in-keeping with the article, here is a different way to represent convex polygons: as Voronoi cells. The construction is very simple: 

1. sample points from a uniform distribution in a 2D region

2. get the Delauney triangulation of the points

3. for all points that aren't near the edge of the region, record the points on the other end of the Delauney triangle edges from that point.

4. in a binary tree fashion, average each pair of such point sets by finding the Euclidean transformation of best fit prior to taking the average of the points.

5. from the final set of points, get the Voronoi cell. 

Firstly, we show an already known result, that the most common Voronoi cell is hexagonal:

Voronoi percentages:

• 3: 1.1%
• 4: 10.7%
• 5: 26.0%
• 6: 29.5%
• 7: 19.8%
• 8: 8.9%
• 9: 2.9%
• >9: 0.9%

and here are the average Voronoi cells from 3 to 6 sides:

 It is interesting to see that there is a consistency, all the point sets are like a regular polygon corners, but skewed and elongated in the direction of one of the corners. 

Here are the red/green point locations relative to the blue point:

•  0.0675228 0.00483061
• -0.0159503  0.0266079
• -0.0119852   -0.02871
• 
  
•  0.0302378 -0.0266203
• 0.0484617  0.053221
• -0.0287175  0.0272383
• -0.0250985 -0.0278927
• 
  
• 0.0110074 0.0534107
• -0.0378463 -0.0411285
•  0.0471344 0.00555105
• -0.0695168  0.0349203
•  0.0234685 -0.0416653
• 
  
•  0.0641922 -0.0373106
•  -0.066082 -0.0260613
• 0.0535024  0.030683
• -0.00745943  -0.0856117
• -0.0467536  0.0363132
• 0.00424583  0.0566692

If we allow reflections when finding the closest correspondance then the results look like this (showing extended edges here):

The Voronoi cells are now asymmetric as we would expect, but they are not particularly extreme.