两个不相等点集之间的最小距离

Question

我希望能够找到xy平面上2组点之间的最小距离。假设第一组点A有9个点，第二组点B有3个点。我想找到连接A中每个点到B中一个点的最小总距离。显然会有一些重叠，甚至可能有一些B中没有链接的点。但A中所有的点必须有且只有一个链接来自B中的一个点。

如果两组集合中的点数相等，我已经找到了解决方法，并提供了代码：

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist
from scipy.optimize import linear_sum_assignment

points1 = np.array([(x, y) for x in np.linspace(-1,1,3) \
          for y in np.linspace(-1,1,3)])
N = points1.shape[0]
points2 = 2*np.random.rand(N,2)-1

cost12 = cdist(points1, points2)
row_ind12, col_ind12 = linear_sum_assignment(cost12)

plt.plot(points1[:,0], points1[:,1], 'b*')
plt.plot(points2[:,0], points2[:,1], 'rh')
for i in range(N):
    plt.plot([points1[i,0], points2[col_ind12[i],0]], [points1[i,1], 
             points2[col_ind12[i],1]], 'k')
plt.show()

- Bobby Stiller

---

你只是想找到每个A点在B中的最近邻吗？ - user2357112

你能否发布你的代码的图表或其他输出？ - Prune

我已经发布了图表。是的，我正在尝试找到A最近的B邻居。 - Bobby Stiller

Answer 1

函数 scipy.cluster.vq.vq 可以实现您想要的功能。

这是您的代码的修改版本，演示了 vq：

import numpy as np
from scipy.cluster.vq import vq
import matplotlib.pyplot as plt


# `points1` is the set A described in the question.
points1 = np.array([(x, y) for x in np.linspace(-1,1,3)
                               for y in np.linspace(-1,1,3)])

# `points2` is the set B.  In this example, there are 5 points in B.
N = 5
np.random.seed(1357924)
points2 = 2*np.random.rand(N, 2) - 1

# For each point in points1, find the closest point in points2:
code, dist = vq(points1, points2)


plt.plot(points1[:,0], points1[:,1], 'b*')
plt.plot(points2[:,0], points2[:,1], 'rh')

for i, j in enumerate(code):
    plt.plot([points1[i,0], points2[j,0]],
             [points1[i,1], points2[j,1]], 'k', alpha=0.4)

plt.grid(True, alpha=0.25)
plt.axis('equal')
plt.show()

脚本生成以下绘图：

- Warren Weckesser