我有一个由方块组成的相连形状，例如拿一张方格纸，在现有线条上画一条线，使其结束于起点并且不交叉。
现在的目标是找到一种算法（非暴力），用尽可能少的不重叠矩形填充这个形状。
我正在寻找最优解。从图片中可以看出，贪心算法（选择最大的矩形）不起作用。
我的场景是顶点约简，但我确信还有其他用例。
注意：这个问题似乎很基础，但我无法在其他地方找到解决方案。此外，这个问题是否是NP-hard？
编辑：我刚意识到，在我的场景中，用尽可能少的不重叠三角形填充形状会得到更好的结果。
现在的目标是找到一种算法（非暴力），用尽可能少的不重叠矩形填充这个形状。
我正在寻找最优解。从图片中可以看出，贪心算法（选择最大的矩形）不起作用。
我的场景是顶点约简，但我确信还有其他用例。
注意：这个问题似乎很基础，但我无法在其他地方找到解决方案。此外，这个问题是否是NP-hard？
编辑：我刚意识到，在我的场景中，用尽可能少的不重叠三角形填充形状会得到更好的结果。