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

張鵬程，郗艷梅，任紅霞

（河北工程技術(shù)高等專科學(xué)校 電力工程系，河北 滄州 061001）

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

張鵬程，郗艷梅，任紅霞

（河北工程技術(shù)高等專科學(xué)校 電力工程系，河北 滄州 061001）

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

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

0 引 言

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

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

1 矩形布局空間的表示

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

例如，一個(gè)布局空間，設(shè)頂點(diǎn)pi的坐標(biāo)為（xi,yi），其中i=0,…,13，布局空間多邊形的頂點(diǎn)連接次序?yàn)轫槙r(shí)針?lè)较?，則該布局空間可以描述為{p0，p1，p2,…，p12，p13}，如圖1所示。在布局算法設(shè)計(jì)過(guò)程中，可以采用動(dòng)態(tài)數(shù)組（CArray）[3]來(lái)記錄這些頂點(diǎn)。

圖1 布局空間的描述

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

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

2 矩形布局空間的更新

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

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

設(shè)原布局空間為{p0，p1，p2,…,pn-1，pn}，方向?yàn)轫槙r(shí)針?lè)较颉．?dāng)前矩形的尺寸為{width, height}，放置的位置即矩形中心的位置為（x,y），矩形的四個(gè)頂點(diǎn)分別設(shè)為V0、V1、V2、V3，則其具體坐標(biāo)可表示為：

矩形的四個(gè)頂點(diǎn)的連接次序如圖3所示，方向?yàn)槟鏁r(shí)針。當(dāng)矩形放入布局空間多邊形時(shí)，放置方式可以分為兩種類型：一是矩形的頂點(diǎn)和布局空間的某個(gè)頂點(diǎn)重合，此時(shí)矩形必定對(duì)布局空間“占角”。二是矩形的四個(gè)頂點(diǎn)皆不與布局空間的頂點(diǎn)重合，此時(shí)矩形則必定和布局空間“貼邊”。矩形A和布局空間“占角”，矩形B和布局空間“貼邊”，如圖4所示。

圖3 矩形的四個(gè)頂點(diǎn)

圖4 矩形放置時(shí)的“占角”和“貼邊”

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

Step1：計(jì)算布局空間的頂點(diǎn)個(gè)數(shù)，記為num。

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

Step3：設(shè)頂點(diǎn)Pi與矩形的頂點(diǎn)Vj重合，則矩形其他三個(gè)頂點(diǎn)可以順次表示為V(j+1)%4，V(j+2)%4，V(j+3)%4，在原布局空間頂點(diǎn)序列中，刪除頂點(diǎn)Pi，在Pi-1的后面依次插入V(j+1)%4，V(j+2)%4，V(j+3)%4三個(gè)點(diǎn)，布局空間的頂點(diǎn)個(gè)數(shù)修改為num=num+2。

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

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

當(dāng)Pk.x

當(dāng)Pk.x>Pk+1.x時(shí)：

此時(shí)，由Pk點(diǎn)開(kāi)始沿矩形的方向（逆時(shí)針?lè)较颍╉槾螌⒕匦蔚乃膫€(gè)頂點(diǎn)插入布局空間序列，布局空間的頂點(diǎn)個(gè)數(shù)修改為num=num+4。

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

當(dāng)Pk.y

當(dāng)Pk.y>Pk+1.y時(shí)：

此時(shí)，由Pk點(diǎn)開(kāi)始沿矩形的方向（逆時(shí)針?lè)较颍╉槾螌⒕匦蔚乃膫€(gè)頂點(diǎn)插入布局空間序列，布局空間的頂點(diǎn)個(gè)數(shù)修改為num=num+4。

Step5：程序結(jié)束。

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

3 矩形布局空間的分割

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

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

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

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

Step2：記當(dāng)前布局空間中頂點(diǎn)的個(gè)數(shù)為num。

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

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

Step4-1：令j=i，即用j來(lái)記錄當(dāng)前頂點(diǎn)的序號(hào)。將Pj點(diǎn)標(biāo)志位al設(shè)置為1，同時(shí)將Pj點(diǎn)記入Q中。

Step4-2：取Pj點(diǎn)的標(biāo)志位in，判斷其是否為交點(diǎn)，如果in=1，則說(shuō)明該點(diǎn)為交點(diǎn)。在布局空間序列P中查找與Pj坐標(biāo)相同的點(diǎn)（該點(diǎn)已被標(biāo)志為交點(diǎn)），令s為其序號(hào)，則取s+1點(diǎn)作為Q中的下一點(diǎn)，即j=s+1。如果in=0，則說(shuō)明該點(diǎn)不是交點(diǎn)，直接取j=j+1。

Step4-3：取新點(diǎn)為Pj'以區(qū)別于原頂點(diǎn)Pj，判斷Pj'和Pj的坐標(biāo)是否相同，如果相同，則該子空間中的所有點(diǎn)已記錄完畢，i=i+1，轉(zhuǎn)Step3；否則轉(zhuǎn)Step4-2。

Step5：程序結(jié)束。

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

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

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

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

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

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

5 矩形布局空間的存儲(chǔ)

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

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

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

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

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

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

7 應(yīng)用實(shí)例

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

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

圖6 一個(gè)吸引子布局效果

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

圖7 兩個(gè)吸引子布局效果

[例3]取四個(gè)吸引子，吸引子分別取在布局空間的四個(gè)頂點(diǎn)上，定位函數(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%，布局時(shí)間為15.5378s。四個(gè)吸引子布局效果如圖8所示。

8 小 結(jié)

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

圖8 四個(gè)吸引子布局效果

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

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

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

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

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

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

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

[8]王金敏，張鵬程，朱艷華.矩形布局可行域的確定[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20(2):246-252.

[9]張鵬程，王金敏，朱艷華.凹點(diǎn)法求解矩形可行域問(wèn)題研究[J].天津工程師范學(xué)院學(xué)報(bào)，2007，17(4):40-44.

[責(zé)任編輯：王瑋明]

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

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

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

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

任紅霞（1965—），女，河北泊頭人，河北工程技術(shù)高等專科學(xué)校電力工程系副教授，碩士.