find最less的矩形来覆盖一组没有重叠的矩形的algorithm
我有一组矩形，我想“减less”设置，所以我有最less数量的矩形来描述与原始设置相同的区域。 如果可能的话，我希望它也快，但是我更关心的是尽量减less矩形的数量。 我现在有一个大部分时间都在使用的方法。
目前，我从最左上angular的矩形开始，看看是否可以在保持矩形的同时将它向右和向下展开。 我这样做，直到它不能再展开，删除和拆分所有相交的矩形，并将扩展的矩形添加到列表中。 然后我再次用下一个最左上angular的矩形开始这个过程，依此类推。 但在某些情况下，这是行不通的。 例如： 
有了这三个矩形的设置，正确的解决scheme将最终有两个矩形，如下所示： 
但是，在这种情况下，我的algorithm从处理蓝色矩形开始。 这向下扩展并拆分黄色矩形（正确）。 但是，当黄色矩形的其余部分被处理时，不是向下扩展，而是先扩展，然后收回之前分割的部分。 然后最后一个矩形被处理，它不能向右或向下扩展，所以原来的一组矩形被留下。 我可以调整algorithm先下拉，然后右下。 这可以解决这个问题，但是在类似的情况下会导致同样的问题。
编辑：只是为了澄清，原来的一组矩形不重叠，不必连接。 如果连接了矩形的一个子集，完全覆盖它们的多边形可以在其中有孔。
尽pipe你的问题的标题，我认为你实际上正在寻找最小解剖矩形的直线多边形。 （Jason的链接是关于矩形的最小覆盖 ，这是一个相当不同的问题。）
David Eppstein在2010年调查文章“ 计算几何问题的图论 – 理论解决scheme”第3部分讨论了这个问题，他在mathoverflow.net的这个答案中给出了一个很好的总结：
这个想法是find有两个凹顶点作为端点的不相交的轴 – 平行对angular线的最大数目，沿这些分割，然后为每个剩余的凹顶点形成一个更多的分割。 为了find不相交的轴平行对angular线的最大数目，形成对angular线的相交图; 这个图是二分的，所以它的最大独立集可以通过图匹配技术在多项式时间中find。
这是我对这个非常简洁的描述的光泽，使用Eppstein的文章中的图2。 假设我们有一个直线多边形，可能带有孔。
当多边形被分割成矩形时，每个凹形顶点将被解剖的边缘所满足。 因此，如果尽可能多的这些边做双重任务，也就是说，他们连接两个凹顶点，我们得到最小的解剖。
因此，让我们绘制两个凹顶点之间的所有轴平行对angular线（ 多边形的对angular线是连接两个不相邻顶点的线）。 我们打算在解剖中尽可能多地使用这些线条。
一组线段的交集图对于每个线段都有一个节点，如果这些线交叉，则一条边将两个节点连接起来。 以下是轴平行对angular线的交点图：
一部分是垂直对angular线，另一部分是水平对angular线。 现在，只要不相交，我们就要尽可能多地select对angular线。 这对应于在交集图中find最大独立集合 。
在一般图中find最大独立集是一个NP完全问题，但是在二部图的特殊情况下， 柯尼希定理表明它等价于find最大匹配问题，这个问题可以用多项式时间求解，例如Hopcroft-Karpalgorithm 。 这是最大的匹配：
这里是相应的最小顶点覆盖 （红色）和最大独立设置（绿色）：
将其转换回解剖问题，这意味着我们可以在解剖中使用五个轴平行对angular线：
最后，从每个剩余的凹angular切割完成解剖：
以下是一些讨论解决这个问题的学术论文。
用于最小矩形覆盖的线性时间近似algorithm （这是为了覆盖多边形，所以这是一个比你在这里提出的更一般的情况）。
凸直线多边形的最佳矩形覆盖 （这是一个更符合您的具体问题的线）
你也可以在这里参考这个主题的更多论文的参考书目。
