13

我有一个 3D 点云，我想有效地查询距任意点 p 距离 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 次查询之后，这些点会发生位移，并且会进行一些（不是很多！）插入和删除。与所有点的边界框相比，偏移向量非常小

4

6 回答 6

6

您想要的是一种分解空间的结构，以便可以有效地找到特定区域。正确分解的八叉树或kD-tree应该可以让您很好地做到这一点，因为您只会“打开”包含您的点的树部分p以查找附近的点。这应该让您对需要比较距离的额外点设置一个相当低的渐近界限（知道在某种程度的分解之下，所有点都足够接近）。不幸的是，我不太了解这方面的文献，无法提供更详细的指示。我遇到这些东西是来自 Barnes-Hut n-Body 模拟算法。

这是另一个与此密切相关的问题。还有一个。第三个，提到我以前没有听说过的数据结构（Hilbert R-Trees）。

于 2009-08-23T13:57:46.127 回答
2

VTK可以帮助：

void vtkAbstractPointLocator::FindPointsWithinRadius（
双 R，双 x，双 y，双 z，vtkIdList * 结果
）

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

于 2009-09-10T13:00:23.673 回答
1

查看最近邻问题的模板（DDJ 的 Larry Andrews）。它唯一的 2D，具有 O(log n) 的检索复杂度，但它也可能被用于 3D。

于 2009-09-10T13:08:39.260 回答
1

我不了解您的 API，您可以将 PointCloud 中位于任意球体内的所有点四舍五入，但您还说点云已存储？在这种情况下，您不应该获得给定球体内的点云列表，否则存储点云有什么意义（请原谅双关语）？

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

我认为你应该实现边界框剔除，然后是更详细的球体搜索作为第一个实现。也许它并没有你想象的那么严重，也许你会有更严重的瓶颈需要考虑。当您真正看到一切都按照您的计划一起工作时，总是可以稍后进行优化。

于 2009-08-23T15:08:48.887 回答
0

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

于 2009-08-23T13:52:02.733 回答
0

好吧，这取决于您需要数据结构的其他用途。

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

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

您可以在地图中查找该点，然后迭代列表，直到距离高于所需距离。

于 2009-08-23T13:52:37.677 回答