羅月童， 呂 師， 江玉清

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

基于掃描區(qū)間表示的不規(guī)則多邊形快速定位算法及應(yīng)用

羅月童， 呂 師， 江玉清

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

不規(guī)則多邊形定位算法是排料算法的重要組成部分，其效率對(duì)排料算法的性能有重要影響?；趻呙鑵^(qū)間表示的不規(guī)則多邊形定位算法因能適應(yīng)任意復(fù)雜多邊形而被廣泛采用，但它存在計(jì)算量大的不足。通過深入研究基于掃描區(qū)間表示的多邊形定位算法，該文從兩個(gè)方面對(duì)其方法進(jìn)行改進(jìn)：首先提出候選平移位置矩陣的概念，進(jìn)而實(shí)現(xiàn)定位掃描算法；然后通過最大跨度比較法快速排除一些不可能的行，從而通過減少定位掃描算法的調(diào)用次數(shù)進(jìn)一步加速。該算法已應(yīng)用于自主開發(fā)服裝排料軟件，多個(gè)實(shí)際衣片數(shù)據(jù)的測(cè)試結(jié)果證明了該文算法的有效性和高效性。

排料；掃描區(qū)間表示法；不規(guī)則多邊形；定位算法

排料問題廣泛應(yīng)用于金屬板材、木料、玻璃、布料等下料問題，設(shè)計(jì)重工業(yè)、輕工業(yè)、微電子等不同領(lǐng)域。人們也對(duì)相關(guān)問題進(jìn)行了廣泛研究[1]。

排料問題實(shí)質(zhì)上是一個(gè)二維不規(guī)則圖形排樣問題，是一個(gè)非確定多項(xiàng)式(non-deterministic polynomial, NP)問題?；谧笙聝?yōu)先排樣算法(bottom-left, BL)[2]和可填充式左下優(yōu)先排樣算法(bottom-left-fill, BLF)等啟發(fā)式策略，排料問題可分成兩個(gè)步驟：一是確定多邊形序列的擺放順序和角度；二是根據(jù)順序進(jìn)行擺放二維圖形。

確定二維圖形的擺放順序和角度是一個(gè)組合爆炸問題，人們使用多種優(yōu)化算法[3]進(jìn)行近似求解，如神經(jīng)網(wǎng)絡(luò)[4]、遺傳算法[5]、模擬退火[6]、粒子群優(yōu)化算法[7]。本文選用遺傳算法選擇二維圖形的擺放順序和角度。因?yàn)槊扛淖円淮味S形狀的擺放順序都要重新進(jìn)行擺放，因此，二維形狀定位算法的效率對(duì)排料算法有重要影響。常用方法有矩形包絡(luò)法[8-9]、NFP算法[10-11]、基于掃描區(qū)域的算法[12]等。其中，基于掃描區(qū)域的二維形狀定位算法因能處理復(fù)雜形狀而備受關(guān)注，但它存在時(shí)間效率低下的缺陷。本文通過深入分析基于掃描區(qū)間的二維形狀定位法，從兩個(gè)方面改進(jìn)該算法，實(shí)現(xiàn)快速基于區(qū)域掃描的二維形狀定位算法。

1 基于掃描區(qū)間的任意多邊形定位算法

文獻(xiàn)[12]詳細(xì)地介紹了這個(gè)方法，本文簡(jiǎn)要描述該方法。

1.1 過程描述

掃描區(qū)間定位算法依據(jù)圖形學(xué)中多邊形掃描轉(zhuǎn)換的思想，將待排多邊形和原料多邊形表示為一系列掃描區(qū)間，從而將復(fù)雜的任意多邊形判交過程，轉(zhuǎn)換為簡(jiǎn)單的掃描區(qū)間判交過程。掃描區(qū)間表示法的每個(gè)掃描區(qū)間由一對(duì)x坐標(biāo)值構(gòu)成，而原料多邊形的掃描區(qū)間中另外加入了臟位標(biāo)志DF(1表示已占用，0表示空閑)。通過比較待排件和原料多邊形上掃描區(qū)間表示的x坐標(biāo)值，結(jié)合DF的值，判斷右移距離。假設(shè)要判斷原料多邊形上某位置positon處是否可以放下排樣件，若發(fā)現(xiàn)待排件中掃描區(qū)間[px1, px2]和板料上的掃描區(qū)間[sx1, sx2]有重疊部分，且DF=1，那么位置 positon處不能放下排樣件。排樣件直接右移距離offset=[sx2-px1]，接著判斷下一位置定位情況。假設(shè)原材料多邊形上已經(jīng)放置了一系列多邊形，此時(shí)需要確定一個(gè)待排多邊形的可行位置，待排多邊形的移動(dòng)過程如圖1所示。

圖1 待排件多邊形排放過程

掃描區(qū)間定位算法對(duì)待排件序列進(jìn)行以下操作：

(1) 初始位置 position(x, y)設(shè)置為原料矩形左下角。

(2) 依次取排樣件Polygon(a)。調(diào)用“定位掃描算法”，Polygon(a)是否可以放在位置 position(x，y)處。如果可以，把排樣件Polygon(a)排放position(x, y)處；返回第(1)步，排放下一個(gè)待排件。

(3) 依據(jù)“定位掃描算法”計(jì)算得到Polygon(a)右移的距離 offset, x=x+offset，即 position(x,y)= position(x, y)+offset。

如果在x方向上排樣件Polygon(a)超出原料矩形范圍，y=y+1, x=0；

如果在y方向上排樣件Polygon(a)超出原料矩形范圍，待排多邊形Polygon(a)在原料上排放不下。

返回到第(2)步。

其中第(3)步調(diào)用了“定位掃描算法”，用來(lái)判斷位置 position(x, y)處是否可以放置待排件對(duì)象，算法簡(jiǎn)單描述如下：

(1) 初始掃描的位置position(x, y), i=0。

(2) 對(duì)Polygon(a)取第i條掃描線與之相交的所有掃描區(qū)間；對(duì)原料矩形取第(y+i)條掃描線與之相交的所有掃描區(qū)間。

(3) 對(duì)從步驟(2)得到的 Polygon(a)上的每一個(gè)掃描區(qū)間[px1, px2]，增加位移x之后得到區(qū)間[px1+x, px2+x]；對(duì)從步驟(3)得到的原料矩形的每一個(gè)掃描區(qū)間[sx1, sx2]，如果掃描區(qū)間[sx1, sx2]的臟位DF=1，且與[px1+x, px2+x]發(fā)生重疊，那么計(jì)算 Polygon(a)可以直接右移的距離值 offset=sx2-(px1+x)，同時(shí)返回FALSE，退出定位掃描算法。

(4) i=i+1，如果i大于經(jīng)過Polygon(a)的掃描線條數(shù)，返回 TRUE，表示 Polygon(a)可以定位在位置position(x, y)處。

返回到步驟(2)。

1.2 問題分析

為保證緊湊的排放效果，多邊形從初始位置出發(fā)，即其包圍盒左下頂點(diǎn)位于原點(diǎn)的位置開始，尋找可行的排放位置。假設(shè)原材料多邊形中已排放若干多邊形，現(xiàn)在要對(duì)新入的多邊形進(jìn)行排放，如圖2(a)所示。

圖2 文獻(xiàn)[12]方法問題分析

(1) 缺少完善的移動(dòng)策略。當(dāng)確定了待排件在y方向上某個(gè)位置后，橫向定位的過程實(shí)質(zhì)上就是多次調(diào)用定位算法，獲得新的offset值，并且不斷地驗(yàn)證，最終找到可排放位置的過程，但過程中不可避免地出現(xiàn)反復(fù)定位。

例如，經(jīng)過若干次掃描區(qū)間定位算法，過程中會(huì)得到圖2(b)所示虛線位置。由于新位置只能保證多邊形部分掃描區(qū)間與原料掃描區(qū)間無(wú)重疊，因而該位置并不一定是最終可行位置，再次調(diào)用掃描區(qū)間定位算法，從下到上比較待排多邊形每行掃描區(qū)間，發(fā)現(xiàn)多邊形對(duì)應(yīng)位置掃描區(qū)間與原料中掃描區(qū)間（A，B）重疊，通過計(jì)算獲得新的offset值，如圖2(c)所示，并且再次使用定位掃描算法，判斷新位置的定位情況。如此反復(fù)必然會(huì)造成時(shí)間復(fù)雜度的提高。

最壞的情況是經(jīng)過一系列的比較后判定該y值下沒有可選位置排放待排多邊形，那么此y值下復(fù)雜的比較過程實(shí)質(zhì)上是不必要的。如圖2(d)所示，待排多邊形多次比較后移動(dòng)到圖形2所在位置，發(fā)現(xiàn)超出原料邊界，因而返回最左位置，并且y方向上移動(dòng)到圖形3所在位置，重新計(jì)算新的offset。特別是當(dāng)待排多邊形復(fù)雜度較高，掃描區(qū)間數(shù)的增多，重復(fù)且不必要的比較過程會(huì)越來(lái)越多，嚴(yán)重降低算法的時(shí)間效率。

(2) 缺少初始定位策略。若當(dāng)前y值下無(wú)法找到可行位置，對(duì)多邊形在y方向上移動(dòng)1個(gè)位置，進(jìn)行橫向可排放位置的搜索。而現(xiàn)實(shí)情況中，為了找到最終可行y值，可能要在y方向上移動(dòng)多次，而且在每個(gè)y值下都要遍歷所有掃描區(qū)間，進(jìn)行重復(fù)且無(wú)用的掃描區(qū)間比較過程，如圖2(e)所示。缺少y值定位策略的缺陷，增加了大量的算法過程中重復(fù)且無(wú)用的掃描區(qū)間比較過程，造成時(shí)間上不必要的浪費(fèi)。

上述兩個(gè)問題在過程中互相影響，也受y方向移動(dòng)次數(shù)的增多等方面的影響，算法消耗的時(shí)間會(huì)越來(lái)越多，如圖2(f)所示。

2 改進(jìn)的快速掃描區(qū)間定位算法

2.1 算法設(shè)計(jì)

經(jīng)過上述分析，提出兩個(gè)優(yōu)化上述問題的針對(duì)性方法。這里改變?cè)隙噙呅螔呙鑵^(qū)間的內(nèi)容，只記錄原料空閑掃描區(qū)間，因而不存在臟位標(biāo)記。

(1) 候選平移位置矩陣。包含多邊形中所有掃描區(qū)間的可行移動(dòng)距離。假設(shè)原料多邊形為矩形，并且設(shè)定其寬度為W。待排多邊形包圍盒的長(zhǎng)和寬分別為l和w；聲明二維矩陣Span[l][w]，并初始化矩陣中所有值為 0，矩陣縱下標(biāo)表示可移動(dòng)距離，行下標(biāo)表示當(dāng)前行值，某位置的值表示該行滿足該移動(dòng)距離的掃描區(qū)間數(shù)。如 Span[i][j]=m表示第 i行有m個(gè)掃描區(qū)間可移動(dòng)距離j；通過對(duì)矩陣列的累加值計(jì)算，可快速計(jì)算出x方向上最小可行移動(dòng)距離。

統(tǒng)計(jì)待排多邊形所有掃描區(qū)間數(shù)。在(1)方法確定y位置下，進(jìn)行如下操作：

①計(jì)算候選平移位置矩陣：對(duì)多邊形所有掃描區(qū)間查找可行移動(dòng)距離，并更新可行矩陣對(duì)于位置的值，取其中某一掃描區(qū)間，其余同理。如圖3所示（其中X1，X2，G1等標(biāo)注代表該位置x值）。圖中表示多邊形掃描區(qū)間在原料對(duì)應(yīng)行的可行移動(dòng)距離區(qū)間有 3個(gè)，分別為（G1-X1，G2-X2）、（G3-X1，G4-X2）、（G5-X1，G6-X2）。則可將Span矩陣對(duì)應(yīng)行的上述 3個(gè)區(qū)間所有位置的值加1，表示該位置可放下此多邊形區(qū)間，同理對(duì)所有掃描區(qū)間進(jìn)行上述計(jì)算過程。

②尋找最小可行移動(dòng)距離：候選平移位置矩陣，從第一列開始，從上到下累加該列所有行的值，如果遇到某位置為 0，則表示該行沒有掃描區(qū)間可以移動(dòng)該距離，則該列無(wú)可行位置，從下一列開始重新累加。如果過程中未遇到 0，則比較最終的累加值和多邊形總區(qū)間數(shù)是否相等，如果相等，則表示移動(dòng)了該距離后，多邊形所有區(qū)間都在原料空閑區(qū)間內(nèi)；同時(shí)，計(jì)算時(shí)從左向右計(jì)算，找到的移動(dòng)距離必然是最小可行移動(dòng)距離。

(2) 最大跨度比較法。排放之前，分別求出待排多邊形和原料多邊形每行掃描區(qū)間的最大值，并且保存。多邊形從原點(diǎn)出發(fā)，比較對(duì)應(yīng)行最大區(qū)間值，若出現(xiàn)多邊形中行最大值大于原料對(duì)應(yīng)行空閑區(qū)間最大值，則該位置確定不可行，對(duì)y進(jìn)行加1操作。此操作是一個(gè)粗定位過程，目的是過濾明顯不符合排放條件的位置，經(jīng)過這個(gè)操作，雖然無(wú)法保證剩下的位置一定可以滿足排放條件，但是確實(shí)可以大量剔除掉一些不合理的位置，從而達(dá)到減少不必要的比較次數(shù)的效果，可有效避免圖 2(d)和圖2(e)的現(xiàn)象。

圖3 可行移動(dòng)距離區(qū)間

依據(jù)這些方面的算法改進(jìn)思想，在原有算法的基礎(chǔ)上，提出了一種更快速，更方便的算法，即基于掃描區(qū)間表示的不規(guī)則多邊形快速定位算法，算法流程圖如圖4所示。

圖4 快速掃描區(qū)間定位算法流程圖

2.2 過程對(duì)比

為了更直觀地展現(xiàn)快速掃描區(qū)間定位算法的優(yōu)點(diǎn)，圖5～6對(duì)同一待排多邊形在不同算法下的軌跡作對(duì)比。要找到待排件2所在位置(如圖5所示)，掃描區(qū)間定位算法沿著箭頭反復(fù)進(jìn)行掃描區(qū)間的比較和縱向移動(dòng)的操作，其過程在時(shí)間上無(wú)疑是一種浪費(fèi)。快速掃描區(qū)間定位算法依據(jù)行最大區(qū)間值比較排除法，盡快找到待排件2的所在位置，同時(shí)依據(jù)快速可行矩陣定位法，一次性計(jì)算出要到達(dá)正確位置2所要移動(dòng)的距離(如圖6所示)。過程顯然優(yōu)于掃描區(qū)間定位算法，在實(shí)際性能上也必然有所提高。

圖5 掃描區(qū)間定位算法軌跡

圖6 快速掃描區(qū)間定位算法軌跡

3 實(shí)驗(yàn)與應(yīng)用

本文算法已經(jīng)在Microsoft Visual Studio 2008使用C++語(yǔ)言開發(fā)實(shí)現(xiàn)，并應(yīng)用于作者所在小組與合肥匯錦數(shù)控設(shè)備制造有限公司聯(lián)合開發(fā)的服裝排料軟件。本節(jié)的相關(guān)實(shí)驗(yàn)數(shù)據(jù)均是由合肥匯錦數(shù)控設(shè)備制造有限公司提供的實(shí)際數(shù)據(jù)，實(shí)驗(yàn)機(jī)器的配置如下：2.80 GHz Intel I5CPU，4.0 G內(nèi)存。

相鄰掃描線之間的距離對(duì)本文算法的精度和速度有重要影響，本文用每厘米中掃描線的數(shù)目(lines per centimeter, LPC)，表示刻畫掃描線的疏密程度，那么布料的寬度、長(zhǎng)度及衣片多邊形的頂點(diǎn)坐標(biāo)可按下式進(jìn)行離散化：

其中 xo表示原始寬度、長(zhǎng)度或坐標(biāo)，r表示原始長(zhǎng)度單位與厘米之間的換算比率， round（·）表示四舍五入。本文算法采用離散化后的坐標(biāo) xd進(jìn)行排料。

LPC越大則掃描線越精細(xì)，排料結(jié)果越精確，但因?yàn)樾枰M(jìn)行更多的掃描線比較，則計(jì)算速度下降。本文中所有實(shí)驗(yàn)數(shù)據(jù)均為 PLT格式保存的衣片多邊形文件，因?yàn)?PLT文件已經(jīng)對(duì)衣片多邊形等進(jìn)行離散化，所以可直接采用測(cè)試文件的離散化結(jié)果，LPC的對(duì)應(yīng)取值為400。本文分別選用含有 20、50、70、100個(gè)衣片模型的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，使用本文方法和文獻(xiàn)[12]的方法擺放衣片，擺放結(jié)果如圖 7所示，原料利用率和時(shí)間消耗結(jié)果如表1所示。

實(shí)驗(yàn)結(jié)果表明本文算法對(duì)時(shí)間性能有明顯改善，且衣片越多，效果越明顯，這是因?yàn)橐缕蕉?，原料上的空閑區(qū)域越復(fù)雜，本文的算法更有可能過濾更多的無(wú)效區(qū)域，從而更好地改善時(shí)間性能。每組實(shí)驗(yàn)結(jié)果是在相同的多邊形序列，相同的原料寬度下，采用不同的算法進(jìn)行。雖然排放序列的最終位置和材料利用率相同，但是時(shí)間消耗卻大不相同。特別是在多邊形個(gè)數(shù)增多的情況下，快速掃描區(qū)間定位算法能夠在很大程度上提高時(shí)間效率。

圖7 排料結(jié)果

表1 利用率及時(shí)間消耗表

4 結(jié) 論

排料問題在很多領(lǐng)域有廣泛應(yīng)用，但迄今為止還沒有完全解決。二維不規(guī)則形狀定位算法是排料問題的重要組成部分，本文通過深入分析獲得廣泛應(yīng)用的基于掃描區(qū)間的二維不規(guī)則形狀定位算法，從兩個(gè)方面對(duì)其進(jìn)行改進(jìn)，從而實(shí)現(xiàn)了一種快速基于掃描區(qū)間的二維不規(guī)則形狀定位算法，實(shí)驗(yàn)表明本文算法時(shí)間性能更優(yōu)。

目前，本文僅基于最大跨度比較法排除一些不可能解，未來(lái)研究基于多邊形面積等排除算法，以排除更多不可能解，從而進(jìn)一步提高算法的效率。

[1] Hopper E, Turton B. A genetic algorithm for a 2D industrial packing problem [J]. Computers & Industrial Engineering, 1999, 37(1): 375-378.

[2] Baker B S, Coffman Jr E G, Rivest R L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing, 1980, 9(4): 846-855.

[3] 韓 珂. 智能優(yōu)化排料方法研究[D]. 南京: 南京理工大學(xué), 2009.

[4] 黃兆龍. 用啟發(fā)算法和神經(jīng)網(wǎng)絡(luò)法解決二維不規(guī)則零件排樣問題[J]. 微計(jì)算機(jī)信息, 2004, 20(7): 118-119.

[5] 賈志欣, 殷國(guó)富, 羅 陽(yáng). 二維不規(guī)則零件排樣問題的遺傳算法求解[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002, 14(5): 467-470.

[6] 陳 勇, 唐 敏, 童若鋒, 董金祥. 基于遺傳模擬退火算法的不規(guī)則多邊形排樣[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2003, 15(5): 598-603.

[7] 李 明, 宋成芳, 周澤魁. 二維不規(guī)則零件排樣問題的粒子群算法求解[J]. 江南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005, 4(3): 266-269.

[8] Li Aiping, Zhang Feng, Liu Xuemei. Range box-based algorithm for optimal blank layout [J]. Computer Engineering and Applications, 2007, 43(1): 198-200.

[9] 李 明, 張光新, 周澤魁. 基于改進(jìn)遺傳算法的二維不規(guī)則零件優(yōu)化排樣[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 33(2): 48-50.

[10] Art R C. An approach to the dimensional irregular cutting-stock problem [R]. IBM Cambridge Scientific Center report 36-Y08, Cambridge: IBM Cambridge Scientific Center, 1966.

[11] Adamowicz M, Albano A. Nesting two-dimensional shapes in rectangular modules [J]. Computer-Aided Design, 1976, 8(1): 27-33.

[12] 陳 勇. 二維不規(guī)則形優(yōu)化排樣技術(shù)研究[D]. 杭州:浙江大學(xué), 2003.

Scan Region Representation Based Fast Irregular Polygon Position Algorithm and Its Application

Luo Yuetong, Lv Shi, Jiang Yuqing
(VCC Division, School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China)

Irregular polygon position algorithm is an important part of nesting algorithm, and it has great influence on nesting algorithm′s performance. Scan region representation based fast irregular polygon position algorithm is widely applied for it can process complex polygon, but it has shortcoming of huge computation. By intensively analyzing the algorithm, the paper improves it in two ways: the paper firstly presents the concept of candidate position matrix to realize fast position scan algorithm; and impossible rows are fast picked out through maximum span cooperation, so that the algorithm is further accelerated by avoid calling position scan algorithm for impossible rows. The algorithm has been applied in self-developed cloth nesting software, several real cloth designs are used to test the algorithm, and the result demonstrates the algorithm′s effectiveness and efficiency.

nesting; scan region representation; irregular polygon; position algorithm

TP 391

A

2095-302X(2014)06-0815-06

2014-05-29；定稿日期：2014-07-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(11305205；61370167；61305093)

羅月童(1978-)，男，安徽青陽(yáng)人，副教授，博士。主要研究方向?yàn)榭茖W(xué)計(jì)算可視化、計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)輔助設(shè)計(jì)。E-mail：ytluo@hfut.edu.cn