介绍

（译者注：略）

内容

（译者注：略）

安装

（译者注：略）

简单的解决方案

这有几个简单的方案讲述如何打包多个矩形到一个封闭的矩形中：

l 你可以将所有矩形在水平方向上一字排开，就像这样：

这很简单也很快，并且可以在所有矩形高度一致时表现的很好。

l 或者你可以在水平方向上排列，就像这样：

这依旧简单快捷，并且当所有矩形宽度一致时表现良好。

但是，这些方案在这些矩阵拥有不同的宽度和高度时留下大量被浪费的空间。这很烦人。所以接下来我们将关注在打包不同宽度和高度矩形时将这种浪费最小化，当然也要尽可能的快和简单。

基本算法

打包多个矩形到尽可能小的封闭矩形的基本算法在Richard E. Korf的文章有有被描述：Optimal Rectangle Packing: Initial Results。

1.根据高度对矩形进行排序，最高的排第一。

2.闭合矩形初始设置为：高度为最高矩形的高度，宽度无限大。

3.将矩形一个个的放入封闭矩形中，由最高的矩形开始，到最矮的矩形结束。放置每个矩形时尽可能靠左。如果有多个左边位置，使用最高的那个（If there are several left most locations, use the highest one ）。比如：

a) 

b) 

c) 

d) 

e) 

4.让闭合矩形的宽度等于弄好的所有矩形的总宽度。即：将闭合矩形的右边缘向左移动，直到接触到最右边矩形的右边缘。这样的话，闭合矩形宽度正合适。

5.你已经将所有矩形放置在闭合矩形内了吗？如果这样的话：

l 如果你得到的这个闭合矩形是目前最小的且“成功”的，将它保存起来。

l 试着宽度减一来获取更小的闭合区域。

6.然而，如果你没有全部将矩形放置在闭合矩形内，很显然闭合矩形小了。如果这样的话，将高度加一。（译者注：就这样重复执行放置矩形到闭合矩形内，直到得到一个原始最佳宽度减一×原始高度不断加一加到能将所有矩形都放入这个新闭合矩形内，其实并不是笨笨的加一，往下看，改进基本算法部分有提到这步具体做法）请注意，减宽度加高度实际上意味着我们将闭合矩形的范围从矮宽到高瘦。比如，当宽度被减少、高度被增加几次后，你可能会得到如下的序列：

a) 

b) 

c) 

d) 

e) 

7.如果你得到的闭合矩形的总面积（宽×高）比所有将放入其中的矩形的面积之和还要小，那这明显不是一个可行的闭合矩形。高度增加一直到你得到一个可行的闭合矩形。然后进入到下一步。

8.如果你获得的这个闭合矩形比迄今为止最好的闭合矩形要大，那么对它进行测试并无意义。宽度减一然后重复第七步来确保不是小了，否则进入下一步。

9.如果你的新的闭合区域比最宽的矩形要窄，你就可以停下了，并且汇报你得到的最佳闭合矩形。这是因为我们这个算法从不会增加闭合矩形的宽度，并且如果最宽矩形都放不下，这明显不需要再测试这个闭合矩形了。（If your new enclosing rectangle is narrower than the widest rectangle, you can stop now, and report the best enclosing rectangle you found so far. This is because the algorithm never increases the width of the enclosing rectangle, and if the widest rectangle won't fit, there is obviously no point in testing the enclosing rectangle.）

10.现在你的新闭合矩形既不太小，也不太大，返回第三步去看看你是否可以将所有矩形放进去。

这个算法已经在下载工程Mapper中的类MapperOptimalEfficiency的函数Mapping中实现了。

稍后我们将看看如何将这个基本算法做的更快些。但是首先让我们看看如何将矩形放入闭合区域中，最主要的是如何记录已放入的矩形来防止新加入矩形与他们重叠。

在一个给定的闭合矩形内安放矩形而不与其他矩形重叠

上面基本算法中的第三步写到“将矩形一个个的放入闭合矩形内，从最高的矩形开始，最矮的结束。放置每个矩形时尽可能的靠左，如果有好几个左边位置，用最高的那个。”

为了找到最左最高的位置来放置一个给定宽度和高度矩形而不与其他矩形重叠，我们需要用一些数据结构来记录闭合矩形中已被占用的区域。并且这个数据结构必须既简单（这样不容易出错）又能快速找到矩形可以被放置的那个最左最高位置。

可以使用一个二维布尔数组，每个格子代表闭合区域中的一个像素。每个布尔标记这个像素是否被占用还是空闲。然而，当你为一个矩形找空时需要访问很多像素，这个方案简单但效率低下。

另一个方案，可以保存闭合矩形中每个矩形的宽和高以及他们的X/Y方向的偏移。这个数据结构比起二维像素数据拥有更少的成员变量，但是在空间足够的情况下，计算出这个最左最高的位置使用这个结构将既复杂又慢。

我想出的解决方法是：使用一个动态的二维布尔数组表示占用或空闲，但是为每行存储一个高度，每列存储一个宽度，这样列数和行数可以保持在最小。这样既减少复杂度又降低了需要访问的格子数（和因此花费的时间）。下面是添加矩形时这个方法如何工作的（白色格子是未被占用，绿色格子是被占用，暗绿色格子是刚被最后一次添加矩形占用的）：

1.首先，只有一行和闭合矩形一样高，一列和闭合矩形一样宽。这意味着只有一个格子。

2.当添加第一个矩形时，找出最左最高的格子很轻松，因为这儿只有一个。确保他对于这个矩形足够大也很简单。所以我们继续，并把它放置在格子的左上角。

我们现在有个格子被部分占用，部分没有被占用。然而一个格子只能是一种状态。为了解决这个问题，将单行分开、单列分开，这样我们就获得了四个格子，这样他们要么被占用，要么没有被占用：

3.该添加第二个矩形了。首先检查最左边的列。从上到下遍历这个列中所有的格子直到你找到一个空闲的格子。然后检查是否能将矩形放在那儿。

最左列有一个空闲格，但是垂直方向上不够放下这个矩形。那么在右边一列如法炮制的查找。

第二列中，最高的那个格子是空间的，并且足够放置矩形，那么这很简单。将矩形放在那。和第一个格子放置时一样，矩形相对于格子比较小，导致一个格子部分被占用，部分未占用。所以分割该格子的行和列来确保格子又回到不是被占用就是未被占用的状态。注意结果，第一个矩形所占用的格子现在被划分为二了，这没关系的。

4.第三个矩形也走同样的流程。然而，因为这个矩形有点矮，所以最左列有足够的空间来放置他。再一次，在这个格子中相交的行列被分割了，来取保所有格子要么是占用要么是未被占用。

5.第四个矩形走同样的流程。如果最左列剩余垂直空间不足，那就在他右边试试。最左列最高的那个格子足够高来放置矩形，但是不够宽。所以测试右边的列看是不是有足够空闲的格子来安放矩形。可以看到起始列和他右边的列组合起来在水平方向上就有足够的空间安放这个矩形，也就是说这个矩形可以用两个格子来放置。再一次格子在行列上被分割，确保格子被占用或非占用。

6.第五个矩形，依旧从左到右的检查列。第二列有一个空闲格，但是对于该矩形在垂直方向上没有足够的空间。第三列有两个不相连的空闲格子，但是他俩高度都不够，并且垂直空间上也无法和其他格子结合凑足垂直空间来放置矩形。

在第四列，有一个空间格子，他既不够高也不够宽来安放矩形。所以检查右边列的格子和下面行的格子看是不是有足够空闲的格子可以组合来容纳矩形。在这种情况下，这证明是可行的。再一次，发生了行列分割来保证格子占用或非占用的唯一性。

通过运行下载文件中的网站，你可以看到更多的例子。他也演示了不是所有矩形都能放置的情况。

找到可以放置矩形的最左最高格子和检查周围格子的代码在下载中的Mapper工程的Canvas类中可以找到。二维动态数组在DynamicTwoDimensionalArray类中实现。因为他被经常使用，这个类为了性能被高度优化，尤其是分割行和列时。

对基本算法的改进

当学习下载的test site中生成的测试例子时，下面的改进会很明显。在写改进在下载的代码中有的。我在文献中没有找到这些改进的方法，所有你可以先读一下他们：

l 减小封闭区域宽度后，增加足够的高度

l 放置所有矩形失败后，增加足够的高度

l 通过设置效率的上限获得加速

减小封闭区域宽度后，增加足够的高度

看下下面那个一轮基本算法生成的闭合矩形：

根据基本算法，你应该将闭合矩形的宽度减一，然后试着重新安放所有矩形。然而，如果你简单的将宽度减一，你知道暗绿色矩形一定会超出闭合矩形的右手边界，对它来说无处容身了就，所以下次尝试安放所有矩形时一定会失败。

另外，算法说当失败的时候将闭合矩形的高度加一。但是，因为暗绿色矩形的高度是十个像素，明显高度加一是不够的。所以基本算法接下来一定会进行十次失败的尝试去安放所有矩形，这很费也没啥必要。

可以通过记录接触到闭合矩形右手边界最高矩形的高度来进行优化。如果你成功安放好所有矩形并将闭合矩形的宽度减一后，可以将闭合矩形的高度加上超出闭合矩形右方的最高矩形的高度。这样算法可以在新的闭合矩形内为超出右方的最高矩形找到新的位置：

放置所有矩形失败后，增加足够的高度

看看下面的序列。使用该算法安放好四个矩形后，放置第五个矩形时失败了。

1 2 3 4 放置矩形失败

这次失败后，基本算法将对闭合矩形的高度加一，然后重新放置矩形。但是仅仅加一的话，前四个矩形还是安放在一模一样的位置，最终安放第五个矩形还是失败。这个算法将会继续高度加一继续尝试，可能还是这种情况，周而复始。这些毫无意义的尝试占用了大量的时间。

使用下面两个高度中较小的值，来代替高度加一。

1．无法安放的矩形的高度

2．可以让闭合矩形对前四个矩形可以进行和之前不同排列的高度——这样至少给算法一个机会来安放第五个矩形

通过选择两项中较小的一个，你将可能得到更接近最小的闭合矩形。

算出上面第二点中提到的高度并不难，只要你意识到这个算法首先试着在最左列放置每个矩形，如果失败了就查看右边这列再次尝试，直到成功。每次在列中放置矩形失败，那是因为列的底部空闲区域对于矩形来说太矮了——空闲高度不足。

拿第二个矩形来说，第一列还差30个像素的空闲高度：

也就是说，如果闭合矩形再高那么30个像素，第二个矩形就可以放在最左边那列了。

同样的，第三个矩形要放在极左列的高度还差25像素，在第二行还差15像素。所以如果闭合矩形再高15个像素，第三个矩形放置的就会不同了：

第四个矩形在极左列还差10像素的空闲高度。所以如果闭合矩形如果高10个像素，第四个矩形也可能被放置在第一列。

我们想要增加闭合矩形所需最小的高度使矩形能排的不同即可。这里，最小的所有列所需空闲高度是10个像素（应用于第四个矩形放在极左列）。由于第五个矩形高了10个像素放置失败，我们需要将闭合矩形的高度增加10像素，希望在下次尝试时放置第五个矩形：（Seeing that the fifth rectangle that failed to be placed is higher than 10px, we need to increase the height of the enclosing rectangle by 10px to have any hope of placing the fifth rectangle at the next try: ）

1 2 3 4 5

这意味着为了防止那么多的失败闭合矩形，算法需要简单的记录下来在列中放置矩形时最小的空闲高度差额。当放置矩形失败的时候，可以用这个最小空闲高度差额增加闭合矩形的高度——如果无法放置矩形的高度更小的话就用他。

这种优化不能确保下一次尝试就能得到成功的闭合矩形。比如，新的高度下，闭合矩形可能会比目前的最佳闭合矩形要打，这种情况下算法将要开始减小他的宽度。这样的话可能会在下次尝试时无法安置所有的矩形因为降低了宽度。此优化是为了减少尝试的次数而非一次成功。

闭合矩形大小和速度间的取舍

如果你决定你可以忍受一定水平的空间浪费，一种方法是减少计算时间来产生闭合矩形，就是当达到这个水平时让代码停止继续获得更小的闭合矩形。

另一种方法提高速度是当找到预设次数成功闭合矩形后就让算法停止。你可以设置限制为一次或两次。这很有吸引力，当你发现这种方法可以让你得到一个足够好的结果并且提高了不少速度。

为了让你自己选，在MapperOptimalEfficiency类中提供了第二个构造函数，通过额外的参数设置这两个选项（with additional parameters to set these two cut offs ）。

矩形打包器的软件接口

下载Mapper项目中有文章中描述的矩形打包器的实现。他给外部提供了一个良好的接口。test side使用了这个接口。为了让你更容易的学习或者在你的项目使用这些代码，下面提供了接口的描述。

你会发现代码涉及到的是图片和精灵而不是矩形和封闭矩形。这是因为他是打算作为实时精灵生成器项目（还未完成）的一部分实现的。

接口

（译者注：略）

实现

（译者注：略）

用法

（译者注：略）

历史记录

（译者注：略）

许可

（译者注：略）

关于作者

（译者注：略）