我有两个坐标列表:
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数组而不是点)?
s2
是s1
的子集,那么它们之间会有一些相等性(即s2
中的某些元素也在s1
中,因此最小距离将为0)。首先搜索这些相等性将显著加快速度。复杂度为 **O((n-k)^2)**,其中k
是公共元素的数量。 - Ma0