Sorting a list of points in 2-D clockwise

Question

I have number of points with co-ordinate (latitude, longitude) in 2-D:

Here is a collection of some points:

\begin{array}{ccc} \hline No.& lon & lat \\ \hline 1& 84.07921& 24.49703 &\\ 2 &84.00658 & 24.46434\\3&84.00838 &24.62689\\4&84.02153 &24.68584\\5&84.06810 &24.60029\\ 6&84.04290 & 24.48070\\7&84.04472 &24.64323 . \end{array}

and scatter plot:

Note 1: The point set may not be convex.

Note 2: We assume the topmost point as the starting point (here it is No.1).

Question : How to sort this points in clockwise direction (for example, in the order (1,5,7,4,3,2,6)) and get a array of points in the order (1,5,7,4,3,2,6)?

Links visited:

1) How to sort vertices of a polygon in counter clockwise order?

2)Algorithm for topological sorting without explicit edge list

Any algorithm, reference or suggestion will be greatly appreciated.

Answer 1

The problem is not well-defined for arbitrary point clouds. Clockwise around which point? How to handle collinear points? Does the path of sorted points need to have certain properties, e.g. no self-intersection?

Here are some ideas, but they all have certain drawbacks:

1. Pick a point $C$, such as the average of all points. Sort all points $P_i$ by the angle of $\overline{CP_i}$ to $\overline{CP_0}$. Problems: If the point cloud is not convex, the result may not correspond to any intuitive notion of clockwise order. How to order points with the same angle (collinear to $C$)?
2. Find the shortest path that connects all points (travelling salesman problem). Sort by clockwise order in that path. Problems: Hard to compute for many points. Using heuristics may lead to self-intersections.
3. Apply a Delaunay triangulation Find the convex hull and sort by clockwise order in it. Problem: Some points may not be part of it.

Answer 2

In this specific case, I'd subtract the average/center from all points.

Then convert the remainder to polar coordinates.

Then sort by angle, but you'd still have to find a starting angle.

(I'd start with $\pi / 2$ and have $5$ as first point).

But as from earlier comments, this is not really a formal mathmatically correct method.

Answer 3

Use a space filling curve (like the Hilbert curve). They are the only way to robustly define a sorting in 2 dimensions.