矩形布局空間的處理及優化研究

張鵬程，郗艷梅，任紅霞

（河北工程技術高等專科學校 電力工程系，河北 滄州 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—），女，河北泊頭人，河北工程技術高等專科學校電力工程系副教授，碩士.