10

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

4

3 回答 3

9

我已经亲自实施并且正是为此目的将投票给八叉树。我发现使用八叉树更容易获得更有效的结果。我说更容易是因为我认为有了这些细微的区别，实际上更多的是关于实现者而不是数据结构。但我认为对于大多数人来说，优化八叉树会更容易。

原因之一是因为 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 兆字节。

于 2018-01-05T15:16:39.923 回答
2

In my project I am using an Octree for the range search and it works efficiently and is easy to implement. Never compared it to KD-Tree though. To my knowledge the worst case time complexity in kd trees for this operation is O(n^(2/3)) for three dimensional data, while Octree can only garantee O(n). So if you care about worst time complexity, choose KD Tree. (I dont care about worst time complexity, if I know in my data set this will never happen.)

于 2013-12-04T14:01:11.923 回答
2

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

您为什么不尝试两者，看看哪个更适合您的数据？

于 2013-08-12T13:44:50.360 回答