周 鑫， 賴曉陽， 孟祥群， 王 堃， 唐厚君

(1. 上海交通大學(xué) 電氣工程系，上海 200240； 2. 上海方菱計(jì)算機(jī)軟件有限公司，上海 200241)

臨界多邊形這一概念由Adamowicz等[1]提出，廣泛應(yīng)用于CAD、圖像圖形學(xué)等領(lǐng)域.臨界多邊形最重要的應(yīng)用為排料問題[2]的相交校驗(yàn).排料問題可概括為如何在有限的空間內(nèi)裝下最多指定形狀的物體[3].排料問題需要測試待排料位置中能否放下指定形狀的物體，此時(shí)需要判斷待排料工件是否與已排料的工件相交，這個(gè)過程稱為相交校驗(yàn).臨界多邊形是排料問題相交校驗(yàn)計(jì)算的重要工具.研究臨界多邊形對(duì)工業(yè)生產(chǎn)具有重要的學(xué)術(shù)價(jià)值和實(shí)用價(jià)值.

國內(nèi)外學(xué)者對(duì)臨界多邊形進(jìn)行了許多研究，提出了多種臨界多邊形的計(jì)算方法[4-5].這些算法包括蟻群算法[6]、元啟發(fā)算法[7]、移動(dòng)碰撞法[8]、模擬退火算法[9]、遺傳算法[10]、重力臨界多邊形算法[11]及軌跡線算法[12-13].

以上算法有一個(gè)共同的局限：算法僅能對(duì)多邊形的排樣進(jìn)行求解.實(shí)際工業(yè)環(huán)境中，待排樣的物體并非嚴(yán)格的多邊形.一種方法是用多邊形對(duì)其輪廓進(jìn)行擬合，這樣在精度上勢必有所損失.一種基于移動(dòng)碰撞法的臨界多邊形算法[14]可以計(jì)算由包含圓弧和線段的臨界多邊形，解決了精度損失問題，但其計(jì)算速度有待提高.

本文在分析了臨界多邊形的多種計(jì)算方法后，研究了計(jì)算速度較快的軌跡線算法，并將其加以拓展，使其能夠計(jì)算包含圓弧和線段的臨界多邊形，解決了精度損失問題，同時(shí)保證了計(jì)算的效率.在沖床自動(dòng)送料機(jī)的排樣中對(duì)算法進(jìn)行了測試和實(shí)驗(yàn)，并將其與基于移動(dòng)碰撞法的臨界多邊形算法和普通的相交校驗(yàn)算法加以比較，驗(yàn)證了算法的效率和精度.

1 臨界多邊形的定義

定義1臨界多邊形.給定多邊形A與多邊形B，固定多邊形A，令多邊形B作不旋轉(zhuǎn)的剛體運(yùn)動(dòng)繞多邊形A運(yùn)動(dòng)一周，繞行過程中，保證A與B邊界上至少有一點(diǎn)互相靠接，且A、B不重疊.在B上任取一參考點(diǎn)M，在繞行過程中M的運(yùn)動(dòng)軌跡為一閉合的多邊形，此多邊形就是B相對(duì)于A的臨界多邊形，記作NFPAB，如圖1所示.

圖1 臨界多邊形NFPAB的定義Fig.1 Definition of No Fit Polygon NFPAB

按上述方式構(gòu)造出來的臨界多邊形NFPAB有著明確的物理意義，當(dāng)多邊形B的參考點(diǎn)M落在NFPAB以內(nèi)時(shí)，多邊形A與多邊形B互相重合.M落在NFPAB邊界上時(shí)，A與B剛好相互靠接.當(dāng)點(diǎn)M落在NFPAB邊界以外時(shí)，A與B不重合.基于這樣的物理性質(zhì)，求解出臨界多邊形后，可以方便地判斷出任意相對(duì)位置下多邊形A、B是否重疊.

在求解排料問題的過程中，需要頻繁地判斷待排料的工件是否與邊界或者已排料的物體重疊，即待排料的物體位置是否合法，此過程被稱為相交校驗(yàn).由臨界多邊形的定義可知，判斷多邊形A與B是否重疊的問題可以轉(zhuǎn)化為判斷B上的參考點(diǎn)M是否在NFPAB內(nèi)部的問題，并且只需計(jì)算一次臨界多邊形，即可對(duì)任意相對(duì)位置下多邊形A與多邊形B的相交校驗(yàn)進(jìn)行計(jì)算.理論和實(shí)踐都證明，在排料問題中使用臨界多邊形能夠大大節(jié)省相交校驗(yàn)的用時(shí).

2 算法整體流程和思想

計(jì)算臨界多邊形的軌跡線算法思想可以描述如下：臨界多邊形是兩個(gè)多邊形靠接繞行過程中的軌跡，繞行過程中都是多邊形A與B僅有兩種狀態(tài)，A的頂點(diǎn)與B的邊靠接或者B的頂點(diǎn)與A的邊靠接.頂點(diǎn)在邊上靠接并滑動(dòng)的過程會(huì)生成一條軌跡線.若枚舉所有的頂點(diǎn)與邊，求解相應(yīng)狀態(tài)下的軌跡線，則待求的臨界多邊形為這些軌跡線組成集合S的一個(gè)子集.由臨界多邊形的定義可知，S內(nèi)軌跡線圍成的最大多邊形即為待求的臨界多邊形.

軌跡線算法的核心是如何快速計(jì)算軌跡線的集合S，并根據(jù)S求解對(duì)應(yīng)臨界多邊形.本文改進(jìn)了原有軌跡線算法的軌跡生成策略以及臨界多邊形求解算法，使其能夠求解包含圓弧的物體間的臨界多邊形.下文將詳細(xì)介紹引入圓弧后軌跡線的求取以及如何從軌跡線集合中提取對(duì)應(yīng)的臨界多邊形.

為了方便起見，指定兩物體的輪廓線方向，輪廓線首尾順次連接，沿逆時(shí)針方向繞物體一周，并將大于180°的圓弧拆分成相連的兩段等長圓弧，保證每段圓弧對(duì)應(yīng)的圓心角小于180°.

2.1 軌跡線的求取

由軌跡線的定義可知，所有物體可能的靠接方式都將形成軌跡線.復(fù)雜物體形成的軌跡線的數(shù)量相當(dāng)巨大，為了簡化計(jì)算，需要對(duì)靠接方式進(jìn)行簡單的校驗(yàn)，排除部分不可能的靠接方式，減少軌跡線的數(shù)量.

下面給出頂點(diǎn)張角和輪廓線法向量的定義.

定義2頂點(diǎn)的張角.對(duì)頂點(diǎn)P，求P點(diǎn)兩側(cè)輪廓線在頂點(diǎn)P處的切向量α1、α2.其中α1對(duì)應(yīng)的輪廓線在前，由向量α1、α2構(gòu)成的角∠P1P2P3記作頂點(diǎn)P的張角，其中P1P2對(duì)應(yīng)向量α1，P2P3對(duì)應(yīng)向量α2.圖2、3分別為P點(diǎn)兩側(cè)為線段、P點(diǎn)兩側(cè)有圓弧邊時(shí)，P點(diǎn)張角的示意圖.

圖4 凸角凹角的示意圖Fig.4 Diagram of convex angle and concave angle

圖5 輪廓線的法向量定義Fig.5 Definition of normal vector of contour

圖2 P兩側(cè)均為線段時(shí)頂點(diǎn)P的張角Fig.2 Expanding angle of P when both sides of P are segments

圖3 P兩側(cè)有圓弧時(shí)頂點(diǎn)P的張角Fig.3 Expanding angle of P when either side of P is arc

定義3角的凹凸性.對(duì)組成幾何圖形的某一頂點(diǎn)P，求取P點(diǎn)的張角∠P1P2P3，若P1位于射線P2P3的順時(shí)針方向，則點(diǎn)P2處頂角為凸角，否則點(diǎn)P2處頂角為凹角，如圖4所示.

定義4輪廓線的法向量.以圖5所示的多邊形V1V2V3為例，對(duì)于線段邊V1V2，將其方向向量逆時(shí)針旋轉(zhuǎn)90° 即可得到其法向量n.對(duì)圓弧邊V2V3，圓弧上任意一點(diǎn)P′均有相應(yīng)的法向量，為該點(diǎn)切線方向向量逆時(shí)針旋轉(zhuǎn)90° 的向量，這些法向量的集合為圓弧的法向量.因此，線段的法向量方向?yàn)橐欢ㄖ?，圓弧的法向量方向?yàn)橐粋€(gè)角度區(qū)間.

圓弧線可以分為外凸圓弧和內(nèi)凹圓弧.由于輪廓線是按照逆時(shí)針方向排列的，則輪廓內(nèi)部始終位于輪廓線方向左側(cè)，根據(jù)此性質(zhì)可以簡單求出圓弧的凹凸性.下面給出圓弧的外凸與內(nèi)凹的判定方法：若圓弧A1相對(duì)于圓心O以逆時(shí)針方向旋轉(zhuǎn)，則A1為外凸圓弧，否則A1為內(nèi)凹圓弧.

引入圓弧后，物體輪廓將包含線段與圓弧兩種邊.此時(shí)的靠接狀態(tài)可以分為三種：一多邊形的頂點(diǎn)與另一多邊形的邊相互靠接、一多邊形的圓弧邊與另一多邊形的線段邊相互靠接以及兩多邊形的圓弧邊相互靠接.以圖6所示的兩個(gè)物體為例，分析物體相互靠接的情況.

圖6 輪廓示意圖Fig.6 Diagram of contour

2.1.1頂點(diǎn)與邊的靠接 對(duì)于外接NFP而言，若頂點(diǎn)P2為凹角，則該點(diǎn)不可能與邊靠接.

若頂點(diǎn)P2不為凹角：

情況1當(dāng)邊為線段時(shí)，以A的頂點(diǎn)P靠接B的L1邊為例，將邊L1的法向量n逆時(shí)針旋轉(zhuǎn)90° 后得到向量β，則且僅當(dāng)β位于張角∠P1P2P3內(nèi)部時(shí)，頂點(diǎn)P與邊L1可能靠接，如圖7所示.

圖7 頂點(diǎn)與線段靠接Fig.7 Vertex touch segment

圖8 頂點(diǎn)與圓弧靠接Fig.8 Vertex touch arc

圖9 線段與圓弧靠接Fig.9 Segment touch arc

2.1.2線段與圓弧邊相互靠接 若邊L1和圓弧A1靠接，此時(shí)L1必定與圓弧A1相切，且A1為外凸圓弧.如圖9所示，求取A1上一點(diǎn)P′，使P′的法向量n2和L1的法向量方向n1相反.若點(diǎn)P′存在且A1外凸，邊L1和圓弧A1可以靠接，靠接點(diǎn)為P′.

2.1.3圓弧與圓弧相互靠接 此時(shí)的靠接情況分為3種：外凸圓弧與外凸圓弧相互靠接、外凸圓弧與內(nèi)凹圓弧相互靠接以及兩段內(nèi)凹圓弧相互靠接.兩段內(nèi)凹圓弧不可能相互靠接，不納入討論范圍，故實(shí)際的靠接情況僅有2種.

情況1當(dāng)兩段圓弧都是外凸圓弧時(shí).如圖10所示，兩段圓弧A1、A2均為外凸圓弧.分別求取A1與A2的法向量，并將A2的法向量逆時(shí)針旋轉(zhuǎn)180°.若這兩段法向量的角度存在交集，A1與A2可能相互靠接.

圖10 兩段外凸圓弧靠接Fig.10 Two convex arc touch

圖11 外凸圓弧與內(nèi)凹圓弧靠接Fig.11 Convex arc touch concave arc

以上是所有可能靠接的軌跡線情況.綜上，軌跡線集合S可以用以下算法求?。?/p>

對(duì)輪廓A、B的所有頂點(diǎn)，計(jì)算其張角，對(duì)所有的邊，計(jì)算其法向量方向(對(duì)于圓弧線求取其法向量范圍).

(1) 遍歷輪廓A、B的所有頂點(diǎn)，對(duì)每個(gè)頂點(diǎn)P，求其張角∠P1P2P3，并判斷其凹凸性，舍棄其中的凹角.再求取A、B中所有邊的法向量.

(2) 對(duì)于(1)中求取的每個(gè)張角∠P1P2P3，遍歷輪廓B的所有邊L，將(1)中求取的法向量逆時(shí)針旋轉(zhuǎn)90°，得到向量或向量集合β.若β的方向落入∠P1P2P3內(nèi)，說明輪廓B的邊L和輪廓A的頂點(diǎn)P可能靠接，將靠接得到的軌跡線加入集合S.

(3) 對(duì)于輪廓B的所有頂點(diǎn)P，重復(fù)步驟(1)、(2)，計(jì)算輪廓B頂點(diǎn)靠接輪廓A的邊形成的軌跡線集合.

(4) 輪廓A任取一條邊L1，輪廓B任取一條邊L2，遍歷所有這樣的邊組合(L1，L2).對(duì)每一個(gè)組合進(jìn)行如下操作：

(a) 若L1、L2均為線段，不作任何操作，計(jì)算下一個(gè)組合.

(b) 若L1、L2其中有一條邊為線段，另一條邊為圓弧，將線段邊的法向量n1旋轉(zhuǎn)180° 后得到向量n2，若n2落在圓弧的法向量范圍內(nèi)，說明兩條邊可能靠接.靠接點(diǎn)的法向量與n2重合.計(jì)算L1、L2相互靠接的軌跡線，加入集合S.

(c) 若L1、L2均為圓弧，判斷L1、L2的凹凸性，若L1、L2均內(nèi)凹，計(jì)算下一個(gè)組合.若L1、L2均外凸，將L2的法向量旋轉(zhuǎn)180°.若旋轉(zhuǎn)后L1與L2法向量范圍有所重合，說明L1、L2可能相交，計(jì)算L1、L2相互靠接的軌跡線，加入集合S.若L1、L2一個(gè)外凸一個(gè)內(nèi)凹，當(dāng)外凸的圓弧半徑小于內(nèi)凹圓弧時(shí)，將L2的法向量旋轉(zhuǎn)180°.若旋轉(zhuǎn)后L1與L2法向量范圍有所重合，說明L1、L2可能相互靠接，計(jì)算L1、L2相互靠接的軌跡線，加入集合S.

2.2 從軌跡線集合中求取臨界多邊形

由臨界多邊形的定義可知，當(dāng)參考點(diǎn)P落在臨界多邊形上時(shí)，待校驗(yàn)的兩物體剛好相互靠接.由輪廓線的定義可知，當(dāng)參考點(diǎn)P落在輪廓線上時(shí)，待校驗(yàn)的兩個(gè)物體至少有一個(gè)交點(diǎn)，故而輪廓線集合中所有點(diǎn)均在臨界多邊形內(nèi)部或邊上.故只需要尋找輪廓線集合的最小包絡(luò)輪廓，此輪廓即為待求的臨界多邊形.

臨界多邊形N求取的算法步驟如下：

(1) 將輪廓線集合置于平面直角坐標(biāo)系中，計(jì)算輪廓線集合S內(nèi)部所有交點(diǎn)，以及圓弧Y值最小的點(diǎn)，組成點(diǎn)集V.

(2)取V中Y值最小的點(diǎn)，作為輪廓起始點(diǎn)PS，選取過PS且與X軸夾角最小的邊作為起始邊.

(3)計(jì)算與當(dāng)前邊可能相交的所有點(diǎn)，取離當(dāng)前點(diǎn)最近的交點(diǎn)作為截?cái)帱c(diǎn)，將當(dāng)前點(diǎn)與截?cái)帱c(diǎn)之間的邊L部分加入外圍輪廓N中.

(4)計(jì)算當(dāng)前邊在截?cái)帱c(diǎn)處的切線向量α，并計(jì)算過截?cái)帱c(diǎn)的其他邊在截?cái)帱c(diǎn)處的切線向量，取與α右側(cè)夾角最小的向量所在邊為下一個(gè)當(dāng)前邊.

(5)重復(fù)步驟(3)～(4)，直至截?cái)帱c(diǎn)與PS重合.此時(shí)外圍輪廓N即為臨界多邊形.

3 算法復(fù)雜度分析

假定多邊形A是由m條邊構(gòu)成，多邊形B是由n條邊構(gòu)成，采用軌跡線算法可以生成k條軌跡線，最終生成的臨界多邊形有l(wèi)條邊.對(duì)于某個(gè)排料問題，需要在p個(gè)不同的相對(duì)位置上對(duì)兩多邊形作相交校驗(yàn).

對(duì)比移動(dòng)碰撞法和軌跡線算法兩種臨界多邊形算法，根據(jù)文獻(xiàn)[12]，移動(dòng)碰撞法的時(shí)間復(fù)雜度為O(lmn)，軌跡線算法的時(shí)間復(fù)雜度為O(lk)，由軌跡線的求取方式可知k≤mn，故而兩算法最大時(shí)間復(fù)雜度相同.但軌跡線算法根據(jù)法向量方向事先排除了大量軌跡線，實(shí)際的軌跡線算法時(shí)間復(fù)雜度遠(yuǎn)小于O(lmn).故而軌跡線算法的效率會(huì)明顯高于移動(dòng)碰撞法.

對(duì)比臨界多邊形算法和常規(guī)相交校驗(yàn)算法.常規(guī)的相交校驗(yàn)是判斷多邊形B內(nèi)任意一點(diǎn)是否落在多邊形A內(nèi).若是，則兩多邊形重疊；若不是，則將多邊形A的每一條邊與多邊形B的每一條邊分別作相交校驗(yàn).如有相交，說明A、B互相重疊，若均無相交，則兩多邊形不重合.采用常規(guī)相交校驗(yàn)算法，進(jìn)行一次套料的時(shí)間復(fù)雜度為O(pmn).

若使用臨界多邊形進(jìn)行校驗(yàn)，一次套料的時(shí)間復(fù)雜度為O(pl+lmn).兩個(gè)校驗(yàn)時(shí)間相比較，可以發(fā)現(xiàn)使用臨界多邊形進(jìn)行校驗(yàn)，會(huì)在生成臨界多邊形本身產(chǎn)生額外的開銷，但在多個(gè)位置進(jìn)行重疊校驗(yàn)時(shí)由于可以直接重復(fù)利用NFP的信息，節(jié)省重復(fù)計(jì)算的時(shí)間.當(dāng)p?mn時(shí)，使用臨界多邊形進(jìn)行校驗(yàn)?zāi)軌驑O大地節(jié)省裝載問題的計(jì)算開銷.

實(shí)際生產(chǎn)過程中，工件與板材形狀往往不會(huì)過度復(fù)雜，但為了最大程度地提高利用效率，裝載問題算法會(huì)計(jì)算大量的排料位置以尋求最優(yōu)解.以沖床自動(dòng)送料機(jī)的加工為例，一次套料中，p的數(shù)量級(jí)在104左右，而工件邊數(shù)一般少于60，滿足p?mn這個(gè)條件.因此采用臨界多邊形算法可以極大地提高運(yùn)算速度.

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

本文對(duì)沖床送料機(jī)常用零件庫中的60種不同工件進(jìn)行了臨界多邊形計(jì)算，總共測試了330種不同的組合.其運(yùn)行平臺(tái)為PC機(jī)，其處理器為 i7-7700HQ，2.81 GHz， 8 GB內(nèi)存，Windows 10操作系統(tǒng).經(jīng)過測試，算法能夠生成正確的臨界多邊形，通過臨界多邊形進(jìn)行的相交校驗(yàn)計(jì)算與傳統(tǒng)的相交校驗(yàn)計(jì)算結(jié)果一致，驗(yàn)證了算法的正確性.

圖12為幾組不規(guī)則工件生成的臨界多邊形.表1對(duì)比了基于軌跡線的臨界多邊形算法和基于移動(dòng)碰撞的臨界多邊形算法的效率.

圖12 幾組不規(guī)則工件生成的臨界多邊形Fig.12 Critical polygons generated by several groups of irregular workpieces

表1 兩種臨界多邊形算法計(jì)算效率的對(duì)比Tab.1 Comparisons of computational efficiency of two critical polygon algorithms

由表1可知，基于軌跡線的臨界多邊形算法在計(jì)算效率上優(yōu)于基于移動(dòng)碰撞的臨界多邊形算法，且工件形狀越復(fù)雜，其計(jì)算效率提高的效果越明顯.

下面以沖床自動(dòng)送料機(jī)為實(shí)際場景，對(duì)算法進(jìn)行測試，將基于軌跡線的臨界多邊形算法和常規(guī)相交校驗(yàn)算法效率進(jìn)行對(duì)比分析.沖床自動(dòng)送料機(jī)使用的工控機(jī)處理器為i7-4900MQ, 2.8 GHz, 8 GB內(nèi)存.圖13為一份典型的沖床自動(dòng)送料機(jī)加工樣例，加工的工件為灰色的五角星形工件.

圖13 沖床自動(dòng)送料機(jī)加工樣例Fig.13 Processing example of punch automatic feeding machine

表2給出了沖床自動(dòng)送料機(jī)在加工不同形狀板材時(shí)，采用兩種算法的效率對(duì)比，測試的板材為眼子料(即常規(guī)鋼板被加工后剩余的邊角料)和板料(分為窄與寬兩種)，測試工件相同，均為扳手形工件(見表1序號(hào)3).

由表2可知，與原有的相交校驗(yàn)算法相比，使用臨界多邊形算法顯著可以提高算法效率，測試用例中，算法效率提高了約30%～55%左右.效率提升的幅度隨著排料區(qū)域的擴(kuò)大而提升.由理論分析可知，臨界多邊形的生成相當(dāng)耗時(shí)，但生成臨界多邊形之后進(jìn)行相交判斷相比常規(guī)算法更為迅速.當(dāng)排料區(qū)域變大時(shí)，排料算法對(duì)相同工件的相交判斷會(huì)更為頻繁，使得臨界多邊形算法的優(yōu)勢得以擴(kuò)大，效率提升更為明顯.表2結(jié)果與理論分析相符.

表2 采用臨界多邊形算法前后沖床套料用時(shí)對(duì)比

5 結(jié)語

本文在基于軌跡線的臨界多邊形算法基礎(chǔ)上，將算法加以改進(jìn)，拓展了算法的應(yīng)用范圍.改進(jìn)后的算法能夠正確計(jì)算包含圓弧的物體所形成的臨界多邊形，解決了使用多邊形擬合曲線帶來的精度損失問題.對(duì)比現(xiàn)有的基于移動(dòng)碰撞法的臨界多邊形算法，該算法顯著提高了計(jì)算速度，在計(jì)算復(fù)雜物體臨界多邊形的情況下，該算法平均能夠提升40%左右的效率.在沖床自動(dòng)送料機(jī)上的測試結(jié)果驗(yàn)證了本文算法的可行性和有效性.