# Sorting array of points in clockwise order

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

}

• return can be return angle1 < angle2 ? 1 : angle2 > angle1 ? -1 : 0; Sep 2 '14 at 14:41
• It can be expressed many ways, but I tend to avoid nested ternary operators especially when giving examples. Sep 12 '14 at 19:09
• @onedayitwillmake Could you move the code you ended up using into an answer? It doesn't really belong in the question, but it's very valuable to future readers.
– Anko
Oct 6 '15 at 12:13
• @Anko I think you are right, but at the same time I think it will be easiest for people to find it in this way. It also helps make sure I don't take away from samhocevar's answer which mine is simply based on. Oct 31 '15 at 22:57

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.

• This worked perfectly :) Jun 6 '11 at 0:39
• Does this method have a name? Jun 6 '11 at 0:49
• I believe this is simply called « sorting by polar angle ». It is a component of the Graham Scan, for instance. 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. Aug 27 '12 at 16:05

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.

• 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 :) Jun 6 '11 at 0:39

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

• 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. Jun 5 '11 at 23:27