kd树与八叉树在三维半径搜索中的比较

Question

我试图确定哪种结构更适合进行多个点的半径搜索，kd-tree还是octree？这已经在这个问题中提到过，但没有答案。在我的看法中，由于octree对于叶子节点有固定的大小，因此可以计算出需要访问的分支，而对于kd-tree，则需要迭代地访问分支，直到覆盖半径。

- paghdv

Answer 1

我个人实现了这两种数据结构，但是为了这个目的，我会选择八叉树。我发现使用八叉树可以更容易地获得更高效的结果。我之所以这么说是因为我认为在这些微妙的区别中，实现者比数据结构更重要。但是我认为对于大多数人来说，优化八叉树会更容易。

其中一个原因是K-D树本质上更深，因为它们是二叉树，每次只在一个维度上进行分割。如果你正在寻找叶子节点上的精确匹配元素，例如用于射线/三角形相交的单一、明确的路径，那么这种更深的性质可能会有所帮助。当深度合理的树与搜索质量的概念相匹配时，它非常有用。

如果你正在寻找最大半径内的最近点，而你花费大部分时间只是在树中上下移动，从叶子节点到父节点再到兄弟节点、祖父节点、父节点的兄弟节点等等，那么拥有一个深度合理的树就不太有用了。如果你可以以缓存友好的方式访问所有内容，并且你可以轻松地使八叉树缓存友好，例如将所有8个子节点连续存储，那么你只需要这样做：

struct OctreeNode
{
    // Index of first child node. To get to the 4th node,
    // we just access nodes[first_child+3], e.g.
    int first_child;
    ...
};

总之，如果这是两个选择，我会投票给八叉树。对于这种类型的接近搜索，你不一定希望八叉树太深。即使我们必须查看比最优解更多的点，使用较浅的树可能比频繁上下遍历树更好。如果在叶子节点中存储的点是连续的，那么可以通过后处理来实现。

请注意，在两种解决方案中，您都必须查看兄弟节点。最接近点并不一定是位于同一叶节点中的点。还有一些情况，仅使用三维网格实际上可以非常有效，具体取决于数据的性质，因为使用三维网格时，您甚至不必从子节点到父节点再到兄弟节点。如果将网格单元的内存开销减少到仅为32位索引，则三维网格似乎会占用大量内存，但实际上不必如此。在这种情况下，100x100x100网格所需的内存不到4兆字节。

- user4842163

---

我希望这是一篇论文，这样我就可以引用你了……人们从来没有足够关注这些事情（在我的领域）。 - kotoko

感谢您的解释，先生！ - Apollys supports Monica

Answer 2

对于3D和固定查询半径，八叉树是一个不错的选择。如果你需要在磁盘上工作，其他数据结构可能会更好，但是k-d树在这里也并不出色。

为什么不尝试两种方法，看看哪种适用于你的数据呢？

- Has QUIT--Anony-Mousse

Answer 3

在我的项目中，我使用八叉树进行范围搜索，它运行效率高且易于实现。虽然我从未将其与KD-Tree进行比较。 据我所知，对于三维数据，在kd树中进行此操作的最坏时间复杂度为O(n^(2/3))，而Octree只能保证O(n)。因此，如果您关心最坏时间复杂度，请选择KD Tree。（我不关心最坏时间复杂度，如果我知道在我的数据集中这永远不会发生。）

- BuddhaWithBigBelly

Answer 4

我以前对同样的问题很感兴趣，并进行了以下实验进行比较。

• 我们将两个点云（.pcd文件，来自LiDAR传感器）作为输入。目标点云大小=65536，源点云大小=3000。
• 对于源点云中的每个点，找到目标点云中的邻近点。
• 尺度大约在10-50米之间，在一个结构化环境中。
• 在一台13代Intel i7 CPU的笔记本上进行单线程处理。
• 数据结构的实现来自PCL，并在一个C++程序中进行了基准测试。

Operation                K-D Tree       Octree
Build Tree                   7 ms        12 ms
K-NN Search (k=1)          124 ms       390 ms
K-NN Search (k=10)         124 ms       395 ms
K-NN Search (k=100)        134 ms       573 ms
Radius Search (r=0.01 m)  1789 ms       126 ms
Radius Search (r=0.1 m)   1799 ms       129 ms
Radius Search (r=1 m)     2011 ms       415 ms

此外，我对这个结果进行了一些消融研究。

• 构建树的时间消耗与目标云的大小成线性关系。
• 每种搜索方法的时间消耗也几乎与源云的大小成线性关系（即大小为30000的云大约需要比大小为3000的云多花费10倍的时间）。
• 源查询云的位置和形状对运行时间影响不大。
• PCL点类型（PointXYZ vs. PointXYZRGBNormal）对运行时间影响不大。

- Hanzhe Teng