logo标签列表

构建四叉树

treetraversalquadtree
3
我正在尝试使用四叉树（4元树）来存储给定 BMP 图像中的信息。
我不知道如何构建这棵树，以适应任何 BMP 图像。基本上，树的结构是这样的，每个叶节点代表一个像素。每个节点有 4 个指针，每个指针都指向图像中剩余的四个象限之一。因此，每个节点将当前图像分成四部分。到了叶子节点，就到达了一个特定的像素。
我不确定如何构建一棵树来映射某个图像。假设该图像的尺寸是2的幂次方，我该怎么办？我明白，一个递归函数可能最优雅地完成这项任务，但我仍在思考如何跟踪我要去哪个像素。
这是用 C++ 编写的，我的 quadtree.h 文件目前包括一个 Node* 根节点，其中节点被定义为具有像素元素和 4 个指向其他节点的指针的结构。每个内部节点（非叶子节点）应该保存它所指向的所有 4 个 RGB 值的平均值。
我正在制作一个算法，但我认为我可能需要在 .h 文件中包含一个或两个结构体。有没有更好/更清晰的方法来解决这个问题？
2个回答
2
嗯，根据您存储位图数据的方式不同，您可能会采取不同的方法。如果您是从文件中读取并将其直接放入树中，那么.BMP文件（如果我记得正确的话）会在顶部告诉您它们的宽度和高度，因此您实际上可以使用它来确定您将有多少层，这可能有助于构建一些东西。
另外，根据您的图像大小，您可以将所有像素存储在节点的二维数组中，并使树“坐在”该数组之上，以便您的叶子在数组中，其他所有内容都在其他地方。如果您这样做，可以编写一些嵌套循环，通过抓取四个节点组，计算它们的平均值并将其合并，然后对刚刚创建的节点执行相同的操作。这可能比从上到下构建树更快，因为除了最后一个步骤之外，您永远不会平均超过四个像素，而从上到下构建则需要每个步骤平均超过四个像素。
如果您不想在数组中执行此操作，我认为最简单的方法是使每个节点跟踪其x，y坐标。这将允许您基本上执行与数组相同的操作，但您不仅仅是插入索引。
这有帮助吗？您是如何存储位图的？最终目标是什么？
1
非平面用户请注意：STANN可能适用于2D/3D，但是据“Readme”文件所述，“它是设计用于低维数据集，最好是3D。” - denis
STANN是一个点四叉树（用于点云），而他需要一个区域四叉树。但我为Morton Order点赞。 - AlexWien
我的想法是每个点一个像素。我假设如果那个人需要四叉树，他正在处理大型图像集的天文/地理信息系统。 - Chad Brewbaker
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接