C++八叉树容器

Question

C++八叉树容器

c++containersoctree

4

我在网上搜索了关于八叉树容器如何工作的解释，但是找不到任何清晰明确的解释。有人知道如何实现一个具有8个子节点（或者更多）的八叉树容器吗？如果知道，请分享/解释其逻辑...或者告诉我去哪里学习如何实现它。

- User

1

这是一个关于八叉树的维基百科链接，它能告诉你需要了解的内容吗？ - Oliver Charlesworth

1

先尝试学习四叉树。然后将这个想法从二维扩展到三维，你就会得到八叉树。 - Shahbaz

@OliCharlesworth 不，那并没有告诉我任何东西。:( - User

@Ohmages：那你卡在哪里了？维基百科文章的第三句话说：“八叉树是四叉树的三维等价物”…… - Oliver Charlesworth

@OliCharlesworth 我对编程的高级主题还很陌生。我不知道八叉树容器只是四叉树的扩展。我不知道如何从头开始逻辑地构建一个八叉树容器。它背后的逻辑是什么？它使用两个容器吗？它在类中使用虚函数吗？子节点是如何工作的？我会研究四叉树（因为有更多的信息）并看看是否有意义 :/ - User

你可以看一下http://www.ogre3d.org/是如何实现它的八叉树的。 - Pete

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shahbaz · Accepted Answer

您的问题比较泛化，但我会尝试给您提供思路。请注意，有许多实现八叉树的方式都取决于您的应用程序。在本例中，我将重点关注简单情况，即您始终按中间分割。

我们首先从简单的开始。想象一下您有一组数字（一维数据）。您希望将它们分组，以便更轻松地搜索它们。一种方法是创建一个树（虽然在这种特殊情况下存在更好的方法），我们称之为二元树（这样它就不会与二叉树混淆，尽管它也是一种二叉树）。

在这个二元树中，每个节点将代表一个范围的中心。左边是小于该值的值，右边是大于该值的值。树的根当然代表最小和最大值之间的中间值。在每个叶子节点中，如果有更多的值超出处理能力，您需要进行分割并创建子树。例如，如果您有0到100之间的值，一个二元树可能是这样的：

                  50
              /        \
           25            75
         /    \        /    \
        12   {27,33}  62    {}
      /    \        /    \
   {1,3}  {13}   {51,52} {72}

这棵树表示了这个数组：

{1, 3, 13, 27, 33, 51, 52, 72}

我假设你熟悉二叉树，因此实现这样的树对你来说应该不是问题。

关键在于，每个叶子节点可以包含多达一定数量的节点。每次向二叉树插入值时，如果一个叶子节点溢出，取其范围的中间值，创建一个节点并将其值分成两个叶子节点。

现在让我们扩展到二维情况。假设你的值是以 (x,y) 的形式而不是只有 x 。我们可以按照上面的方式将这些值分割，但是不是将它们分为中间的左边和右边，而是将它们分为中心的左上、左下、右上和右下四个区域。其余部分完全相同。我们称之为四叉树，因为它有 4 个子节点。实现这个四叉树与二叉树完全相同，所以你现在应该能够理解它。

下面是维基百科的一个例子，其中每个叶子节点只能包含一个值：

enter image description here

最后是将其扩展到三维。与之前相同，现在的值是以 (x,y,z) 的形式出现。这一次，不再将值分为 4 个区域，而是将它们分成 8 个区域：左上前、左上后、左下前、左下后、右上前、右上后、右下前和右下后。我们称之为八叉树，实现方式与其他树完全相同。

我对从头开始逻辑构建卡住了。背后的逻辑是什么？它使用两个容器吗？它在类中使用虚函数吗？子节点部分是如何工作的？

与实现二叉树的方式完全相同。如果你在那里使用了虚函数，也可以在八叉树中使用虚函数。