From Random Polygon to Ellipse

Take a polygon with random vertices, find the mid-points of its sides, and use these to create a new polygon, replacing the original. Do this repeatedly and an ellipse will eventually form!

Step 0

Reading the demonstration

• After each step, the polygon is normalised: its x and y coordinates are each rescaled to fill the square. Otherwise it would shrink to a point.
• The dashed ellipse is the one the polygon will become.
• The filled vertex is the first, to show the vertices sliding round. Below, snapshots at steps 0, 1, 2, 4, 8 and so on.
• It stops once every vertex is within half a pixel of the ellipse. Each time the vertices double, that takes four times as many steps, so bigger polygons are run faster.
• With an even number of vertices, alternate steps lie on two slightly different ellipses, so the picture flickers; showing only alternate frames hides it.

Why an ellipse?

I discovered this while reading The Mathematical Experience, shown as an example of "order out of chaos". In fact, Elmachtoub and van Loan show using eigenanalysis that any random polygon will tend towards an ellipse tilted at 45° when undergoing this transformation.

Read the x coordinates, in order round the polygon, as a wave, and the y coordinates as another. Averaging each value with the next smooths both, the fastest wiggles fading fastest, until only the slowest is left: one cosine, once round. One cosine plotted against another of the same period is an ellipse, and scaled to the same size, it lies at 45°. Its shape is fixed from the start by the difference between their phases, which is how the dashed ellipse is drawn.

References

• The Mathematical Experience, Philip J. Davis, Reuben Hersh, pp. 175-177.
• From Random Polygon to Ellipse: An Eigenanalysis, Adam N. Elmachtoub, Charles F. van Loan, SIAM Review 52(1), 2010, pp. 151–170 (free copy).
• Thanks to Phil Howard for suggesting the “show alternate frames” option, and to Roy Tu for pointing out a bug in the implementation.