我有一个3D点云和我想有效地查询距离d内的所有点从任意点P（这不一定是所存储的点云的一部分）
查询看起来是这样的
Pointcloud getAllPoints(Point p, float d);
什么accelerationstructure将是适宜的？ 一系列的树似乎只适合查询长方形卷，而不是球体体积（当然我可以查询领域的外接矩形框，然后整理出具有比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次查询，积分得到位移和一些（不是很多！），插入和缺失制成。 相比于所有点的外接矩形框的偏移向量都非常小
你想要的是分解空间，使特定区域可以有效地发现的结构。 一个正确分解八叉树或kD树应该让你做好这一点，因为你只会“开放”包含您点树的部分p找点附近。 这应该让你把一个相当低的渐近绑定在你需要多少额外的点距离比较（明知下面分解一定程度上，所有的点都足够接近）。 不幸的是，我不知道在这方面不够好，提供更详细的指点文献。 我的这些事情遇到的是从巴恩斯必胜客N体模拟算法。
这里的另一个问题密切相关的这一个。 而另一个 。 和第三 ，提的是，我没有以前听说过的数据结构（希尔伯特R树）。
VTK可以帮助：
无效vtkAbstractPointLocator :: FindPointsWithinRadius（
双R，双层的x，双Y，双Z，vtkIdList *结果
）
的子类vtkAbstractPointLocator包含搜索加速不同的数据结构：普通水桶，KD树和八叉树。
我不明白你的API，你可以在一个点云摆在任意球中集齐所有点，但你也说，点云存储？ 在这种情况下，你不应该得到点云是给定的范围内的清单，否则什么是点（原谅双关语）有其中存储的点云？
而不是试图预先定义的API，当你需要它定义它。 有没有必要实施的东西，永远不会被使用，更不用说优化是永远不会被调用的函数（除非它是当然的:)有趣）。
我想你应该实现包围盒剔除，然后是更详细的球形搜索作为第一个实施。 也许它不是这样的瓶颈，你想，也许你会有更严重的瓶颈问题需要考虑。 它总是可以稍后优化当你真正看到你所拥有的一切toghether工作，你有计划。
看看一个模板的近邻问题（拉里·安德鲁斯在DDJ） 。 其唯一的2D，其为O（log n）的retrival复杂，但它可能会为3D采用为好。
一个Map键等于距离和值是该点本身就允许你查询不到一定距离或给定范围内的所有点。
嗯，这取决于使用什么其他你需要的数据结构。
您可以从点p距离等穴位，按距离排序的名单，而这些名单映射到同一个HashMap的点。
map:
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}]
p2 -> ...
...
你可以看一下点地图，并重复列表，直到距离高于所需。
文章来源: which data structure is appropriate to query “all points within distance d from point p”
