11

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?

andand
  • 17,134
  • 11
  • 53
  • 79
Daniel
  • 30,896
  • 18
  • 85
  • 139

2 Answers2

10

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.

Foo Bah
  • 25,660
  • 5
  • 55
  • 79
9

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 Xmin and Xmax) and draw the line between them. In the case where you have multiple points with the same X value at the extremes, pick Xmin with the minimum Y value and Xmax with the maximum Y value.
  2. Split the list of points into two sub lists where all of the points below the line connecting Xmin and Xmax are in one list and all those above that line are in another. Include Xmin in the first list and Xmax 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 Xmax 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 Xmin.
  5. Append the two lists together (it doesn't matter which is first).
Foo Bah
  • 25,660
  • 5
  • 55
  • 79
andand
  • 17,134
  • 11
  • 53
  • 79
  • 1
    FYI: There is absolutely no need to use inverse trig functions to radially sort the points. You can just sort based on the actual value (y - y0)/(x-x0). That's the kernel of the graham scan – Foo Bah Sep 10 '11 at 07:25
  • @Foo Bah: Thanks for point that out. It wasn't clear from your answer. BTW, did you downvote the answer? If so, why did you edit it? – andand Sep 10 '11 at 15:45
  • I edited it because i wanted to undo my downvote, then forgot to do so afterwards. I have removed it now. – Foo Bah Sep 10 '11 at 15:46