Hi, I have a huge list of unordered points which make up a polygon.
To order the polygon (anticlockwise or clockwise doesn't matter),

1. I select a starting point (from the unordered list) and remove it from the unordered list and add to an ordered list.,
2. I then find the closest point(in the unordered list) to the 1st point, and add that to the ordered list and remove it from the unordered list.
3. I then find the closest point(in the unordered list) to the 2nd point, and add that to the ordered list and remove it from the unordered list.
4. I keep going until the unordered list has no points left in it.

Unfortunately, this is order n^2 or O(n^2) - Is there a better way to do it?

Thanks,
r_bewick

The first option that springs to mind is to put the points in a kd-tree which would significantly speed up finding of the closest point.

The first option that springs to mind is to put the points in a kd-tree which would significantly speed up finding of the closest point.

Thanks

Just a note, your method isn't guaranteed to work without several assumptions about the polygon in question.

Try a convex hull algorithm http://en.wikipedia.org/wiki/Convex_hull_algorithms if you know that your polygon is convex.