Sort Four Points in Clockwise Order

Question

Four 2D points in an array. I need to sort them in clockwise order. I think it can be done with just one swap operation but I have not been able to put this down formally.

Edit: The four points are a convex polygon in my case.

Edit: The four points are the vertices of a convex polygon. They need not be in order.

Solution 1

If you want to take a more mathematical perspective, we can consider the permutations of 4 points

In our case there are 4 permutations that are in clockwise order

A B C D
B C D A
C D A B
D A B C

All other possible permutations can be converted to one of these forms with 0 or 1 swaps. (I will only consider permutations starting with A, as it is symmetrical)

1. A B C D - done
2. A B D C - swap C and D
3. A C B D - swap B and C
4. A C D B - swap A and B
5. A D B C - swap A and D
6. A D C B - swap B and D

Thus only one swap is ever needed - but it may take some work to identify which.

By looking at the first three points, and checking the sign of the signed area of ABC, we can determine whether they are clockwise or not. If they are clockwise then we are in case 1 2 or 5

to distinguish between these cases we have to check two more triangles - if ACD is clockwise then we can narrow this down to case 1, otherwise we must be in case 2 or 5.

To pick between cases 2 and 5, we can test ABD

We can check for the case of ABC anti-clockwise similarly.

In the worst case we have to test 3 triangles.

If your points are not convex, you would find the inside point, sort the rest and then add it in any edge. Note that if the quad is convex then 4 points no longer uniquely determine the quad, there are 3 equally valid quads.

Solution 2

A couple of thoughts worth considering here;

• Clockwise is only meaningful with respect to an origin. I would tend to think of the origin as the centre of gravity of a set of points. e.g. Clockwise relative to a point at the mean position of the four points, rather than the possibly very distant origin.

• If you have four points, a,b,c,d, there exists multiple clockwise orderings of those points around your origin. For example, if (a,b,c,d) formed a clockwise ordering, so would (b,c,d,a), (c,d,a,b) and (d,a,b,c)

• Do your four points already form a polygon? If so, it is a matter of checking and reversing the winding rather than sorting the points, e.g. a,b,c,d becomes d,c,b,a. If not, I would sort based on the join bearing between each point and the origin, as per Wedges response.

Edit: regarding your comments on which points to swap;

In the case of a triangle (a,b,c), we can say that it is clockwise if the third point c, is on the right hand side of the line ab. I use the following side function to determine this based on the point's coordinates;

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

If I have a four point convex polygon, (a,b,c,d), I can consider this as two triangles, (a,b,c) and (c,d,a). If (a,b,c) is counter clockwise, I change the winding (a,b,c,d) to (a,d,c,b) to change the winding of the polygon as a whole to clockwise.

I strongly suggest drawing this with a few sample points, to see what I'm talking about. Note you have a lot of exceptional cases to deal with, such as concave polygons, colinear points, coincident points, etc...

Solution 3

If someone is interested, here is my quick and dirty solution to a similar problem.

My problem was to have my rectangle corners ordered in the following order:

top-left > top-right > bottom-right > bottom-left

Basically it is clockwise order starting from the top-left corner.

The idea for the algorithm is:

Order the corners by rows and then order corner-pairs by cols.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}

Solution 4

Calculate the area from the coordinates with the shoelace formula (devoided of the absolute value such that the area can be positive or negative) for every points permutations. The maximal area values seems to correspond to direct simple quadrilaterals:Simple direct quadrilaterals found with the shoelace formula

Solution 5

Oliver is right. This code (community wikified) generates and sorts all possible combinations of an array of 4 points.

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}

View more solutions