This is my current problem. I have a series of order pairs stored in a Vector such that the first ordered pair has the xcoord in index 0 and the ycoord in index 1, and so on for every ordered pair. Now I want to print out a traversal of the pairs in clockwise order, with the start point being arbitrary. Anyone have any ideas of how to sort these coords in a clockwise order or how to print them out that way. Any help or ideas would be appreciated. Thanks, j_fish_

Firstly, I'm assuming these pairs are cartesian coordinates. If they are not, I cannot help you.

Points on a plane need not form a convex hull. As such, there may not be a distinct "clockwise order" which you can put them in.

What you need is a convex hulls algorithm (Perhaps called convex polygons in 2d, the principle is the same).

Once you've made them into a convex hull, then sorting clockwise should be easy enough. Just start anywhere, and go around in the direction which is clockwise, which you can tell by testing whether the first three points are clockwise or anticlockwise:

Basically points ABC are in clockwise order if the right-hand vector perpendicular to AB is in the same direction as BC, that's to say, the angle between the normal of AB and BC is less than 90 degrees.

Of course if you know they already form a convex hull and are ordered EITHER clockwise or anticlockwise, all you need to do is test the first three points, and if they're the wrong way around, reverse them.

Mark

The points in the vector are the convex hull vertices. However, they are not ordered in any particular order. Should the algorithm give the vertices in clockwise (or anticlockwise) order?

j_fish_

In which case, I'd be tempted to pick an arbritary start point, then find relative vectors from there to each of the others.

Find the angle of each of those (using atan2), then sort according to that value, and your list are in clockwise order.

There is probably a cleverer way of doing this (without trig), but if it's not time-critical, that would work fine.

Mark