tree - 构建四叉树

Question

我正在尝试使用四叉树(四叉树)来保存给定 BMP 中的信息。
我正在努力弄清楚如何在给定任何 BMP 的情况下构建树。

基本上结构是这样的，每个叶子代表一个像素。每个节点有 4 个指针，每个指针指向图像中剩余的四个象限之一。这样每个节点将当前图片分成4个部分。当您到达叶子时，您已到达一个特定像素。

我不确定如何构建树来映射特定图像。假设图像的尺寸是 2 的幂，我应该怎么做。我知道递归函数可能最优雅地做到这一点，但我正在努力弄清楚如何跟踪图像中我将要到达的位置。

这是在 C++ 中，目前我的 quadtree.h 文件包含一个 Node* 根，其中一个节点被定义为一个具有像素元素和 4 个指向其他节点的指针的结构。每个内部节点(非叶节点)应该保存它导致的所有 4 个 RGB 值的平均值。

我正在尝试制作一个算法，但我认为我可能需要在 .h 文件中包含一两个结构。有没有更好/更干净的方法来解决这个问题？

Answer 1

好吧，根据您存储位图数据的方式，您可能会做不同的事情。您是从文件中读取它并将其直接放入树中吗？如果是这样，.BMP 文件(如果我没记错的话)会在顶部告诉您它们的宽度和高度，因此您实际上可以使用它来计算您将拥有多少级别，这可能有助于您构建一些东西。

此外，根据图像的大小，您可以将所有像素存储在二维节点数组中，并让树“位于”数组之上，这样您的叶子就在数组中，所有的东西都在数组中else 在别处。如果你要这样做，你可以编写一些嵌套循环，这些循环将通过并获取四个节点的组，计算它们的平均值，并将它们集中在一起，然后对刚创建的节点执行相同的操作。这可能比自上而下构建树更快，因为您永远不会平均超过 4 个像素，而自上而下构建树除了最后一步外，每一步都需要平均超过 4 个像素。

如果您不想在数组中执行此操作，在我看来，最简单的方法就是让每个节点跟踪其 x,y 坐标。这将允许您做与数组基本相同的事情，但您不只是插入索引。

这有帮助吗？你如何存储位图？最终目标是什么？