我正在寻找一种算法或alogirthms我可以采取非交叉的凹多边形，并找到分割多边形的最小边缘对齐矩形集 . 矩形可以重叠（优选最小） .
我正在考虑使用耳剪来找到最小三角形 . 我可以从这些三角形构建矩形 . 我想每个三角形都可以有一组矩形 . 然后我检查矩形并与其他共线矩形合并 . 我不知道这是不是一个好方法 .
我认为这个问题听起来有点主观，但我仍然认为有一种很好的方法可以用已知算法和一些启发式方法来解决这个问题 .
*编辑：更多的启发式，我可以预期轴对齐矩形，顺便说一句，是一个常见的出现 .
**编辑：我也可以预期凸角的零度小于90度 .
1 回答
公平的警告，我没有计算几何的背景，所以我基本上只是在做事情 . 这将是我对问题的初步处理方法 .
弄清楚多边形是否凸出 . 如果是这样，请用一个与边缘对齐的矩形覆盖它 . 要做到这一点，我会说只是尝试所有边缘，看看哪一个给出了面积最小的矩形 . 可能有更好的方法来确定使用哪个边缘，但同样，这个东西没有背景 .
如果多边形是凹的，如果它不在多边形的凸包上，我们将边称为“凹边” . 在多边形中找到凹边，并将其扩展以将多边形切割为两个或多个新的较小多边形 . 递归每个子多边形 .
如果多边形有足够的边缘，我认为穷举搜索是合理的，只需选择覆盖你的启发式最佳的匹配（最少的矩形，不在多边形内的最小空间量，重叠量，一些功能的以前的因素等）