Sign in to follow this  

[java] Clockwise algorithm?

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster

/**
* 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);
}

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this