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

Question

我有一组矩形,我想"减少"这个集合,所以我有最少的矩形来描述与原始集合相同的区域.如果可能的话,我希望它也快,但我更关心的是尽可能减少矩形的数量.我现在有一种方法,大部分时间都可以使用.

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

使用这组三个矩形,正确的解决方案最终会有两个矩形,如下所示:

但是,在这种情况下,我的算法从处理蓝色矩形开始.这会向下扩展并分割黄色矩形(正确).但是当处理黄色矩形的剩余部分时,它不是向下扩展,而是首先向右扩展并收回先前分离的部分.然后处理最后一个矩形,它不能向右或向下扩展,因此保留原始的矩形集.我可以调整算法,先向下扩展然后向右扩展.这将解决这种情况,但它会在翻转的类似场景中导致同样的问题.

编辑:只是为了澄清,原始的矩形集不重叠,不必连接.如果连接了矩形的子集,则完全覆盖它们的多边形可以在其中具有孔.

Answer 1

尽管问题的标题,我认为你实际上正在寻找直线多边形的矩形的最小解剖.(Jason的链接是关于矩形的最小覆盖,这是一个完全不同的问题.)

David Eppstein在2010年调查文章Graph-Theoretic Solutions to Computational Geometry Problems的第3部分讨论了这个问题,他在mathoverflow.net的这个答案中给出了一个很好的总结:

我们的想法是找到具有两个凹顶点作为端点的不相交的轴平行对角线的最大数量,沿着它们分开,然后为每个剩余的凹顶点形成一个更多的分割.要找到不相交的轴平行对角线的最大数量,请形成对角线的交点图; 这个图是二分的,因此它的最大独立集可以通过图匹配技术在多项式时间中找到.

这是我对Eppstein的文章中图2的令人钦佩的简洁描述的光泽.假设我们有一个直线多边形,可能有孔.

当多边形被解剖成矩形时,每个凹顶点必须被解剖的至少一个边缘满足.因此,如果尽可能多的这些边做双重任务,即它们连接两个凹顶点,我们得到最小的解剖.

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

(如果没有轴平行的对角线,解剖是微不足道的 - 只需从每个凹顶点切割.或者如果在轴平行对角线之间没有交叉点,那么我们全部使用它们,加上每个剩余凹顶点的切口.否则,请继续阅读.)

一组线段的交叉图具有每个线段的节点,并且如果线交叉,则边连接两个节点.这是轴平行对角线的交点图:

它是二部分,一部分是垂直对角线,另一部分是水平对角线.现在,我们希望尽可能多地选择对角线,只要它们不相交即可.这对应于在交叉图中找到最大独立集.

在一般图中找到最大独立集是NP难问题,但在二分图的特殊情况下,König定理表明它等于找到最大匹配的问题,可以在多项式时间内求解,例如Hopcroft-Karp算法.给定的图形可以有几个最大匹配,但它们中的任何一个都可以,因为它们都具有相同的大小.在该示例中,所有最大匹配都具有三对顶点,例如{(2,4),(6,3),(7,8)}:

(此图中的其他最大匹配项包括{(1,3),(2,5),(7,8)}; {(2,4),(3,6),(5,7)};以及{ (1,3),(2,4),(7,8)}.)

要从最大匹配到相应的最小顶点覆盖,请应用König定理的证明.在上面显示的匹配中,左集是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  ∩  ž)= {2,3,7}在下文显示为红色,在绿色的最大独立集:

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

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