基于最小包絡矩形的不規則凸多邊形的三角形處理算法

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

1(湖北工業大學電氣與電子工程學院 湖北 武漢 430068)2(湖北工業大學計算機學院 湖北 武漢 430068)3(華中科技大學水電與數字化工程學院 湖北 武漢 430074)

?

基于最小包絡矩形的不規則凸多邊形的三角形處理算法

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

1(湖北工業大學電氣與電子工程學院 湖北 武漢 430068)2(湖北工業大學計算機學院 湖北 武漢 430068)3(華中科技大學水電與數字化工程學院 湖北 武漢 430074)

針對最小矩形包絡算法處理不規則多邊形時包絡率低并造成板材使用率低的現象，在最小矩形包絡算法基礎上，提出三角形處理法。通過包絡求解、分類、組合三個環節將不規則凸多邊形轉化成矩形，并采用遺傳算法及最低水平輪廓算法進行矩形排樣。通過對比實驗，驗證了三角形處理算法提高板材使用率的有效性。

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

0 引 言

自動排樣技術在建筑、航空等各工業領域中廣泛應用。不規則多邊形由于形狀與大小相對復雜，其排樣過程比規則多邊形困難許多，因而成為學者們重點研究方向。常見思路有以下幾種:1)臨界多邊形法NFP，此方法能有效解決不規則多邊形排樣問題，但其計算復雜，效率較低[1,3]；2)碰撞算法，該算法通常求解時間比較長，且不容易產生最優解[2,5]；3)轉化為規則圖形[3-5]。

為了簡化不規則的排樣，工業上通常會把不規則多邊形轉化成矩形，然后進行矩形排樣，通常使用最小矩形包絡算法[4]。該算法具有操作簡單方便、復雜度低的優點，其缺點在于包絡時會產生大量空白區域，造成板材的浪費[5]。文獻[6]在最小矩形包絡算法基礎上研究了多邊形兩兩組合的算法，該方法能有效提高板材利用率，但比較復雜，計算量較大。少量文獻研究了圓形件的排樣，如文獻[7]采用了圓形包絡算法與矩形排樣相結合，但并不能有效提高板材使用率。

本文針對最小矩形包絡算法的缺點，在此基礎上提出三角形處理算法對不規則凸多邊形進行預處理，從而到達既簡化排樣又提高板材利用率的目的；并采用遺傳算法及最低水平輪廓布局算法進行矩形排樣。

1 最小矩形包絡算法

能夠將不規則圖形所有點和線全部包圍的矩形稱為包絡矩形。每個不規則多邊形有無窮多個包絡矩形，其中面積最小的稱為最小包絡矩形[3]。

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

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

Step2 利用坐標轉換公式，旋轉凸多邊形，使li與x軸平行;

Step3 利用式(1)計算旋轉后各頂點的坐標，找出xmin、xmax、ymin、ymax；

Step4 利用式(2)計算包絡矩陣長L、寬W以及面積S。

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

x′=x+d-d×cosθ

(1)

y′=y-d×sinθ

(2)

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

L=xmax-xmin

(3)

W=ymax-ymin

(4)

S=WL

(5)

最小矩形包絡算法優點是操作簡單、時間復雜度低、易于實現，但缺點在于待排樣圖形的面積與包絡矩形的面積之比較小，排樣圖形之間空隙大，造成板材浪費。

2 三角形處理算法

2.1 三角形處理算法

為了簡便排樣同時又提高板材利用率，本文在最小包絡矩形基礎上提出了三角形處理算法。該算法主要包括四個環節:包絡圖形求解、包絡方法的選擇、包絡三角形的分類、同類三角形的組合。流程如圖1所示。

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

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

2.2 包絡三角形的求解

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

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

Step1 計算不規則多邊形頂點個數n，若n>3，跳至下步驟，若n=3，包絡三角形已經生成，停止于此步驟；

Step2 求得不規則多邊形的最短邊li，將此邊相鄰的兩條邊li-1，li+1延長，相交于一點P，則P將成為包絡三角形的一個頂點，同時刪除最短邊。重復Step1-Step2。

圖2 三角形包絡效果圖

實驗證明，只有一大部分不規則凸多邊形，三角形包絡算法比最小矩形包絡算法的包絡圖形面積更小。因此，對于每一個不規則凸多邊形，本文將分別使用最小矩形包絡算法與三角形包絡算法包絡該凸多邊形，計算包絡矩形面積Sa與包絡三角形面積Sb。若Sa>Sb，則該凸多邊形使用最小矩形包絡算法；若Sa

2.3 余弦向量分類三角形

為了大小及形狀相似的包絡三角形以最簡單方式組合拼接成新圖形進行排樣，將采用余弦向量法對包絡三角形進行分類。包絡三角形的特征向量表示形式如下：

(6)

其中:

(7)

(8)

(9)

(10)

其中，c1、c2、c3分別表示包絡三角形最長邊、次長邊、最短邊。

定義1特征向量相似度:用來衡量兩個特征向量的相似度，本文選取為兩條射線之間夾角余弦值[8]。

(11)

P值越大，兩個特征向量夾角就越小，方向就越一致，特征向量相似度越大，兩個包絡三角形之間形狀大小差異也就越小。當P>0時，說明兩個包絡三角形形狀大小有相似之處；當P<0時，說明兩個包絡三角形之間形狀大小差異性較大[8]。

在使用余弦定理求解之前，對所有包絡三角形特征向量組成的矩陣進行歸一化處理。求解結果表明，選取分類閾值為0.9時分類效果比較好。

2.4 同類三角形的組合

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

Step1 找出同一類別中每個包絡三角形最短邊、次短邊、最長邊，并分別求出這些最短邊的最大值c1、次短邊最大值c2、最長邊最大值c3。

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

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

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

3 矩形排樣

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

圖3 矩形排樣流程圖

(1) 編碼

假設有標號為1～n的待排樣矩形,將標號1～n按照隨機順序組合成一個序列,序列中每個數字的正負號隨機生成。

(2) 解碼

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

(3) 適應度函數

對于底邊長度一定的矩形板材,排樣區域高度越小,則說明排樣效果越好。故取適應度函數為:

(12)

(4) 選擇

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

(5) 變異

對于賭輪盤選擇操作中淘汰的染色體,將進行染色體變異的進化行為。隨機產生兩個[0,1]的數字P1和P2,若P1>pb1,則隨機選擇染色體中的兩個數字,并將兩個數字間的數字倒置,逆序放置；若P2>pb2,則改變基因的正負號。其中pb1、pb2為變異算子。

(6) 交叉

隨機產生一個[0,1]的數字P3,若P3>pc,則隨機選擇賭輪盤中兩個淘汰的染色體,取其相同部分基因進行交換。如果交換后有重復數字,則使用重復數字的對應位數字進行調整，直到沒有重復數字。如染色體1234與染色體4312第2～3位交叉后為1312與4232，調整后的子代為2314與4231，其中pc為交叉算子。

4 實驗結果

4.1 凸多邊形矩形包絡和三角形包絡對比

使用MATLAB 7.0實現算法，隨機選取了十個凸多邊形，分別采用最小矩形包絡和三角形包絡，得到兩種包絡方法的占有率，實驗數據如表1所示。

表1 矩形包絡與三角形包絡對比數據

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

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

4.2 整體排樣結果比較

為了檢驗三角形處理算法的效果，本文采用遺傳算法和最低水平輪廓算法進行矩形排樣，分別使用三角形處理算法和最小矩形包絡算法將不規則凸多邊形轉換成矩形。

本文采用實驗樣本是如表1所示隨機產生的10種不規則凸多邊形，每種多邊形個數如表2所示。

表2 矩形排樣樣本

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

三角形處理法組合環節中，會將同一類的幾個三角形拼接組合后，再進行最小矩形包絡。因此，實驗樣本經過三角形算法處理的矩形(如圖4所示)和直接經過最小包絡矩形算法處理的矩形(如圖6所示)并不相同。三角形處理算法得到的矩形個數更少，面積更大。

圖4 矩形算法排樣效果 圖5 矩形排樣適應度函數

圖6 三角形算法排樣效果 圖7 三角形排樣適應度函數

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

5 結 語

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

[1] 楊衛波,王萬良.改進臨界多邊形生成算法[J].計算機工程與應用,2013,49(1):32-35.

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

[3] 郭怡,李輝.基于蟻群算法的矩形件排樣問題研究[J].中國農機化學報,2014,35(4):250-252，256.

[4] 陳小雨.二維不規則零件自動優化排樣算法的研究[D].哈爾濱：哈爾濱理工大學,2012.

[5] 程暉.基于遺傳模擬退火的服裝排料算法的研究[D].上海：東華大學，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] 梅穎.船體建造板材套料系統中排樣優化算法與碰靠技術研究[D].廣州：華南理工大學,2010.

[8] 吳軍.數學之美[M].北京：人民郵電出版社,2012.

[9] 郭瑞峰.基于病毒進化遺傳算法的二維不規則圖形排樣[D].廣州：廣東工業大學,2014.

[10] 劉璐.基于遺傳算法的鈑金排樣系統研究[D].西安：西安工業大學,2014.

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

[12] 吳忻生,吳超成,劉海明.基于改進遺傳算法的矩形件排樣優化算法[J].制造業自動化,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。國家自然科學基金項目(51379080,51309094,61473116)。王淑青，教授，主研領域：智能控制，系統建模。陳軍，碩士生。潘健，副教授。張子蓬，副教授。袁曉輝，教授。何莉，副教授。

TP3

A

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