c++ - C++ 八叉树容器

Question

我在网上搜索了有关八叉树容器如何工作的解释。我找不到任何关于如何工作的明确解释。（至少，这对我来说很有意义......）有谁知道如何实现一个八叉树容器？一个有 8 个孩子（左右）。如果是这样，你介意分享/解释逻辑......或者我可以去哪里学习如何实现一个。

Answer 1

你的问题很笼统。但我会试着给你这个想法。请注意，有很多方法可以实现八叉树，这都取决于您的应用程序。在这个例子中，我将专注于简单的情况，你总是在中间分开。

让我们先从简单的开始。假设您有一组数字（一维数据）。您可能希望对它们进行分组，以便更轻松地搜索它们。一种方法（即使在这种特殊情况下存在更好的方法）是创建一棵树。让我们称它为比特树（这样它就不会与二叉树混合，即使它是一种二叉树）。

在这个比特树中，每个节点将代表一个范围的中间。左边的值会小于这个值，右边的值会更大。树的根当然代表最小值和最大值之间的中间值。在每个叶子中，如果您的值超出您的处理能力，则拆分并创建一个子树。例如，如果您的值介于 0 和 100 之间，则比特树可能如下所示：

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

这棵树代表这个数组：

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

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

这里的关键是，每个叶子最多可以包含一定数量的节点。每次插入比特树时，如果叶子溢出，您将获得其范围的中间，创建一个节点并将值划分为两个叶子。

现在让我们将其扩展到 2d。想象一下你的价值观是(x,y)（而不是只是x）的形式。我们可以像上面一样划分这些值，但不是将它们划分为中间的左右，而是将它们划分为中心的左上、左下、右上和右下。其余的完全一样。我们称之为四叉树，因为它有 4 个孩子。这个四叉树的实现和二叉树完全一样，所以你现在应该可以理解了。

来自 Wikipedia 的示例，其中每个叶子只能包含 1 个值：

最后一步是将其扩展到 3d。和以前一样，现在的值是(x,y,z). 这一次，不是将值划分为 4 个区域，而是将它们划分为 8 个区域：左上前、左上后、左下前、左下后、右上前、右上-后，右前和右后。我们称其为八叉树，其实现再次与其他的完全相同。

我被困在你如何从头开始合乎逻辑地构建一个。其背后的逻辑是什么？它使用两个容器吗？它在类中使用虚函数吗？孩子们的部分是如何工作的？

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