我有 2 个点云(3D 空间中的一组点)和一个迭代算法。其中一个云(我们称之为A)在每次迭代中都是恒定的，而另一个云(称之为B(i))在每次迭代中都略有不同(这意味着< em>B(i+1) 与 B(i) 仅在几个点上有所不同)。在每次迭代i时，对于A中的每个点，我的算法应该找到距B(i)最近的点。
我的问题是:如何以最快的方式计算这些距离？
这是我已经尝试过的:
- 强力计算(计算 A 和 B(i) 中每对点的所有距离) - 绝对低效。
- 在每次迭代中为 B(i) 构建一个 KD 树，然后从 A 中找到每个点的最近点 - 比暴力破解更快，但计算成本仍然很高(因为我应该在每次迭代时重建 KD 树)。
看来我应该利用 B(i) 和 B(i+1) 彼此之间仅略有不同的事实，但我仍然不能想出一个好的解决办法。预先感谢您。
最佳答案
对于 A 中的每个点，记录上一次迭代 B(i) 中最接近的点。
在迭代 i+1 时，列出 B 中在 i 和 i+1 之间删除或更改的每个点，以及 B 中的每个新点。
对于 A 中的每个点:
- 如果 B 中前一个最近的点没有更改或删除，那么您只需计算从 A 到 B(i+1) 中新点中最近的点的距离，并与 B(i+1) 中前一个最近的点进行检查)。
- 如果 B(i) 中之前最近的点已更改或删除，则需要计算从 A 到 B(i+1) 中任意点的最近距离
您可以使用 KD 树或任何您喜欢的空间数据结构来加快速度，但优化来自第一种情况。请注意，KD 树允许删除，因此您无需每次迭代都从头开始重建整个事物。
关于algorithm - 有效查找点云之间的距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44422807/