Ordering CONCAVE polygon vertices in (counter)clockwise?

Question

I have a set of disordered vertices that may form a concave polygon. Now I wish to order them in either clockwise or counterclockwise.

An answer here suggests the following steps:

• Find the polygon center
• Compute angles
• Order points by angle

This is obviously only for convex polygon and will fail when the points form a concave one.

How may I do this to a concave one?

I am using Python, but welcome all generic answers.

Answer 1

In general, your problem seems ill-defined. For example, given the following set of vertices:

 

which of these non-convex polygons would you consider to be the "correct" way to connect them?

     

Now, obviously, there are various possible criteria that you could use to choose between different possible orders. For example, you might want to choose the ordering that minimizes the total length of the edges, which should yield fairly "reasonable" results if the points do, in fact, lie fairly close to each other on the boundary of a simple polygon:

 

Unfortunately, for a general set of points, finding the ordering that minimizes the total edge length turns out to be a well known NP-complete problem. That said, there are many heuristic algorithms that can usually find a nearly optimal solution quickly, even if they can't always guarantee that the solution they find is the true minimum.