Sort point list into polygon

Question

I have a set of points. This set of points do define a (non convex) polygon but its not ordered.

Since it's not ordered I cannot just draw from point to point to draw its border. How can I sort it in a way I can walk through this point list and draw a polygon?

My first idea was to use a convex hull but my polygons are, most of the time, concave.

Answer 1

I don't think there's a well-defined solution to this. Consider five points like this:

.   .
  .
.   .

What polygon would be correct here?

Answer 2

You have to order the points so you walk around the polygon with the interior on your left (or right) as you move from point to point. Convex or concave, this is the correct approach.

But knowing the points is not sufficient. You have to know the connectivity of each edge segment as well. Knowing that, you can start at any point and walk along the perimeter until you reach the starting point again.

Answer 3

I'm not sure this is the fastest way, but it seems to work.

The whole idea is to connect the points using line segments that do not intersect (except at the points, and this is a little trickier to define than you might think). So start with the original unsorted list, connect them in order -- forming a closed path that may have many crossings -- and then eliminate the crossings one by one, by means of reversing subsequences of points in the list.

Suppose we start with [a b c d e f g h], and discover that the b-c edge crosses the g-h edge. We reverse the c-g sequence to get a new list: [a b g f e d c h]. Two edges have been removed and two new ones created; the rest are undisturbed (although some have had their directions reversed).

I have not been able to find a case in which this process would run forever (that is, the list would return to a previous state), nor a proof that this cannot happen.