找到最少的矩形来覆盖一组没有重叠的矩形的算法 [英] Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
问题描述
我有一组矩形，我想减少这个集合，所以我有最少数量的矩形来描述与原始集合相同的区域。如果可能的话，我希望它也很快，但我更关心的是尽量减少矩形的数量。我现在有一种方法可以在大多数情况下使用。
目前，我从最左上角的矩形开始，看看我是否可以正确地将其展开保持一个矩形。我这样做直到它不能再展开为止，删除并拆分所有相交的矩形，并将展开的矩形添加回列表中。然后我再次用下一个最左上角的矩形开始该过程，依此类推。但在某些情况下，它不起作用。例如：
使用这组三个矩形，正确的解决方案将以两个矩形结束，如下所示：
编辑：只是为了澄清，原始的一组矩形不重叠并且不必连接。如果连接了矩形的子集，完全覆盖它们的多边形可能会有空洞。
你的问题，我想你实际上是在寻找最小的解剖成直线多边形的矩形。 （Jason的链接是关于最小的封面的矩形，这是一个非常不同的问题。）
$ b
具有用于每个线段的节点，并且如果这些线交叉，则边缘将连接两个节点。以下是轴线平行对角线的交点图： b
$ b
这是双方 a>，一部分垂直对角线，另一部分水平对角线。现在，只要不相交，我们希望尽可能多地选择对角线。这对应于在交集图中查找最大独立集。
在一般图中找到最大独立集合是一个NP完全问题，但是在二分图的特殊情况下， Hopcroft-Karp算法。这里是最大的匹配：
以下是相应的最小顶点覆盖
a>（红色）和最大独立集（绿色）：
将这转换回解剖问题，这意味着我们可以在解剖中使用五个轴平行对角线：
最后，从每个剩余的凹角切下来完成解剖：
I have a set of rectangles and I would like to "reduce" the set so I have the fewest number of rectangles to describe the same area as the original set. If possible, I would like it to also be fast, but I am more concerned with getting the number of rectangles as low as possible. I have an approach now which works most of the time.
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:
However, in this case, my algorithm starts by processing the blue rectangle. This expand downwards and splits the yellow rectangle (correctly). But then when the remainder of the yellow rectangle is processed, instead of expanding downwards, it expands right first and takes back the portion that was previously split off. Then the last rectangle is processed and it can't expand right or down, so the original set of rectangles is left. I could tweak the algorithm to expand down first and then right. That would fix this case, but it would cause the same problem in a similar scenario that was flipped.
Edit: Just to clarify, the original set of rectangles do not overlap and do not have to be connected. And if a subset of rectangles are connected, the polygon which completely covers them can have holes in it.
Despite the title to your question, I think you're actually looking for the minimum dissection into rectangles of a rectilinear polygon. (Jason's links are about minimum covers by rectangles, which is quite a different problem.)
David Eppstein discusses this problem in section 3 of his 2010 survey article Graph-Theoretic Solutions to Computational Geometry Problems, and he gives a nice summary in 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.
Here's my gloss on this admirably terse description, using figure 2 from Eppstein's article. Suppose we have a rectilinear polygon, possibly with holes.
When the polygon is dissected into rectangles, each of the concave vertices is going to be met by an edge of the dissection. So we get the minimum dissection if as many of these edges as possible do double-duty, that is, they connect two of the concave vertices.
So let's draw all the axis-parallel diagonals between two concave vertices (a diagonal of a polygon is a line connecting two non-adjacent vertices). We are going to want to use as many of these lines as possible in the dissection.
The intersection graph of a set of line segments has a node for every line segment, and an edge joins two nodes if the lines cross. Here's the intersection graph for the axis-parallel diagonals:
It's bipartite with the vertical diagonals in one part, and the horizontal diagonals in the other part. Now, we want to pick as many of the diagonals as possible as long as they don't intersect. This corresponds to finding the maximum independent set in the intersection graph.
Finding the maximum independent set in a general graph is an NP-complete problem, but in the special case of a bipartite graph, König's theorem shows that it's equivalent to the problem of finding a maximum matching, which can be solved in polynomial time, for example by the Hopcroft–Karp algorithm. Here's the maximum matching:
And here are the corresponding minimum vertex cover (red) and maximum independent set (green):
Translating this back into the dissection problem, this means that we can use five axis-parallel diagonals in the dissection:
Finally, make a cut from each remaining concave corner to complete the dissection:
这篇关于找到最少的矩形来覆盖一组没有重叠的矩形的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
