计算 3D 点的距离矩阵

Question

我在 Matlab 中有列表 xA、yA、zA 和列表 xB、yB、zB。包含类型 A 和类型 B 的点的 x、y 和 z 坐标。类型 A 和类型 B 点的数量可能不同。

我想计算一个矩阵，包含A类和B类点之间的欧式距离。当然，我只需要计算矩阵的一半，因为另一半包含重复数据。

最有效的方法是什么？

完成后，我想找到最接近 A 型点的 B 型点。然后如何找到最近、第二近、第三近等的坐标B 类积分？

Answer 1

给定一个大小为 [N,3] 的矩阵 A 和一个大小为 [M,3] 的矩阵 B，您可以使用 pdist2 函数得到一个矩阵大小 [M,N] 包含所有成对距离。

如果你想根据点到 A 中第 r 点的距离对 B 中的点进行排序，那么你可以对 r 中的第 r 行进行排序成对距离矩阵。

% generate some example data
N = 4
M = 7

A = randn(N,3)
B = randn(M,3)

% compute N x M matrix containing pairwise distances
D = pdist2(A, B, 'euclidean')

% sort points in B by their distance to the rth point in A
r = 3
[~, b_idx] = sort(D(r,:))

然后 b_idx 将包含 B 中的点的 索引 按它们到 r 中第 [=] 个点的距离排序13=]。所以b_idx排序的B中的实际点可以用B(b_idx,:)得到，和B.

大小一样

如果您想对所有 r 执行此操作，您可以使用

[~, B_idx] = sort(D, 1)

同时对 D 的所有行进行排序。那么 B_idx 的第 r 行将包含 b_idx.

---

如果你唯一的 objective 是为 A 中的每个点找到 B 中最近的 k 点（对于一些正整数 k小于 M)，那么我们通常 而不是 想要计算所有成对距离。这是因为 space-partitioning 类似 K-D-trees 的数据结构可用于提高搜索效率，而无需显式计算所有成对距离。

Matlab 提供了一个 knnsearch 函数，它使用 K-D-trees 来达到这个目的。例如，如果我们做

k = 2
B_kidx = knnsearch(B, A, 'K', k)

那么 B_kidx 将是 B_idx 的前两列，即对于 A 中的每个点，B 中最近的两个点的索引。另外，请注意，当 k 相对较小时，这只会比 pdist2 方法更有效。如果 k 太大，那么 knnsearch 将自动使用之前的显式方法而不是 K-D-tree 方法。