基于位圖的排樣多邊形最小包絡(luò)矩形求解

張鵬程,王春艷

(1.河北工程技術(shù)高等專科學(xué)校 電力工程系,河北 滄州 061001;2.滄州設(shè)備安裝技工學(xué)校,河北 滄州 061000)

排樣問題在機械制造、輕工、船舶、家具以及服裝等行業(yè)中應(yīng)用十分廣泛。二維排樣問題按形狀可分為矩形、任意多邊形排樣,按單元排列方式分固定方向的、可旋轉(zhuǎn)的等排樣,按有無人的參與分為自動排樣和輔助排樣。實際生產(chǎn)中大部分二維零件毛坯是任意多邊形,而單純矩形件毛坯只占很少一部分。通常將矩形之外的其余形狀圖形的排樣歸類為二維不規(guī)則排樣。

二維不規(guī)則排樣問題屬于最復(fù)雜的組合優(yōu)化問題之一,從數(shù)學(xué)計算復(fù)雜性理論看,排樣問題屬于具有最高計算復(fù)雜性的一類問題—— NP完全問題,因為存在計算上的“組合爆炸”,其求解十分困難。對于NP完全問題,目前還沒有找到解決該類問題的多項式算法[1],采用手工排樣很難得到利用率很高的排樣方案,即使采用計算機排樣,也必須開發(fā)出高效的排樣算法才能得到較好的排樣方案。

1 二維不規(guī)則零件排樣

二維不規(guī)則零件的排樣問題是尋找平面最優(yōu)布局的優(yōu)化問題,其數(shù)學(xué)模型可進(jìn)行如下描述[2]：

設(shè)有一塊矩形待排板材,長為 L,寬為W,待排的多邊形零件的面積分別為 S1,S2,…,Sn,n為多邊形零件的數(shù)量,則排樣方案的目標(biāo)函數(shù)為

其約束條件為 0≤i≤n,i為已經(jīng)完成排樣的零件數(shù)量,多邊形的頂點和各條邊不越界并且不相互重疊。

目前,對不規(guī)則排樣的處理方法大體上可以分兩類[3]：基于規(guī)則零件排樣處理的矩形近似法和不規(guī)則零件的直接處理法。以目前已有的算法來直接進(jìn)行二維不規(guī)則零件排樣,一般效果不佳且耗時較長。矩形近似法又稱矩形包絡(luò)法,是找到單個不規(guī)則零件或者多個不規(guī)則零件的組合的近似包絡(luò)矩形,然后用矩形件代替原不規(guī)則零件進(jìn)行排樣,如圖1所示,從而把不規(guī)則排樣問題簡化為矩形排樣問題[4]。

圖1 二維排樣圖形的外包絡(luò)矩形

2 零件的位圖表示

矩形包絡(luò)法將多邊形排樣問題轉(zhuǎn)化為矩形排樣問題進(jìn)行處理,簡化了排樣圖形描述(不規(guī)則幾何圖形描述復(fù)雜度大大高于矩形),判交和碰靠過程只需記錄已排零件有關(guān)頂點的信息(有關(guān)頂點的信息即為邊界的約束信息),這樣,插入新的排樣圖形時操作簡單,計算量小。

文中利用位圖方式來描述排樣多邊形零件。采用位圖而非輪廓矢量信息來描述排樣零件圖形,其優(yōu)勢在于[5]：在整體上,基于位圖的靠接在時間上優(yōu)于基于輪廓靠接;位圖文件通過象素的屬性、顏色和灰度值描述圖像,相對于用矢量描述的圖形而言,其直接存取方式簡化了信息的存儲過程,而且使得基于位圖的操作相對簡便;排樣不受圖形凹凸的限制,更適合于形狀怪異、空洞較多的圖形排樣。

3 最小包絡(luò)矩形求解

3.1 位圖多邊形邊界頂點的確定

在位圖的存貯信息中,沒有頂點、邊等矢量信息,文中采用拐點檢測的方法來獲得頂點信息,以此來設(shè)計外包矩形集算法。

設(shè) t時刻點(xt,yt)處于位圖(如圖2)中位置 0,為了查找和確定位圖中的邊界像素點,從位置 1開始依圖中數(shù)字所示的方向和順序?qū)χ車南袼攸c進(jìn)行考察,搜索第一個非背景像素所在的位置(xi+1,yi+1),若(xi-1,yi-1)、(xi,yi)、(xi+1,yi+1)三點不在一條直線上,則記為拐點 Tj(xj,yj),位圖所有拐點的集合記為 T。

如圖2所示,取位圖中的三個像素點：若(xi-1,yi-1)在位置 5,(xi,yi)在位置 0,(xi+1,yi+1)在位置 2,則記(xi,yi)為拐點;若(xi+1,yi+1)在位置 1則說明是非拐點。

圖2 搜索拐點時依次搜索的像素位置圖

3.2 最小外包絡(luò)矩求解思想

設(shè) G(θ)為圖形 G旋轉(zhuǎn)θ后得到的圖形,z(t)=x(t)+iy(t),(0＜t＜1),z(0)=z(1),為封閉曲線,旋轉(zhuǎn)θ后的坐標(biāo)與原坐標(biāo)之間的關(guān)系為：

在求解過程中,如選定的θ值越小,其求解得到的多邊形的最小包絡(luò)矩形越精確,但所耗費的計算時間也越長;如果選定的θ值較大,則可能會丟掉θ值區(qū)間上的最優(yōu)解。在實際求解過程中,應(yīng)根據(jù)多邊形的形狀和拐點的數(shù)量進(jìn)行權(quán)衡選優(yōu),以求在較短的時間內(nèi)獲得最小的包絡(luò)矩形。

3.3 外包絡(luò)矩形覆蓋率

采用包絡(luò)矩形法求解多邊形排樣問題,是利用矩形代替多邊形以完成全部排樣計算。由于矩形的面積一般要大于多邊形的面積(只有多邊形也為矩形時面積相等),故該方法不可避免會產(chǎn)生一定量的材料浪費,在多邊形的眾多包絡(luò)矩形中,只有最小包絡(luò)矩形與其面積差值最小。

為了評定矩形代替多邊形進(jìn)行排樣的效果,將多邊形位圖面積 Sraw與位圖最小外包絡(luò)矩形面積 Smabr的比值定義為位圖對外包絡(luò)矩形的覆蓋率,即d=Sraw/Smabr。顯然 0＜d≤1,d越大多邊形越接近外包絡(luò)矩形,d=1時位圖本身即為矩形形狀,而當(dāng)d的值低于 0.7時,為了避免材料浪費過多,應(yīng)首先將多邊形零件進(jìn)行拼接和組合,然后再求解其整體的外包絡(luò)矩形以提高覆蓋率d。

3.4 最小包絡(luò)矩形的算法流程

利用位圖表示多邊形時,其最小包絡(luò)矩形計算步驟如下：

Step1：輸入零件位圖G,將其轉(zhuǎn)變?yōu)槎祱DB(G),并確定其邊界 E(G)。

Step2：計算邊界拐點 T(G)。

Step3：以零件位圖的拐點集 T為依據(jù),計算多邊形重心O。

Step4：確定角度增量θ,將多邊形繞其重心旋轉(zhuǎn),每次旋轉(zhuǎn)角度均為θ,求得其對應(yīng)狀態(tài)下多邊形的包絡(luò)矩形 Rθ,獲得外包絡(luò)矩形集 R。

Step5：旋轉(zhuǎn)角度 滿 180°后 ,對各次的包絡(luò)矩形 Rθ進(jìn)行比較,從中取面積最小的矩形作為最小包絡(luò)矩形。

4 應(yīng)用實例及分析

利用 MATLAB編程[6]實現(xiàn)文中所給零件位圖的最小包絡(luò)矩形的求解。為了檢測文中方法的可行性及優(yōu)劣,取兩種不同類種的多邊形(一個直線多邊形和一個任意多邊形)進(jìn)行計算,獲得的多邊形最小包絡(luò)矩形分別如圖3和圖4所示,其求解結(jié)果數(shù)據(jù)如表 1所示。表 1中 Sraw為排樣多邊形零件位圖面積,Smabr為多邊形最小包絡(luò)矩形面積,length為包絡(luò)矩形的寬,height為包絡(luò)矩形的高,d為位圖在最小包絡(luò)矩形中的覆蓋率。

圖3 直線多邊形及其最小包絡(luò)矩形

圖4 多邊形及其最小包絡(luò)矩形比較圖

表1 實例中多邊形及其最小包絡(luò)矩形結(jié)果數(shù)據(jù)

5 結(jié)論

采用位圖表示排樣多邊形有利于對圖形進(jìn)行編碼,快速的完成多邊形圖形的聚類、歸類等相關(guān)運算,可以明顯減少排樣中多邊形靠碰時間計算,從而完成高效的多邊形二維零件自動排樣系統(tǒng)的設(shè)計。實例測算表明,文中的方法可以快速有效地獲得基于位圖表示的多邊形排樣零件的最小包絡(luò)矩形,從而為下一步二維多邊形排樣設(shè)計打下良好的基礎(chǔ)。

[1]賈丹,董方敏.二維優(yōu)化排樣問題研究[J].計算機系統(tǒng)應(yīng)用.2008(7)：21-24.

[2]靳旭玲.二維不規(guī)則排樣問題的研究 [D].濟南：山東科技大學(xué),2003.

[3]黃紅兵,蔣望東.二維不規(guī)則零件排樣問題研究[J].廣西科學(xué)院學(xué)報,2004,20(4)：225-227.

[4]查建中,唐曉君,陸一平.布局及布置設(shè)計問題求解自動化的理論與方法綜述 [J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2002,14(8)：705-712.

[5]宋亞男,楊宜民,葉家瑋,等.排樣圖形預(yù)處理中的幾個實用算法 [J].系統(tǒng)工程與電子技術(shù),2005,27(6)：1102-1104.

[6]王志廣.MATLAB工程計算 [M].北京：清華大學(xué)出版社,2008.