毛良獻(xiàn),王 品

1(中國科學(xué)院大學(xué),北京 100049)

2(中國科學(xué)院 沈陽計算技術(shù)研究所,沈陽 110168)

3(沈陽高精數(shù)控智能技術(shù)股份有限公司,沈陽 110168)

板材排樣問題影響著許多領(lǐng)域,例如紡織品、塑料、金屬切削等等,其中最主要的就是兩維不規(guī)則形狀的排樣.這些問題通?？梢悦枋鰹椋簩⒁幌盗械牟灰?guī)則的二維形狀放置在一個或多個板子上,使得他們盡可能的接觸,這樣就可以節(jié)約板材的面積,提高板材利用率.這種板材排樣是一個NP 難問題,因此有許多方法用于解決它,包括線性規(guī)劃方法,啟發(fā)式放置方法等等[1-4].通常,絕大多數(shù)情況都可以利用三角函數(shù)[5]來解決,但NFP 提供了一種高效的解決策略.

在本文中,介紹了非擬多邊形及實現(xiàn)它一種方法.非擬合多邊形結(jié)構(gòu)能處理一些傳統(tǒng)方法(基于三角函數(shù))很難解決的特殊情況,說明非擬合多邊形在排樣處理中可以作為一種解決思路.

1 非擬合多邊形

本文提出了一種非擬合多邊形(No-Fit Polygon,NFP) 的構(gòu)造方式,原理是利用環(huán)繞的方法來產(chǎn)生NFP[6],該算法是對文獻(xiàn)[6]提出的算法的一種改進(jìn)實現(xiàn).比起傳統(tǒng)的利用三角函數(shù)的重疊測試[7-10],實現(xiàn)該算法簡單,同時具有時間復(fù)雜度較低的優(yōu)點(diǎn).

算法的原理如下,輸入?yún)?shù)是兩個二維多邊形,形狀可以是不規(guī)則的.假定其中一個多邊形(記為A)保持不動,另一個多邊形(記為B) 繞A 運(yùn)動.這樣當(dāng)B 環(huán)繞A 一周后,就可以生成一個非擬合多邊形(下面簡稱為NFP).

假定多邊形A 為固定多邊形,B 為環(huán)繞多邊形.算法實現(xiàn)過程分為4 步.(1)首先需要A 與B 接觸；(2)移動B；(3)找到下一個起點(diǎn)；(4)將平移向量合并.

1.1 多邊形A 與B 的接觸

在B 繞A 運(yùn)動之前,需要把B 放置在A 的邊上,保證B 接觸A,但又和A 不相交.然后,可以對B 沿某方向平移,使之一直是和A 保持接觸.

例如,圖1給出的多邊形A和B,同時標(biāo)記了A 的最低點(diǎn)A_minY和B 的最高點(diǎn)B_maxY.

圖1 多邊形A和B

那么,可以讓B 的最高點(diǎn)與A 的最低點(diǎn)接觸,這樣A 與B 是一定接觸,但不相交(也可以有其他方法,例如B 最左點(diǎn)和A 的最右點(diǎn)接觸,等等).平移向量

那么B 按T 平移后,如圖2所示,B 與A 接觸并且不交叉.此時,B 所在位置是B 繞A 運(yùn)動的開始位置,并記錄起點(diǎn)和B 的參考點(diǎn),保證B 在繞A 平移過程中可以回到初始位置.設(shè)B 的參考點(diǎn)和起點(diǎn)都為A_minY.那么,當(dāng)B 的參考點(diǎn)再次平移到起點(diǎn)(A_minY)時,就可以確定B 繞A 一周.

1.2 移動B

在A 與B 接觸后,需要對B 做平移操作.這個過程細(xì)分為以下5 步.

1.2.1 找出接觸邊對

當(dāng)前A和B 接觸,通過遍歷A和B 的全部邊,找出所有接觸點(diǎn).繼而確定全部接觸邊對.

如圖3所示,找到4 組接觸邊對,分別是＜a1,b1＞,＜a1,b3＞,＜a2,b1＞,＜a2,b3＞.

圖2 多邊形B 沿T 向量平移

圖3 接觸點(diǎn)及接觸邊對

1.2.2 從接觸邊對中找出平移向量

在1.2.1 節(jié)中,找到4 組接觸邊對.接觸邊對的作用是：一組接觸邊對能生成一個平移向量,故能得到全部的平移向量.例如,在圖3的4 組邊對中,1 號邊對＜a1,b1＞可以生成一個平移向量=-,是由邊b1 生成的.那為什么是由邊b1 生成,而非a1 生成? 算法假定平移向量是接觸點(diǎn)到邊的終點(diǎn),故a1 生成的是空向量.是的反向,這是認(rèn)為B 必須繞A 做逆時針運(yùn)動.那么2 號邊對＜a1,b3＞就不能生成平移向量.因為接觸點(diǎn)是a1(也是b3)的終點(diǎn).而3 號邊對＜a2,b1＞(a2 與b1 是平行關(guān)系)可以生成平移向量=(或者=-).也就是說,在這種情況下可以選擇任何一邊來生成平移向量.4 號邊對＜a2,b3＞中,=.接觸邊對對應(yīng)的平移向量見表1.

1.2.3 刪除不可行的平移向量

對1.2.2 節(jié)中找到的所有平移向量,需要依次判斷多邊形A 與B 這些向量移動會不會交叉.若有交叉,那么該向量就是不可行的.按如下方式思考：因為B 繞A 運(yùn)動,那么1.2.1 節(jié)中的接觸邊對中來自B 的邊是運(yùn)動的.也就是說,我們可以對每一個平移向量,依次針對每一組接觸邊對,判斷來自B 的邊按該向量平移,是否與來自A 的邊相交.若有一組接觸邊相交,那么就可以判斷該平移向量是不可行的,直接舍棄.

表1 多邊形A和B 的接觸邊對對應(yīng)的平移向量

那么怎么驗證接觸邊對中來自B 的邊按平移向量平移,會不會與來自A 的接觸邊交叉.對于每一組接觸邊對而言,可以計算出弧度區(qū)間,使得來自B 的邊沿區(qū)間中的某個弧度方向平移,不會和來自A 的邊相交.故只需要判斷平移向量的弧度方向是否在該區(qū)間內(nèi)即可.例如,對1.2.1 節(jié)中的四組接觸邊對,可以確定相應(yīng)的弧度區(qū)間(用圓弧表示可行的弧度區(qū)間,如圖4所示.

圖4 接觸邊對的可行弧度區(qū)間

1.2.4 修剪可行的平移向量

通過1.2.3 的過濾,找到了全部可行的平移向量.那么接下來,需要判斷每一個可行的平移向量是否能全部應(yīng)用.

在圖5中,A 是一個不規(guī)則多邊形,B 是一個矩形.紅色的是一個可行的平移向量,淺綠色是紅色的平移向量平移到B 的每個頂點(diǎn)之后的情況.

此時B 沿著紅色的平移向量平移,A 與B 必然交叉.從而,必須對紅色向量進(jìn)行修剪.圖中得到修剪后的是綠色的平移向量.看到有兩個綠色向量,但取得是較短的那個.同時,需要注意的是,B 按修剪后的平移向量平移,一定不會與A 相交?

圖5 多邊形沿平移向量平移,交叉

在圖6中,A 不變,B 是較大的矩形,紅色向量仍是可行的平移向量.將紅色向量平移到B 的每個頂點(diǎn),發(fā)現(xiàn)并不需要修剪平移向量.但是按紅色向量平移后,如圖7所示,A 與B 相交.這種情況下,就需要考慮將可行的平移向量平移到A 的每個頂點(diǎn),然后再修剪.如圖8所示.

在圖8中,將平移向量的每個終點(diǎn)平移到A 的每個頂點(diǎn),判斷與B 的交叉性,最終得到修剪后的平移向量(綠色).然后將兩種情況的最小值作為最終的可行平移向量.對每一個可行的平移向量執(zhí)行上述過程之后,就能得到全部修剪后的平移向量,然后按從長到短排序.接下來只需要按最長的修剪后的可行平移向量平移B 就可以了.

圖6 平移向量的起點(diǎn)放置在B 的每個頂點(diǎn)

圖7 多邊形B 沿平移向量平移

圖8 平移向量的修剪

值得指出的是,在文獻(xiàn)[5]中,直接使用修剪后的最長平移向量進(jìn)行平移.但是,在實驗中發(fā)現(xiàn)該平移向量不一定是能用的.也就是說,按此平移向量平移后,B 在下一次平移之前就不一定與A 接觸了.

1.2.5 移動多邊形B

通過前面的步驟,得到了修剪后最長的可行平移向量.接下來,B 按這個向量平移即可.但需要注意兩點(diǎn)：(1)判斷B 的參考點(diǎn)是否回到了起點(diǎn).若回到起點(diǎn),得到一個NFP.(2)判斷B 的參考點(diǎn)是否越過起點(diǎn).這個是對文獻(xiàn)[5]的一個補(bǔ)充.也就是此時B 的平移距離過長,超過了起點(diǎn),如圖10所示.

圖9 B 沿平移向量 (或)平移情況分析

圖10 B 的參考點(diǎn)沿平移向量平移越過起點(diǎn)

在圖10中,紅色的是可行的平移向量,綠色的表示B 的參考點(diǎn)的平移.由圖知,當(dāng)B 的參考點(diǎn)沿平移向量平移后,越過了起點(diǎn).本來可以生成一個NFP,現(xiàn)在就會無限循環(huán)下去,因為B 的參考點(diǎn)不會移東到起點(diǎn)了.在這種情況下,需要縮短平移向量.

1.3 找到下一個起點(diǎn)

在1.2 節(jié)中,生成了一個完整的外部NFP,是B 對A 的外部環(huán)繞.是否存在著其他NFP 呢? 也就是B 在A 的內(nèi)部平移存不存在,從而生成內(nèi)部的NFP.這里涉及到起點(diǎn)搜索.在1.2 節(jié)中,我們假定的起點(diǎn)是A 的最低點(diǎn).而在這里,我們需要找到其他起點(diǎn),以便B 能從這些起點(diǎn)出發(fā),得到其他的NFP.

1.3.1 起點(diǎn)搜索算法

在尋找外部NFP 過程中,A 中的有些邊可能沒有遍歷到.故可以從這些邊中尋找起點(diǎn).假設(shè)a 是A 中一條未遍歷的邊,試著在a 中找到一個可行的起點(diǎn).算法過程如下：依次讓B 的每個頂點(diǎn)平移到a 的起點(diǎn),判斷：(1)如果A 此時與B 沒有相交,那么a 的起點(diǎn)是一個可行的起點(diǎn).可再次運(yùn)用1.2 節(jié)中介紹的方法.(2)如果A 此時與B 有交叉,那么需要讓B 沿著a 移動,直到平移到一個的不相交位置,或者到達(dá)a 的終點(diǎn)(這就說明在a 上不可能找到起點(diǎn)).

現(xiàn)在,假定A 與B 相交,然后B 沿a 平移尋找可行的起點(diǎn).首先,可以快速判斷一下,B 沿著a 移動是否一定存在交叉.方法如下：因為此時的接觸點(diǎn)是a 的起點(diǎn),并且B 中有兩條邊也接觸到這個頂點(diǎn).那只要判斷一下,B 的兩條接觸邊是否至少有一條邊在a 的左側(cè).若成立,那么B 沿著a 移動一定會與A 相交.這樣,就需要判斷A 中其他未遍歷的邊了.如果通過上述判斷,就需要修剪a 向量.過程如下：當(dāng)前的平移向量=a 的起點(diǎn)-＞a 的終點(diǎn).同樣,利用1.2.4 中介紹的修剪方法修剪,得到.那么B 按平移,同時更新接觸點(diǎn)和B 的參考點(diǎn).再次運(yùn)用1.2 節(jié)中介紹的方法,找出剩余的平移向量.這里要注意,就是對a 進(jìn)行標(biāo)記,表示a 被遍歷過了.那么在下一次的搜索中就不會遍歷邊a 了.

1.4 平移向量合并生成NFP

通過1.1 節(jié)到1.3 節(jié)的計算,找到所需要的全部平移向量.現(xiàn)在,就需要對他們合并生成NFP.每一組平移向量都對應(yīng)一個起點(diǎn)和B 的參考點(diǎn).那么對B 的參考點(diǎn)執(zhí)行一組平移操作,就可以生成一個NFP.

2 案例介紹

下面舉一些例子,如圖11至圖15,表明算法的運(yùn)行情況.圖11至圖15中左圖是多邊形的初始位置,右圖是平移的開始位置、起點(diǎn)和生成的NFP.

圖11 生成一個外部的NFP

3 測試

根據(jù)文獻(xiàn)[5]和來自the Association of the European Operational Research Societies 的板材排樣工作小組的數(shù)據(jù)集(https：//www.euro-online.org/websites/esicup/data-sets/),執(zhí)行如表2所列出的測試.實驗中使用的機(jī)器為Intel Core i5-3230M@2.6 GHz,8 GB 內(nèi)存.表格的形式參考了文獻(xiàn)[5].

圖12 生成一個外部的NFP

圖13 生成內(nèi)部和外部的NFP

圖14 生成內(nèi)部和外部的NFP

圖15 互鎖和外部的NFP

4 結(jié)論與展望

生成了完整的NFP 結(jié)構(gòu),給出算法實現(xiàn)的具體細(xì)節(jié)和一些要點(diǎn).通過測試,表明該方法具有一定的高效性.與先前的一些借助于三角函數(shù)的方法相比,該算法的實現(xiàn)簡單,高效,且不需要對每一種特殊情況做特殊的考慮.利用起點(diǎn)搜索過程,對某些傳統(tǒng)方法無法解決的互鎖,洞等情況,能夠成功解決.對板材排樣系統(tǒng)的設(shè)計與實現(xiàn)有一定的借鑒意義.

表2 對不同數(shù)據(jù)集的測試結(jié)果