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

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.