-2

I have a long list of xy coordinates like the following:

>>> data = [(x1,y1),(x2,y2),(x3,y3),...]

Every pair of coordinates represents a point of a contour in an image and I would like to sort them like they are arranged along the contour (shortest path). The shape of the contour is very complex (it's the shape of a country), that's why a ConvexHull won't work.

I tried out this code, but it is not precise enough:

>>> import math
>>> import matplotlib.patches as patches
>>> import pylab

>>> pp=[(1,1),(2,3),(3,4)]

# compute centroid
>>> cent=(sum([p[0] for p in pp])/len(pp),sum([p[1] for p in pp])/len(pp))
# sort by polar angle
>>> pp.sort(key=lambda p: math.atan2(p[1]-cent[1],p[0]-cent[0]))
# plot points
>>> pylab.scatter([p[0] for p in pp],[p[1] for p in pp])
# plot polyline

>>> pylab.gca().add_patch(patches.Polygon(pp,closed=False,fill=False))
>>> pylab.grid()
>>> pylab.show()

I already tried like suggested in this case but it did not work out well, because my list of coordinates is too long.

As the points are very close to each other the solution to this question might seem too complicated for my case.

This might illustrate my problem

Community
  • 1
  • 1
feinheitsbrei
  • 51
  • 2
  • 5
  • 2
    The task what you described is called the problem of the travelling salesman, and is hard to solve in general. If you could show us some sample image and same sample data, maybe someone will notice a pattern which allows us to suggest an efficient algorithm. – Tamas Hegedus Aug 24 '16 at 08:48
  • As it is a countour it can normally be assumed that for each point there are 2 nearest neighbors - the one before and the one after on the path - and that the shortest path will also only include such pairs. So you can use a greedy algorithm with a runtime of O(n*n) or better. – janbrohl Aug 24 '16 at 10:16
  • Can you explain a bit more why "this question might seem too complicated for my case"? Have you tried his solution and what's the problem? – Jason Nov 02 '17 at 03:22

4 Answers4

0

If your shape is 'simple' as your example, you can compute the center of your cloud of points (average of X and Y). Sort your points by the angle from the center to the points and if two of them share the same angle, sort them by their distance from the center. That should do the trick.

center = functools.reduce(lambda p1, p2: (p1[0]+p2[0], p1[1]+p2[1]), data)
center = (center[0] / len(data), center[1] / len(data))

def angle(p1, p2):
    return math.atan2(p2[1], p2[0]) - math.atan2(p1[1], p1[0])

answer = sorted(data, key=lambda p: (angle(p, center), distance(p, center)))

For more complex shapes, I have another algorithm that I call deflating hull. From the hull of your cloud, you deflate it until it touch all the remaining points:

def deflate_hull(points):
    hull = convex_hull(points)

    for p in hull:
        points.remove(p)

    while points:
        l = len(hull)
        _, p, i = min((distance(hull[i-1], p) + distance(p, hull[i]) - distance(hull[i-1], hull[i]), p, i) 
                      for p in points 
                      for i in range(l))
        points.remove(p)
        hull = hull[:i] + [p] + hull[i:]

    return hull

def convex_hull(points):
    if len(points) <= 3:
        return points
    upper = half_hull(sorted(points))
    lower = half_hull(reversed(sorted(points)))
    return upper + lower[1:-1]

def half_hull(sorted_points):
    hull = []
    for C in sorted_points:
        while len(hull) >= 2 and turn(hull[-2], hull[-1], C) <= -1e-6: 
            hull.pop()
        hull.append(C)
    return hull

def turn(A, B, C):
    return (B[0]-A[0]) * (C[1]-B[1]) - (B[1]-A[1]) * (C[0]-B[0]) 

def distance(p1, p2):
    return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

answer = deflate_hull(data)
Cabu
  • 514
  • 2
  • 5
  • 15
  • mostly correct for at least [star-shaped](https://en.wikipedia.org/wiki/Star_domain) pictures – janbrohl Aug 24 '16 at 09:44
  • this totally works for konvex shapes and if the points are distributed *nicely* this works for star-like shapes, too - but if the distribution is not *nice* finding the right center is less simple – janbrohl Aug 24 '16 at 10:28
  • the simple code does not work, because the shapes are too complex and for your second suggestion there are too many points, therefore it is too slow. – feinheitsbrei Aug 25 '16 at 14:51
0

The problem you described is similar to finding a convex hull. You can have a look here

gjjhhh_
  • 169
  • 3
  • 21
  • The convex hull algorithm will not take the 'inner' points into account. It seems that he want them all. – Cabu Aug 24 '16 at 09:49
0

You can do this by selecting a random point and find the next points from there like

def distance(a,b):
    pass
    #propably something with math.hypot for euclidean norm

points=set([(1,2),(2,3)])
current=points.pop()
path=[current]
while points:
    current=min(points,key=(lambda p: distance(current,p))
    points.remove(current)
    path.append(current)

This is not a fast algorithm (about O(n*n)) but it is simple.

You can speed up the search by using a kd-tree - simplest case would be a binary tree/binary search along only one of the axes - but building the tree/sorting the points first is not actually fast.

If your countour is even almost convex, the solution of @Cabu is fastest.

janbrohl
  • 2,626
  • 1
  • 17
  • 15
0

Update: meanwhile I solved it by using OpenCV's findContours - that outputs the coordinates like I whished!

feinheitsbrei
  • 51
  • 2
  • 5