# [java] Clockwise algorithm?

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

## Recommended Posts

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_

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

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

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

##### Share on other sites
/** * Returns a positive value for clockwise, a negative value for * counterclockwise, and 0 if both points lie in the same line. * * All comparisons are with respect to the origin, of course. */static int clockwise(int x1, int y1, int x2, int y2){    return (x2 * y1) - (x1 * y2);}

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 14
• 9
• 10
• 12
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009830
• ### Who's Online (See full list)

There are no registered users currently online

×