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 (这是为了覆盖多边形,所以这是一个比你在这里提出的更一般的情况)。

凸直线多边形的最佳矩形覆盖 (这是一个更符合您的具体问题的线)

你也可以在这里参考这个主题的更多论文的参考书目。