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

Question

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

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

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

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

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

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

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

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

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

如果有剩余的框，则递归地对由最后一个矩形诱导的所有三个剩余矩形重复该过程，它们分别是右下角和右下角：

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

score 1 · Accepted Answer

由于您不是在寻找最小平方数，因此我建议您使用一种仍然保持算法简单的折衷方案。

最佳解决方案取决于您的数据，但一种简单的替代方法是仅沿一行收集框。IE：

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

将导致：

skip 2
draw 3
skip 3
draw 4
skip 1

这将减少对绘制框的调用次数，而无需任何缓存（即您可以即时构建您的框）。

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

score 0 · Accepted Answer

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

score 0 · Accepted Answer

我必须解决类似的问题，我的算法支持锯齿状数组，我已经对其进行了大量测试和评论，但它比 joel-in-gö 的建议慢： https ://stackoverflow.com/a/13802336

5 回答 5