Python - 给定两个元组列表，找到它们之间最接近的元组（距离）

Question

我有两个包含元组（坐标）的列表，例如：

some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]

• 元组中的每个值都是平面的
• 这些列表的长度不同

我想要找到两个列表之间最接近的两个点。我不知道如何做，也许可以使用距离来完成。我希望有一种更有效的方法来完成这个任务，因为我需要这个函数尽可能快地工作（它是更大功能的一部分）。

- eran halperin

---

这是一个要求，两个点必须分别来自于_两个_列表中，还是您也包括来自同一列表的点之间的距离？ - Aemyl

最接近的是按什么度量？欧几里得距离吗？ - timgeb

每个点必须来自不同的列表是一个要求。 - eran halperin

通过欧几里得算法... - eran halperin

Answer 1

或者，可以参考Tim Seed的代码。这可以使用。

from scipy.spatial import distance
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]

empthy_dict = {}
for i in range(len(some_pt1)):
    for j in range(len(some_pt2)):
        dist = distance.euclidean(some_pt1[i],some_pt2[j])
        empthy_dict[dist] = [some_pt1[i],some_pt2[j]]

shortest = sorted(empthy_dict.keys())[0]
points = empthy_dict[shortest]
print('Shortest distance is ' ,shortest,' and points are ' ,points)

- demirbilek

Answer 2

这个怎么样？

from pprint import pprint

some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]


distance = {}
for x in some_pt1:
    for y in some_pt2:
        dist =abs(abs(x[0])-abs(y[0]))+abs(abs(x[1])-abs(y[1]))
        distance[dist]=[x,y]

shortest =sorted(distance.keys())[0]
print("Min Distance is {} Objects are  {} {} ".format(shortest, distance[shortest][0],distance[shortest][0]))

- Tim Seed

---

这几乎就是曼哈顿距离（有太多绝对值了），但是那不是正确的 :) - timgeb

Answer 3

无论如何，您需要做所有可能的组合，有一些算法可以帮助您以最佳顺序或避免重复距离进行操作。如果您想要快速完成，应该使用一个特殊的库来帮助编译或预编译数组，这可以通过Numba或Cython来实现。其他库，如scipy，有特殊模块，例如scipy.spatial.distance。查看此帖子以获取更多疑问类似问题。

示例：

import scipy.spatial.distance as sd
import numpy as np
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
np.unravel_index(np.argmin(sd.cdist(some_pt1, some_pt2)), (len(some_pt1), len(some_pt2)))

结果：(2, 4)

这段代码将返回第一个列表和第二个列表中的位置。

- Jorge Rodriguez Molinuevo

Answer 4

通过欧几里得距离：

>>> some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
>>> some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
>>> 
>>> def dist_sq(p1_p2):
...     p1, p2 = p1_p2
...     return sum(x*y for x,y in zip(p1, p2))
... 
>>> 
>>> min(((p1, p2) for p1 in some_pt1 for p2 in some_pt2), key=dist_sq)
((3.24, 4.28), (6.91, 0.56))

其运行时间为O(n*m)（其中n、m为列表的长度）。由于您需要查看所有的成对组合，因此不可能比这更好。

请注意，仅比较平方距离就足够了，无需计算根号。

- timgeb

---

谢谢，看起来这个方法可以胜任，但是我想问一下：有没有其他更高效的方法来处理这个问题，而不是检查每一个点？因为我将要处理的真实列表会很长，可能会有极远的点。 - eran halperin

@eranhalperin 不，你不能减少算法的复杂度。你可以使用numpy和Jorge Rodriguez Molinuevo提到的其他技术使其更快，但你需要比较每一对。 - timgeb

好的，那么我该如何使用NumPy（举个例子）让它更快？ - eran halperin