algorithm - 反矩形包装

Question

我有一个连接的形状，由放在一起的正方形组成，例如拿一张方格纸，沿着现有的线画一条线，这条线结束于它的起点并且不与自己交叉。

现在的目标是找到一种算法(不是蛮力)用尽可能少的、不重叠的矩形填充这个形状。

我正在寻找最佳解决方案。从图像中可以看出，朴素的贪婪方法(取最大的矩形)不起作用。

(最佳)

(贪心)

我的场景是减少顶点，但我确信还有其他用例。

注意:这个问题看起来很基本，但我无法在其他地方找到解决方案。另外，这个问题是 NP-hard 问题吗？

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

Answer 1

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

http://blackflux.wordpress.com/2014/03/01/meshing-in-voxel-engines-part-2/

复杂性实际上比对没有孔的多边形进行最佳三角剖分更好(更快)。最慢的部分是Hopcroft-Karp算法。

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