基于掃描區間表示的不規則多邊形快速定位算法及應用

羅月童， 呂 師， 江玉清

（合肥工業大學計算機與信息學院VCC研究室，安徽 合肥 230009）

基于掃描區間表示的不規則多邊形快速定位算法及應用

羅月童， 呂 師， 江玉清

（合肥工業大學計算機與信息學院VCC研究室，安徽 合肥 230009）

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

排料；掃描區間表示法；不規則多邊形；定位算法

排料問題廣泛應用于金屬板材、木料、玻璃、布料等下料問題，設計重工業、輕工業、微電子等不同領域。人們也對相關問題進行了廣泛研究[1]。

排料問題實質上是一個二維不規則圖形排樣問題，是一個非確定多項式(non-deterministic polynomial, NP)問題?；谧笙聝炏扰艠铀惴?bottom-left, BL)[2]和可填充式左下優先排樣算法(bottom-left-fill, BLF)等啟發式策略，排料問題可分成兩個步驟：一是確定多邊形序列的擺放順序和角度；二是根據順序進行擺放二維圖形。

確定二維圖形的擺放順序和角度是一個組合爆炸問題，人們使用多種優化算法[3]進行近似求解，如神經網絡[4]、遺傳算法[5]、模擬退火[6]、粒子群優化算法[7]。本文選用遺傳算法選擇二維圖形的擺放順序和角度。因為每改變一次二維形狀的擺放順序都要重新進行擺放，因此，二維形狀定位算法的效率對排料算法有重要影響。常用方法有矩形包絡法[8-9]、NFP算法[10-11]、基于掃描區域的算法[12]等。其中，基于掃描區域的二維形狀定位算法因能處理復雜形狀而備受關注，但它存在時間效率低下的缺陷。本文通過深入分析基于掃描區間的二維形狀定位法，從兩個方面改進該算法，實現快速基于區域掃描的二維形狀定位算法。

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

文獻[12]詳細地介紹了這個方法，本文簡要描述該方法。

1.1 過程描述

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

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

掃描區間定位算法對待排件序列進行以下操作：

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

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

(3) 依據“定位掃描算法”計算得到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)步調用了“定位掃描算法”，用來判斷位置 position(x, y)處是否可以放置待排件對象，算法簡單描述如下：

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

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

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

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

返回到步驟(2)。

1.2 問題分析

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

圖2 文獻[12]方法問題分析

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

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

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

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

上述兩個問題在過程中互相影響，也受y方向移動次數的增多等方面的影響，算法消耗的時間會越來越多，如圖2(f)所示。

2 改進的快速掃描區間定位算法

2.1 算法設計

經過上述分析，提出兩個優化上述問題的針對性方法。這里改變原料多邊形掃描區間的內容，只記錄原料空閑掃描區間，因而不存在臟位標記。

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

統計待排多邊形所有掃描區間數。在(1)方法確定y位置下，進行如下操作：

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

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

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

圖3 可行移動距離區間

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

圖4 快速掃描區間定位算法流程圖

2.2 過程對比

為了更直觀地展現快速掃描區間定位算法的優點，圖5～6對同一待排多邊形在不同算法下的軌跡作對比。要找到待排件2所在位置(如圖5所示)，掃描區間定位算法沿著箭頭反復進行掃描區間的比較和縱向移動的操作，其過程在時間上無疑是一種浪費?？焖賿呙鑵^間定位算法依據行最大區間值比較排除法，盡快找到待排件2的所在位置，同時依據快速可行矩陣定位法，一次性計算出要到達正確位置2所要移動的距離(如圖6所示)。過程顯然優于掃描區間定位算法，在實際性能上也必然有所提高。

圖5 掃描區間定位算法軌跡

圖6 快速掃描區間定位算法軌跡

3 實驗與應用

本文算法已經在Microsoft Visual Studio 2008使用C++語言開發實現，并應用于作者所在小組與合肥匯錦數控設備制造有限公司聯合開發的服裝排料軟件。本節的相關實驗數據均是由合肥匯錦數控設備制造有限公司提供的實際數據，實驗機器的配置如下：2.80 GHz Intel I5CPU，4.0 G內存。

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

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

LPC越大則掃描線越精細，排料結果越精確，但因為需要進行更多的掃描線比較，則計算速度下降。本文中所有實驗數據均為 PLT格式保存的衣片多邊形文件，因為 PLT文件已經對衣片多邊形等進行離散化，所以可直接采用測試文件的離散化結果，LPC的對應取值為400。本文分別選用含有 20、50、70、100個衣片模型的數據進行實驗，使用本文方法和文獻[12]的方法擺放衣片，擺放結果如圖 7所示，原料利用率和時間消耗結果如表1所示。

實驗結果表明本文算法對時間性能有明顯改善，且衣片越多，效果越明顯，這是因為衣片越多，原料上的空閑區域越復雜，本文的算法更有可能過濾更多的無效區域，從而更好地改善時間性能。每組實驗結果是在相同的多邊形序列，相同的原料寬度下，采用不同的算法進行。雖然排放序列的最終位置和材料利用率相同，但是時間消耗卻大不相同。特別是在多邊形個數增多的情況下，快速掃描區間定位算法能夠在很大程度上提高時間效率。

圖7 排料結果

表1 利用率及時間消耗表

4 結 論

排料問題在很多領域有廣泛應用，但迄今為止還沒有完全解決。二維不規則形狀定位算法是排料問題的重要組成部分，本文通過深入分析獲得廣泛應用的基于掃描區間的二維不規則形狀定位算法，從兩個方面對其進行改進，從而實現了一種快速基于掃描區間的二維不規則形狀定位算法，實驗表明本文算法時間性能更優。

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

[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] 韓 珂. 智能優化排料方法研究[D]. 南京: 南京理工大學, 2009.

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

[5] 賈志欣, 殷國富, 羅 陽. 二維不規則零件排樣問題的遺傳算法求解[J]. 計算機輔助設計與圖形學學報, 2002, 14(5): 467-470.

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

[7] 李 明, 宋成芳, 周澤魁. 二維不規則零件排樣問題的粒子群算法求解[J]. 江南大學學報(自然科學版), 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]. 湖南大學學報(自然科學版), 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] 陳 勇. 二維不規則形優化排樣技術研究[D]. 杭州:浙江大學, 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

國家自然科學基金資助項目(11305205；61370167；61305093)

羅月童(1978-)，男，安徽青陽人，副教授，博士。主要研究方向為科學計算可視化、計算機圖形學和計算機輔助設計。E-mail：ytluo@hfut.edu.cn