排序在python

Question

x，y座標的列表，我還有很長的XY座標列表如下所示：

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

每對座標表示輪廓點的圖像中，我想整理他們就像他們沿着輪廓排列（最短路徑）。輪廓的形狀很複雜（這是一個國家的形狀），這就是爲什麼一個ConvexHull 將無法​​正常工作。

我嘗試了這種代碼，但它是不夠精確：

>>> 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() 

我已經嘗試過類似建議在this case 但它並沒有進行得很順利，因爲我的座標列表太長。

由於點彼此非常接近，因此對於我的情況來說，對於this question 的解決方案可能看起來過於複雜。

This might illustrate my problem

Answer 1

如果你的形狀是「簡單的」爲你的榜樣，你可以計算你的點雲（平均X和Y）的中心。按照從中心到點的角度對點進行排序，如果它們中的兩個具有相同的角度，則按距離中心的距離對它們進行排序。這應該夠了吧。

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))) 

對於更復雜的形狀，我有另一種算法，我稱之爲放氣船體。從你的雲的外殼，你放氣，直到它觸及所有其餘的點：

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) 

Answer 2

你描述的問題類似於找到一個凸包。你可以看看here

Answer 3

您可以通過選擇一個隨機點做到這一點，並找到下一個點，從那裏像

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) 

這不是一個快速算法（約O（N * N）），但很簡單。

您可以使用kd-tree加速搜索 - 最簡單的情況是沿着一個軸進行二叉樹/二進制搜索 - 但先構建樹/排序點實際上並不快。

如果您countour甚至幾乎凸，@Cabu的解決方案是最快的。

Answer 4

更新： 同時我解決它使用的OpenCV的findContours - 輸出就像我whished的座標！