Menu
I want to sort a vector of points in clockwise order to form a polygon but I need the proper center to do so. I have tried the averages method, but a few of the points did not sort correctly at all. What is the correct way to find the center that will work when sorting points in a clockwise manner?
It is failing on the concave parts
Thanks
Here is a picture:
The green circle is the center.
It should look more like this:
401
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.
By choosing an arbitrary (x, y) pair as your "center", you can compute the polar angle of each point relative to your center, and then sort them based on this angle. The end result sorts the polygon's point in clockwise/counterclockwise direction.
How can I sort the coordinate tuples within each sublist in counter-clockwise direction? 1) Compute the mean of x and y, which gives you the coordinates of the center. 2) Compute the angle from the center to each point, using math. atan() 3) Sort the points according to the angles.
The notion of "sorting in clockwise order" is not well-defined if you don't have a pre-defined center point.
If all you have is just a bunch of points that you need to sort and you don't know the center in advance, then the problem does not generally have a single solution. The problem has many alternative solutions, each of which will give you a different polygon as the result.
Moreover, finding a center that would allow you to re-create the original polygon by CW (or CCW) sorting is only possible for a special class of polygons: so called star-shaped polygons. The main property of star-shaped polygon is that it is possible to find a point inside the polygon from which the entire interior of the polygon is "observable" (I hope it is clear without definition what "observable" means).
If your polygon is not star-shaped, then such center point simply does not exist. And, for this reason, it is not possible to re-create the original polygon by CW sorting.
Your cow contour in the picture is obviously not a star-shaped polygon, which means that you will never be able to re-create the original cow contour by sorting the points around some center, any center. There's no "correct way". It is not possible.
98
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
