polygon_average

polygon_average, a Python code which demonstrates a process of repeatedly averaging and normalizing the vertices of a polygon, illustrating a property of the power method.

The process can be analyzed in terms of the power method, and the eigenvalues of the matrix that carries out the averaging process.

A polygon is represented by a list of N vertices. An averaging step involves:

• replacing each vertex by the average of its two neighbors,
• shifting these vertices to have centroid 0;
• scaling the X and Y coordinates separately so that the max-norms of the X and Y coordinate vectors are both 1.

If the averaging process is carried out recursively, the resulting polygon rapidly converges to an ellipse at a 45 degree tilt.

The direction of the tilt, and the ratio between the major and minor axis lengths, vary depending on the initial polygon.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

polygon_average is available in a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

polygon, a Python code which carries out geometric calculations on polygons, including angles, area, centroid, containment of a point, diameter, integrals of monomials, convexity, distance to a point, sampling, triangulation.

power_method, a Python code which carries out the power method for finding a dominant eigenvalue and its eigenvector.

Reference:

1. Charles Van Loan, Daisy Fan,
   Insight Through Computing,
   SIAM Publishing, 2010,
   ISBN: 978-0-898716-91-7
2. Adam Elmachtoub, Charles Van Loan,
   From Random Polygon to Ellipse: An Eigenanalysis,
   SIAM Review,
   Volume 52, Number 1, March 2010, pages 151-170.

Source Code:

• polygon_average.py, the source code.
• polygon_average.sh, runs all the tests.
• polygon_average.txt, the output file.

• polygon_original.png, a plot of the starting polygon.
• polygon_average.png, a plot of the polygon after 20 averaging steps.