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.

Montymonument

Do you mean clockwise around the origin? – Tee

Or it could be clockwise around bondary center. – Adequate

To me, clockwise order for a convex polygon means that you only make right hand turns when traversing the points. The origin should not matter. – Montymonument

If we are talking about a clockwise polygon, check my edit regarding decomosing to two triangles and swapping on that basis. This is a way simpler proposition. – Sulfate

See also: #2855689 – Anecdote

Does this mathoverflow.net/questions/65200/… answer your question? – Endocrinotherapy

Answer 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.

Jae

Could you explain what "signed area of ABC" mean? – Pauli

Answer 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...

Sulfate

This only works if the two triangles you split it into do not intersect. See the second diagram in my post - ABC and CDA intersect each other and so making them clockwise does not fix the whole problem – Jae

I consider (a,b,c,d) to be an ordered set of vertices or cycle, such that the sides of the polygon are ab,bc,cd and da. I think this is reasonable as the opening question relates to a convex polygon, which implies an ordering of the vertices. – Sulfate

I meant the points are vertices of a convex polygon. I did not mean that they are in order. – Montymonument

Answer 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;
    }

Natal

In orderPointsByRows, shouldn't it be if (p1.y > p2.y) return -1; if (p1.y < p2.y) return 1;? You want larger (top) y first. – Wedge

Answer 4

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

Montymonument

Separating out the signed area calculation as a function would improve readability. If performance is important then you can pull out all the expressions like (a.xc.y - c.xa.y) - you end up using them all twice. – Jae

Answer 5

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

Benil

Answer 6

I have one further improvement to add to my previous answer

remember - these are the cases we can be in.

1. A B C D
2. A B D C
3. A C B D
4. A C D B
5. A D B C
6. A D C B

If ABC is anticlockwise (has negative signed area) then we are in cases 3, 4, 6. If we swap B & C in this case, then we are left with the following possibilities:

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A D B C
6. A D B C

Next we can check for ABD and swap B & D if it is anticlockwise (cases 5, 6)

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A B D C
6. A B D C

Finally we need to check ACD and swap C & D if ACD is anticlockwise. Now we know our points are all in order.

This method is not as efficient as my previous method - this requires 3 checks every time, and more than one swap; but the code would be a lot simpler.

Jae

Answer 7

if you just need to deal with 4 points then there is a most easy way of doing that

1. sort by y value

2. top row is the first two points, bottom row is the rest 2 points

3. for top and bottom row, sort them by x value

.

corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]

topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]

Freakish

Answer 8

Work it out the long way then optimize it.

A more specific problem would be to sort the coordinates by decreasing angle relative to the positive x axis. This angle, in radians, will be given by this function:

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

Then, of course, it's just a matter of sorting the coordinates by angle. Note that arctan(w) > arctan(z) if and only if x > z, so you can optimize a function which compares angles to each other pretty easily.

Sorting such that the angle is monotonically decreasing over a window (or such that it increases at most once) is a bit different.

In lieu of a an extensive proof I'll mention that I verified that a single swap operation will sort 4 2D points in clockwise order. Determining which swap operation is necessary is the trick, of course.

Tacmahack

"In lieu of a an extensive proof I'll mention that I verified that a single swap operation will sort 4 2D points in clockwise order. Determining which swap operation is necessary is the trick, of course." How did you verify that? – Montymonument

@Vulcan by inspection, there are only so many possible ways to order 4 values, I listed all of those ways and then determined how to sort them in the desired way, for every case only one swap operation was needed. You can do this yourself, write all the ways to order the numbers 1,2,3,4. – Tacmahack

This arranges the points to be clockwise around the origin, not in a clockwise quadrilateral. Plus arctan is (relatively) slow. – Jae

note that in .NET Math.Atan2(x, y) calculates your angle without all that mess. – Jae

@Oliver well, the real goal is to create an optimized solution which doesn't use atan at all. – Tacmahack

Answer 9

var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

Where reference point lies inside the polygon.

More info at this site

Wilmington

Answer 10

I believe you're right that a single swap can ensure that a polygon represented by four points in the plane is convex. The questions that remain to be answered are:

• Is this set of four points a convex polygon?
• If no, then which two points need to be swapped?
• Which direction is clockwise?

Upon further reflection, I think that the only answer to the second question above is "the middle two".

Asterisk

-1 since your answer to the second question is wrong, unless you assume the points are either in clockwise or anticlockwise order (consider the example I give below). – Jae

Answer 11

How about this?

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

Ideas?

Montymonument

Swap opposite verts not adjacent ones. But otherwise, yes. – Proclaim

PS: You only need to do the second test if the signed area of ABC is zero (or within some epsilon of it). – Proclaim

Answer 12

if we assume that point x is bigger than point y if the angle it has with the point (0,0) is bigger then we can implement this this way in c#

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}

Brooks

Note that you calculate the same angle for (1, 1) and (-1, -1). You want Math.Atan2(x, y) – Jae

Answer 13

if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

The first 'if/elif' brings the four points in clockwise or counterclockwise order. (Since your polygon is convex, the only other 'crossing' alternative is 'AC crosses BD', which means that the four points are already sorted.) The last 'if' inverts orientation whenever it is counter-clockwise.

Outlaw

p.s. One swap is not sufficient to bring the four points in clockwise order. This would be the same as pretending to sort three numbers in ascending order with only one swap (3 1 2, what do you do?). – Outlaw

Wrong. In the numbers example: 1, 2 and 3 have fixed final positions. In the 4 points clockwise case, we can have ABCD, BCDA, CDAB and DABC. – Montymonument

Ok I'm wrong but not for the reason you mentioned. My idea was this: sorting A312 (only a relabeling of ADBC) in order to give A123 is the same as sorting 312 in ascending order. This is true in a sense, but irrelevant here, because in our setting I can move also A. – Outlaw

Anyway, why all this fuss about swaps? Swapping is indeed a fast operation, and I would prefer to compute 2 areas and do 2 swaps rather than computing 3 areas in order to choose the only right swap that will do the magic. – Outlaw

Answer 14

You should take a look at the Graham's Scan. Of course you will need to adapt it since it finds to points counter-clockwise.

p.s: This might be overkill for 4 points but if the number of points increase it could be interesting

Naranjo

Answer 15

Wedge’s Answer is correct.

To implement it easily, I think the same way as smacl: you need to find the boundary’s center and translate your points to that center.

Like this:

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

Then, decrease centerPointX and centerPointY from each poin in order to translate it to boundary’s origin.

Finally, apply Wedge’s solution with just one twist: Get the Absolute value of arctan(x/y) for every instance (worked for me that way).

Adequate

Answer 16

if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

The '>' might be facing the wrong way, but you get the idea.

Proclaim