Python - 计算两个点列表（坐标）的最小欧氏距离

Question

我有两个n个形状的列表，每个点将被比较（欧氏距离）到第二个列表的每个点，然后选择最小距离，例如：

答： [（1，1），（2，1），（3，1）]

B： [（2，2），（3，3）]

输出将为 3 个距离：

分钟（（1，1） -> （2，2）， （1，1） -> （3，3）），

分钟（ （2，1） -> （2，2）， （2，1） -> （3，3） ），

分钟 （ （3，1） -> （2，2）， （3，1） -> （3，3） ）

->欧氏距离

困难的部分是制作有效的代码。

Answer 1

下面是一个可能有帮助的示例代码：from scipy.spatial import distanceA = [(1,1),(2,1),(3,1)]B = [(2,2),(3,3)]min_dist = []for a in A:    dist = []    for b in B:        dist.append(distance.euclidean(a,b))    min_dist.append(min(dist))>> min_dist>> [1.4142135623730951, 1.0, 1.4142135623730951]我正在为此使用库。也可以使用 .这种方法适合您吗？scipynumpy.linalg.norm

Answer 2

这取决于你所说的“高效”是什么意思。如果你有相当大的列表，并且你要做很多比较，你应该只寻找最小平方距离，这计算起来要快得多，因为你避免了平方根运算。这是处理欧氏距离时的标准技巧。如果最后，你想要实际的欧氏距离，那么取平方根。考虑：import numpy as npA = [(1, 1), (2, 1), (3, 1)]B = [(2, 2), (3, 3)]# compare each point in A to all points in B, return the shortest distancefor pt in A:    min_sq_dist = min( (pt[0] - t[0])**2 + (pt[1] - t[1])**2 for t in B )    print(np.sqrt(min_sq_dist))输出：1.41421356237309511.01.4142135623730951最大的区别是什么？上面的代码计算 3 个平方根。朴素方法计算 6 （|{B}|倍数）

Answer 3

我找到了一种方法，我不知道是否有人能更有效地做到这一点，import numpy as npfrom scipy.spatial import distances1 = 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])