Sorting polygon's points

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?

---

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.

---

Assuming your points are all on the convex hull of your polygon, you can use the following:

1. Pick the two extreme points with the min and max X value, (call them X_min and X_max) and draw the line between them. In the case where you have multiple points with the same X value at the extremes, pick X_min with the minimum Y value and X_max with the maximum Y value.
2. Split the list of points into two sub lists where all of the points below the line connecting X_min and X_max are in one list and all those above that line are in another. Include X_min in the first list and X_max in the second.
3. Sort the first list in ascending order of X value. If you have multiple points with the same X value, sort them in ascending Y value. This should only happen for points with the same X component as X_max since the polygon is convex.
4. Sort the second list in descending order of X value. Again, sort in descending Y value in the event of multiple points with the same X value (which should only happen for points with X component X_min.
5. Append the two lists together (it doesn't matter which is first).