C++八叉树容器

Question

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

Answer 1

你的问题非常笼统.但我会试着给你这个想法.请注意,实现八叉树的方法有很多种,这取决于您的应用程序.在这个例子中,我将集中讨论简单的情况,你总是在中间划分.

让我们先简单一点.想象一下,你有一组数字(1维数据).您可能希望对这些进行分组,以便您可以更轻松地搜索它们.一种方法(即使在这种特殊情况下存在更好的方法),也就是创建一棵树.让我们把它称为bitree(这样它就不会与二叉树混合,即使它是一种二叉树).

在此bitree中,每个节点将代表范围的中间.在左侧,您将获得小于该值的值,并在右侧更大.当然,树的根将代表最小值和最大值之间的中间值.在每个叶子中,如果您拥有的值多于可以处理的值,则拆分并创建子树.例如,如果您的值介于0和100之间,则bitree可能如下所示:

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

此树表示此数组:

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

我假设你熟悉二叉树,所以实现这样一棵树对你来说应该不是问题.

这里的关键是,每个叶子可以包含多达一定数量的节点.每次插入bitree时,如果叶子溢出,则得到其范围的中间值,创建一个节点并将值分成两个叶子.

现在让我们将其扩展到2d.想象一下你的价值观是(x,y)(而不仅仅是x)的形式.我们可以用与上面相同的方式划分这些值,但不是将它们分成中间的左右两侧,而是将它们分为中心的左上,左下,右上和右下.其余的完全相同.我们称之为四叉树,因为它有4个孩子.这个四叉树的实现与bitree完全相同,所以你现在应该能够理解它.

来自维基百科的示例,其中每个叶子只能包含1个值:

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

我坚持你将如何从头开始逻辑地构建一个.它背后的逻辑是什么？它使用两个容器吗？它是否在课堂上使用虚拟功能？孩子们如何工作？

再次,与实现二叉树的方式完全相同.如果在那里使用虚函数,也可以在八叉树中使用虚函数.