Sort Four Points in Clockwise Order

by

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.

More Related Contents:

  1. Algorithm to detect intersection of two rectangles?
  2. How do you find a point at a given perpendicular distance from a line?
  3. Find if a point is inside a convex hull for a set of points without computing the hull itself
  4. How to determine if a point is in a 2D triangle? [closed]
  5. How to calculate an angle from three points? [closed]
  6. Why is quicksort better than mergesort?
  7. Which sort algorithm works best on mostly sorted data? [closed]
  8. How to find the intersection point between a line and a rectangle?
  9. Quicksort: Choosing the pivot
  10. How do I efficiently determine if a polygon is convex, non-convex or complex?
  11. Natural Sorting algorithm
  12. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  13. Compute the minimal number of swaps to order a sequence
  14. Is there an efficient algorithm to generate a 2D concave hull?
  15. Which parallel sorting algorithm has the best average case performance?
  16. Fast algorithm implementation to sort very small list
  17. Sorting in linear time? [closed]
  18. How to find two most distant points?
  19. median of three values strategy
  20. Collision detection of huge number of circles
  21. What is a bubble sort good for? [closed]
  22. Calculating the position of points in a circle
  23. Quicksort superiority over Heap Sort
  24. Comparison-based ranking algorithm
  25. Compute the area of intersection between a circle and a triangle?
  26. Why is bubble sort O(n^2)?
  27. Stable separation for two classes of elements in an array
  28. Location of highest density on a sphere
  29. Distance from a point to a polygon
  30. Best algorithm for matching colours.

Leave a Comment