矩形布局空间的处理及优化研究

张鹏程，郗艳梅，任红霞

（河北工程技术高等专科学校 电力工程系，河北 沧州 061001）

矩形布局空间的处理及优化研究

张鹏程，郗艳梅，任红霞

（河北工程技术高等专科学校 电力工程系，河北 沧州 061001）

针对矩形布局中的空间处理问题，根据布局空间的结构特点及变化规律，提出采用可行域算法求解矩形布局问题，并利用Visual C++6.0编程工具开发出具有实用意义的矩形智能布局系统。实例表明，该方法可以提高矩形布局问题的求解效率。

矩形布局；布局空间；子空间；悬边；存储结构

0 引 言

矩形布局问题是应用背景较强的离散组合最优化问题，属于NP完全问题，在有限的时间内不可能获得最优解，其解决只能依赖于各种局部寻优的启发式算法[1-2]。采用可行域算法求解矩形布局问题，是一种很好的思路。可行域算法的引入避开了布局求解过程中最复杂的矩形和布局空间、矩形和矩形之间的干涉计算，而保留了启发式算法中灵活选用布局策略的特点，使得该算法对不同类型的布局问题具有更广泛的适用性。

布局空间是指矩形能够放入的范围，在布局开始时，一般为一个简单、规则的矩形区域；随着布入矩形数量的增多，布局空间形状越来越复杂，布局过程结束时，布局空间将被布入的矩形最大限度的填充。布局空间在每一个矩形布入后其大小和形状都要发生相应的变化，而这些变化又将直接影响着下一个矩形的具体放置。另外，对布局空间简单而优化的处理算法可以在很大程度上提高整个布局问题的求解效率。因此，布局空间的确定对于布局问题的整个求解过程都有着极为重要的影响。

1 矩形布局空间的表示

对于矩形布局问题而言，布局空间可以描述为一个（或一组）由竖直边和水平边交替垂直首尾连接而成的简单直角多边形。在描述布局空间时，首先规定布局空间多边形的方向（本文采用顺时针方向为正向），然后用坐标值（x,y），来描述多边形各顶点的位置，采用一些数据结构来记录这些顶点的相关信息，如该顶点是否是交点、顶点的凹凸性等。

例如，一个布局空间，设顶点pi的坐标为（xi,yi），其中i=0,…,13，布局空间多边形的顶点连接次序为顺时针方向，则该布局空间可以描述为{p0，p1，p2,…，p12，p13}，如图1所示。在布局算法设计过程中，可以采用动态数组（CArray）[3]来记录这些顶点。

图1 布局空间的描述

当布局空间被矩形分割成由某些悬边相连的两个或多个子空间时[4]，布局空间不再作为一个整体，而是对由悬边连接的不同的子空间分别进行描述和处理。a,b为连接布局子空间的悬边，此时布局空间转变为三个独立的子空间，如图2所示。

图2 悬边a,b连接的三个布局子空间

2 矩形布局空间的更新

布局空间的更新是指，矩形放入布局空间之后，引起了布局空间顶点数量及形状的变化，此时，需要在原布局空间的基础上根据矩形的顶点位置进行相应的处理和更新。

在矩形的放置方式上，黄文奇等[5]论证了“占角”和“贴边”策略的优越性，因为这样可以使矩形之间更加紧凑，减小空间的浪费，提高整体的空间利用率，也符合“金角银边草肚皮”的传统方法[6]。本文在放置矩形时采用“占角”和“贴边”策略。

设原布局空间为{p0，p1，p2,…,pn-1，pn}，方向为顺时针方向。当前矩形的尺寸为{width, height}，放置的位置即矩形中心的位置为（x,y），矩形的四个顶点分别设为V0、V1、V2、V3，则其具体坐标可表示为：

矩形的四个顶点的连接次序如图3所示，方向为逆时针。当矩形放入布局空间多边形时，放置方式可以分为两种类型：一是矩形的顶点和布局空间的某个顶点重合，此时矩形必定对布局空间“占角”。二是矩形的四个顶点皆不与布局空间的顶点重合，此时矩形则必定和布局空间“贴边”。矩形A和布局空间“占角”，矩形B和布局空间“贴边”，如图4所示。

图3 矩形的四个顶点

图4 矩形放置时的“占角”和“贴边”

布局空间更新的算法步骤如下：

Step1：计算布局空间的顶点个数，记为num。

Step2：取布局空间多边形中的凸顶点，设为Pi，比较其是否与矩形的四个顶点中的某一个重合。如果此时矩形和布局空间“占角”，转Step3处理；否则为“贴边”，转Step4处理。

Step3：设顶点Pi与矩形的顶点Vj重合，则矩形其他三个顶点可以顺次表示为V(j+1)%4，V(j+2)%4，V(j+3)%4，在原布局空间顶点序列中，删除顶点Pi，在Pi-1的后面依次插入V(j+1)%4，V(j+2)%4，V(j+3)%4三个点，布局空间的顶点个数修改为num=num+2。

Step4：查找布局空间中第一条和矩形相贴的边Pk，Pk+1，可判断出：

（1）如果Pk，Pk+1为水平边，则只可能和矩形的V0，V1或V2，V3相贴，比较它们四个端点的坐标，根据Pk，Pk+1的方向，其位置关系有以下三种：

当Pk.x

当Pk.x>Pk+1.x时：

此时，由Pk点开始沿矩形的方向（逆时针方向）顺次将矩形的四个顶点插入布局空间序列，布局空间的顶点个数修改为num=num+4。

（2）如果Pk, Pk+1为垂直边，则只可能和矩形的V1，V2或V3，V0相贴，比较它们四个端点的坐标，根据Pk，Pk+1的方向，其位置关系有以下三种：

当Pk.y

当Pk.y>Pk+1.y时：

此时，由Pk点开始沿矩形的方向（逆时针方向）顺次将矩形的四个顶点插入布局空间序列，布局空间的顶点个数修改为num=num+4。

Step5：程序结束。

通过上述处理，可以获得更新后的布局空间。

3 矩形布局空间的分割

由于在布局空间的处理过程中采用了“贴边”策略，随着布入矩形的增多和布局空间的形状变化，更新后的布局空间很可能会出现不同的区域单边相连（实际上是两条不相邻的边发生重合）的情况，即导致前面所述的悬边的出现。为了布局过程的统一需去掉悬边，将布局空间分成几个独立子空间，从而后序的布局过程中将对这些布局子空间分别执行布局操作。

设置顶点的标志位al来标记该顶点是否已经被处理过，al=0表示该点尚未处理，al=1表示该点已经被处理过。设置标志位in来表示该顶点是否为交点，in=1表示该点为交点，in=0表示该点不是交点。如果布局空间上的某顶点落在与其不相邻的边上，此时令该点的标志位in=1，同时在对应的不相邻的边上，插入新顶点，其标志位in也记为1。布局空间中如果有悬边出现，布局子空间必定将在悬边的端点处分割，也就是上述交点处。

布局空间分割的算法步骤如下：

Step1：搜索并记录布局空间顶点序列P中所有的交点，并在其对应的边上插入新的点，其坐标与交点的坐标相同，设置所有交点的标志位in=1。

Step2：记当前布局空间中顶点的个数为num。

Step3：取布局空间序列中的顶点Pi，查看标志位al的状态，如果al=1，重新取下一点进行判断；如果al=0，则继续执行Step4。

Step4：设计数器count=0，查找顶点Pi所在的布局子空间中的所有点，依次记入新序列Q中。

Step4-1：令j=i，即用j来记录当前顶点的序号。将Pj点标志位al设置为1，同时将Pj点记入Q中。

Step4-2：取Pj点的标志位in，判断其是否为交点，如果in=1，则说明该点为交点。在布局空间序列P中查找与Pj坐标相同的点（该点已被标志为交点），令s为其序号，则取s+1点作为Q中的下一点，即j=s+1。如果in=0，则说明该点不是交点，直接取j=j+1。

Step4-3：取新点为Pj'以区别于原顶点Pj，判断Pj'和Pj的坐标是否相同，如果相同，则该子空间中的所有点已记录完毕，i=i+1，转Step3；否则转Step4-2。

Step5：程序结束。

通过上述处理，更新后的布局空间中的所有悬边将被去除，布局空间被分割成几个独立子空间。

4 矩形布局空间的调整

去除布局空间中的悬边之后，需对布局子空间做进一步调整，使之更加适合布局操作。

（1）去掉布局空间上的重合点。在布局空间的边上，有三个或三个以上的点具有相同的x坐标或y坐标，此时记录该水平边或垂直边只需两个端点，所以，在调整布局空间时，应该首先将该边上中间的那些点去除。去除的方法只需取布局空间顶点序列中相邻的三个点的坐标进行判断，通过比较它们的坐标，即可以将中间的无效点去除，同时将顶点数量减1。遍历所有序列中的点，直到其数量不再发生变化为止。对于重合点的去除可以取两个相邻的顶点比较，当它们坐标相同时，删除其中的一个即可。

（2）去掉悬边。在分割布局空间过程中，所有的布局子空间都被独立的分割出来。在悬边位置上，a，b两条边分割布局空间后，只剩下该边的两个顶点，如图2所示。它们显然不能构成布局空间，也不会对以后的布局过程产生任何影响，只是在更新布局空间时，为了统一只将它们看作一个独立的布局子空间来处理和记录。因此，在调整布局子空间时，这些点也应被相应的去除。遍历所有子空间，计算每个子空间顶点的数量，如果某个子空间的顶点的数量小于4，则直接将此子空间的相关顶点从子空间序列中去除，同时布局子空间的数量减1。

（3）去掉一些无效子空间。无效子空间是指从布局空间中分割出来的，其面积小于最小矩形面积的子空间。显然，在后序的布局过程中，不可能有矩形可以放入该区域。去除的方法是，计算待布矩形中最小矩形的面积Smin，以此为标准，遍历所有的布局子空间并计算其面积，如果某子空间的面积小于Smin，则将该子空间去除，同时布局子空间的数量减1。

5 矩形布局空间的存储

在布局过程中，布局空间形状总是在变化，其顶点数量也不断变化，因而不宜用普通的数组来存储。在算法实现中，采用VC++提供动态数组类来存储。动态数组的元素个数是可以变化的，且具有功能完备的成员函数，使对顶点的相关操作非常方便和简单。

布局过程中后期，布局空间可能被分割成几个子空间，为了便于进行统一存储和运算，另设一个指针数组来记录每个布局子空间中元素的个数。这样通过两个动态数组，就可以实现对布局空间的所有存储、管理和操作，如图5所示。

图5 布局空间的顶点数组和子空间指针数组

6 矩形布局空间的选择与重组

当布局空间由几个独立子空间组成时，矩形布入时要首先选择一个子空间作为布局空间。本文给出两种选择布局空间的方式，即按子空间的位置优先和按可行域面积优先。按子空间的位置优先是先计算布局空间中心位置，然后将其带入某一定位函数，取函数值最小的子空间作为布局空间，该方法与王金敏等[7]提出的吸引子方法是一致的。按可行域面积优先是指计算出矩形在所有布局子空间中的可行域，取其中可行域面积最小的子空间作为布局空间，该方法可以将矩形放置到其最适合的子空间中。

在布局过程中，虽然布局空间可能被分割成几个独立子空间，但对于一个具体的矩形来讲，布局只能在一个子空间内进行。因此，在处理布局空间问题时，先将选定的布局子空间从布局空间顶点数组中取出，而矩形布入该子空间后，该子空间还可能被新布入的矩形再分割成几个独立的部分，因而在处理完矩形的布入问题之后，需要再次将被分割成几个独立子空间重新插入到布局空间的顶点数组中，同时修改指针数组。

7 应用实例

采用本文的布局空间处理方法，结合矩形在布局空间中的可行域[8-9]，利用文献[7]中的定位策略，以Visual C++6.0作为工具，实现矩形布局问题的自动求解，开发出具有实用意义的矩形智能布局系统。以开放的矩形布局数据集http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/strip1.txt中Category 7中Problem1中的矩形数据为依据进行测试，布局空间为240×160，矩形个数为196个。测试使用计算机配置为PⅢ667MHZ，256M内存。

[例1]取一个吸引子，位置在布局空间左下角，定位函数参数分别为α1=0.2，β2=0.8,ω1=1。布局空间利用率为97.11%，布局时间为16.0360s。一个吸引子布局效果如图6所示。

图6 一个吸引子布局效果

[例2]取两个吸引子，位置分别在布局空间的左下角和右下角，定位函数参数分别为α1=0.3，β1=0.7，α2=0.65，β2=0.35, ω1=ω2=0.5。布局空间利用率为96.93%，布局时间为19.2782s。两个吸引子布局效果如图7所示。

图7 两个吸引子布局效果

[例3]取四个吸引子，吸引子分别取在布局空间的四个顶点上，定位函数参数分别为α1=0.5,α2=0.3,α3=0.2, α4=0.65，β1=0.5, β2=0.7, β3=0.8,β4=0.35，ω1=0.5,ω2=0.2, ω3=0.1,ω4=0.1。布局空间利用率为96.84%，布局时间为15.5378s。四个吸引子布局效果如图8所示。

8 小 结

在布局过程中对布局空间的表示、更新、分割、调整、存储等问题分析，分别给出相应的方法或算法，对于基于启发式算法求解矩形布局问题有一定的指导性。结合矩形布局的可行域的求解，利用本文算法开发出具有实用意义的矩形智能布局系统。实践证明，可行域算法是求解矩形布局问题行之有效的一种方法，而本文对于布局空间处理的相关算法是简单、可行、高效的。

图8 四个吸引子布局效果

[1]唐晓君，查建中，陆一平.布局问题的复杂性和建模方法[J].北方交通大学学报，2003，27(1):12-15.

[2]陈矛，黄文奇.求解VLSI布局问题的启发式算法[J].计算机科学，2006，33(3):197-199.

[3]Microsoft公司.Microsoft Visual C++6.0 MFC Library Reference类库参考手册(-):上[M].北京:北京希望电子出版社，1999:2.

[4]饶上荣，金文华，唐卫清，等.平面扩展轮廓的表示和求取[J].计算机辅助设计与图形学学报，2001，13(3):218-222.

[5]黄文奇，陈端兵.一种求解矩形块布局的拟物拟人算法[J].计算机科学，2005，32(11):182-186.

[6]何大勇，鄂明成，查建中,等.基于空间分解的集装箱布局启发式算法及布局空间利用率规律[J].计算机辅助设计与图形学学报，2000，12(5):367-370.

[7]王金敏，杨维嘉.动态吸引子在布局求解中的应用[J].计算机辅助设计与图形学学报，2005，17(8):1725-1730.

[8]王金敏，张鹏程，朱艳华.矩形布局可行域的确定[J].计算机辅助设计与图形学学报，2008，20(2):246-252.

[9]张鹏程，王金敏，朱艳华.凹点法求解矩形可行域问题研究[J].天津工程师范学院学报，2007，17(4):40-44.

[责任编辑：王玮明]

Research on Algorithm of Rectangle Packing Space and its Optimization

ZHANG Pengcheng, XI Yanmei, REN Hongxia
(Department of Electrical Engineering, Hebei Engineering and Technical College, Cangzhou, 061001, China)

In terms of the calculation of rectangle packing space, this paper, in the light of the structure and change rule of packing space, provides feasible region method to solve the problems. A practical intelligent rectangle packing system is developed through Visual C++6.0 program tools. It shows that the method can improve the efficiency of solving rectangle packing problems.

Rectangle packing; Packing space; Subspace; Stick; Storage structure

TP301.6

A

1671-4326(2011)01-0054-05

2010-11-02

河北省教育厅高等学校自然科学研究指导项目（Z2010230）

张鹏程（1976—），男，河北泊头人，河北工程技术高等专科学校电力工程系，实验师，硕士；

郗艳梅（1977—），女，河北唐山人，河北工程技术高等专科学校电力工程系讲师，硕士；

任红霞（1965—），女，河北泊头人，河北工程技术高等专科学校电力工程系副教授，硕士.