首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >寻找覆盖一组无重叠矩形的最少矩形的算法

寻找覆盖一组无重叠矩形的最少矩形的算法
EN

Stack Overflow用户
提问于 2011-05-07 13:21:13
回答 3查看 21.9K关注 0票数 80

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

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

对于这组三个矩形,正确的解决方案应该是两个矩形,如下所示:

然而,在本例中,我的算法从处理蓝色矩形开始。这将向下展开并(正确地)拆分黄色矩形。但是,当处理完黄色矩形的其余部分时,它不会向下扩展,而是直接首先扩展,并取回之前拆分出来的部分。然后最后一个矩形被处理,它不能向右或向下扩展,所以原始的矩形集是左边的。我可以调整算法,先向下扩展,然后向右扩展。这可以解决这种情况,但在翻转的类似场景中也会导致相同的问题。

编辑:只是为了澄清一下,原始的一组矩形不重叠,也不需要连接。如果矩形的一个子集是连通的,则完全覆盖它们的多边形中可以有洞。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2011-07-09 20:15:37

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

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

的想法是找到以两个凹顶点为端点的不相交的轴平行对角线的最大数量,沿着这些顶点拆分,然后为每个剩余的凹顶点形成一个拆分。为了求出不相交的轴平行对角线的最大个数,构造了对角线的交图,该图是二部图,利用图匹配技术可以在多项式时间内找到它的最大独立集。

下面是我使用Eppstein文章中的图2对这段令人赞叹的简洁描述的说明。假设我们有一个直角多边形,可能有洞。

当多边形被剖分成矩形时,每个凹顶点必须至少与剖分的一条边相交。因此,如果尽可能多的边做双重任务,也就是说,它们连接两个凹顶点,我们就可以得到最小的剖分。

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

(如果没有轴平行对角线,则剖分是微不足道的-只需从每个凹顶点进行切割即可。或者,如果轴平行对角线之间没有交点,那么我们将使用所有这些对角线,并从每个剩余的凹顶点进行切割。否则,请继续阅读。)

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

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

在一般图中寻找最大独立集是一个NP-hard问题,但在二部图的特殊情况下,König’s theorem证明了它等价于寻找最大匹配的问题,该问题可以在多项式时间内解决,例如用Hopcroft–Karp algorithm。一个给定的图可以有几个最大匹配,但它们中的任何一个都可以,因为它们都具有相同的大小。在示例中,所有最大匹配都有三对顶点,例如{(2,3),(6,3),(7,8)}:

(此图中的其他最大匹配数包括{(1,113),(2,05),(7,08)};{(2,04),(3,06),(5,07)};以及{(1,03),(2,04),(7,08)}。)

要获得与相应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)∪(R∩∩)= {2,3,7},如下红色所示,最大独立集为绿色:

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

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

票数 136
EN

Stack Overflow用户

发布于 2021-03-31 23:09:18

感谢这本书,它对我真的很有帮助。

根据这两件事:

1.我真的很累。2.我是个糟糕的程序员。

我已经成功地遵循了这些步骤,并用许多Orthogons进行了测试,现在我得到了一组令人费解的矩形。

好的,但是现在我真的很难用它来计算矩形列表。

粗鲁的谈话或过程。

先谢谢你。

让-伊夫

票数 1
EN

Stack Overflow用户

发布于 2021-06-13 00:58:49

今天我找到了这个问题的O(N^5)解决方案,我将在这里分享它。

对于第一步,您需要找到一种方法来获得矩阵中任意矩形的和,复杂度为O(1)。这很容易做到。

现在,对于第二步,您需要了解动态编程。这个想法是存储一个矩形,并将其拆分成更小的片段。如果矩形为空,则可以返回0。如果已填满,则返回1。

有N^4个状态来存储矩形,加上每个状态的O(N)复杂度...所以你将得到一个O(N^5)算法。

这是我的代码。我想这会有帮助的。

输入很简单。N,M(矩阵的大小)之后,下面的N行将有1和0。示例:

代码语言:javascript
复制
4 9
010000010
111010111
101111101
000101000
代码语言:javascript
复制
#include <bits/stdc++.h>
#define MAX 51
int tab[MAX][MAX];
int N,M;
int sumed[MAX][MAX];
int t(int x,int y) {
    if(x<0||y<0)return 0;
    return sumed[x][y];
}
int subrec(int x1,int y1,int x2,int y2) {
    return t(x2,y2)-t(x2,y1-1)-t(x1-1,y2)+t(x1-1,y1-1);
}
int resp[MAX][MAX][MAX][MAX];
bool exist[MAX][MAX][MAX][MAX];
int dp(int x1,int y1,int x2,int y2) {
    if(exist[x1][y1][x2][y2])return resp[x1][y1][x2][y2];
    exist[x1][y1][x2][y2]=true;
    int soma = subrec(x1,y1,x2,y2);
    int area = (x2-x1+1)*(y2-y1+1);
    if(soma==area){return resp[x1][y1][x2][y2]=1;}
    if(!soma) {return 0;}
    int best = 1000;
    for(int i = x1;i!=x2;++i) {
        best = std::min(best,dp(x1,y1,i,y2)+dp(i+1,y1,x2,y2));
    }
    for(int i = y1;i!=y2;++i) {
        best = std::min(best,dp(x1,y1,x2,i)+dp(x1,i+1,x2,y2));
    }
    return resp[x1][y1][x2][y2]=best;
}
int main()
{
    std::cin >> N >> M;
    for(int i = 0; i != N;++i) {
        std::string s;
        std::cin >> s;
        for(int j = 0; j != M;++j) {
            if(s[j]=='1')tab[i][j]++;
        }
    }
    for(int i = 0; i != N;++i) {
        int val = 0;
        for(int j = 0; j != M;++j) {
            val += tab[i][j];
            sumed[i][j]=val;
            if(i)sumed[i][j]+=sumed[i-1][j];
        }
    }
    std::cout << dp(0,0,N-1,M-1) << std::endl;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5919298

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档