是否有任何算法可以用 n 个不重叠的矩形来近似给定的多边形，从而提供最大的覆盖范围？我所说的最大覆盖范围是指矩形区域的总和最大化。矩形的大小不一定相等。
我处理的多边形是凸的。如果很难找到精确的解决方案/找到它的成本很高(我希望如此)，也欢迎使用简单的启发式方法。
编辑 我一直想用多边形内的矩形来近似多边形，但矩形不完全在多边形内的解决方案也很好。如果是这样的话，面积的最大化就变成了面积的最小化。
编辑 2 我忘了说这些矩形是正交矩形，即与轴对齐。
最佳答案
一种方法是为您的多边形创建一个(在一般情况下为矩形)边界框。计算边界框面积与多边形面积之差。如果差异足够小，你就完成了，如果不是，继续...
将盒子分成 4 个大小相等的矩形，2x2。找出这些矩形中的哪一个完全在多边形内。计算多边形内部矩形的总面积与多边形的总面积之差。如果差异足够小你就完成了，如果没有继续......
将 4 个矩形中的每一个分成 4 个子矩形...如果在任何阶段您发现一个矩形完全位于多边形内部或完全位于多边形外部，您可以将其从矩形列表中删除以在下一次迭代中分割.
换句话说，使用 quadtree划分包含多边形的空间，并将其扩展到满足精度标准所需的范围。
关于algorithm - 如何用 n 个矩形近似多边形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10916040/