Fitting a general simple polygon to a regular polygon

Question

Is there a method for finding the best fit approximation of a general simple polygon (the coastline of metropolitan France, say) by a regular polygon with given number of sides (a hexagon, say), using any reasonable interpretation of "best fit"?

Answer 1

I've done this kind of thing in the past.

The main idea is to use the fit of a straight line to a set of point that is independent of any axis. This is done by the distance being minimized being the sum of the squares of the lines from the points with the lines being perpendicular to the line being fitted.

I gave a method to do this in an answer somewhere here - I'll see if I can find it.

Aha! Here's the link:

linear least squares minimizing distance from points to rays - is it possible?

Anyway, once you have this method, use an incremental method to construct the fitted lines.

Start with two consecutive points. For each point adjacent to the current points, append the neighboring points. If the fitted line for these points (each considered separately) has a mean square error that is small enough (that's for you to decide), keep that point, and keep adding is that direction. When the adding stops in both directions, that is one of your lines.

Start with two points in one of the directions, only, from now on, only move in that direction.

Continue this until all the points are used.

The time for this is linear in the number of points, so you can try various experiments such as starting at various initial points.

Good luck.