基于最小包絡(luò)矩形的不規(guī)則凸多邊形的三角形處理算法

王淑青 陳 軍 潘 健 張子蓬 袁曉輝 何 莉

1(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院 湖北 武漢 430068)2(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430068)3(華中科技大學(xué)水電與數(shù)字化工程學(xué)院 湖北 武漢 430074)

?

基于最小包絡(luò)矩形的不規(guī)則凸多邊形的三角形處理算法

王淑青1陳 軍1潘 健1張子蓬2袁曉輝3何 莉1

1(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院 湖北 武漢 430068)2(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430068)3(華中科技大學(xué)水電與數(shù)字化工程學(xué)院 湖北 武漢 430074)

針對(duì)最小矩形包絡(luò)算法處理不規(guī)則多邊形時(shí)包絡(luò)率低并造成板材使用率低的現(xiàn)象，在最小矩形包絡(luò)算法基礎(chǔ)上，提出三角形處理法。通過(guò)包絡(luò)求解、分類(lèi)、組合三個(gè)環(huán)節(jié)將不規(guī)則凸多邊形轉(zhuǎn)化成矩形，并采用遺傳算法及最低水平輪廓算法進(jìn)行矩形排樣。通過(guò)對(duì)比實(shí)驗(yàn)，驗(yàn)證了三角形處理算法提高板材使用率的有效性。

三角形處理算法 最小包絡(luò)矩形 矩形排樣 遺傳算法

0 引 言

自動(dòng)排樣技術(shù)在建筑、航空等各工業(yè)領(lǐng)域中廣泛應(yīng)用。不規(guī)則多邊形由于形狀與大小相對(duì)復(fù)雜，其排樣過(guò)程比規(guī)則多邊形困難許多，因而成為學(xué)者們重點(diǎn)研究方向。常見(jiàn)思路有以下幾種:1)臨界多邊形法NFP，此方法能有效解決不規(guī)則多邊形排樣問(wèn)題，但其計(jì)算復(fù)雜，效率較低[1,3]；2)碰撞算法，該算法通常求解時(shí)間比較長(zhǎng)，且不容易產(chǎn)生最優(yōu)解[2,5]；3)轉(zhuǎn)化為規(guī)則圖形[3-5]。

為了簡(jiǎn)化不規(guī)則的排樣，工業(yè)上通常會(huì)把不規(guī)則多邊形轉(zhuǎn)化成矩形，然后進(jìn)行矩形排樣，通常使用最小矩形包絡(luò)算法[4]。該算法具有操作簡(jiǎn)單方便、復(fù)雜度低的優(yōu)點(diǎn)，其缺點(diǎn)在于包絡(luò)時(shí)會(huì)產(chǎn)生大量空白區(qū)域，造成板材的浪費(fèi)[5]。文獻(xiàn)[6]在最小矩形包絡(luò)算法基礎(chǔ)上研究了多邊形兩兩組合的算法，該方法能有效提高板材利用率，但比較復(fù)雜，計(jì)算量較大。少量文獻(xiàn)研究了圓形件的排樣，如文獻(xiàn)[7]采用了圓形包絡(luò)算法與矩形排樣相結(jié)合，但并不能有效提高板材使用率。

本文針對(duì)最小矩形包絡(luò)算法的缺點(diǎn)，在此基礎(chǔ)上提出三角形處理算法對(duì)不規(guī)則凸多邊形進(jìn)行預(yù)處理，從而到達(dá)既簡(jiǎn)化排樣又提高板材利用率的目的；并采用遺傳算法及最低水平輪廓布局算法進(jìn)行矩形排樣。

1 最小矩形包絡(luò)算法

能夠?qū)⒉灰?guī)則圖形所有點(diǎn)和線全部包圍的矩形稱(chēng)為包絡(luò)矩形。每個(gè)不規(guī)則多邊形有無(wú)窮多個(gè)包絡(luò)矩形，其中面積最小的稱(chēng)為最小包絡(luò)矩形[3]。

假定某凸多邊形的邊按逆時(shí)針排列依次為l1，l2，…，li，…,ln，其最小矩形包絡(luò)算法步驟如下:

Step1 選擇凸多邊形一條邊li，計(jì)算此邊與x軸的夾角;

Step2 利用坐標(biāo)轉(zhuǎn)換公式，旋轉(zhuǎn)凸多邊形，使li與x軸平行;

Step3 利用式(1)計(jì)算旋轉(zhuǎn)后各頂點(diǎn)的坐標(biāo)，找出xmin、xmax、ymin、ymax；

Step4 利用式(2)計(jì)算包絡(luò)矩陣長(zhǎng)L、寬W以及面積S。

重復(fù)Step1-Step4，直至遍歷完凸多邊形每一條邊，得到n個(gè)包絡(luò)矩形，并選擇面積最小的作為最小包絡(luò)矩形。

x′=x+d-d×cosθ

(1)

y′=y-d×sinθ

(2)

其中，(x,y)為坐標(biāo)轉(zhuǎn)換前各點(diǎn)坐標(biāo)，(x′,y′)為坐標(biāo)轉(zhuǎn)換后各點(diǎn)坐標(biāo)。d為坐標(biāo)轉(zhuǎn)換前各點(diǎn)到旋轉(zhuǎn)中心點(diǎn)(x0,y0)的距離。

L=xmax-xmin

(3)

W=ymax-ymin

(4)

S=WL

(5)

最小矩形包絡(luò)算法優(yōu)點(diǎn)是操作簡(jiǎn)單、時(shí)間復(fù)雜度低、易于實(shí)現(xiàn)，但缺點(diǎn)在于待排樣圖形的面積與包絡(luò)矩形的面積之比較小，排樣圖形之間空隙大，造成板材浪費(fèi)。

2 三角形處理算法

2.1 三角形處理算法

為了簡(jiǎn)便排樣同時(shí)又提高板材利用率，本文在最小包絡(luò)矩形基礎(chǔ)上提出了三角形處理算法。該算法主要包括四個(gè)環(huán)節(jié):包絡(luò)圖形求解、包絡(luò)方法的選擇、包絡(luò)三角形的分類(lèi)、同類(lèi)三角形的組合。流程如圖1所示。

圖1 三角形處理算法流程圖

三角形處理后得到的矩形，將進(jìn)行矩形排樣。該過(guò)程將采用遺傳算法和最低水平輪廓布局算法對(duì)所有轉(zhuǎn)換成矩形的凸多邊形整體排樣。

2.2 包絡(luò)三角形的求解

包絡(luò)圖形面積較大是最小矩形包絡(luò)算法造成材料浪費(fèi)的主要原因。本文提出了使用三角形包絡(luò)不規(guī)則凸多邊形的方法，使包絡(luò)圖形面積更小。

假定某個(gè)多邊形有n個(gè)頂點(diǎn)，其坐標(biāo)按逆時(shí)針排列依次為(x1,y1)，(x2,y2)，…，(xn,yn)，邊分為l1，l2，…，li，…，ln。其三角形包絡(luò)的步驟如下:

Step1 計(jì)算不規(guī)則多邊形頂點(diǎn)個(gè)數(shù)n，若n>3，跳至下步驟，若n=3，包絡(luò)三角形已經(jīng)生成，停止于此步驟；

Step2 求得不規(guī)則多邊形的最短邊li，將此邊相鄰的兩條邊li-1，li+1延長(zhǎng)，相交于一點(diǎn)P，則P將成為包絡(luò)三角形的一個(gè)頂點(diǎn)，同時(shí)刪除最短邊。重復(fù)Step1-Step2。

圖2 三角形包絡(luò)效果圖

實(shí)驗(yàn)證明，只有一大部分不規(guī)則凸多邊形，三角形包絡(luò)算法比最小矩形包絡(luò)算法的包絡(luò)圖形面積更小。因此，對(duì)于每一個(gè)不規(guī)則凸多邊形，本文將分別使用最小矩形包絡(luò)算法與三角形包絡(luò)算法包絡(luò)該凸多邊形，計(jì)算包絡(luò)矩形面積Sa與包絡(luò)三角形面積Sb。若Sa>Sb，則該凸多邊形使用最小矩形包絡(luò)算法；若Sa

2.3 余弦向量分類(lèi)三角形

為了大小及形狀相似的包絡(luò)三角形以最簡(jiǎn)單方式組合拼接成新圖形進(jìn)行排樣，將采用余弦向量法對(duì)包絡(luò)三角形進(jìn)行分類(lèi)。包絡(luò)三角形的特征向量表示形式如下：

(6)

其中:

(7)

(8)

(9)

(10)

其中，c1、c2、c3分別表示包絡(luò)三角形最長(zhǎng)邊、次長(zhǎng)邊、最短邊。

定義1特征向量相似度:用來(lái)衡量?jī)蓚€(gè)特征向量的相似度，本文選取為兩條射線之間夾角余弦值[8]。

(11)

P值越大，兩個(gè)特征向量夾角就越小，方向就越一致，特征向量相似度越大，兩個(gè)包絡(luò)三角形之間形狀大小差異也就越小。當(dāng)P>0時(shí)，說(shuō)明兩個(gè)包絡(luò)三角形形狀大小有相似之處；當(dāng)P<0時(shí)，說(shuō)明兩個(gè)包絡(luò)三角形之間形狀大小差異性較大[8]。

在使用余弦定理求解之前，對(duì)所有包絡(luò)三角形特征向量組成的矩陣進(jìn)行歸一化處理。求解結(jié)果表明，選取分類(lèi)閾值為0.9時(shí)分類(lèi)效果比較好。

2.4 同類(lèi)三角形的組合

在所有包絡(luò)三角形分類(lèi)之后，本文提出一種簡(jiǎn)單易操作組合方式，將這些大小形狀相同的三角形組合成新圖形，并將新圖形包絡(luò)成最小矩形用于矩形排樣。以下為同類(lèi)三角形組合的具體步驟:

Step1 找出同一類(lèi)別中每個(gè)包絡(luò)三角形最短邊、次短邊、最長(zhǎng)邊，并分別求出這些最短邊的最大值c1、次短邊最大值c2、最長(zhǎng)邊最大值c3。

Step2 用(c1，c2，c3)三條邊組成的三角形包絡(luò)這一類(lèi)別中所有不規(guī)則凸多邊形。

Step3 用對(duì)頭雙排方式組合，將大小形狀相同的三角形使用翻轉(zhuǎn)拼接在一起，組合成新圖形。組合后的圖形將是三角形、梯形、平行四邊形三種圖形其中一種。

Step4 將組合后的新圖形包絡(luò)成最小矩形，用于同直接使用最小矩形包絡(luò)算法得到的矩形一起進(jìn)行矩形排樣。

3 矩形排樣

不規(guī)則多邊形經(jīng)過(guò)處理轉(zhuǎn)化成矩形后，對(duì)其進(jìn)行矩形排樣。矩形排樣需考慮“矩形排樣定序”和“矩形排放布局”兩個(gè)問(wèn)題。本文分別采用“遺傳算法”[9-12]和“最低水平輪廓算法”[11]解決這兩個(gè)問(wèn)題。其算法流程如圖3所示。

圖3 矩形排樣流程圖

(1) 編碼

假設(shè)有標(biāo)號(hào)為1～n的待排樣矩形,將標(biāo)號(hào)1～n按照隨機(jī)順序組合成一個(gè)序列,序列中每個(gè)數(shù)字的正負(fù)號(hào)隨機(jī)生成。

(2) 解碼

本文采用最低水平輪廓線算法對(duì)染色體中每一個(gè)基因代表的矩形進(jìn)行排樣。每一個(gè)待排圖形,先找出能放下該圖形的輪廓,再在這些輪廓中挑選最下最左的輪廓。若是沒(méi)有長(zhǎng)度大于待排矩形寬的輪廓,則90°旋轉(zhuǎn)待排矩形,用旋轉(zhuǎn)前的方法選擇適合的輪廓線排放。如果90°旋轉(zhuǎn)后也沒(méi)有適合輪廓,則將矩形放置于板材未排區(qū)域最左最下處。

(3) 適應(yīng)度函數(shù)

對(duì)于底邊長(zhǎng)度一定的矩形板材,排樣區(qū)域高度越小,則說(shuō)明排樣效果越好。故取適應(yīng)度函數(shù)為:

(12)

(4) 選擇

適應(yīng)度越高的編碼,排樣效果越好,越應(yīng)該選擇遺傳到下一代。本文采用賭輪盤(pán)的方法選擇存留幾率大的染色體編碼,不經(jīng)過(guò)變異、組合操作,直接保存至下一代染色體。

(5) 變異

對(duì)于賭輪盤(pán)選擇操作中淘汰的染色體,將進(jìn)行染色體變異的進(jìn)化行為。隨機(jī)產(chǎn)生兩個(gè)[0,1]的數(shù)字P1和P2,若P1>pb1,則隨機(jī)選擇染色體中的兩個(gè)數(shù)字,并將兩個(gè)數(shù)字間的數(shù)字倒置,逆序放置；若P2>pb2,則改變基因的正負(fù)號(hào)。其中pb1、pb2為變異算子。

(6) 交叉

隨機(jī)產(chǎn)生一個(gè)[0,1]的數(shù)字P3,若P3>pc,則隨機(jī)選擇賭輪盤(pán)中兩個(gè)淘汰的染色體,取其相同部分基因進(jìn)行交換。如果交換后有重復(fù)數(shù)字,則使用重復(fù)數(shù)字的對(duì)應(yīng)位數(shù)字進(jìn)行調(diào)整，直到?jīng)]有重復(fù)數(shù)字。如染色體1234與染色體4312第2～3位交叉后為1312與4232，調(diào)整后的子代為2314與4231，其中pc為交叉算子。

4 實(shí)驗(yàn)結(jié)果

4.1 凸多邊形矩形包絡(luò)和三角形包絡(luò)對(duì)比

使用MATLAB 7.0實(shí)現(xiàn)算法，隨機(jī)選取了十個(gè)凸多邊形，分別采用最小矩形包絡(luò)和三角形包絡(luò)，得到兩種包絡(luò)方法的占有率，實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 矩形包絡(luò)與三角形包絡(luò)對(duì)比數(shù)據(jù)

由表1可以看出，部分凸多邊形包絡(luò)三角形比最小包絡(luò)矩形面積小，從而比最小矩形包絡(luò)更節(jié)省材料；但是形狀接近平行四邊形的凸多邊形使用最小矩形包絡(luò)法(如編號(hào)2、6、ee8樣本)的包絡(luò)圖形面積更小。

因此本文對(duì)每個(gè)待排樣凸多邊形分別進(jìn)行最小矩形包絡(luò)和三角形包絡(luò)，算出兩種方法的包絡(luò)圖形面積，然后選擇包絡(luò)圖形面積小的方法進(jìn)行包絡(luò)和處理。

4.2 整體排樣結(jié)果比較

為了檢驗(yàn)三角形處理算法的效果，本文采用遺傳算法和最低水平輪廓算法進(jìn)行矩形排樣，分別使用三角形處理算法和最小矩形包絡(luò)算法將不規(guī)則凸多邊形轉(zhuǎn)換成矩形。

本文采用實(shí)驗(yàn)樣本是如表1所示隨機(jī)產(chǎn)生的10種不規(guī)則凸多邊形，每種多邊形個(gè)數(shù)如表2所示。

表2 矩形排樣樣本

圖4與圖5分別為使用最小矩形包絡(luò)算法處理后得到的矩形排樣效果圖以及適應(yīng)度函數(shù)值變化曲線圖。圖6與圖7分別為使用三角形處理算法后得到的矩形排樣效果圖以及適應(yīng)度函數(shù)值變化曲線圖。

三角形處理法組合環(huán)節(jié)中，會(huì)將同一類(lèi)的幾個(gè)三角形拼接組合后，再進(jìn)行最小矩形包絡(luò)。因此，實(shí)驗(yàn)樣本經(jīng)過(guò)三角形算法處理的矩形(如圖4所示)和直接經(jīng)過(guò)最小包絡(luò)矩形算法處理的矩形(如圖6所示)并不相同。三角形處理算法得到的矩形個(gè)數(shù)更少，面積更大。

圖4 矩形算法排樣效果 圖5 矩形排樣適應(yīng)度函數(shù)

圖6 三角形算法排樣效果 圖7 三角形排樣適應(yīng)度函數(shù)

由圖4至圖7可以看出，寬度為400單位長(zhǎng)度的板材，三角形處理算法處理后的矩形排樣板材使用高度為260單位長(zhǎng)度，最小矩形排樣算法處理后矩形排樣板材使用高度為280單位長(zhǎng)度。三角形處理算法的板材使用面積是最小矩形包絡(luò)算法的91%，這在工業(yè)上將節(jié)約大量的成本。三角形處理算法能在最小矩形包絡(luò)算法基礎(chǔ)上提高板材使用率。

5 結(jié) 語(yǔ)

最小矩形包絡(luò)算法處理不規(guī)則多邊形簡(jiǎn)單易操作，但待排樣圖形包絡(luò)率低，從而造成板材浪費(fèi)。本文提出三角形處理算法，將待排樣不規(guī)則凸多邊形有選擇性地進(jìn)行三角形包絡(luò)，分類(lèi)組合成新圖形，再使用最小矩形包絡(luò)算法包絡(luò)。結(jié)合遺傳算法和最低水平輪廓算法進(jìn)行矩形排樣，在最小矩形包絡(luò)算法基礎(chǔ)上使板材利用率提高。后期還可以對(duì)凹多邊形的三角形包絡(luò)以及三角形分類(lèi)時(shí)特征向量選擇進(jìn)行研究。

[1] 楊衛(wèi)波,王萬(wàn)良.改進(jìn)臨界多邊形生成算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(1):32-35.

[2] 梁利東,鐘相強(qiáng).碰靠定位算法在不規(guī)則件排樣優(yōu)化中的應(yīng)用研究[J].中國(guó)機(jī)械工程,2013,24(23):3191-3195.

[3] 郭怡,李輝.基于蟻群算法的矩形件排樣問(wèn)題研究[J].中國(guó)農(nóng)機(jī)化學(xué)報(bào),2014,35(4):250-252，256.

[4] 陳小雨.二維不規(guī)則零件自動(dòng)優(yōu)化排樣算法的研究[D].哈爾濱：哈爾濱理工大學(xué),2012.

[5] 程暉.基于遺傳模擬退火的服裝排料算法的研究[D].上海：東華大學(xué)，2012.

[6] Elkeran A.A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J].European Journal of Operational Research,2013,231(3):757-769.

[7] 梅穎.船體建造板材套料系統(tǒng)中排樣優(yōu)化算法與碰靠技術(shù)研究[D].廣州：華南理工大學(xué),2010.

[8] 吳軍.數(shù)學(xué)之美[M].北京：人民郵電出版社,2012.

[9] 郭瑞峰.基于病毒進(jìn)化遺傳算法的二維不規(guī)則圖形排樣[D].廣州：廣東工業(yè)大學(xué),2014.

[10] 劉璐.基于遺傳算法的鈑金排樣系統(tǒng)研究[D].西安：西安工業(yè)大學(xué),2014.

[11] 王淑青,雷蕾,曾仕琦,等.基于改進(jìn)遺傳算法的二維圖形優(yōu)化排樣方法[J].工業(yè)控制計(jì)算機(jī),2012,25(12):51-53.

[12] 吳忻生,吳超成,劉海明.基于改進(jìn)遺傳算法的矩形件排樣優(yōu)化算法[J].制造業(yè)自動(dòng)化,2013,35(10):55-58，115.

[13] Domovic D,Rolich T,Grundler D,et al.Algorithms for 2D nesting problem based on the no-fit polygon[C]//Information and Communication Technology,Electronics and Microelectronics (MIPRO),2014 37th International Convention on.IEEE,2014:1094-1099.

A TRIANGLE PROCESSING ALGORITHM FOR IRREGULAR CONVEX POLYGON BASED ON SMALLEST ENVELOPE RECTANGLE

Wang Shuqing1Chen Jun1Pan Jian1Zhang Zipeng2Yuan Xiaohui3He Li1

1(School of Electrical and Electronic Engineering，Hubei University of Technology，Wuhan 430068，Hubei,China)2(School of Computer，Hubei University of Technology，Wuhan 430068，Hubei,China)3(School of Hydropower and Information Engineering，Huazhong University of Science and Technology，Wuhan 430074，Hubei,China)

When dealing with irregular polygons,the smallest rectangle envelope algorithm has low envelopment rate,this causes low sheet utilisation rate.To solve the problem,this paper puts forward the triangular processing algorithm based on the smallest rectangle envelope method,it converts irregular convex polygon into a rectangle through three links of envelope calculation,classification and composition.Moreover,it uses genetic algorithm and minimum-level horizontal contour algorithm to operate rectangular layout.Contrast experimental results verify the effectiveness of the proposed algorithm in increasing the sheet utilisation rate.

Triangular processing algorithm Smallest envelope rectangle Rectangular layout Genetic algorithm

2015-06-02。國(guó)家自然科學(xué)基金項(xiàng)目(51379080,51309094,61473116)。王淑青，教授，主研領(lǐng)域：智能控制，系統(tǒng)建模。陳軍，碩士生。潘健，副教授。張子蓬，副教授。袁曉輝，教授。何莉，副教授。

TP3

A

10.3969/j.issn.1000-386x.2016.11.046