矩形布局問題可行域的求解

矩形布局問題可行域的求解

結(jié)構(gòu)啟動布局算法將布局對象的布局過程分為兩個階段。也就是說，布局順序規(guī)則確定了布局順序，定位規(guī)則確定了正確的配置位置。布局對象的位置可以通過定序和定位確定。在選擇定序規(guī)則和定位規(guī)則時，例如，如果將所選矩形位域與所選矩陣進行相結(jié)合，則布局過程可以變得更加靈活，提高算法的適應(yīng)性?？蓤?zhí)行區(qū)域的確定不僅用于布局問題，而且對于解決圖形分割、邊緣多邊形解算方法、零件路徑規(guī)劃和其他問題非常重要?？尚杏虻母拍钤谝恍┚匦尾季謫栴}求解的相關(guān)文獻中也有所涉及,但多是采用對布局空間分解的方式(如正交分解)來處理,在某一個分解后的子空間中確定布局物體的可行域,而分解后的子空間一般仍是一矩形.這樣雖然簡化了求解可行域的計算,但限制了矩形布入的范圍,實際上是縮小了物體的可行域,從而將錯過一些更好的放置位置,且降低了布局效率.布局可行域是指布局物體所有可行的放置位置,即保證布局物體不與布局空間和其他布局物體發(fā)生干涉的位置.目前,研究矩形在任意布局空間中的可行域問題的相關(guān)文獻并不多見,可行域求解算法本質(zhì)上類似于不適合邊界算法.針對矩形布局空間的特點(為直角多邊形),可行域的求解過程可分為3個步驟:偏移多邊形的獲得、自交點的確定和邊界多邊形及可行域的求解.1原布局空間或偏移定義為了敘述方便,對以下幾個定義進行說明.定義1.布局可行域.布局可行域是指布局物體在布局空間所有可行位置的集合,具體可表示為布局物體上任意一點(本文中取矩形的中心)在物體沿布局空間邊界移動時的封閉軌跡包含的區(qū)域.如圖1所示.矩形布局問題的可行域可以為空、點、直線段和平面區(qū)域;可行域為空的情況表示物體不能放入;可行域為點時表示布局物體只有一個擺放位置;可行域為直線段表示物體在布局空間中的可行點均在一條直線上;當(dāng)可行域為一平面區(qū)域時,表示物體可以放置在該區(qū)域的任一位置.定義2.多邊形鏈.多邊形的頂點P0,P1,…,Pn-1,Pn按順序連接成一條封閉環(huán)P,稱之為多邊形鏈,簡稱為鏈.偏移多邊形鏈、邊界多邊形鏈的方向皆由布局空間多邊形鏈的方向確定,而布局空間多邊形鏈的方向由原始布局空間方向給出,即先確定原始布局空間(一般為一矩形)方向,然后在每一矩形布入時,按一定規(guī)則在原布局空間多邊形鏈上插入新頂點而不改變原多邊形鏈的方向,從而保證了布局過程中所有臨時布局空間的方向與原布局空間方向一致.本文中取布局空間的方向為順時針方向.定義3.偏移多邊形.根據(jù)各頂點的形態(tài),將布局空間的多邊形各頂點的坐標(biāo)向布局空間內(nèi)部分別以待布入矩形的長和寬的一半為距離進行偏移,并順次連接偏移后各頂點所獲得的多邊形,稱為布局空間的偏移多邊形.偏移多邊形的各頂點和布局空間的頂點是一一對應(yīng)的,如圖2所示.如果偏移多邊形中有自交點存在(如圖2中A,B兩點),說明原布局空間中必然存在不可行區(qū)域.定義4.布局空間頂點的凹凸性及形態(tài).在布局空間多邊形中,當(dāng)頂點“指向”布局空間外部時,定義該頂點為凸點;當(dāng)頂點“指向”布局空間內(nèi)部時,定義該頂點為凹點.如圖2中C,D兩點,分別為布局空間上的凸點和凹點.由于布局空間的相鄰接的2條邊皆相互垂直,因此布局空間上頂點只有4種形態(tài),可根據(jù)布局空間頂點的凹凸性確定其偏移多邊形頂點的位置.如圖3a所示,當(dāng)頂點Pi為凸點時,相應(yīng)的偏移多邊形頂點取在A點,當(dāng)頂點Pi為凹點時,相應(yīng)的偏移多邊形頂點取在B點.定義5.多邊形自交點.如果多邊形不相鄰的2條邊有且僅有一個重合的點,則稱該點為多邊形自交點.如圖2中A,B所示.多邊形自交點有以下3種情況:1)交點位于2條邊上.2)交點位于一條邊上,且與另一條邊的端點重合.3)交點為2條邊的端點.定義6.頂點的序號坐標(biāo).將多邊形所有頂點P0,P1,…,Pi-1,Pi,Pi+1,…,Pn-1,Pn分別按x坐標(biāo)和y坐標(biāo)排序,用頂點的x和y坐標(biāo)的序號來定位每個頂點,稱為頂點的序號坐標(biāo).例如,頂點Pi記為Pi(a,b),i為頂點的序號,a表示頂點Pi的x坐標(biāo)序號,b表示頂點Pi的y坐標(biāo)序號.用頂點的序號坐標(biāo)描述多邊形頂點,不僅可以用序號坐標(biāo)來替代x,y坐標(biāo)進行比較,而且序號坐標(biāo)也標(biāo)明了各頂點之間的位置關(guān)系.定義7.偏移多邊形的外邊界多邊形.沿偏移多邊形的外邊界進行一次搜索,順次將所經(jīng)過的邊界上的頂點連接起來,形成的多邊形稱為偏移多邊形的外邊界多邊形.外邊界多邊形舍去偏移多邊形內(nèi)部可能出現(xiàn)的復(fù)雜的自交情況,只取外邊界上的點進行研究.圖4中,圖4a所示為含有自交的偏移多邊形,圖4b所示為圖4a的外邊界多邊形.2偏移雙邊算法一般多邊形頂點的凹凸性判斷方法有多種,如角度法、坐標(biāo)行列式法、凸多邊形法、拓撲映射法等.考慮到布局空間多邊形形態(tài)的特殊性,本文提出根據(jù)布局空間多邊形的方向?qū)ο噜忢旤c坐標(biāo)進行簡單比較便可迅速確定頂點凹凸性及其形態(tài)的方法,再通過簡單偏移計算,即可獲得偏移多邊形.令當(dāng)前布局空間的頂點鏈為P={P0P1…Pi-1PiPi+1…Pn-1Pn}(其中Pn=P0,以下不再特別指出),采用循環(huán)雙鏈表作為存儲頂點鏈的數(shù)據(jù)結(jié)構(gòu),頂點連接次序按順時針方向確定.設(shè)待布矩形的寬和高分別為width和height,P′鏈表示偏移多邊形的頂點.設(shè)Pi-1,Pi,Pi+1為布局空間多邊形邊界上相鄰的任意3個頂點,Pi(x)和Pi(y)分別表示頂點Pi的x,y坐標(biāo).算法1.確定偏移多邊形算法Step1.取頂點Pi-1,Pi,Pi+1,它們是布局空間多邊形邊界上順時針次序相鄰的任意3個頂點.Step2.如果Pi(x)和Pi-1(x)相同,轉(zhuǎn)Step3;否則(具有相同的y坐標(biāo)),轉(zhuǎn)Step4.Step3.如果Pi(y)>Pi-1(y),那么,若Pi+1(x)>Pi(x),Pi為凸點,形態(tài)如圖3a所示,則P′i(x)=Pi(x)+width2,P′i(y)=Pi(y)-height2;若Pi+1(x)<Pi(x),Pi為凹點,形態(tài)如圖3b所示,則P′i(x)=Pi(x)+width2,P′i(y)=Pi(y)+height2.如果Pi(y)<Pi-1(y),那么,若Pi+1(x)>Pi(x),Pi為凹點,形態(tài)如圖3c所示,則P′i(x)=Pi(x)-width2,P′i(y)=Pi(y)-height2;若Pi+1(x)<Pi(x),Pi為凸點,形態(tài)如圖3d所示,則P′i(x)=Pi(x)-width2,P′i(y)=Pi(y)+height2.Step4.如果Pi(x)<Pi-1(x),那么,若Pi+1(y)<Pi(y),Pi為凹點,形態(tài)如圖3a所示,則P′i(x)=Pi(x)-width2,P′i(y)=Pi(y)+height2;若Pi+1(y)>Pi(y),Pi為凸點,形態(tài)如圖3c所示,則P′i(x)=Pi(x)+width2,P′i(y)=Pi(y)+height2.如果Pi(x)>Pi-1(x),那么,若Pi+1(y)<Pi(y),Pi為凸點,形態(tài)如圖3b所示,則P′i(x)=Pi(x)-width2,P′i(y)=Pi(y)-height2;若Pi+1(y)>Pi(y),Pi為凹點,形態(tài)如圖3d所示,則P′i(x)=Pi(x)+width2,P′i(y)=Pi(y)-height2.Step5.順次遍歷和處理所有頂點,即可獲得偏移多邊形鏈P′.連接偏移多邊形鏈的各頂點,即可獲得當(dāng)前布局空間的偏移多邊形.3偏移雙邊點算法布局空間中若含有不可行域,經(jīng)偏移后形成的偏移多邊形區(qū)域必出現(xiàn)自交現(xiàn)象.確定偏移多邊形的自交點是去除偏移多邊形中不可行區(qū)域的一個關(guān)鍵,多邊形自交點的確定和自交區(qū)域的去除也是CAD?CAM以及計算機圖形學(xué)的一個重要問題.文獻提出了多邊形自交點的確定方法,但由于布局問題的偏移多邊形交點求解問題的特殊性,頂點角皆為直角且多邊形的邊為水平或垂直邊,使得問題的計算相對簡單,可能出現(xiàn)的偏移多邊形的多邊互交和多邊形鏈的非單調(diào)性又使問題處理變得復(fù)雜.本文以偏移多邊形中各水平邊為研究對象,遍歷多邊形中與該水平邊不相鄰的所有垂直邊,判斷它們是否相交,記錄交點坐標(biāo)并置交點的標(biāo)志位tag來確定偏移多邊形的自交點;tag=0表明該點不是交點,tag=1表明該點是交點.該算法只需對多邊形頂點進行比較和判斷,無需其他復(fù)雜運算.算法2.確定偏移多邊形自交點的算法Step1.取偏移多邊形鏈P′的所有頂點{P0P1…Pi-1PiPi+1…Pn-1Pn},頂點的標(biāo)志位tag默認為0,表明該頂點是偏移多邊形上的頂點(以區(qū)別于多邊形的自交點tag=1).Step2.用序號坐標(biāo)標(biāo)記所有偏移多邊形頂點.Step3.取頂點(即tag=0的點,開始時交點無記錄)進行判斷.設(shè)當(dāng)前頂點為Pi,其前一頂點為Pi-1,后一頂點為Pi+1.Step4.設(shè)Pi-1Pi構(gòu)成水平邊,PiPi+1構(gòu)成垂直邊(如果Pi-1Pi構(gòu)成垂直邊,PiPi+1構(gòu)成水平邊,處理方法類似),取Pi-1Pi即水平邊進行研究.設(shè)Pi-1和Pi的序號坐標(biāo)分別表示為Pi-1(a,c)和Pi(b,c).如果|a-b|>1,即Pi和Pi-1的x坐標(biāo)不相鄰,轉(zhuǎn)Step5;否則,轉(zhuǎn)Step6.Step5.順次取垂直邊Pi+2Pi+3,Pi+4Pi+5,Pi+6Pi+7,…,Pi-4Pi-3(這里不用取PiPi+1,Pi-2Pi-1,因為其和Pi-1Pi相鄰),分別進行如下處理:Step5.1.如果當(dāng)前垂直邊已經(jīng)處理過,轉(zhuǎn)Step5,否則,設(shè)當(dāng)前垂直邊為PjPj+1,Pj和Pj+1的序號坐標(biāo)分別為Pj(k,m)和Pj+1(k,n).Step5.2.如果PjPj+1的x坐標(biāo)位于Pi-1Pi之間或與Pi-1Pi的一個端點相等,即a≤k≤b或b≤k≤a成立;若Pi-1Pi的y坐標(biāo)位于PjPj+1之間或與PjPj+1的一個端點相等,即m≤c≤n或n≤c≤m成立,則Pi-1Pi和PjPj+1必相交,設(shè)交點為R,其序號坐標(biāo)為R(k,c),置標(biāo)志位tag=1,表示該點為2條邊的交點.將該點插入到Pi-1Pi和PjPj+1上(如果交點為Pi-1Pi或PjPj+1的一個端點,則不用插入),轉(zhuǎn)Step5.1;否則,說明Pi-1Pi和PjPj+1必不相交,j=j+2,取下一條垂直邊轉(zhuǎn)Step5.1繼續(xù)判斷.Step6.令i=i+2,取下一條水平邊判斷,如果該邊未曾處理,轉(zhuǎn)Step4;否則,說明所有水平邊已經(jīng)處理完畢.4q鏈中pi+1的位置根據(jù)定義3,偏移多邊形的頂點連接次序和原布局空間的頂點連接次序是相同的,所以在偏移多邊形的不可行區(qū)域上各邊的方向必然與可行區(qū)域上各邊的方向相反,而且不同方向的區(qū)域之間以自交點為界,如圖5所示.當(dāng)分割區(qū)域的方向與原布局空間方向相同時,該區(qū)域必是可行域;否則,該區(qū)域必是由不可行域偏移出來的.確定可行域時,只需將方向為順時針的分割區(qū)域上的各頂點記錄下來.本文采用flag標(biāo)志位來標(biāo)記和區(qū)分可行域、非可行域上的點.根據(jù)偏移多邊形邊界頂點的連接次序,按順時針方向順序搜索偏移多邊形鏈,記錄偏移多邊形的外邊界所經(jīng)過的頂點,記邊界鏈為Q.算法3.獲得偏移多邊形的邊界多邊形頂點的算法Step1.取偏移多邊形的最左邊的y坐標(biāo)的最小頂點,設(shè)為Pi-1,作為Q鏈的第一點,記為Q1,Q1=Pi-1.Step2.取Pi-1的后繼Pi和前趨Pi-2,判斷它們的坐標(biāo)關(guān)系.如果Pi(x)和Pi-1(x)相同,說明Pi-1Pi方向是順時針方向,取Pi為Q鏈中的第二點Q2,記Q1和Q2的flag=1,表明它們?yōu)榭尚杏蛏系狞c,轉(zhuǎn)Step3.如果Pi-2(x)和Pi-1(x)相同,說明Pi-2Pi-1是逆時針方向,取Pi-2為Q鏈中的第二點Q2,記Q1和Q2的flag=0,表明它們?yōu)椴豢尚杏蛏系狞c,轉(zhuǎn)Step4.Step3.取Pi的后繼點Pi+1,如果Pi+1=Q1,說明已經(jīng)遍歷偏移多邊形的所有頂點,轉(zhuǎn)Step5;否則,判斷Pi+1是否為交點.如果不是交點(tag=0),置flag=1,并直接記入Q鏈中,i=i+1,轉(zhuǎn)Step3;如果是交點(tag=1),取與Pi+1重合的不相鄰邊上的交點Pj,判斷Pi與Pi+1(Pj)坐標(biāo)關(guān)系,以確定Q鏈中下一點.Step3.1.Pi(x)和Pi+1(x)相同,說明PiPi+1構(gòu)成垂直邊,判斷Pi(y)和Pi+1(y)的大小:若Pi(y)>Pi+1(y)(小于類似),則取Pi+1的后繼點(其前趨點為Pi,故不用考慮)、Pj的前趨點和后繼點的坐標(biāo)判斷.Q鏈中的下一點可能落在圖6所示的①,②方向上(即以Pi+1為中心,PiPi+1分別順時針旋轉(zhuǎn)90°,180°方向),不可能落在③方向上.首先判斷3個點中是否有點落在圖6所示①方向上,如果只有一個,則取該點為Q鏈中的下一點Qn;如果有2個,則取距Pi+1近的那個點為Qn;如果沒有,則?、诜较?判斷方法和①方向相同.下面根據(jù)Qn和交點Pi+1(或Pj)的連接關(guān)系(前趨還是后繼),確定如何標(biāo)記flag和取Q鏈中的下一點.有3種情況:a.若Qn是Pi+1的后繼點Pi+2,記Pi+1.flag=1,令i=i+1,轉(zhuǎn)Step3;b.若Qn是Pj的后繼點Pj+1,記Pj.flag=1,令i=j,轉(zhuǎn)Step3;c.若Qn是Pj的前趨點Pj-1,記Pj.flag=1,令i=j,轉(zhuǎn)Step4.Step3.2.Pi(y)和Pi+1(y)相同,處理方法和上面類似,不再贅述.Step4.取Pi的前趨點Pi-1,如果Pi-1=Q1,說明已經(jīng)遍歷偏移多邊形的所有頂點,轉(zhuǎn)Step5;否則,判斷Pi-1:如果不是交點,置flag=0,并直接記入Q鏈中,i=i-1,取新點重新判斷;否則,取與Pi-1重合的不相鄰邊上的交點Pk,判斷Pi與Pi-1(Pk)坐標(biāo)關(guān)系,以確定如何取Q鏈中下一點.Step4.1.Pi(x)和Pi-1(x)相同,說明PiPi-1構(gòu)成垂直邊.判斷Pi(y)和Pi-1(y)的大小:若Pi(y)>Pi-1(y)(小于類似),取Pi-1的前趨點(其后繼點為Pi,故不用考慮)、Pk的前趨點和后繼點等3個點的坐標(biāo)判斷,Q鏈中的下一點可能落在圖7所示的①,②方向上(即以Pi-1為中心,PiPi-1分別順時針旋轉(zhuǎn)90°,180°方向),不可能落在③方向上.首先判斷3個點中是否有點落在圖7所示①方向上,如果有一個,則取該點為Q鏈中的下一點Qn;如果有2個,則取距Pi-1近的那個點為Qn;如果沒有,則?、诜较?判斷方法和①方向上相同.下面根據(jù)Qn和交點Pi-1(或Pk)的連接關(guān)系(前趨還是后繼),確定如何標(biāo)記flag和取Q鏈中的下一點.有3種情況:a.若Qn是Pi-1的前趨點Pi-2,記Pi-1.flag=0,令i=i-1,轉(zhuǎn)Step4;b.若Qn是Pk的后繼點Pk+1,記Pk.flag=1,令i=k,轉(zhuǎn)Step3;c.若Qn是Pk的前趨點Pk-1,記Pk.flag=0,令i=k,轉(zhuǎn)Step4.Step4.2.Pi(y)和Pi-1(y)相同,處理方法和上面類似,不再贅述.Step5.輸出邊界多邊形頂點鏈,程序結(jié)束.最后,對偏移多邊形的邊界鏈進行搜索,取所有flag=1的點,即可獲得所求矩形在布局空間中的可行域.通過算法3處理圖5所示的布局空間及偏移多邊形,可以獲得圖8所示的邊界多邊形.取邊界多邊形鏈上的flag=1的所有頂點,它們所包圍的區(qū)域(圖中陰影部分)就是所求矩形在該布局空間中的可行域,即邊界多邊形中被自交點分割而方向和布局空間方向一致的區(qū)域.5算法的時間復(fù)雜度本文算法首先通過對原布局空間的頂點進行計算獲得偏移多邊形;然后求解偏移多邊形的自交點并搜索邊界多邊形而求得可行域.求解偏移多邊形只需遍歷布局空間的n個頂點并進行簡單的運算,其時間復(fù)雜度為O(n);求解偏移多邊形的自交點需分別遍歷所有的水平邊和垂直邊,需要(n2)×(n2)次運算,故其時間復(fù)雜度為(n24);搜索邊界多邊形