我有两组点A and B.
我想找到所有点B是在一定范围内的r to A，其中一点b in B据说在范围内r to A如果至少有一个点a in A其（欧几里得）距离b等于或小于r。
两组点中的每一个都是连贯的点集。它们是根据两个不重叠对象的体素位置生成的。
在一维中这个问题相当简单：所有点B在[分钟(A)-r max(A)+r]
但我是3D的。
做这个的最好方式是什么？
我目前重复搜索每个点A所有点在B使用某种 knn 算法（即 matlab 的 rangesearch）在范围内，然后联合所有这些集合。但我有一种感觉应该有更好的方法来做到这一点。我更喜欢 matlab 中的高级/矢量化解决方案，但伪代码也很好:)
我还考虑将所有点写入图像并在半径为 r 的对象 A 上使用图像膨胀。但这听起来像是相当大的开销。
您可以使用k-d tree https://en.wikipedia.org/wiki/K-d_tree存储 A 的所有点。
迭代 B 的点 b，并且对于每个点 -找到 A 中最近的点 https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search（设其为 k-d 树中的 a）。当且仅当距离 b 点才应包含在结果中d(a,b)则较小r.
复杂度将是O(|B| * log(|A|) + |A|*log(|A|))
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
