在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的结构(而不​​是点,例如使用2d数组)？

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

通过直接0从s1in中的任意点输出可能会获得更高的速度s2。

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

您也可以通过更换得到的性能提升s1，并s2通过np.arrayS，尽管scipy可能会做在内部，我不知道。

如果这还不够优化，我想您可以在O（n _s2 * log（n _s2）+ n _s1）中进行操作，方法是查找点中的Voronoi图，s2然后循环遍历s1以查看该点所在的区域将与中的最接近点匹配s2。