我有一组矩形，我想“减少”该组，以便用最少数量的矩形来描述与原始组相同的区域。如果可能的话，我希望它也能很快，但我更关心的是让矩形的数量尽可能少。我现在有一个在大多数情况下都有效的方法。
Currently, I start at the top-left most rectangle and see if I can expand it out right and down while keeping it a rectangle. I do that until it can't expand anymore, remove and split all intersecting rectangles, and add the expanded rectangle back in the list. Then I start the process again with the next top-left most rectangle, and so on. But in some cases, it doesn't work. For example:
With this set of three rectangles, the correct solution would end up with two rectangles, like this:
然而，在这种情况下，我的算法首先处理蓝色矩形。这会向下扩展并分割黄色矩形（正确）。但是，当黄色矩形的剩余部分被处理时，它不是向下扩展，而是首先向右扩展并收回之前被分割掉的部分。然后处理最后一个矩形，它不能向右或向下扩展，所以留下了原始的一组矩形。我可以调整算法，先向下扩展，然后向右扩展。这可以解决这个问题，但在类似的翻转场景中会导致同样的问题。
Edit:只是为了澄清，原始的矩形集不重叠，也不必连接。如果连接了矩形的子集，则完全覆盖它们的多边形可以在其中有孔。
尽管你的问题有标题，但我认为你实际上是在寻找最低限度解剖成直线多边形的矩形。 （杰森的链接大约是最少的covers由矩形组成，这是一个完全不同的问题。）
大卫·爱普斯坦 http://www.ics.uci.edu/~eppstein/在他 2010 年调查文章的第 3 节中讨论了这个问题计算几何问题的图论解决方案 http://arxiv.org/pdf/0908.3916v1，他在中给出了很好的总结mathoverflow.net 上的这个答案 https://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles/28350#28350:
这个想法是找到以两个凹顶点作为端点的不相交轴平行对角线的最大数量，沿着这些顶点分割，然后为每个剩余的凹顶点再形成一个分割。找出不相交的平行轴对角线的最大数量，形成对角线的交图；该图是二分图，因此可以通过图匹配技术在多项式时间内找到其最大独立集。
这是我对这个令人钦佩的简洁描述的注释，使用了 Eppstein 文章中的图 2。假设我们有一个直线多边形，可能有孔。
当多边形被分割成矩形时，每个凹顶点必须至少与分割的一条边相交。所以我们得到minimum如果尽可能多的这些边具有双重功能，即它们连接两个凹顶点，则可以进行解剖。
因此，让我们在完全包含在多边形内的两个凹顶点之间绘制与轴平行的对角线。 （“轴平行”在这里是指“水平或垂直”，并且多边形的对角线 http://en.wikipedia.org/wiki/Diagonal#Polygons是连接两个不相邻顶点的线。）我们希望在解剖中使用尽可能多的这些线，只要它们不相交。
（如果没有与轴平行的对角线，则解剖很简单 - 只需从每个凹顶点进行切割即可。或者，如果与轴平行的对角线之间没有交点，那么我们将全部使用它们，再加上从每个剩余的凹顶点进行切割.否则，请继续阅读。）
The 交集图 http://en.wikipedia.org/wiki/Intersection_graph一组线段的每个线段都有一个节点，如果线相交，则一条边连接两个节点。这是与轴平行的对角线的交集图：
It’s 两部分 http://en.wikipedia.org/wiki/Bipartite_graph一个部分为垂直对角线，另一部分为水平对角线。现在，我们要选择尽可能多的对角线，只要它们不相交。这对应于找到最大独立集 http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29在交集图中。
在一般图中找到最大独立集是一个 NP 难题，但在二分图的特殊情况下，柯尼希定理 http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29表明它等价于寻找最大匹配的问题，可以在多项式时间内解决，例如通过Hopcroft-Karp 算法 http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm。给定的图可以有多个最大匹配，但其中任何一个都可以，因为它们都具有相同的大小。在示例中，所有最大匹配都具有三对顶点，例如 {(2, 4), (6, 3), (7, 8)}：
（此图中的其他最大匹配包括 {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; 和 { (1, 3), (2, 4), (7, 8)}。)
从最大匹配得到对应的最小顶点覆盖 http://en.wikipedia.org/wiki/Vertex_cover，应用柯尼希定理的证明 https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)#Proof。在上面显示的匹配中，左边的集合是L= {1, 2, 6, 7}，正确的集合是R= {3, 4, 5, 8}，以及不匹配顶点的集合L is U= {1}。只有一条替代路径从U，即 1–3–6，因此交替路径中的顶点集合为Z= {1, 3, 6} 最小顶点覆盖为K = (L \ Z) ∪ (R ∩ Z) = {2, 3, 7}，如下图红色所示，最大独立集为绿色：
将其转化回解剖问题，这意味着我们可以在解剖中使用五个轴平行的对角线：
最后，从每个剩余的凹顶点进行切割以完成解剖：
