在 Python 中查找两个列表的点之间的最小距离

Question

我有两个坐标列表：

 s1 = [(0,0), (0,1), (1,0), (1,1)]
s2 = [(3,2), (1,9)]

我想计算 s1 中每个点到 s2 中任意点的最小距离。例如，结果应该如下。

 result = [3.60, 3.16, 2.82, 2.23]

问题： 为了达到这个结果，在执行时间方面最优化的方法是什么？

到目前为止，我已经试过了，但执行时间并不乐观：

 import math
def nearestDistance(boundary, p):
    minDistList = map(lambda b: (b[0] - p[0])**2 + (b[1] - p[1])**2, boundary)
    minDist2 = min(minDistList)
    return math.sqrt(float(minDist2))

d = []
for p in s1:
    d.append(nearestDistance(s2, p))

我是否应该更改 s1 和 s2 的结构（而不是点，例如使用二维数组）？

原文由 orak 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

最简单的方法可能是使用 scipy.spatial.distance.cdist ：

 import numpy as np
from scipy.spatial import distance

s1 = np.array([(0,0), (0,1), (1,0), (1,1)])
s2 = np.array([(3,2), (1,9)])
print(distance.cdist(s1,s2).min(axis=1))
# array([3.60555128, 3.16227766, 2.82842712, 2.23606798])

对于来自 s1 0 也可以在 s2 中获得更多速度。

原文由 Graipher 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您是否尝试过使用 cdist ：

 import numpy as np
from scipy.spatial.distance import cdist

np.min(cdist(s1,s2))

回报

array([ 3.60555128,  3.16227766,  2.82842712,  2.23606798])

You might also get a performance boost by replacing s1 and s2 by np.array s, although scipy might be doing that internally, I’我不确定。

如果这不够优化，我认为你可以在 O(n s2 *log(n s2 ) + n s1 ) 中通过找到 s2 中的点的 Voronoi 图 来做到这一点，然后循环 s1 查看点落在哪个区域将与 s2 中的最近点匹配。

原文由 Dan 发布，翻译遵循 CC BY-SA 3.0 许可协议