反向矩形填料

Question

我有一个连接的形状,由放在一起的正方形组成,例如,取一个方形纸,沿着现有的线条绘制一条线,该线条在其开始处结束并且不会交叉.

现在的目标是找到一个算法(而不是强力),用尽可能少的非重叠矩形填充这个形状.

我正在寻找最佳解决方案.从图像中可以看出,天真贪婪的方法(采取最大的矩形)不起作用.

(最佳)

(贪婪)

我的场景是顶点缩减,但我确信还有其他用例.

注意:此问题似乎很基本,但我无法在其他地方找到解决方案.还有,这个问题NP难吗？

编辑:我刚刚意识到,在我的场景中,用尽可能少的非重叠三角形填充形状会产生更好的结果.

Answer 1

自从我提出最初的问题以来，我花了很多时间研究这个问题。对于第一个问题（用矩形最佳地填充形状），我在“最佳贪婪网格划分”标题下编写了解决方案：

实际上，其复杂性比对无孔多边形进行最佳三角剖分更好（更快）。最慢的部分是 Hopcroft-Karp 算法。

链接的博客文章中还讨论了将形状视为多边形。请注意，我也在考虑漏洞。