1

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.

Pritesh
  • 3,208
  • 9
  • 51
  • 70

3 Answers3

3

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.

mpenkov
  • 21,621
  • 10
  • 84
  • 126
  • No, i just have 20 points which is P1 to P20 and its x and y values, and it does not in a order means from P1 to P20 those are scattered around the plane what i want is to make those point in order from P1 to P20 or P20 to P1. Thanks.......... – Pritesh Feb 01 '11 at 10:59
  • So why is the convex hull **not** what you want? – mpenkov Feb 01 '11 at 11:05
  • Convex hull will remove the concave points. in my case(see image) it will remove points from P2 to P7 which is undesirable. – Pritesh Feb 01 '11 at 11:09
3

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.

Christian Severin
  • 1,793
  • 19
  • 38
2

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.

ltjax
  • 15,837
  • 3
  • 39
  • 62
  • 1
    That would not work if the image were tilted so that P19 becomes the right-most point: P2 - P8 would not be ordered correctly. – Christian Severin Feb 01 '11 at 11:06
  • Rightmost point is P1. Won't P4 and P13 will have a similar angle relative to P1? – mpenkov Feb 01 '11 at 11:07
  • @Christian, correct - edited my answer. The problem dawned on me right after I posted. – ltjax Feb 01 '11 at 11:11
  • 2
    @Pritesh, that's not enough! You can have more than one clock-wise order for your points. – ltjax Feb 01 '11 at 11:39
  • @Itjax, how it is? after all i want only one boundary that cover all given points. Thanks...... – Pritesh Feb 01 '11 at 11:44
  • 2
    Imagine a square and a fifth point right in the middle. You can have at least 4 orders that are all clock-wise. I.e. the point in the middle can be between any of the four points in the (unique, because it's convex!) square. – ltjax Feb 01 '11 at 12:44