5
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ What does clockwise mean? With respect to which center? (If the point set fails to be convex there is no natural (or largely irrelevant) choice $\endgroup$ – Hagen von Eitzen Nov 12 '14 at 7:40
  • $\begingroup$ Thanks for attention. In this specific problem I need to sort these points in any specific direction. So, my idea is to select the topmost point as the starting point and then arrange the other points which are clockwise to the top most point. $\endgroup$ – Janak Nov 12 '14 at 8:41
6
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thanks for the help. Yes, the path of the sorted points is not self intersecting. $\endgroup$ – Janak Nov 12 '14 at 10:11
  • $\begingroup$ Since I am concern about the boundary of a point set, I am sure your third idea is very helpful for me. But I am thinking about the computational difficulties in finding the clockwise order in the boundary path. We need to compare the faces of each edge to all other faces of all other edges, to find the adjacent faces of adjacent edge. It will be very helpful for me if any reference of this algorithm is provided. $\endgroup$ – Janak Nov 12 '14 at 10:37
  • 1
    $\begingroup$ Nice overview of the possible ideas. Regarding point (2): The solution of a travelling salesman problem cannot intersect itself, because if you had an intersection that looked like X you could replace it by either || or = and reduce the total length. One of the two options will disconnect the tour into two disjoint cycles, but the other won't. Re (3): You don't need the full Delaunay triangulation. Its boundary is the same as the boundary of the convex hull of the points. $\endgroup$ – Rahul Nov 12 '14 at 15:42
  • $\begingroup$ @Rahul Nice catch. Updated. $\endgroup$ – Sebastian Negraszus Nov 12 '14 at 16:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the help. I edited the question and mentioned the starting point. $\endgroup$ – Janak Nov 12 '14 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.