2

我正在用 C++ 实现一个八叉树，它稍后应该包含一个用于渲染的网格。但目前我正在努力构建八叉树。更准确地说，导致问题的是 addNode() 函数。我想到了一个类似于二叉树的递归实现： Binary Tree implementation C++

但是，在八叉树中，每个节点都有 8 个儿子，而不仅仅是 2 个。此外，因此我不能像在二叉树中那样使用简单的开关（左/右）来决定在哪里添加节点。我需要检查 8 个儿子之一是否为空（指针为 NULL），如果没有指针为空，我需要使用其中一个儿子作为参数调用 add 函数。然而，这将导致一个八叉树，其中第一个儿子总是包含所有后续的子八叉树。这个 add 函数通常是如何实现的并避免了这个问题？

4

2 回答 2

0

您需要检查对象的 x、y、z 尺寸，并且八叉树可以保存有限数量的对象。

于 2014-03-03T20:53:07.183 回答
0

你有正确的想法，你只需要将概念扩展到三个维度。除了决定将孩子插入左侧还是右侧（x 维度）之外，您还必须选择上方或下方（y 维度）以及前方或后方（z 维度）。您可以使用这样的三维数组：

Node* children[2][2][2];

你的内部节点（那些有分支的）应该有一个 3-D 中心和大小。在决定应将值插入八叉树的何处时，您需要将插入或搜索的位置与当前八分圆的中心进行比较：

children[position.x > center.x][position.y > center.y][position.z > center.z]

这给出了您要插入的指针。如果这个位置有节点，如果它是另一个分支，则需要递归，如果它为空则创建一个新节点，或者如果它是叶节点，则创建一个分支并重新插入。

迭代子项时，您可能会发现 3 维数组很麻烦。相反，您可以使用一维数组并对其进行索引，就好像它具有三个维度：

Node* children[8];

int index = (position.x > center.x) << 2 |
            (position.y > center.y) << 1 |
            (position.z > center.z);

这通过根据位置相对于八分圆中心的位置设置位来生成索引 [0-7]。

于 2017-11-30T16:27:23.580 回答