Sorting array of points in clockwise order

Question

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);

        //For counter-clockwise, just reverse the signs of the return values
        if(angle1 < angle2) return 1;
        else if (angle2 < angle1) return -1;
        return 0;
    }

}

Answer 1

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.

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.

Answer 2

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.

Answer 3

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 :) )