Sorting of Points in 2D space

问题:

Suppose random points P1 to P20 scattered in a plane. Then is there any way to sort those points in either clock-wise or anti-clock wise.

Here we can’t use degree because you can see from the image many points can have same degree. E.g, here P4,P5 and P13 acquire the same degree.

回答1:

If your picture has realistic distance between the points, you might get by with just choosing a point at random, say P1, and then always picking the nearest unvisited neighbour as your next point. Traveling Salesman, kind of.

回答2:

Are you saying you want an ordered result P1, P2, ... P13?

If that's the case, you need to find the convex hull of the points. Walking around the circumference of the hull will then give you the order of the points that you need.

In a practical sense, have a look at OpenCV's documentation -- calling convexHull with clockwise=true gives you a vector of points in the order that you want. The link is for C++, but there are C and Python APIs there as well. Other packages like Matlab should have a similar function, as this is a common geometrical problem to solve.

EDIT

Once you get your convex hull, you could iteratively collapse it from the outside to get the remaining points. Your iterations would stop when there are no more pixels left inside the hull. You would have to set up your collapse function such that closer points are included first, i.e. such that you get:

and not:

In both diagrams, green is the original convex hull, the other colors are collapsed areas.

回答3:

Find the right-most of those points (in O(n)) and sort by the angle relative to that point (O(nlog(n))).

It's the first step of graham's convex-hull algorithm, so it's a very common procedure.

Edit: Actually, it's just not possible, since the polygonal representation (i.e. the output-order) of your points is ambiguous. The algorithm above will only work for convex polygons, but it can be extended to work for star-shaped polygons too (you need to pick a different "reference-point").

You need to define the order you actually want more precisely.