python - Ordering CONCAVE polygon vertices in (counter)clockwise?

8
votes

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.

1
pythonalgorithm
What did you find in your search for an algorithm to find the concave hull of a set of points ? Once you have those points a walk around them ought to be straightforward to program. – High Performance Mark
@HighPerformanceMark I think you are referring to the alpha shape. Yes, I have looked into it, but encountered an unsolved issue here and therefore cannot proceed. – Sibbs Gambling
I don't think clockwise and counter-clockwise order make any sense when talking about the vertices of a general concave polygon. – martineau
@martineau But in order for the point-in-polygon algorithm Ray Casting Method to work, one has to order the vertices first and then perform it. I actually feel the same way but confused what to do if they are just unordered like so. Could ypu please advise? – Sibbs Gambling
The points could be ordered in more than one way -- all creating valid polygons of different types (including those with self-intersecting edges). For example another ordering I can think of would be picking the closest neighboring point. That could be further restricted to the closest that doesn't cross an existing edge. Could get very slow, like trying to solve the traveling-salesman shortest path problem. – martineau

1 Answers

13
votes

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

  Four points on the plane in a non-convex arrangement

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

  Polygon ABCD   Polygon ACDB   Polygon ACBD

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:

  Simple non-convex polygon with many vertices

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.