Arrange vertices of CONCAVE polygons in (counter) clockwise?

Question

I have a set of unordered vertices that can form a concave polygon. Now I want to order them clockwise or counterclockwise.

The answer here suggests the following steps:

• Find the center of the polygon
• Calculate angles
• Specify points by angle

This is obviously only for a convex polygon and a failure when the points form a concave.

How can I make it concave?

I use Python, but welcome all the general answers.

Answer 1

All in all, your problem seems fuzzy. For example, given the following set of vertices:

which of these non-convex polygons would you consider the “right” way to connect them?

Now, obviously, there are various possible criteria that can be used to choose between the various possible orders. For example, you can choose the order in which it minimizes the total length of the edges , which should give quite “reasonable” results if the points really lie close enough to each other on the border of a simple polygon:

Unfortunately, for a general set of points, finding an order that minimizes the total length of an edge is a well-known NP-complete problem . However, there are many heuristic algorithms.