List of polygon sorting points

Question

I have a set of points. This set of points defines a (non-convex) polygon, but is not ordered.

Since it is not ordered, I cannot just draw from point to point to draw its border. How can I sort it so that I can go through this list of points and draw a polygon?

My first idea was to use a convex body, but my polygons are most often concave.

Answer 1

I do not think there is a clear solution. Consider five such points:

. . . . . 

Which polygon will be right here?

Answer 2

You must order the points so that you walk along the polygon with the inside on the left (or right) when moving from point to point. Convex or concave, this is the right approach.

But knowing the point is not enough. You should also be aware of the connectivity of each edge segment. Knowing this, you can start at any moment and walk along the perimeter until you reach the starting point.

Answer 3

I am not sure if this is the fastest way, but it works.

The whole idea is to connect the points using line segments that do not intersect (other than points, and it's a little harder to determine than you might think). So, start with the original unsorted list, connect them in order - forming a closed path that can have many intersections - and then eliminate the intersections one by one by changing the subsequences of the points in the list.

Suppose we start with [abcdefgh] and find that the edge bc intersects the edge gh. We undo the cg sequence to get a new list: [abgfedch]. Two ribs were removed and two new ones were created; the rest are undisturbed (although some of them have changed direction).

I could not find a case where this process will work forever (i.e. the list will return to its previous state), as well as proof that this cannot happen.