我很想用最小的矩形覆盖一个简单的凹多边形。我的矩形可以是任意长度，但它们具有最大宽度，并且多边形永远不会有锐角。
我想过尝试将我的凹多边形分解为三角形，这些三角形生成一组最小重叠的矩形，最小限度地限制每个三角形，然后将这些矩形合并成更大的矩形。但是，我认为这不适用于多边形边缘的小凹口。由这些凹口上的反射顶点创建的三角形将创建错误的矩形。我正在寻找可以跨越/忽略缺口的矩形。
我对计算几何一无所知，所以我不确定如何开始提出这个问题。
我发现了其他类似的帖子，但不是我需要的：
一些例子：黑色是输入。红色是可接受的输出。
另一个例子：首选第二个输出。但是，生成两个输出并使用另一个因素来确定偏好可能是必要的，而不是该算法的责任。
模仿曲线的多边形极为罕见。在这种情况下，矩形的大部分区域都被浪费了。但是，这是可以接受的，因为每个矩形都遵循最大宽度约束。
另外，我发现这篇文章接近我需要的：
- 用Paul Iacob、Daniela Marinescu 和 Cristina Luca的长方形作品覆盖
也许更好的问题是“如何识别凹多边形的矩形部分？”
这是显示所需实现的图像：
绿色是实际的材料使用量。红色矩形是布局。蓝色是整个多边形的 MBR。我想我应该尝试获取小 MBR 并填充它们。左上角终止于多边形中间的 2-3 个绿色矩形很昂贵。这就是我想要最小化的。绿色矩形有最小和最大宽度和高度，但我可以使用尽可能多的行和列来覆盖一个区域。同样，我必须尽量减少不跨越输入的矩形数量。我还可以修改绿色矩形的形状以适应也非常昂贵的小地方。换句话说，让尽可能多的矩形尽可能多地跨越是理想的。
也许我应该简单地尝试识别这样的矩形区域：
或者，也许更好的方法是使用最大内接矩形而不是 MBR。我可以使用矩形不断地削减我的多边形，直到留下最大内接矩形不与原始多边形共享边的区域。其余区域必须采用启发式方法进行处理。
我一直在与我公司的工程和制造部门合作，以进一步澄清这个问题。我仍在等待确认，但我现在认为返回最大内接矩形集的算法会起作用。虽然它没有完全覆盖形状，但它会优先考虑正交区域，同时将非正交区域留给一些启发式方法。唯一的技巧是最大化那些正交区域。