胡勝紅

（湖北經(jīng)濟學(xué)院計算機學(xué)院，湖北 武漢 430205）

對面域作圖的DXF文件優(yōu)化激光加工路徑

胡勝紅

（湖北經(jīng)濟學(xué)院計算機學(xué)院，湖北 武漢 430205）

DXF(Drawing Exchange File) 文件的圖形元素通常是無序排列的，其圖元數(shù)據(jù)在激光加工過程中無效行程多、效率低下。以DXF文件中記錄的圖形元素為對象，用面域作圖技術(shù)將零散的加工圖形盡可能編組為連續(xù)的封閉圖組，從原點開始貪婪地選擇到下一個圖組起始點的最短路徑，直至得到整個圖紙的優(yōu)化路徑。算法時間復(fù)雜性為O(n2)。實驗證明該算法應(yīng)用到激光雕切加工中能減少光頭的空走行程和開關(guān)光次數(shù)，提高加工效率。

計算機應(yīng)用；路徑優(yōu)化；旅行商問題；面域

加工路徑優(yōu)化類似于經(jīng)典的旅行商問題(Traveling Salesman Problem，TSP)，屬于NP難問題[1]。其一般化的數(shù)學(xué)模型可以用圖的理論表示如下：存在圖G =〈V，E〉，V為組成圖的結(jié)點，E為連接這些結(jié)點的邊，尋找一條最小耗費的路徑，使得這條路徑只對每一個結(jié)點穿行一次[2]。在大多數(shù)這類問題中，隨著求解問題規(guī)模的擴大，得到最優(yōu)解往往意味著無法完成的計算量。因此，工程上往往尋找一種能夠在可約束條件下的優(yōu)化算法，以較低的復(fù)雜性獲取針對某類具體應(yīng)用的快速解。

激光加工軟件在切割和標(biāo)刻時，通常從已編輯好的 DXF文件中依次讀出所有圖元數(shù)據(jù)，這些圖元可以分為兩類，即封閉圖元和非封閉圖元。封閉圖元和非封閉圖元的加工方式不同，封閉圖元要考慮輪廓和填充掃描線，非封閉圖元只需要考慮輪廓即可。如果將填充掃描線的優(yōu)化算法另外考慮，僅針對行走路徑，減少激光空走行程也是提高加工效率的重要途徑[3]。實際加工過程中，從每個圖元中得到連續(xù)的輪廓路徑，再將所有的輪廓路徑按一定的順序連接起來，而連接這些輪廓路徑的線段在激光加工中對應(yīng)于空走行程，一般可以將輸出脈沖定得很高以實現(xiàn)較快的加工速度[5-6]。文獻[4]設(shè)計了易于實現(xiàn)的DXF路徑排序算法，對多義線、多邊形、圓等封閉圖元有良好的排序效果。但初次作圖產(chǎn)生的 DXF文件中不僅只包括上述幾種封閉圖元，還包含許多由直線、圓弧、樣條曲線等非封閉的圖元，它們中的多數(shù)盡管存取位置是零散的但邏輯關(guān)系上可進一步被定義為封閉區(qū)域的邊界，如在AutoCAD中被編輯為面域，對DXF文件中所有符合該特性的非封閉圖元預(yù)處理為面域后即可充分滿足激光雕切加工對封閉路徑的需求。因此，文獻[4]設(shè)計的排序算法引入面域圖元后還有進一步的優(yōu)化空間，本文據(jù)此對面域預(yù)處理過的DXF文件設(shè)計用于激光雕切加工的路徑優(yōu)化算法。

1 DXF文件中離散圖元的連接預(yù)處理

DXF文件中圖形元素以圖元繪制先后順序為依據(jù)的記錄順序以及 DXF對某一圖元的控制點順序存在默認(rèn)排序的情況，使得針對 DXF文件排序計算量大，效率低。如果在提取 DXF文件中的圖形元素數(shù)據(jù)時，對無序的離散圖元進行連接處理之后再應(yīng)用排序算法，可以得到一種局部有序的 DXF圖元數(shù)據(jù)序列。連接處理的過程要考慮各種圖形元素的特性，同時為了提高計算速度，采取“邊讀取邊排序”的方式，排序算法則使用包含頭指針和尾指針的鏈表進行二路插入排序算法。具體實現(xiàn)過程如下：

（1） 將非封閉圖組和封閉圖組都設(shè)計為鏈表，分別用頭指針和尾指針來表示加工方向上的第一個圖元的起點和最后一個圖元的終點，每一個連續(xù)加工序列都唯一對應(yīng)這樣一個鏈表；

（2） 按DXF文件中ENTITY段中的圖元順序逐個讀取每一圖元的屬性值，進行分類處理：

1） 如果該圖元是直線(LINE)，則將直線的首末點與每一個鏈表的頭指針和尾指針分別作比較，如果該直線的一端與頭指針相同，則插入到隊頭，修改頭指針指向該直線的另一端；否則如果該直線的一端與尾指針相同，則插入到隊尾，修改尾指針指向該直線的另一端；否則就以該直線為第一個圖元建立新的鏈表；

2） 如果該圖元是非封閉的圓弧(ARC)、曲線段(SPLINE)，則處理方法與直線類似，只不過圓弧要通過起止角計算起止點；

3）如果該圖元是非封閉多義線(LWPOLYLINE)，則除了比較起止點外，如果需要交換起止點，則還需要將每一個圖元按第一個與最后一個，第二個與倒數(shù)第二個，……，的順序進行交換；

4） 如果該圖元是封閉的，如面域(REGION)、圓(CIRCLE)、封閉曲線、封閉多義線等，就新建一個鏈表，按這些封閉圖元的原始順序記錄到鏈表中。

（3） 用一個模板數(shù)組存儲這些鏈表。

上述算法在排序時只需比較頭指針和尾指針，最壞的情況為每個鏈表需要比較4次，假設(shè)雙向鏈表的數(shù)目是 n，原始圖元的數(shù)目為 m(m>n)，則其算法復(fù)雜度為 O(mn)，比窮盡搜索算法（復(fù)雜度為 O(m2)）效率高。其中，影響該算法效率的關(guān)鍵是圖元的數(shù)目m，在連續(xù)圖元較多的情況下(n << m)，連接預(yù)處理的效率會很高。因此，提高連接預(yù)處理效率的關(guān)鍵是簡化 DXF文件結(jié)構(gòu)，盡可能多地生成無需排序的封閉圖元。DXF文件中可存取的封閉圖元除圓、封閉曲線、多義線外，還包括面域。在AutoCAD作圖時，任意復(fù)雜的平面圖案都可以由面域及其并、交、差操作生成，尤其是能構(gòu)成連續(xù)路徑的非封閉圖形。只要作圖人員盡可能將雕切圖案編輯為面域，再采用文獻[7]介紹的算法讀取DXF文件中的面域，即可大大降低連接預(yù)處理的比較次數(shù)。

2 封閉圖組和非封閉圖組

圖組(Graphic Group, GG)被定義為由連續(xù)圖元按逆時針或順時針方向連續(xù)排列的集合，也是路徑優(yōu)化的基本單元。一個圖組可以是封閉的，也可以是不封閉的。

連接預(yù)處理算法執(zhí)行后，DXF文件中的圖元T被分成兩大類，記為始末點不重合的非封閉圖組(Unclosed Graphic Group，UGG)和始末點重合的封閉圖組(Closed Graphic Group，CGG)。則T =UGG∪CGG。將DXF中的UGG和CGG作如下約定：

（1） 將非封閉圖組UGG的控制點表示為Pj，j = {0，1，…，N-1}，Pj為UGG中第j個控制頂點，根據(jù)DXF記錄順序，P0、Pj、PN-1分別表示UGG的起點、第j點、末點。排序算法中，若欲處理的圖元Ti∈UGG，則Ti-1至Ti的距離僅與Ti的兩端點有關(guān)。

（2） 將封閉圖組CGG的控制點表示為Pj，j = {0，1，…，N-1}。CGG為多邊形或封閉多義線時，其控制頂點按 DXF默認(rèn)的記錄順序依次為P0、…、Pj、…、PN-1(P0)。若CGG為圓或橢圓時，其控制點則退化為圓心P圓心。算法中若Ti∈CGG時，Ti-1至Ti的距離與Ti的各控制點有關(guān)。面域也屬于CGG。

3 路徑優(yōu)化算法

3.1 優(yōu)化算法概述

針對包含N個CGG和UGG的DXF圖元結(jié)構(gòu)，其路徑優(yōu)化可以用貪婪法求解：

圖1 參考點到圖組的距離計算方法

第1步 以原點為初始加工點。從原點開始，遍歷N個圖組的控制點求其距離，取最小值時的圖組作為繪圖或加工的起始圖組，取最小值時的控制點作為該圖組加工方向的起點，該圖組的末點作為到下一圖組的參考點。將該圖組的索引加入到隊列中，作為隊首元素，并將該圖組標(biāo)記為已排序。

第2步 以新的參考點求其到余下N-1個圖組控制點的距離。重復(fù)第1步直至第N 個圖元。在處理過程中，若有相等距離的圖組，或同一圖組的兩個端點距離相等的情況，按先出現(xiàn)者先處理的原則進行。將該圖組索引追加到隊尾，并將該圖組標(biāo)記為已排序。

第3步 按上述步驟可得到所有圖組均按優(yōu)化順序存儲在一個隊列中。在加工時，只要按照該隊列輸出圖元加工數(shù)據(jù)，就可以使空走行程減少，提高加工效率。

3.2 計算參考點到圖組的距離

在計算參考點到圖組T的行走距離時，針對封閉圖組和非封閉圖組進行比較：以上述步驟確定最短距離時，應(yīng)考慮圖組控制點Pi本身在DXF中記錄的始末順序。根據(jù)上述圖元分類，判斷T的類型，針對不同類型的圖組采用如下方式進行處理：

（1） 對于非封閉圖組，如圖1(a)，起點P0與 Pn-1分別與參考點計算距離為 d0和 d1。如果d0≤d1，則 P0仍為原圖組的起始點，Pn-1仍為原圖組的末點，圖組中圖元順序不變。如果d0> d1，則Pn-1變?yōu)樵瓐D組的起始點，P0變?yōu)樵瓐D組的末點，將圖組控制點順序改為Pn-1、Pn-2、…、P0，修改圖組中首尾隊列的指針。

（2） 對于封閉圖組，如圖1(b)，將參考點與每一個控制點計算，得到{d0，d1，…，dn-1}，取d =min(di) (i=0，1，…，n-1)，將頭指針從P0移到Pi，將尾指針從Pn-2移到Pi，控制點加工順序變?yōu)?Pi、Pi+1、…、Pn-1、P0、…、Pi-1、Pi。

（3） 另外，如果該封閉圖組是一個單獨的圓或橢圓，如圖1(c)，則只需要根據(jù)參考點到圓

圖2 未經(jīng)過面域處理的卡通圖樣激光切割路徑實際空走行程

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

首先在AutoCAD 2004軟件中繪制圖2所示加工圖紙，將面域作圖前后的圖紙分別保存為不同的DXF文件。被面域化的DXF文件僅僅只包含 12個面域，且每一個面域都確定一條連續(xù)路徑。應(yīng)用本文提出的路徑優(yōu)化算法對兩個 DXF心的連線與圓方程計算交點P0，就可以將其作為加工起點。

按照上述步驟預(yù)處理后，應(yīng)用3.1節(jié)優(yōu)化算法模擬整幅 DXF文件圖紙的實際行走路徑（圖3），與未作預(yù)處理的圖2作對比，空走行程大大減少。其中虛線表示光頭的空走行程。文件在一臺 1600mm×1000mm 幅面雕刻機上分別執(zhí)行一次雕刻加工，面域編輯過的 DXF文件空走行程由 815.24mm降低到 581.35mm，開關(guān)光次數(shù)也從20次降低到13次。由此可知：

圖3 經(jīng)過面域處理的卡通圖樣激光 切割路徑優(yōu)化后實際空走行程

（1） 經(jīng)過路徑優(yōu)化后，DXF文件中圖元輪廓連接路徑得到優(yōu)化。表1顯示了優(yōu)化前后的空走行程大幅減少，加工效率被大大提高，開關(guān)光次數(shù)也大幅減少，延長光學(xué)器件的使用壽命；

表1 優(yōu)化效率對照表

（2） 在圖形編輯時創(chuàng)建的面域越多，得到的路徑優(yōu)化效果越好，因此在AutoCAD編輯中作圖時應(yīng)該多生成面域，才能充分利用本文所給出的優(yōu)化算法。

（3） 該算法使用隊列存放圖組和圖元，保證了“先進先出”的行走順序，同時改變圖元順序只需要修改隊頭指針和隊尾指針，減少計算量，算法效率較高。

由于激光加工中原點是固定的，該算法時間復(fù)雜度為O(n2)，但n是指圖組的數(shù)目，而非原始圖元的數(shù)目。盡管該算法不一定得到TSP路徑的最優(yōu)解，但在實時加工環(huán)境中極大地降低了計算復(fù)雜性。另外，通過對 DXF文件中的圖元及其控制點的優(yōu)化排序，實現(xiàn)了按繪圖或加工方向的圖元優(yōu)化排序的數(shù)據(jù)輸出，應(yīng)用于激光加工軟件中，優(yōu)化了其圖形雕切時的路徑順序，減少了大量無效空走行程，利用較低復(fù)雜度算法實現(xiàn)了雕切效率的極大提高，降低了經(jīng)濟成本[5]。

[1]王曉東. 算法設(shè)計與分析[M]. 北京：清華大學(xué)出版社, 2003. 315-323.

[2]Sun Huiwen. Using genetic algorithm to solve traveling salesman problem [J]. Journal of Southwest Jiaotong University, 1997, 31(5)：550-554.

[3]劉 瀏, 容太平, 郭治國, 等. 通過 DXF數(shù)據(jù)交換接口實現(xiàn) AutoCAD在激光加工中的應(yīng)用[J]. 激光技術(shù), 2005, 29(1)：32-34.

[4]龔清洪, 常智勇, 莫 蓉, 等. 基于 DXF文件的圖元優(yōu)化排序[J]. 計算機應(yīng)用, 2006, 26(1)：169-173.

[5]劉曉東, 胡 兵, 何云貴, 等. 激光雕刻的數(shù)學(xué)模型及快速算法研究[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報,1999, 11(2)：151-153.

[6]王 偉. 激光圖形切雕系統(tǒng)智能化應(yīng)用研究[D]. 武漢：華中科技大學(xué), 2006.

[7]胡勝紅, 劉曉東. 基于 AutoCAD 面域的圖形接口開發(fā)及其應(yīng)用[J]. 工程圖學(xué)學(xué)報, 2007, 28(5)：1-6.

Optimizing the Laser Machining Path of DXF File Drawn with Region Graphics

HU Sheng-hong
( Computer School, Hubei University of Economics, Wuhan Hubei 430205, China )

A DXF file is normally occupied by many disorder graphic elements, which cause numerous vain journeys yet low efficiency in laser machining. With the graphic elements of DXF file as the object, region drawing technology is used to convert those scattered graphics into a list of closed graphic groups. Starting from the origin, the shortest path from current position to the start of next graphic groups is obtained greedily until the optimized path of the whole drawing is achieved. Time complexity of the algorithm is O(n2). The experimental results prove that the proposed algorithm applied to laser curving and cutting can reduce the vacant path and the numbers of turning on or off the laser, and thus improve the efficiency of machining.

computer application; path optimization; traveling salesman problem; region

TP 302.7

A

1003-0158(2010)06-0106-05

2008-07-16

胡勝紅（1979-），男，湖北武漢人，講師，博士研究生，主要研究方向為激光先進制造技術(shù)。