張鵬程，郗艷梅，任紅霞

（河北工程技術(shù)高等?？茖W校 電力工程系，河北 滄州 061001）

矩形布局空間的處理及優(yōu)化研究

張鵬程，郗艷梅，任紅霞

（河北工程技術(shù)高等?？茖W校 電力工程系，河北 滄州 061001）

針對矩形布局中的空間處理問題，根據(jù)布局空間的結(jié)構(gòu)特點及變化規(guī)律，提出采用可行域算法求解矩形布局問題，并利用Visual C++6.0編程工具開發(fā)出具有實用意義的矩形智能布局系統(tǒng)。實例表明，該方法可以提高矩形布局問題的求解效率。

矩形布局；布局空間；子空間；懸邊；存儲結(jié)構(gòu)

0 引 言

矩形布局問題是應(yīng)用背景較強的離散組合最優(yōu)化問題，屬于NP完全問題，在有限的時間內(nèi)不可能獲得最優(yōu)解，其解決只能依賴于各種局部尋優(yōu)的啟發(fā)式算法[1-2]。采用可行域算法求解矩形布局問題，是一種很好的思路。可行域算法的引入避開了布局求解過程中最復(fù)雜的矩形和布局空間、矩形和矩形之間的干涉計算，而保留了啟發(fā)式算法中靈活選用布局策略的特點，使得該算法對不同類型的布局問題具有更廣泛的適用性。

布局空間是指矩形能夠放入的范圍，在布局開始時，一般為一個簡單、規(guī)則的矩形區(qū)域；隨著布入矩形數(shù)量的增多，布局空間形狀越來越復(fù)雜，布局過程結(jié)束時，布局空間將被布入的矩形最大限度的填充。布局空間在每一個矩形布入后其大小和形狀都要發(fā)生相應(yīng)的變化，而這些變化又將直接影響著下一個矩形的具體放置。另外，對布局空間簡單而優(yōu)化的處理算法可以在很大程度上提高整個布局問題的求解效率。因此，布局空間的確定對于布局問題的整個求解過程都有著極為重要的影響。

1 矩形布局空間的表示

對于矩形布局問題而言，布局空間可以描述為一個（或一組）由豎直邊和水平邊交替垂直首尾連接而成的簡單直角多邊形。在描述布局空間時，首先規(guī)定布局空間多邊形的方向（本文采用順時針方向為正向），然后用坐標值（x,y），來描述多邊形各頂點的位置，采用一些數(shù)據(jù)結(jié)構(gòu)來記錄這些頂點的相關(guān)信息，如該頂點是否是交點、頂點的凹凸性等。

例如，一個布局空間，設(shè)頂點pi的坐標為（xi,yi），其中i=0,…,13，布局空間多邊形的頂點連接次序為順時針方向，則該布局空間可以描述為{p0，p1，p2,…，p12，p13}，如圖1所示。在布局算法設(shè)計過程中，可以采用動態(tài)數(shù)組（CArray）[3]來記錄這些頂點。

圖1 布局空間的描述

當布局空間被矩形分割成由某些懸邊相連的兩個或多個子空間時[4]，布局空間不再作為一個整體，而是對由懸邊連接的不同的子空間分別進行描述和處理。a,b為連接布局子空間的懸邊，此時布局空間轉(zhuǎn)變?yōu)槿齻€獨立的子空間，如圖2所示。

圖2 懸邊a,b連接的三個布局子空間

2 矩形布局空間的更新

布局空間的更新是指，矩形放入布局空間之后，引起了布局空間頂點數(shù)量及形狀的變化，此時，需要在原布局空間的基礎(chǔ)上根據(jù)矩形的頂點位置進行相應(yīng)的處理和更新。

在矩形的放置方式上，黃文奇等[5]論證了“占角”和“貼邊”策略的優(yōu)越性，因為這樣可以使矩形之間更加緊湊，減小空間的浪費，提高整體的空間利用率，也符合“金角銀邊草肚皮”的傳統(tǒng)方法[6]。本文在放置矩形時采用“占角”和“貼邊”策略。

設(shè)原布局空間為{p0，p1，p2,…,pn-1，pn}，方向為順時針方向。當前矩形的尺寸為{width, height}，放置的位置即矩形中心的位置為（x,y），矩形的四個頂點分別設(shè)為V0、V1、V2、V3，則其具體坐標可表示為：

矩形的四個頂點的連接次序如圖3所示，方向為逆時針。當矩形放入布局空間多邊形時，放置方式可以分為兩種類型：一是矩形的頂點和布局空間的某個頂點重合，此時矩形必定對布局空間“占角”。二是矩形的四個頂點皆不與布局空間的頂點重合，此時矩形則必定和布局空間“貼邊”。矩形A和布局空間“占角”，矩形B和布局空間“貼邊”，如圖4所示。

圖3 矩形的四個頂點

圖4 矩形放置時的“占角”和“貼邊”

布局空間更新的算法步驟如下：

Step1：計算布局空間的頂點個數(shù)，記為num。

Step2：取布局空間多邊形中的凸頂點，設(shè)為Pi，比較其是否與矩形的四個頂點中的某一個重合。如果此時矩形和布局空間“占角”，轉(zhuǎn)Step3處理；否則為“貼邊”，轉(zhuǎn)Step4處理。

Step3：設(shè)頂點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三個點，布局空間的頂點個數(shù)修改為num=num+2。

Step4：查找布局空間中第一條和矩形相貼的邊Pk，Pk+1，可判斷出：

（1）如果Pk，Pk+1為水平邊，則只可能和矩形的V0，V1或V2，V3相貼，比較它們四個端點的坐標，根據(jù)Pk，Pk+1的方向，其位置關(guān)系有以下三種：

當Pk.x

當Pk.x>Pk+1.x時：

此時，由Pk點開始沿矩形的方向（逆時針方向）順次將矩形的四個頂點插入布局空間序列，布局空間的頂點個數(shù)修改為num=num+4。

（2）如果Pk, Pk+1為垂直邊，則只可能和矩形的V1，V2或V3，V0相貼，比較它們四個端點的坐標，根據(jù)Pk，Pk+1的方向，其位置關(guān)系有以下三種：

當Pk.y

當Pk.y>Pk+1.y時：

此時，由Pk點開始沿矩形的方向（逆時針方向）順次將矩形的四個頂點插入布局空間序列，布局空間的頂點個數(shù)修改為num=num+4。

Step5：程序結(jié)束。

通過上述處理，可以獲得更新后的布局空間。

3 矩形布局空間的分割

由于在布局空間的處理過程中采用了“貼邊”策略，隨著布入矩形的增多和布局空間的形狀變化，更新后的布局空間很可能會出現(xiàn)不同的區(qū)域單邊相連（實際上是兩條不相鄰的邊發(fā)生重合）的情況，即導(dǎo)致前面所述的懸邊的出現(xiàn)。為了布局過程的統(tǒng)一需去掉懸邊，將布局空間分成幾個獨立子空間，從而后序的布局過程中將對這些布局子空間分別執(zhí)行布局操作。

設(shè)置頂點的標志位al來標記該頂點是否已經(jīng)被處理過，al=0表示該點尚未處理，al=1表示該點已經(jīng)被處理過。設(shè)置標志位in來表示該頂點是否為交點，in=1表示該點為交點，in=0表示該點不是交點。如果布局空間上的某頂點落在與其不相鄰的邊上，此時令該點的標志位in=1，同時在對應(yīng)的不相鄰的邊上，插入新頂點，其標志位in也記為1。布局空間中如果有懸邊出現(xiàn)，布局子空間必定將在懸邊的端點處分割，也就是上述交點處。

布局空間分割的算法步驟如下：

Step1：搜索并記錄布局空間頂點序列P中所有的交點，并在其對應(yīng)的邊上插入新的點，其坐標與交點的坐標相同，設(shè)置所有交點的標志位in=1。

Step2：記當前布局空間中頂點的個數(shù)為num。

Step3：取布局空間序列中的頂點Pi，查看標志位al的狀態(tài)，如果al=1，重新取下一點進行判斷；如果al=0，則繼續(xù)執(zhí)行Step4。

Step4：設(shè)計數(shù)器count=0，查找頂點Pi所在的布局子空間中的所有點，依次記入新序列Q中。

Step4-1：令j=i，即用j來記錄當前頂點的序號。將Pj點標志位al設(shè)置為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'以區(qū)別于原頂點Pj，判斷Pj'和Pj的坐標是否相同，如果相同，則該子空間中的所有點已記錄完畢，i=i+1，轉(zhuǎn)Step3；否則轉(zhuǎn)Step4-2。

Step5：程序結(jié)束。

通過上述處理，更新后的布局空間中的所有懸邊將被去除，布局空間被分割成幾個獨立子空間。

4 矩形布局空間的調(diào)整

去除布局空間中的懸邊之后，需對布局子空間做進一步調(diào)整，使之更加適合布局操作。

（1）去掉布局空間上的重合點。在布局空間的邊上，有三個或三個以上的點具有相同的x坐標或y坐標，此時記錄該水平邊或垂直邊只需兩個端點，所以，在調(diào)整布局空間時，應(yīng)該首先將該邊上中間的那些點去除。去除的方法只需取布局空間頂點序列中相鄰的三個點的坐標進行判斷，通過比較它們的坐標，即可以將中間的無效點去除，同時將頂點數(shù)量減1。遍歷所有序列中的點，直到其數(shù)量不再發(fā)生變化為止。對于重合點的去除可以取兩個相鄰的頂點比較，當它們坐標相同時，刪除其中的一個即可。

（2）去掉懸邊。在分割布局空間過程中，所有的布局子空間都被獨立的分割出來。在懸邊位置上，a，b兩條邊分割布局空間后，只剩下該邊的兩個頂點，如圖2所示。它們顯然不能構(gòu)成布局空間，也不會對以后的布局過程產(chǎn)生任何影響，只是在更新布局空間時，為了統(tǒng)一只將它們看作一個獨立的布局子空間來處理和記錄。因此，在調(diào)整布局子空間時，這些點也應(yīng)被相應(yīng)的去除。遍歷所有子空間，計算每個子空間頂點的數(shù)量，如果某個子空間的頂點的數(shù)量小于4，則直接將此子空間的相關(guān)頂點從子空間序列中去除，同時布局子空間的數(shù)量減1。

（3）去掉一些無效子空間。無效子空間是指從布局空間中分割出來的，其面積小于最小矩形面積的子空間。顯然，在后序的布局過程中，不可能有矩形可以放入該區(qū)域。去除的方法是，計算待布矩形中最小矩形的面積Smin，以此為標準，遍歷所有的布局子空間并計算其面積，如果某子空間的面積小于Smin，則將該子空間去除，同時布局子空間的數(shù)量減1。

5 矩形布局空間的存儲

在布局過程中，布局空間形狀總是在變化，其頂點數(shù)量也不斷變化，因而不宜用普通的數(shù)組來存儲。在算法實現(xiàn)中，采用VC++提供動態(tài)數(shù)組類來存儲。動態(tài)數(shù)組的元素個數(shù)是可以變化的，且具有功能完備的成員函數(shù)，使對頂點的相關(guān)操作非常方便和簡單。

布局過程中后期，布局空間可能被分割成幾個子空間，為了便于進行統(tǒng)一存儲和運算，另設(shè)一個指針數(shù)組來記錄每個布局子空間中元素的個數(shù)。這樣通過兩個動態(tài)數(shù)組，就可以實現(xiàn)對布局空間的所有存儲、管理和操作，如圖5所示。

圖5 布局空間的頂點數(shù)組和子空間指針數(shù)組

6 矩形布局空間的選擇與重組

當布局空間由幾個獨立子空間組成時，矩形布入時要首先選擇一個子空間作為布局空間。本文給出兩種選擇布局空間的方式，即按子空間的位置優(yōu)先和按可行域面積優(yōu)先。按子空間的位置優(yōu)先是先計算布局空間中心位置，然后將其帶入某一定位函數(shù)，取函數(shù)值最小的子空間作為布局空間，該方法與王金敏等[7]提出的吸引子方法是一致的。按可行域面積優(yōu)先是指計算出矩形在所有布局子空間中的可行域，取其中可行域面積最小的子空間作為布局空間，該方法可以將矩形放置到其最適合的子空間中。

在布局過程中，雖然布局空間可能被分割成幾個獨立子空間，但對于一個具體的矩形來講，布局只能在一個子空間內(nèi)進行。因此，在處理布局空間問題時，先將選定的布局子空間從布局空間頂點數(shù)組中取出，而矩形布入該子空間后，該子空間還可能被新布入的矩形再分割成幾個獨立的部分，因而在處理完矩形的布入問題之后，需要再次將被分割成幾個獨立子空間重新插入到布局空間的頂點數(shù)組中，同時修改指針數(shù)組。

7 應(yīng)用實例

采用本文的布局空間處理方法，結(jié)合矩形在布局空間中的可行域[8-9]，利用文獻[7]中的定位策略，以Visual C++6.0作為工具，實現(xiàn)矩形布局問題的自動求解，開發(fā)出具有實用意義的矩形智能布局系統(tǒng)。以開放的矩形布局數(shù)據(jù)集http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/strip1.txt中Category 7中Problem1中的矩形數(shù)據(jù)為依據(jù)進行測試，布局空間為240×160，矩形個數(shù)為196個。測試使用計算機配置為PⅢ667MHZ，256M內(nèi)存。

[例1]取一個吸引子，位置在布局空間左下角，定位函數(shù)參數(shù)分別為α1=0.2，β2=0.8,ω1=1。布局空間利用率為97.11%，布局時間為16.0360s。一個吸引子布局效果如圖6所示。

圖6 一個吸引子布局效果

[例2]取兩個吸引子，位置分別在布局空間的左下角和右下角，定位函數(shù)參數(shù)分別為α1=0.3，β1=0.7，α2=0.65，β2=0.35, ω1=ω2=0.5。布局空間利用率為96.93%，布局時間為19.2782s。兩個吸引子布局效果如圖7所示。

圖7 兩個吸引子布局效果

[例3]取四個吸引子，吸引子分別取在布局空間的四個頂點上，定位函數(shù)參數(shù)分別為α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 小 結(jié)

在布局過程中對布局空間的表示、更新、分割、調(diào)整、存儲等問題分析，分別給出相應(yīng)的方法或算法，對于基于啟發(fā)式算法求解矩形布局問題有一定的指導(dǎo)性。結(jié)合矩形布局的可行域的求解，利用本文算法開發(fā)出具有實用意義的矩形智能布局系統(tǒng)。實踐證明，可行域算法是求解矩形布局問題行之有效的一種方法，而本文對于布局空間處理的相關(guān)算法是簡單、可行、高效的。

圖8 四個吸引子布局效果

[1]唐曉君，查建中，陸一平.布局問題的復(fù)雜性和建模方法[J].北方交通大學學報，2003，27(1):12-15.

[2]陳矛，黃文奇.求解VLSI布局問題的啟發(fā)式算法[J].計算機科學，2006，33(3):197-199.

[3]Microsoft公司.Microsoft Visual C++6.0 MFC Library Reference類庫參考手冊(-):上[M].北京:北京希望電子出版社，1999:2.

[4]饒上榮，金文華，唐衛(wèi)清，等.平面擴展輪廓的表示和求取[J].計算機輔助設(shè)計與圖形學學報，2001，13(3):218-222.

[5]黃文奇，陳端兵.一種求解矩形塊布局的擬物擬人算法[J].計算機科學，2005，32(11):182-186.

[6]何大勇，鄂明成，查建中,等.基于空間分解的集裝箱布局啟發(fā)式算法及布局空間利用率規(guī)律[J].計算機輔助設(shè)計與圖形學學報，2000，12(5):367-370.

[7]王金敏，楊維嘉.動態(tài)吸引子在布局求解中的應(yīng)用[J].計算機輔助設(shè)計與圖形學學報，2005，17(8):1725-1730.

[8]王金敏，張鵬程，朱艷華.矩形布局可行域的確定[J].計算機輔助設(shè)計與圖形學學報，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

河北省教育廳高等學校自然科學研究指導(dǎo)項目（Z2010230）

張鵬程（1976—），男，河北泊頭人，河北工程技術(shù)高等?？茖W校電力工程系，實驗師，碩士；

郗艷梅（1977—），女，河北唐山人，河北工程技術(shù)高等?？茖W校電力工程系講師，碩士；

任紅霞（1965—），女，河北泊頭人，河北工程技術(shù)高等?？茖W校電力工程系副教授，碩士.