寻找最少矩形覆盖一组矩形而不重叠的算法 [英] Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
问题描述
我有一组矩形，我想减少"该组，因此我用最少的矩形来描述与原始组相同的区域.如果可能的话，我希望它也很快，但我更关心的是尽可能减少矩形的数量.我现在有一种在大多数情况下都有效的方法.
目前，我从最左上角的矩形开始，看看是否可以在保持矩形的同时向右和向下展开它.我这样做直到它不能再扩展，删除并拆分所有相交的矩形，然后将扩展的矩形添加回列表中.然后我从左上角的下一个矩形再次开始该过程，依此类推.但在某些情况下，它不起作用.例如:
对于这组三个矩形，正确的解决方案最终会得到两个矩形，如下所示:
然而，在这种情况下，我的算法首先处理蓝色矩形.这向下扩展并拆分黄色矩形(正确).但是当黄色矩形的其余部分被处理时，它不是向下扩展，而是首先向右扩展并收回之前被分割的部分.然后最后一个矩形被处理，它不能向右或向下扩展，所以原始的矩形集是左边的.我可以调整算法先向下扩展然后向右扩展.这会解决这个问题，但它会在类似的场景中导致同样的问题.
只是为了澄清，原始矩形集不重叠，也不必连接.如果矩形的子集相连，则完全覆盖它们的多边形中可能有孔.
尽管您的问题标题如此，但我认为您实际上是在寻找最小解剖成直线多边形的矩形.(Jason 的链接是关于矩形的最小覆盖，这是一个完全不同的问题.)
是连接两个不相邻顶点的线.)我们希望在解剖中尽可能多地使用这些线，只要它们不相交即可.
(如果没有平行轴的对角线，解剖是微不足道的 - 只需从每个凹顶点切割.或者如果轴平行的对角线之间没有交点，那么我们使用它们，加上每个切割剩余的凹顶点.否则，继续阅读.)
一组线段的，其中一部分是垂直对角线，另一部分是水平对角线.现在，我们希望选择尽可能多的对角线，只要它们不相交.这对应于在交集图中找到，应用柯尼希定理的证明.在上面显示的匹配中，左边的集合是 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}，下图红色表示，绿色表示最大独立集:
将其转换回解剖问题，这意味着我们可以在解剖中使用五个平行轴的对角线:
最后，对每个剩余的凹顶点进行切割以完成解剖:
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 must be met by at least one 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 the axis-parallel diagonals between two concave vertices that are contained entirely within the polygon. (‘Axis-parallel’ means ‘horizontal or vertical’ here, and a diagonal of a polygon is a line connecting two non-adjacent vertices.) We want to use as many of these lines as possible in the dissection as long as they don’t intersect.
(If there are no axis-parallel diagonals, the dissection is trivial—just make a cut from each concave vertex. Or if there are no intersections between the axis-parallel diagonals then we use them all, plus a cut from each remaining concave vertex. Otherwise, read on.)
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-hard 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. A given graph can have several maximum matchings, but any of them will do, as they all have the same size. In the example, all the maximum matchings have three pairs of vertices, for example {(2, 4), (6, 3), (7, 8)}:
(Other maximum matchings in this graph include {(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; and {(1, 3), (2, 4), (7, 8)}.)
To get from a maximum matching to the corresponding minimum vertex cover, apply the proof of König’s theorem. In the matching shown above, the left set is L = {1, 2, 6, 7}, the right set is R = {3, 4, 5, 8}, and the set of unmatched vertices in L is U = {1}. There is only one alternating path starting in U, namely 1–3–6, so the set of vertices in alternating paths is Z = {1, 3, 6} and the minimum vertex cover is thus K = (L Z) ∪ (R ∩ Z) = {2, 3, 7}, shown in red below, with the maximum independent set in 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 vertex to complete the dissection:
这篇关于寻找最少矩形覆盖一组矩形而不重叠的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
