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

Answer 2

好吧，644点不能连接到620点，因为620点已经是你路径的一部分了。你知道吗

至于为什么它连接到645而不是更接近的675：在你的循环中，你实际上不记得最近点的索引，你只记得它的x坐标。在循环之后，您可以定位一个具有相同x坐标的任意点-它可以位于穿过所需点的垂直线上的任何位置。你知道吗

Answer 3

我不知道如何在Python3.x中实现这一点，因此请原谅我没有对Python2.7进行的更改。你还需要弄清楚你想从哪一点开始：

def find_distance(point1, point2):
    distance = sqrt(square(point1[0]-point2[0]) + square(point1[1] - point2[1]))
    return distance

x, y = getBorder('large.png', maxRes = 125)
points_in_border = [(i,j) for i, j in zip(x,y)] 
current_point = points_in_border.pop([0])
points_in_order = [current_point]


while len(points_in_border) > 0:
    min_distance = 10000
    for point in points_in_border:
        if find_distance(current_point, point) < min_distance:
            closest_point = point
            min_distance = find_distance(current_point, point)
     points_in_border.remove(closest_point)
     current_point = closest_point
     points_in_order.append(closest_point)