基于軌跡線的臨界多邊形算法拓展

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

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

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

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

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

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

1 臨界多邊形的定義

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

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

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

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

2 算法整體流程和思想

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

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

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

2.1 軌跡線的求取

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

下面給出頂點張角和輪廓線法向量的定義.

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

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

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

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

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

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

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

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

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

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

2.1.1頂點與邊的靠接 對于外接NFP而言，若頂點P2為凹角，則該點不可能與邊靠接.

若頂點P2不為凹角：

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

圖7 頂點與線段靠接Fig.7 Vertex touch segment

圖8 頂點與圓弧靠接Fig.8 Vertex touch arc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)計算與當(dāng)前邊可能相交的所有點，取離當(dāng)前點最近的交點作為截斷點，將當(dāng)前點與截斷點之間的邊L部分加入外圍輪廓N中.

(4)計算當(dāng)前邊在截斷點處的切線向量α，并計算過截斷點的其他邊在截斷點處的切線向量，取與α右側(cè)夾角最小的向量所在邊為下一個當(dāng)前邊.

(5)重復(fù)步驟(3)～(4)，直至截斷點與PS重合.此時外圍輪廓N即為臨界多邊形.

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

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

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

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

圖13 沖床自動送料機加工樣例Fig.13 Processing example of punch automatic feeding machine

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

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

表2 采用臨界多邊形算法前后沖床套料用時對比

5 結(jié)語

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