Menu
I have a convex polygon ABCDE... (it can have any number of points). I need to sort all its vertexes so none of the edges will intersect.
example:
A _____ B
\ /
\ /
X
/ \
/___\
C D
That polygon in ABCD order has intersecting edges. however in ABDC order:
A _____ B
| |
| |
| |
| |
|___|
C D
None of the edges intersect so ABDC is the expected output.
How can I do this?
437
If it's > 0, return points A, B, C, if it isn't, return A, C, B. If you have set of points and know, they make convex polygon (all are part of convex hull), and want to get their order, you can use Graham Scan or Jarvis's March (these are algorithms to find convex hull from many points, but it should also work here :) )
All points will be sorted in clockwise order with the first point in the North West quadrant. In your case since you only have 4 points and they are the corners, simply insert the last point (SW) into the first position in the list 10-12-2016 12:32 PM Thanks for the feedback.
A good method for an unknown number of points could be the following one: let P [0], P [1], ... P [n-1] be the list of points to sort compute a [0], a [1], ... a [n-1] such that a [i] = atan2 (P [i].y - M.y, P [i].x - M.x); sort points relative to their a value, using qsort for instance.
flip the list so that they are sorted in reverse (+180 to -180) or sort in reverse in the first place. All points will be sorted in clockwise order with the first point in the North West quadrant. In your case since you only have 4 points and they are the corners, simply insert the last point (SW) into the first position in the list
choose two points on the polygon. the midpoint of the line will be contained within that polygon. Let that point be M.
Then, sort the points based on the angle based from M (along the X axis), breaking degeneracy based on distance from M. Iterating in that order ensures that no two edges will intersect.
89
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
