四叉树如何处理非正方形区域？

Question

7

我了解四叉树在方形图像上的工作原理（通过将图像分割直到该部分为单一颜色，并将其存储在叶节点中）。

如果图像的一个维度比另一个维度更长，那么最小子单位可能是2x1像素区域，这使得使用四叉树分割方法来存储单一颜色变得困难。您将如何解决此问题？

- user559142

3个回答

1

为什么不允许在树中存在空的叶子节点？编辑：也许我没理解问题。你的问题是最终得到了一些非正方形的图像，例如2x1，但想把它们表示为四叉树节点吗？

当你有一个2x2的正方形像这样： 1 2 3 4

你可以创建一个四叉树节点，例如“new QuadNode(1,2,3,4)”。

对于一个2x1的矩形，我建议使用类似“new QuadNode（1,2,null,null）”的方法进行处理。如果有更大的缺失块，您可以使用相同的系统。例如，如果有一个4x2的图片像这样：

1 2 3 4 5 6 7 8

那么你可以使用“new QuadNode(new QuadNode(1,2,3,4),null,new QuadNode(5,6,7,8),null)”进行表示。

这种方法也适用于颜色相同而不是像素的图块。

我是否正确理解了你的问题并表达清楚？

- kasten

抱歉，我不明白。如果我有一个空节点，它就不会绘制像素。但我仍希望它能绘制整个图像... - user559142

修改我的答案。或许现在有帮助。 - kasten

1

一个正方形是一个特殊的矩形，四叉树也适用于矩形。你只需要一个分割方法，为给定的矩形提供4个子矩形。

如果最上层的根节点是一个矩形，则只需将其宽度和高度除以2。

在像素的情况下，仅当根单元格的宽度和高度都是2的幂时才有意义。

因此，如果根单元格=2048*1024，则分割只需将宽度和高度都除以2。

- AlexWien

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MatrixPeckham · Accepted Answer

你可以将图像填充到相等的2的幂大小。虽然这样做可能会增加一些额外的内存需求，但增加的量不应该很大。

2x1的示例会被填充到标准的2x2并存储真实大小，或者使用填充节点的特殊值，以便恢复原始大小。