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 distance

A = [(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 np

A = [(1, 1), (2, 1), (3, 1)]

B = [(2, 2), (3, 3)]

# compare each point in A to all points in B, return the shortest distance

for 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.4142135623730951

1.0

1.4142135623730951

最大的区别是什么？上面的代码计算 3 个平方根。朴素方法计算 6 （|{B}|倍数）

Answer 3

我找到了一种方法，我不知道是否有人能更有效地做到这一点，

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