CODEWITHSUNDEEP
algorithmmathgeometry
Pritesh
Pritesh

Reputation: 3288

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. enter image description here

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.

Upvotes: 1

Views: 6567

Answers (3)

mpenkov
mpenkov

Reputation: 21932

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:

enter image description here

and not:

enter image description here

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

Upvotes: 3

ltjax
ltjax

Reputation: 16007

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.

Upvotes: 2

Christian Severin
Christian Severin

Reputation: 1831

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.

Upvotes: 3

Related Questions