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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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