我有一个由正方形组成的连接形状，例如，拿一张方格纸，沿着现有的线画一条线，这条线在它的开始处结束，并且不交叉。
现在的目标是找到一种算法（不是蛮力），用尽可能少的非重叠矩形填充这个形状。
我正在寻找最佳解决方案。从图像中可以看出，天真的贪心方法（取最大的矩形）不起作用。
（最佳）
（贪婪的）
我的场景是减少顶点，但我确信还有其他用例。
注意：这个问题似乎很基本，但我无法在其他地方找到解决方案。另外，这个问题是NP难的吗？
编辑：我刚刚意识到，在我的场景中，用尽可能少的非重叠三角形填充形状会产生更好的结果。