# Fast way to order points

This topic is 2610 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites

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

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633696
• Total Posts
3013394
×