问题标签 [quadtree]

这是我过去几个小时一直在考虑的事情。这是一个头脑练习。

所以我今天知道了八叉树是什么！很有意思！我一直在考虑如何实现一个解析为体素的八叉树。

我现在无法解决的最大问题是引用八叉树中的位置。

免责声明：首先，我将在二维平面中使用四叉树来可视化我的问题。其次，我在这里不理解正确的术语，我将假设八叉树中作为父级的任何细分都是“分支”，而任何只有子级的细分（在这种情况下它解析为体素）是一片树叶”。第三，我要对四叉树的一个分支中的每个空间进行编号，从左到右从上到下 {1,2,3,4}

假设我有一个定义 16x16 单位空间的四叉树。在位置 [16,16] 我存储了一个体素。

现在假设我们将一个体素添加到位置 [4,4]。（注意，我们从零开始）

现在假设我想检查 [16,8] 以查看是否存储了体素。使用前面的方法，我们将在技术上遍历这些分支：

但是 4->1 没有分配任何数据，所以它是空的。（它没有细分，因为它没有在使用中）。

我的问题变成了这个，我怎样才能快速遍历四叉树找到体素？

我的第一个也是最简单的方法是以我上面使用的格式沿着分支向下移动。

这里的问题是 voxelArray[16][16]、voxelArray[4][4] 或 voxelArray[16][8] 要快得多。使用更大的四叉树 (256x256) 会增加深度（从 4 到 8）。嵌套数组仍然是 2 个内存操作。（注意，对于四叉树，实际上我们将使用访问器的东西并检查以确保孩子存在条件逻辑）

我的第二个想法是将四叉树本身存储为体素。例如，假设我们有一个 2x2 数组，空它看起来像

在位置 [1,1] 我们将添加一个体素，它会变成

如果我们要存储四叉树，它看起来像这样

把它带到一个 4x4 和

尽管现在您可以直接访问数据，但您已经失去了四叉树的内存紧凑性，您仍然可以执行许多逻辑操作。IMO 仅当您有大面积的 0 和小范围的 1 时，这才会有效。

通过将体素存储在四叉树/八叉树中，您可以在循环遍历所有体素时获得性能，但在直接访问它们时会损失性能。

如果我想遍历四叉树，尺寸必须只有 2^n 吗？如果不是，如果它不能被分成相等的子象限怎么办？例如，带有数据的 5x6 表。

我将 2 个对象添加到 QuadTree，但是当我查看整个对象列表时，我只能找到 1 个对象。为什么会这样，我能做些什么来解决它？

当我插入对象时，它会打印出来

platform.Platforms 对象位于 0x0236F950 platform.Platforms 对象位于 0x0236F950 platform.Platforms 对象位于 0x0236F950 platform.Platforms 对象位于 0x0236F950 platform.Platforms 对象位于 0x0236FAB0 platform.Platforms 对象位于 0x0236FAB0 对象 platform.FAB0236 平台对象位于 0x023P6

这很好我想要可变树中有两个不同的对象但是当我调用它时它只有列表中的第二个

所以我做了一个函数

打印出来

platform.Platforms 对象位于 0x02320A70 rect(350, 630, 110, 110) platform.Platforms 对象位于 0x02320A70 rect(350, 630, 110, 110) platform.Platforms 对象位于 0x02320A70 rect(350, 630, 110, 110) 平台。平台对象位于 0x02320A70 rect(350, 630, 110, 110)

我一直在搜索谷歌和亚马逊，但在基于四叉树的 LOD 地形上找不到任何合适的资源。有些人只是解释了粗略的概念，但这是我已经知道的，我需要的是带有一些评论的示例。

我有一个与小波包分解有关的问题。

我需要从完整（完整）树（四叉树）中计算出最佳树（基础）。这可以通过 MATLAB 的函数besttree来完成。不幸的是，我不能在我的程序中使用 m 文件。

我在 python 上编写程序，pywt引起了我的注意，但是在这个模块中没有计算最佳树的函数。是否有任何模块、库或一些示例在 C++/C 或 python 上计算出最佳树小波包分解（四叉树）？是否有可能将 m 文件转换为 C++/C 或 python？

我将编写一个 KDTree 的模板化实现，它现在只能用作 BarnesHut 实现的 Quadtree 或 Octree。

这里的关键是设计，我想指定树定义为模板参数的维数，然后简单地声明一些常用方法，它们会自动以正确的方式运行（我认为那时需要一些模板专业化）。

我想专门化模板以获得 2^2（四叉树）或 2^3（八叉树）节点。

有人有一些设计理念吗？我想避免继承，因为它限制我进行动态内存分配而不是静态分配。

这里 N 可以是 2 或 3

另一个问题是四叉树有 4 个节点但 2 维，八叉树有 8 个节点但 3 维，即节点数为2^dimension。我可以通过模板元编程指定这个吗？我想保留数字 4 和 8，以便循环展开器可以更快。

谢谢！

我正在使用这篇维基百科文章中描述的技术构建一个四叉树。我将坐标存储在 2 维或 3 维数组中。

我需要一种方法来计算 z 顺序中下一个框的坐标。它可以通过交错位来工作，增加一而不是去交错，但这会变得非常复杂。我希望有一个类似于文章中 cmp_zorder(...) 方法的实现，它可以在不交错位的情况下工作。

有没有办法在四叉树细分中找到相邻的单元格？我的意思是在任何级别与所选单元格相邻的所有单元格？

我正在创建一个分块的 QuadTree 地形，并试图确保两个节点之间的细节差异不会超过一个级别。我当前的构造函数代码是这样的：

这很好用。但是为了强制两个相邻节点之间的差异不超过一个级别，我试图将其添加到构造函数的末尾：

但是那个堆栈溢出了。我认为的一个原因是该Children[iii] = new QuadNode(GetRect(iii), this, Root);语句的赋值部分永远不会执行，并且FindNeighbour()需要设置孩子以找到合适的邻居。但我认为这不是唯一的问题，因为代码实际上从未到达第二neighbour = FindNeighbour(direction);行，而且我不知道是什么原因造成的。

如果我在树的基本创建之后在新函数中运行第二个代码片段，它或多或少可以工作，但是它需要多次传递以确保新创建的节点本身不会产生大于 1 的级别差异。所以我如果可能的话，我宁愿在构造函数中包含这段代码。谁能想到实现这一目标的方法？

课堂上的一些笔记，以防它有助于QuadrantNeedsChild(int quadrant)确保水平永远不会超过 8，所以我知道我不仅仅是太深了。Subdivide()只是Children[iii] = new QuadNode(GetRect(iii), this, Root);在所有象限上运行。FindNeighbour(int direction)可以返回父级或祖先。例如，如果 D 正在寻找北邻居，如果 B 从未细分为以下内容，它将获得其祖父母（整个图表）：

如果提供了超出范围的象限，则细分功能仅细分给定的象限或所有象限。

我的代码中有一个类似四叉树的结构，我想在 gnuplot 中对其进行可视化。这意味着我想查看矩形细分。我想在 gnuplot 中使用它的原因是因为我想在这个轮廓上绘制一个 2d 函数以显示细分数量和函数值之间的相关性。

有没有人知道如何做到这一点？