python中按距离排序点的奇怪结果

Question

我通过提取图像的边缘得到了一个点列表，比如：但是它的顺序不是很好，所以如果我把它连接成一条线，它将是：

因此，我想排序这个列表如果点。比如，从点0开始，找出哪一个距离它最短，比如说，点3，然后找到哪一个离点3最近，然后继续。。。 为了对这些点进行排序，我写了这样一段话：

import matplotlib.pyplot as plt
import numpy as np
import math
def dist(now, seek):
    return math.sqrt((now[0] - seek[0])**2 + (now[1] - seek[1])**2)

def sortNearest(x, y):
    if len(x) != len(y):
        raise Exception('Error! Array length do not match!')
        return False
    xNew = []; yNew = []

    nearest = 0 #record which point is nearest
    now = [x[0], y[0]] #start point index
    seekValue = 0
    while len(x) > 0:
        distance = (max(x) - min(x)) + (max(y) - min(y))
        for seek in range(len(x)): # other
            temp = dist(now, [x[seek], y[seek]])
            if temp < distance and temp != 0.0:
                distance = temp
                seekValue = x[seek]
        xNew.append(now[0]); 
        yNew.append(now[1]); 

        if len(x) > 0:
            x.remove(now[0])
            y.remove(now[1])
        if len(x) > 0:
            nearest = x.index(seekValue)
            now = [x[nearest], y[nearest]]
    x = list(xNew); y = list(yNew)
    return xNew, yNew

x, y = getBorder('large.png', maxRes = 125)
x, y = sortNearest(x, y)

但效果不好，我想到了： 这显然是不正确的，如果我放大，请看： 如果我的代码运行我想要的，点644应该连接620或675，除了645。。。怎么了？你知道吗

Answer 1

我认为可以使用numpy和scipy优化您想要做的事情：

import numpy as np
import scipy.spatial.distance as distance
import matplotlib.pyplot as plt

points = np.random.random((6,2))
dists =distance.pdist(points)
m=np.argsort(distance.squareform(dists))[:,1:]
order = [0,m[0,0]]
next_point = order[-1]
while len(order)<len(points):
    row = m[next_point]
    i = 0
    while row[i] in order:
        i += 1
    order.append(row[i])
    next_point = order[-1]
order.append(0)
ordered=points[order]
plt.plot(ordered[:,0], ordered[:,1], 'o-')

这段代码的基本思想如下。首先计算所有的距离。然后使用argsort获得将对每一行进行排序的索引。可以删除第一列，因为每个点都最接近自身。我们知道。然后你看看哪个是下一个最近的点，如果这个点还没有出现，你就把它添加到列表中。然后转到与此点对应的行，并查找下一个点。等等。你知道吗

如果您只感兴趣的是对封闭的点集进行排序，则可以使用^{}查找它们：

ch = ConvexHull(points)
plt.plot(points[ch.vertices,0], points[ch.vertices,1], 'o-')