构建四叉树

Question

我试图使用四叉树（一种四叉树）来保存给定BMP中的信息。
我正在努力弄清楚如何构建给定任何BMP的树。

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

我不知道如何去构建一棵树来映射某个图像。假设图像的尺寸是2的幂次，我该怎么做。我明白，递归函数可能最优雅地做到这一点，但我正在努力弄清楚如何跟踪图像中的位置。

这是C++和目前我quadtree.h文件包括其中节点被定义为与一个像素元件的结构和图4点的指针到其它节点的节点*根。每个内部节点（非叶节点）应该保持所有4个RGB值的平均值。

我试图做一个算法，但我想我可能需要在.h文件结构或两项。有没有更好的/更干净的方法来解决这个问题？

Answer 1

好吧，取决于你如何存储你的位图数据，你可能会做不同的事情。你是从文件中读取它并直接放入树中吗？如果是这样，.BMP文件（如果我没有记错的话）告诉你它们在顶部的宽度和高度，所以你可以真正使用它来确定你有多少级别，这可能会帮助你建立一些东西。另外，根据您的图片的大小，您可以将所有像素存储在二维节点数组中，并使树排列在数组的顶部，以便您的叶子在数组中，并且其他一切都在别处。如果你这样做，你可以编写一些嵌套的循环，并且抓取四个节点的组，然后计算它们的平均值，并将它们集中在一起，然后对刚刚创建的节点执行相同的操作。这可能比从上到下构建树更快，因为你永远不会平均超过四个像素，而从上到下构建平均需要除了最后一个以外的每个步骤平均超过四个像素。

如果你不想做在一个阵列中，最容易的事情，在我看来，将有每一个节点跟踪它的X，Y坐标。这将允许你做与数组基本相同的事情，但你不会只是插入索引。

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

Answer 2

STANN是目前最好的开源实现。

http://sites.google.com/a/compgeom.com/stann/

聪明人的话，使用伯尔尼等人的四叉树构建算法和放弃时髦的树操作。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

1. 排序所有Morton的顺序分。
2. 计算每对连续点之间的四叉树框长度。
3. 做一个最接近的最大值计算来找到父母/兄弟姐妹。

我正在为OpenCl开发一个库。我会在完成测试后发布链接。