用于划分的基于细胞的形状成矩形的最小量的最佳方式 [英] Optimal way for partitioning a cell based shape into a minimal amount of rectangles

问题描述

假设一个布尔数组，如：

Assume a boolean array like:

1111
1111
1110
1111
1001

现在你需要找到安排任何尺寸的最小矩形来实现这种形状的方法。因此，举例来说，你会发现这样的：

Now you need to find the way of arranging the least rectangles of any size to achieve this shape. So, for example, you'd find this:

+-++
| |+
| |
+-++
+  +

在哪里+是一个角的矩形和|， - 矩形边框

Where + is a corner of a rectangle and |, - borders of a rectangle.

我想过做开始与尽可能大的矩形，检查是否有数组中它可以被放置，其中包括的矩形每个数组元素是真实的任何地方。如果这样的地方存在，矩形将被添加到列表。然后我们在阵列左侧空间检查是否有另一个位置把该矩形中，然后减小矩形的大小，并与剩余的空间重复该过程，直至大小为0

What I thought about doing is starting with the largest possible rectangle, checking if there is any place in the array it can be placed, where every array element covered by the rectangle is true. If such a place exists, the rectangle would be added to a list. Afterwards we check in the left space of the array if there is another spot to put the rectangle in, then decrease the size of the rectangle and repeat the process with the remaining space until the size is 0.

这应该产生良好的结果，因为我们总是先从大的矩形，我们可以 - 当然 - 少用，这反过来我们使用少量的矩形的手段

This should yield good results since we always start with large rectangles, that we can — of course — use less of, which in turn means we are using small amounts of rectangles.

然而，这仅仅是一个概念，我想到了，但还没有付诸实施。它似乎很低效的，所以我想知道是否有任何已知的快速算法来实现这一目标？

However, this is just a concept I've thought of and have not yet put into practice. It seems quite inefficient, so I was wondering if there were any known quick algorithms to achieve this?

推荐答案

我真的被困在思考这个问题，让我进去看了公布的研究。事实证明，如果你想要一个最佳的解决方案，这是（如果你想成为技术NP难）一pretty的疑难问题解决效率。退房的论文一种算法被覆多边形与矩形信息与控制中，如果你不想把我的话。这里有很多有趣的想法在纸上，作者给出的算法寻找最佳的覆盖物。显然，这不会在多项式时间内运行，但它可能是足够快的问题实例你的尺寸。你甚至想尝试一个更简单的疲惫技术首先，看它是否适合你所感兴趣的问题。

I really got stuck thinking about this problem, so I looked into the published research. It turns out that if you want an optimal solution, this is a pretty hard problem to solve efficiently (NP-Hard if you want to be technical). Check out the paper "An Algorithm for Covering Polygons with Rectangles" in Information and Control if you don't want to take my word for it. There are a lot of interesting ideas in the paper, and the authors give an algorithm for finding optimal coverings. Obviously it doesn't run in polynomial time, but it may be fast enough for problem instances your size. You might even want to try an even simpler exhaustion technique first to see if it works for the problems you're interested in.

下面是我原来的建议，我将不再担保是最优的，但一个反例也没有ocurred给我呢：

Here's my original suggestion, which I will no longer vouch for being optimal, though a counterexample hasn't ocurred to me yet:

开始用矩形空集合称为R.对于每个位置（i，j）条中的阵列值为1，找到最宽的矩形1秒，它包含（I，J）的W和添加然后延伸W¯¯到最大高度的矩形m种将包含全1。添加M向集合R如果它不是present。完成后，使通过R和删除被完全覆盖在研发其他矩形的任何矩形。

Start with an empty collection of rectangles called R. For each position (i,j) in your array with a value of 1, find the widest rectangle W of 1s that contains (i,j), and add then extend W to the rectangle M of maximum height that will contain all 1s. Add M to the collection R if it is not present. After you finish, make a pass over R and remove any rectangle that is completely covered by the other rectangles in R.

这篇关于用于划分的基于细胞的形状成矩形的最小量的最佳方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！