algorithm - 有效地找到点云之间的距离

Question

我有 2 个点云(3D 空间中的一组点)和一个迭代算法。其中一朵云(我们称之为 A)在每次迭代中都是不变的，而另一朵云(称之为 B(i))在每次迭代中略有不同(这意味着 < em>B(i+1) 与 B(i) 仅在几点不同)。在 A 中的每个点的每次迭代 i 中，我的算法应该从 B(i) 中找到最近的点。

我的问题是:如何以最快的方式计算这些距离？

这是我已经尝试过的:

• 蛮力计算(计算每对点与 A 和 B(i) 的所有距离)- 绝对低效。
• 在每次迭代中为 B(i) 构建一个 KD 树，然后从 A 中找到每个点的最近点 - 比蛮力更快，但计算量仍然很大(因为我应该在每次迭代时重建 KD 树)。

似乎我应该利用一个事实，即 B(i) 和 B(i+1) 彼此之间仅略有不同，但我仍然不能想出一个好的解决办法。提前谢谢你。

Answer 1

对于 A 中的每个点，记录在上一次迭代 B(i) 中哪个点最接近。

在第 i+1 次迭代中，列出 B 中在 i 和 i+1 之间被删除或更改的每个点，以及 B 中的每个新点。

对于 A 中的每个点:

• 如果 B 中先前最近的点未更改或删除，则您只需要计算从 A 到 B(i+1) 中最近的新点的距离，并检查 B(i) 中先前最近的点).
• 如果 B(i) 中先前最近的点被更改或删除，那么您需要计算从 A 到 B(i+1) 中任何点的最近距离

您可以使用 KD 树或您喜欢的任何空间数据结构来加快速度，但优化来自第一种情况。请注意，KD 树允许删除，因此您无需每次迭代都从头开始重建整个事物。