如何将由小方块组成的区域划分为更大的矩形？

Question

我将去哪里寻找采用0或1的2d网格作为输入的算法，然后识别其中所有可能的非重叠矩形？

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

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

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

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

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

Answer 1

我已经做了类似的事情，用于使用OpenGL进行快速而肮脏的3D盒子体素可视化。

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

绘制矩形（如果已填充）。

如果有剩余的框，则递归重复上一个矩形（右边，右下角和右下角）引起的所有三个剩余矩形的过程：

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

查看 Dobb博士门户网站上的这篇文章，找到适合您情况的最大矩形。这是一个非常有效的算法的非常详细的讨论，我认为迭代地重复它可能会解决你的问题。

Answer 3

由于您没有寻找最小数量的方格，我建议使用折衷方案，这仍然可以使您的算法变得简单。

最佳解决方案取决于您的数据，但一个简单的替代方案是只收集一行的方框。即：

0 0 1 1 1 0 0 0 1 1 1 1 0

将导致：

skip 2
draw 3
skip 3
draw 4
skip 1

这将减少绘制框的调用次数而不需要缓存（即您可以动态构建框）。

如果你想创建更大的盒子，我会建议你回溯算法，你找到第一个1，并尝试在所有方向扩展框。构建一个框列表，并在使用它们时清除它们。

Answer 4

所以你正在寻找'ON'方块的矩形边界？
你想要内部还是外部？
即。边界必须只有“ON”方块，或者您是否希望矩形包含组中的所有“ON”方块？

Answer 5

我必须解决类似的问题，我的算法支持锯齿状数组，我经过严格的测试和评论，但它比joel-in-g＆＃246;的建议慢： https://stackoverflow.com/a/13802336