寻找最少矩形以覆盖一组矩形而不重叠的算法 [英] 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屋！
