找到最少的矩形以覆盖一组矩形而不重叠的算法

Question

我有一组矩形，我想“减少”这组，这样我就可以使用最少数量的矩形来描述与原始组相同的区域。如果可能的话，我希望它也快，但我更关心的是尽可能减少矩形的数量。我现在有一种在大多数情况下都有效的方法。

目前，我从最左上角的矩形开始，看看能否在保持矩形不变的情况下向右和向下扩展它。我这样做直到它不能再扩展，删除并拆分所有相交的矩形，然后将扩展的矩形添加回列表中。然后我用下一个最左上角的矩形再次开始这个过程，依此类推。但在某些情况下，它不起作用。例如:

对于这组三个矩形，正确的解决方案将以两个矩形结束，如下所示:

但是，在这种情况下，我的算法从处理蓝色矩形开始。这会向下扩展并拆分黄色矩形(正确)。但是当黄色矩形的剩余部分被处理时，它不是向下扩展，而是先向右扩展并收回之前拆分的部分。然后处理完最后一个矩形，不能向右扩展也不能向下扩展，所以就剩下原来的一组矩形。我可以调整算法先向下扩展然后向右扩展。这会解决这个问题，但它会在翻转的类似场景中导致同样的问题。

编辑:澄清一下，原来的矩形集不重叠，也不必连接。如果矩形的子集相连，则完全覆盖它们的多边形可能会有洞。

Answer 1

尽管您的问题标题如此，但我认为您实际上是在寻找直线多边形矩形的最小剖分。 (Jason 的链接是关于矩形的最小覆盖，这是一个完全不同的问题。)

David Eppstein在他 2010 年调查文章的第 3 节中讨论了这个问题 Graph-Theoretic Solutions to Computational Geometry Problems ，他在 this answer on mathoverflow.net 中给出了很好的总结:

The idea is to find the maximum number of disjoint axis-parallel diagonals that have two concave vertices as endpoints, split along those, and then form one more split for each remaining concave vertex. To find the maximum number of disjoint axis-parallel diagonals, form the intersection graph of the diagonals; this graph is bipartite so its maximum independent set can be found in polynomial time by graph matching techniques.

以下是我对这个令人赞叹的简洁描述的注释，使用的是 Eppstein 文章中的图 2。假设我们有一个直线多边形，可能有孔。

当多边形被分割成矩形时，每个凹顶点必须与分割的至少一条边相交。因此，如果尽可能多的这些边执行双重任务，即它们连接两个凹顶点，我们将得到最小解剖。

因此，让我们在完全包含在多边形内的两个凹顶点之间绘制轴平行对角线。 (“轴平行”在这里表示“水平或垂直”，diagonal of a polygon 是连接两个不相邻顶点的线。)我们希望在解剖中尽可能多地使用这些线，只要它们不t相交。

(如果没有轴平行对角线，剖分很简单——只需从每个凹顶点切开。或者如果轴平行对角线之间没有交点，那么我们将全部使用它们，再加上每个凹顶点的切开剩下的凹顶点。否则，请继续阅读。)

intersection graph一组线段的每个线段都有一个节点，如果线交叉，则边连接两个节点。这是轴平行对角线的交点图:

是 bipartite一部分是垂直对角线，另一部分是水平对角线。现在，我们要选择尽可能多的对角线，只要它们不相交即可。这对应于查找 maximum independent set在交叉图中。

在一般图中寻找最大独立集是一个 NP-hard 问题，但在二部图的特殊情况下，König’s theorem表明它等同于寻找最大匹配的问题，可以在多项式时间内解决，例如 Hopcroft–Karp 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)}.)

从一个最大匹配得到对应的minimum vertex cover , 应用 proof of König’s theorem .在上面显示的匹配中，左边的集合是 L = {1, 2, 6, 7}，右边的集合是 R = {3, 4, 5, 8 }，并且 L 中的不匹配顶点集是 U = {1}。在 U 中只有一条交替路径，即 1–3–6，因此交替路径中的顶点集为 Z = {1, 3, 6} 并且因此，最小顶点覆盖为 K = (L\Z) ∪ (R ∩ Z) = {2, 3, 7}，如下图红色所示，最大独立集为绿色:

将其转化回解剖问题，这意味着我们可以在解剖中使用五个轴平行的对角线:

最后，从每个剩余的凹顶点进行切割以完成解剖: