Menu
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:
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.
592
tl;dr By using atan((y-y0) / (x-x0)) , you can calculate the polar angle of a point, based on some reference point (x0, y0) . Sorting based on these angles lets you sort all the points in a clockwise or counterclockwise direction.
Orientation of a simple polygonIf the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant is non-zero if points A, B, and C are non-collinear.
Order vertices of a convex polygon You can use the centroid as the origin and construct the vectors from the centroid to each vertex. For each vector, you can compute the angle made with the horizontal axis. You can then sort the angles, which provides a sequential ordering of the vertices of the convex polygon.
A concave polygon has at least one vertex that points inwards to give the concave shape. It has at least one reflex angle. It means that at least one of the interior angles is greater than 180° and less than 360° If a line segment is drawn crossing the concave polygon, it will intersect the boundary more than two times.
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.
143
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
