是否有任何算法可以近似具有n个非重叠矩形的给定多边形，从而给出最大覆盖范围？我的意思是，最大覆盖范围是矩形区域的总和最大化。矩形不一定等于大小。如何用n个矩形近似一个多边形？
我正在处理的多边形是凸面的。如果确切的解决方案很难/昂贵（我期待它），但也欢迎简单的良好启发式方法。
编辑我一直以为约计与多边形内部的矩形多边形的，但与矩形的解决方案并不完全内部的多边形也很好。如果是这样的话，该区域的最大化就是该区域的最小化。
编辑2我忘了提及这些矩形是正交矩形，即与轴对齐。
第一个想法，也许其他人可以改善它。
一种方法是为您的多边形创建（通常情况下为矩形）边界框。计算边界框的面积与多边形的面积之间的差值。如果差值足够小，就大功告成了，如果没有，继续......
鸿沟箱分成4个大小相等的长方形，2×2。找出哪些矩形完全位于多边形内部。计算多边形内和多边形内矩形的总面积之差。如果差值足够小，就大功告成了，如果再继续......每4个矩形进4子矩形......如果在任何阶段，你会发现一个长方形或者是内外完全或完全
鸿沟在多边形之外，您可以从矩形列表中将其删除，以便在下一次迭代中进行细分。
换句话说，使用一个quadtree划分包含您的多边形空间并发展到满足您的精度标准所必需的程度。
初期多边形自Q
删除多边形P
10。以P，A的下一个最长边，并转到5
11。从A向上投影出一个红色矩形。找到与P，B和C相交的2点： 
12。选择较长的（B）并最终确定绿色矩形
13。将其余数字（D，E和F）添加到Q
14。转到3
你能提供更多的信息吗？我想知道，你想获得什么信息（矩形数量，总面积总和，浪费空间的百分比）。此外，您还需要指定一些内容：您是否希望使用最少数量的矩形进行最大面积覆盖？因为有很多1mm^2的矩形，你可以近似该区域的相当好。如果是这样，这听起来像http://en.wikipedia.org/wiki/Multi-objective_optimization。也许你可以把你的问题投射到多背包问题上。 – Slomo
@Slomo：我会给出多边形和矩形的数量作为输入。够了吗？ – nimcap
好的，谢谢。基于此，Jens Schauder的第一个想法似乎是合理的。由于您只有凸多边形，最大的矩形将位于中心。所以你可以递归地找到剩余的下一个较小区域的最大矩形。您的递归将在您打开第n个矩形（输入）时结束。 – Slomo