哪种数据结构适合查询“距离点p小于d的所有点”？

Question

我有一个三维点云，想要高效地查询距离任意点p（不一定是存储的点云中的点）距离为d以内的所有点。

查询操作应该类似于：

Pointcloud getAllPoints(Point p, float d);

对于这种情况，应该选择哪种加速结构呢？Range-Tree 似乎只适用于查询矩形体积，而不适用于球体积（当然我可以查询球体的边界框，然后筛选出距离大于 d 的所有顶点 - 但也许有更好的方法？）

谢谢！

根据 Novelocrat 的建议，我尝试定义了所需结构的功能：

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次查询后，点会发生位移，并进行少量（不多！）插入和删除操作。与所有点的边界框相比，偏移向量非常小。

- genesys

---

“Query” 只有一个 ‘r’。我建议为了后人修复这个错误。 - Phil Miller

Novelocrat：你说得对——新的点云是旧点云的修改版本，但这些修改相当困难（所有点都会移动，每个点都会朝着不同的方向移动，而且还可能添加之前不存在的新点），所以我认为每次重新创建地图会是最好的选择。在点云移动之前，一个包含n个点的地图大约会有n个这样的查询。 - genesys

你应该指定这些结构在程序运行时如何变化，而不是假设完全重建是最佳方法。计算几何学家已经做了一些非常聪明的工作。考虑到他们的一个主要历史资金来源（美国海军研究办公室）移动点可能是一个非常感兴趣的话题。你应该将所有这些信息融入到问题中。 - Phil Miller

我根据标签并查看类似的内容，给我的回答添加了一堆链接。 - Phil Miller

你的问题通常有多大？原始点云有多大？你计划进行多少次查询？在查询中，“d”范围通常有多大——你期望结果点云有多大？我只是想了解你真正需要扩展的维度，看看是否值得描述我所拥有的解决方案... - balint.miklos

Answer 1

你需要的是一种将空间分解以便能够高效地找到特定区域的结构。一个正确分解的八叉树或kD树应该能够很好地实现这一点，因为你只需要“打开”包含你的点p附近点的树部分即可。这应该让你能够对需要比较距离的额外点数设置相当低的渐近界限（知道在某个分解级别以下，所有点都足够接近）。不幸的是，我对这个领域的文献了解不够，无法给出更详细的指导。我的经验来自Barnes-Hut n-Body模拟算法。

这里有另一个问题与此密切相关。 还有另一个。 以及第三个，提到了一个我之前没有听说过的数据结构（希尔伯特R树）。

- Phil Miller

---

我考虑过八叉树，但似乎不太合适，因为可能存在实际上在距离d范围内但位于p本身所在的另一个部分的点。因此，必须查询与由p和d定义的球相交的所有部分。 - genesys

这是一个很好的观点。如果有一些范围树变体的八叉树，那么你就会很成功。 - Phil Miller

SciPy有一个KDTree实现，它有一个名为query_ball_point的函数，可以完美地完成这个任务。 - sffc

Answer 2

VTK 可以帮助您：

void vtkAbstractPointLocator::FindPointsWithinRadius (
double R, double x, double y, double z, vtkIdList * result
)

vtkAbstractPointLocator 的子类包含不同的数据结构，用于加速搜索：常规桶、kd树和八叉树。

- tim_hutton

Answer 3

我不理解你的API，你可以将PointCloud中所有位于任意球内的点舍入，但你也说点云是存储的？如果是这样，那么你不应该得到一个在给定球内的PointCloud列表吗？否则，为什么要存储PointClouds呢？

与其试图预先定义API，不如在需要时再定义它。没有必要实现永远不会使用的东西，更不用说优化永远不会被调用的函数了（除非当然是为了好玩 :))。

我认为你应该首先实现边界框裁剪，然后是更详细的球形搜索。也许这不是你想象中的瓶颈那么严重，也许你将有更严重的瓶颈需要考虑。当你实际看到你计划中的一切都能很好地协同工作时，随时可以进行优化。

- crunchdog

Answer 4

请查看最近邻问题的模板（Larry Andrews在DDJ上）。它只有2D，检索复杂度为O(log n)，但也可以用于3D。

- RED SOFT ADAIR

Answer 5

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

- duffymo

---

距离不能是关键因素，因为p是任意点（因此p是查询的参数 - 我在这方面不够具体）。 - genesys

一旦您指定了点，就可以填充数据结构。更改点后，重新填充。我认为它仍然有效。 - duffymo

每个查询中的点都是不同的。更新所有距离到点p的距离已经需要O(n)的时间了。 - genesys

是的，我同意，但我看不到任何解决办法。你呢？ - duffymo

Answer 6

这取决于您对数据结构的其他用途。

您可以拥有从点p到其他点的距离列表，按距离排序，并使用哈希映射将这些列表映射到相应的点。

map:
p1 -> [{p2, d12}, {p4, d14}, {p3, d13}]
p2 -> ...
...

你可以在地图上查找该点，并迭代列表，直到距离大于所需距离。

- Zed