Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Is there such an algorithm to sort an array of 2D points in clockwise order?
I'm specifically dealing with right triangle in my case so only 3 points.

However I'm interested in knowing if such an algorithm exist, if not what is a simple way to return the 3 points of my triangle in clockwise order?

Edit: I am trying to compute the points clockwise relative to the centroid of the polygon, which is convex.

Update: This is the implementation I ended up using based on the chosen answer, it's not performance critical and only happens once in a while so it works out.

ArrayList<PVector> pointList = new ArrayList<PVector>();
pointList.add(A);
pointList.add(B);
pointList.add(C);
Collections.sort( pointList, new TriangleVectorComparator(origin) );

return pointList;

// Comparator
package triangleeditor;

import java.util.Comparator;

import processing.core.PVector;

public class TriangleVectorComparator implements Comparator<PVector>  {
    private PVector M; 
    public TriangleVectorComparator(PVector origin) {
        M = origin;
    }

    public int compare(PVector o1, PVector o2) {
        double angle1 = Math.atan2(o1.y - M.y, o1.x - M.x);
        double angle2 = Math.atan2(o2.y - M.y, o2.x - M.x);

        if(angle1 < angle2) return 1;
        else if (angle2 > angle1) return -1;
        return 0;
    }

}
share|improve this question
add comment

3 Answers 3

up vote 13 down vote accepted

Your question is not precise enough. An array of points is only « clockwise » or « anti-clockwise » relative to a reference point. Otherwise, any array of three points can always be either CW or CCW. See the following picture: on the left, the points are ordered clockwise; on the right, the exact same points are ordered anticlockwise.

clockwise or anticlockwise

In your case, I believe using the barycenter of the points as a reference point is reasonable.

A good method for an unknown number of points could be the following one:

  • let P[0], P[1], ... P[n-1] be the list of points to sort
  • let M be the barycenter of all points
  • compute a[0], a[1], ... a[n-1] such that a[i] = atan2(P[i].y - M.y, P[i].x - M.x);
  • sort points relative to their a value, using qsort for instance.

However, you can be sure that a good sorting algorithm will perform poorly with three input values compared to an ad-hoc method. Using atan2 is still valid, but just don't use qsort.

share|improve this answer
    
This worked perfectly :) –  onedayitwillmake Jun 6 '11 at 0:39
1  
Does this method have a name? –  onedayitwillmake Jun 6 '11 at 0:49
1  
I believe this is simply called « sorting by polar angle ». It is a component of the Graham Scan, for instance. –  Sam Hocevar Jun 6 '11 at 9:10
    
The performance hit of qsort here is tiny compared to atan2. –  user6347 Jun 6 '11 at 9:18
    
Small warning: This will potentially crash & burn (depending on the programming language and libraries used) if any of the points happens to be exactly at the barycentre (or whatever other point of orientation you use). You might want to exclude such points between the second and third step. –  Martin Sojka Aug 27 '12 at 16:05
add comment

Can you give more info? You want CCW order of points, but what point should be center of ordering?

If you have just triangle (3 points) in plane, you can compute determinant from matrix, where lines are coordinates of points (3rd coordinate is 1). If determinant is > 0, points are in CCW order. If not, you can swith for example last two points and you will get CCW order.

If you have points A, B, C, then your matrix looks like:

|xA, yA, 1|
|xB, yB, 1|
|xC, yC, 1|

Determinant is: xA*yB + xB*yC + xC*yA - yB*xC - yC*xA - yA*xB. Then you can compare it with zero. If it's > 0, return points A, B, C, if it isn't, return A, C, B.

If you have set of points and know, they make convex polygon (all are part of convex hull), and want to get their order, you can use Graham Scan or Jarvis's March (these are algorithms to find convex hull from many points, but it should also work here :) )

share|improve this answer
    
to complete what zacharmarz said if you just want to sort your points in clockwise order around an specific point you can create an array from pairs of float and point in which you store all the points with their coresponding angle from that specific point, and then sort that array. –  Ali.S Jun 5 '11 at 23:27
add comment

I believe that what you're actually asking about here is the triangle's winding order, which is actually pretty simple to test.

Since there are only three points in your triangle, your triangle is already in either a clockwise or counter-clockwise order, and so all you need to do is to check which of those two it is, and reverse the order of indices if the winding isn't the one you want.

Here's the general idea, assuming that the three vertices of a triangle are a, b, and c, and that you have a simple vector subtraction operation:

Vector2 AToB = b - a;
Vector2 BToC = c - b;
float crossz = AToB.x * BToC.y - AToB.y * BToC.x;
if ( crossz > 0.0f )
{
  // clockwise
}
else
{
  // counter-clockwise.  Need to reverse the order of our vertices.
}

Note that depending upon which way you've oriented your +y axis (up or down), the "clockwise" and "counter-clockwise" cases may be reversed from how I've labelled them in the comments in this sample code.

share|improve this answer
    
I need to pass these points to Box2D (java implementation) in order to create a polygon. although it's not what I was asking, very good insight :) –  onedayitwillmake Jun 6 '11 at 0:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.