算法寻找最少矩形以覆盖一组矩形 [英] Algorithm for finding the fewest rectangles to cover a set of rectangles

问题描述

我有一组矩形，我想减少的设置，所以我有数量最少的矩形来描述同一地区原设定。如果可能的话，我想它也快，但我更关心的是获得矩形尽可能低的数量。我现在有一个方法，它工作的大部分时间。

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:

然而，在这种情况下，我的算法开始通过处理蓝色矩形。这扩大向下并拆分黄色矩形（正确）。但随后，当黄色矩形的其余部分进行处理，而不是向下扩展，它扩展了正确的第一和收回，这是previously分裂出去的部分。那么最后矩形被处理，它不能膨胀向右或向下，所以原来矩形集合在左边。我可以调整算法扩大下来，然后再正确的。这将解决这个情况，但它会导致同样的问题，这是翻转类似的情景。

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.

感谢您事先的任何帮助。

Thank you in advance for any help.

编辑：只是为了澄清，原来设置的矩形不重叠，不具备进行连接。而如果矩形的一个子集被连接，这完全覆盖他们的多边形可以有孔，它

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.)

大卫Eppstein的讨论在他2010年的调查文章的Graph-Theoretic解决方案计算几何问题的，他给在<一个一个很好的总结href="http://mathoverflow.net/questions/28303/split-polygon-into-minimum-amount-of-rectangles-and-triangles/28350#28350">this在mathoverflow.net 回答：

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.

下面是对这个令人钦佩的简短说明我的光泽，用图2从Eppstein的的文章。假设我们有一个直线形的多边形，可能带有孔

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.

查找在一个一般图形的最大独立集是一个NP完全问题，但在二部图，柯尼希定理的显示，它是等效于寻找最大匹配，其可在多项式时间内解决的问题，例如由 Hopcroft - 卡普算法。这里的最大匹配：

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屋！