哪个数据结构适合查询"距离点p的距离d内的所有点"

Question

我有一个3D pointcloud,我想从任意点p(它不一定是存储的pointcloud的一部分)有效地查询距离d内的所有点

查询看起来像

Pointcloud getAllPoints(Point p, float d);

什么加速结构适合这个？范围树似乎仅适用于查询矩形体积,而不是球体体积(当然,我可以查询球体的边界框,然后整理距离大于d的所有顶点 - 但也许有更好的方法可以做到这个？？)

谢谢!

根据Novelocrats的建议,我尝试定义结构的所需功能:

SearchStructure Create(Set<Point> cloud) 
Set<Point> Query(SearchStructure S, Point p, float maxDistance)
SearchStructure Remove(Point p)
SearchStructure Insert(Point p)
SearchStructure Displace(Set<Point> displacement) //where each value describes an offsetVector to the currently present points

通常,在n次查询之后,这些点会被取代,并且会进行一些(不是很多!)插入和删除.与所有点的边界框相比,偏移矢量非常小

Answer 1

你想要的是一个分解空间的结构,以便有效地找到特定的区域.正确分解的八叉树或kD树应该可以让你做得很好,因为你只需要"打开"包含你的点的树的部分p来寻找附近的点.这应该让你在比较距离所需的额外点数上设置一个相当低的渐近界限(知道在某种程度的分解下,所有点都足够接近).不幸的是,我不清楚这个领域的文献是否足以提供更详细的指示.我遇到这些事情来自Barnes-Hut n-Body模拟算法.

这是另一个与此问题密切相关的问题.而另一个.和第三,提的是,我没有以前听说过的数据结构(希尔伯特R树).

Answer 2

键等于距离且值为点本身的地图将允许您查询小于给定距离或给定范围内的所有点。