我有两组点 A 和 B。
我想找到B中所有在r到A范围内的点，其中a点b<B 中的/strong> 被认为在范围 r 到 A 中，如果至少有一个点 a在 A 中，其到 b 的(欧几里德)距离等于或小于 r。
两组点中的每一个都是一组连贯的点。它们是从两个不重叠对象的体素位置生成的。
在 1D 中这个问题相当简单:B 的所有点在 [min(A)-r max(A)+r]
但我在 3D 中。
执行此操作的最佳方法是什么？
我目前使用某种 knn 算法(即 matlab 的范围搜索)重复搜索 A 中 B 中所有点的每个点，然后将所有这些集合结合起来。但我觉得应该有更好的方法来做到这一点。我更喜欢 matlab 中的高级/矢量化解决方案，但伪代码也很好:)
我还想过将所有点写入图像，并在半径为 r 的对象 A 上使用图像膨胀。但这听起来开销很大。
最佳答案
您可以使用 k-d tree存储 A 的所有点。
迭代 B 的点 b，对于每个点 - find the nearest point in A (让它成为)在 k-d 树中。当且仅当距离 d(a,b) 小于 r 时，点 b 才应包含在结果中。
复杂度为 O(|B| * log(|A|) + |A|*log(|A|))
关于algorithm - 找到范围内的所有点到另一组的任何点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18086052/