geometry - 如何将一个由小正方形组成的区域划分为更大的矩形？

Question

我会去哪里寻找将 0 或 1 的二维值网格作为输入然后识别其中所有可能的非重叠矩形的算法？

在更实际的解释中:我正在绘制一个由多个正方形表示的网格，我希望找到一种方法将尽可能多的相邻正方形组合成矩形，以减少骑自行车所花费的时间每个正方形并绘制它。

不需要最高效率，速度更重要。

附录:显然我正在寻找的似乎是一种称为 Tesselation 的技术。现在我只需要为这个特定案例找到一个很好的描述。

附录 2:“1”方格的边界将是不规则的，在某些情况下甚至不相连，因为“1”方格的分布将是完全随机的。我需要识别这些不规则的形状并将其分成规则的矩形。

正确答案:为了在速度和效率之间获得最佳平衡，最好使用网格数据填充四叉树，每个节点的状态值为空/部分填充/填充。

Answer 1

我已经用 OpenGL 对 3d 框的快速和肮脏的体素可视化做了类似的事情。

我从左上角的框开始并存储空/填充标志。然后我尝试将矩形向右扩展，直到我碰到一个带有不同标志的框。我在向下的方向上做了同样的事情。

绘制矩形，如果它被填充。

如果还有剩余的框，则对由最后一个矩形引出的所有三个剩余矩形(右、下和右下)递归重复该过程:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333