kd-tree vs octree for 3d radius search

Question

我试图弄清楚哪种结构对点,kd树或八叉树的半径搜索更好？在这个问题中已经提到过,但没有答案.在我看来,由于八叉树具有固定的叶子大小,它已经可以计算出我需要访问的分支,而对于kd-tree,你必须迭代地访问分支,直到覆盖半径.

Answer 1

我已经亲自实施了，并且正是出于这个目的，我会投票给octree。我发现使用八叉树获得更有效的结果要容易得多。我说起来容易些，因为我认为通过这些细微的区别，与数据结构相比，实际上更多地是关于实现者的。但是我认为对于大多数人来说，优化八叉树会比较轻松。

原因之一是因为KD树本质上更深，是一次在一个维度上分裂的二叉树。如果您要在叶子上寻找精确的匹配元素（例如沿着树的单一清晰路径进行射线/三角形相交），那么这种更深的性质可能会有所帮助。当一棵深树仔细地切开，与搜索质量的想法相匹配时，这很有用。

如果要搜索最大半径内的最近点，而最终却花费大部分时间只是沿着树上下移动，从叶子到父级再到同级，那么拥有一棵深的，仔细分裂的树并不是那么有用。祖父母或父母兄弟姐妹等等。如果可以以一种缓存友好的方式访问所有内容，这会有所帮助，并且您可以轻松地使八叉树成为缓存友好的，例如连续存储所有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;
    ...
};

因此，无论如何，如果这是两个选择，我将在这种情况下投票给八叉树。同样对于这种类型的邻近搜索，您不一定希望八叉树太深。即使我们必须用较浅的树查看比最佳值更多的点，这也比必须在树上上下移动要好得多。如果您存储在叶子中的点是连续的，这确实有帮助。完成构建树后，您可以通过后处理来实现这一目标。

请注意，对于这两种解决方案，您都必须查看同级节点。最接近点的点不一定是位于同一叶节点中的点。在某些情况下，根据数据的性质，实际上只有3维网格实际上可以达到最佳效果，因为有了3D网格，您甚至不必费心从子级到父级再到同级。3D网格在内存使用中似乎具有爆炸性，但如果您将网格单元的内存开销降低到仅32位索引，则不一定必须如此。在这种情况下，100x100x100的网格占用不到4兆字节。

Answer 2

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

为什么不尝试两者并看看哪一种更适合您的数据呢？