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

Answer 2

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.

Answer 3

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.

Answer 4

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?