对面域作图的DXF文件优化激光加工路径

胡胜红

（湖北经济学院计算机学院，湖北 武汉 430205）

对面域作图的DXF文件优化激光加工路径

胡胜红

（湖北经济学院计算机学院，湖北 武汉 430205）

DXF(Drawing Exchange File) 文件的图形元素通常是无序排列的，其图元数据在激光加工过程中无效行程多、效率低下。以DXF文件中记录的图形元素为对象，用面域作图技术将零散的加工图形尽可能编组为连续的封闭图组，从原点开始贪婪地选择到下一个图组起始点的最短路径，直至得到整个图纸的优化路径。算法时间复杂性为O(n2)。实验证明该算法应用到激光雕切加工中能减少光头的空走行程和开关光次数，提高加工效率。

计算机应用；路径优化；旅行商问题；面域

加工路径优化类似于经典的旅行商问题(Traveling Salesman Problem，TSP)，属于NP难问题[1]。其一般化的数学模型可以用图的理论表示如下：存在图G =〈V，E〉，V为组成图的结点，E为连接这些结点的边，寻找一条最小耗费的路径，使得这条路径只对每一个结点穿行一次[2]。在大多数这类问题中，随着求解问题规模的扩大，得到最优解往往意味着无法完成的计算量。因此，工程上往往寻找一种能够在可约束条件下的优化算法，以较低的复杂性获取针对某类具体应用的快速解。

激光加工软件在切割和标刻时，通常从已编辑好的 DXF文件中依次读出所有图元数据，这些图元可以分为两类，即封闭图元和非封闭图元。封闭图元和非封闭图元的加工方式不同，封闭图元要考虑轮廓和填充扫描线，非封闭图元只需要考虑轮廓即可。如果将填充扫描线的优化算法另外考虑，仅针对行走路径，减少激光空走行程也是提高加工效率的重要途径[3]。实际加工过程中，从每个图元中得到连续的轮廓路径，再将所有的轮廓路径按一定的顺序连接起来，而连接这些轮廓路径的线段在激光加工中对应于空走行程，一般可以将输出脉冲定得很高以实现较快的加工速度[5-6]。文献[4]设计了易于实现的DXF路径排序算法，对多义线、多边形、圆等封闭图元有良好的排序效果。但初次作图产生的 DXF文件中不仅只包括上述几种封闭图元，还包含许多由直线、圆弧、样条曲线等非封闭的图元，它们中的多数尽管存取位置是零散的但逻辑关系上可进一步被定义为封闭区域的边界，如在AutoCAD中被编辑为面域，对DXF文件中所有符合该特性的非封闭图元预处理为面域后即可充分满足激光雕切加工对封闭路径的需求。因此，文献[4]设计的排序算法引入面域图元后还有进一步的优化空间，本文据此对面域预处理过的DXF文件设计用于激光雕切加工的路径优化算法。

1 DXF文件中离散图元的连接预处理

DXF文件中图形元素以图元绘制先后顺序为依据的记录顺序以及 DXF对某一图元的控制点顺序存在默认排序的情况，使得针对 DXF文件排序计算量大，效率低。如果在提取 DXF文件中的图形元素数据时，对无序的离散图元进行连接处理之后再应用排序算法，可以得到一种局部有序的 DXF图元数据序列。连接处理的过程要考虑各种图形元素的特性，同时为了提高计算速度，采取“边读取边排序”的方式，排序算法则使用包含头指针和尾指针的链表进行二路插入排序算法。具体实现过程如下：

（1） 将非封闭图组和封闭图组都设计为链表，分别用头指针和尾指针来表示加工方向上的第一个图元的起点和最后一个图元的终点，每一个连续加工序列都唯一对应这样一个链表；

（2） 按DXF文件中ENTITY段中的图元顺序逐个读取每一图元的属性值，进行分类处理：

1） 如果该图元是直线(LINE)，则将直线的首末点与每一个链表的头指针和尾指针分别作比较，如果该直线的一端与头指针相同，则插入到队头，修改头指针指向该直线的另一端；否则如果该直线的一端与尾指针相同，则插入到队尾，修改尾指针指向该直线的另一端；否则就以该直线为第一个图元建立新的链表；

2） 如果该图元是非封闭的圆弧(ARC)、曲线段(SPLINE)，则处理方法与直线类似，只不过圆弧要通过起止角计算起止点；

3）如果该图元是非封闭多义线(LWPOLYLINE)，则除了比较起止点外，如果需要交换起止点，则还需要将每一个图元按第一个与最后一个，第二个与倒数第二个，……，的顺序进行交换；

4） 如果该图元是封闭的，如面域(REGION)、圆(CIRCLE)、封闭曲线、封闭多义线等，就新建一个链表，按这些封闭图元的原始顺序记录到链表中。

（3） 用一个模板数组存储这些链表。

上述算法在排序时只需比较头指针和尾指针，最坏的情况为每个链表需要比较4次，假设双向链表的数目是 n，原始图元的数目为 m(m>n)，则其算法复杂度为 O(mn)，比穷尽搜索算法（复杂度为 O(m2)）效率高。其中，影响该算法效率的关键是图元的数目m，在连续图元较多的情况下(n << m)，连接预处理的效率会很高。因此，提高连接预处理效率的关键是简化 DXF文件结构，尽可能多地生成无需排序的封闭图元。DXF文件中可存取的封闭图元除圆、封闭曲线、多义线外，还包括面域。在AutoCAD作图时，任意复杂的平面图案都可以由面域及其并、交、差操作生成，尤其是能构成连续路径的非封闭图形。只要作图人员尽可能将雕切图案编辑为面域，再采用文献[7]介绍的算法读取DXF文件中的面域，即可大大降低连接预处理的比较次数。

2 封闭图组和非封闭图组

图组(Graphic Group, GG)被定义为由连续图元按逆时针或顺时针方向连续排列的集合，也是路径优化的基本单元。一个图组可以是封闭的，也可以是不封闭的。

连接预处理算法执行后，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个控制顶点，根据DXF记录顺序，P0、Pj、PN-1分别表示UGG的起点、第j点、末点。排序算法中，若欲处理的图元Ti∈UGG，则Ti-1至Ti的距离仅与Ti的两端点有关。

（2） 将封闭图组CGG的控制点表示为Pj，j = {0，1，…，N-1}。CGG为多边形或封闭多义线时，其控制顶点按 DXF默认的记录顺序依次为P0、…、Pj、…、PN-1(P0)。若CGG为圆或椭圆时，其控制点则退化为圆心P圆心。算法中若Ti∈CGG时，Ti-1至Ti的距离与Ti的各控制点有关。面域也属于CGG。

3 路径优化算法

3.1 优化算法概述

针对包含N个CGG和UGG的DXF图元结构，其路径优化可以用贪婪法求解：

图1 参考点到图组的距离计算方法

第1步 以原点为初始加工点。从原点开始，遍历N个图组的控制点求其距离，取最小值时的图组作为绘图或加工的起始图组，取最小值时的控制点作为该图组加工方向的起点，该图组的末点作为到下一图组的参考点。将该图组的索引加入到队列中，作为队首元素，并将该图组标记为已排序。

第2步 以新的参考点求其到余下N-1个图组控制点的距离。重复第1步直至第N 个图元。在处理过程中，若有相等距离的图组，或同一图组的两个端点距离相等的情况，按先出现者先处理的原则进行。将该图组索引追加到队尾，并将该图组标记为已排序。

第3步 按上述步骤可得到所有图组均按优化顺序存储在一个队列中。在加工时，只要按照该队列输出图元加工数据，就可以使空走行程减少，提高加工效率。

3.2 计算参考点到图组的距离

在计算参考点到图组T的行走距离时，针对封闭图组和非封闭图组进行比较：以上述步骤确定最短距离时，应考虑图组控制点Pi本身在DXF中记录的始末顺序。根据上述图元分类，判断T的类型，针对不同类型的图组采用如下方式进行处理：

（1） 对于非封闭图组，如图1(a)，起点P0与 Pn-1分别与参考点计算距离为 d0和 d1。如果d0≤d1，则 P0仍为原图组的起始点，Pn-1仍为原图组的末点，图组中图元顺序不变。如果d0> d1，则Pn-1变为原图组的起始点，P0变为原图组的末点，将图组控制点顺序改为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，控制点加工顺序变为 Pi、Pi+1、…、Pn-1、P0、…、Pi-1、Pi。

（3） 另外，如果该封闭图组是一个单独的圆或椭圆，如图1(c)，则只需要根据参考点到圆

图2 未经过面域处理的卡通图样激光切割路径实际空走行程

4 实验结果与分析

首先在AutoCAD 2004软件中绘制图2所示加工图纸，将面域作图前后的图纸分别保存为不同的DXF文件。被面域化的DXF文件仅仅只包含 12个面域，且每一个面域都确定一条连续路径。应用本文提出的路径优化算法对两个 DXF心的连线与圆方程计算交点P0，就可以将其作为加工起点。

按照上述步骤预处理后，应用3.1节优化算法模拟整幅 DXF文件图纸的实际行走路径（图3），与未作预处理的图2作对比，空走行程大大减少。其中虚线表示光头的空走行程。文件在一台 1600mm×1000mm 幅面雕刻机上分别执行一次雕刻加工，面域编辑过的 DXF文件空走行程由 815.24mm降低到 581.35mm，开关光次数也从20次降低到13次。由此可知：

图3 经过面域处理的卡通图样激光 切割路径优化后实际空走行程

（1） 经过路径优化后，DXF文件中图元轮廓连接路径得到优化。表1显示了优化前后的空走行程大幅减少，加工效率被大大提高，开关光次数也大幅减少，延长光学器件的使用寿命；

表1 优化效率对照表

（2） 在图形编辑时创建的面域越多，得到的路径优化效果越好，因此在AutoCAD编辑中作图时应该多生成面域，才能充分利用本文所给出的优化算法。

（3） 该算法使用队列存放图组和图元，保证了“先进先出”的行走顺序，同时改变图元顺序只需要修改队头指针和队尾指针，减少计算量，算法效率较高。

由于激光加工中原点是固定的，该算法时间复杂度为O(n2)，但n是指图组的数目，而非原始图元的数目。尽管该算法不一定得到TSP路径的最优解，但在实时加工环境中极大地降低了计算复杂性。另外，通过对 DXF文件中的图元及其控制点的优化排序，实现了按绘图或加工方向的图元优化排序的数据输出，应用于激光加工软件中，优化了其图形雕切时的路径顺序，减少了大量无效空走行程，利用较低复杂度算法实现了雕切效率的极大提高，降低了经济成本[5]。

[1]王晓东. 算法设计与分析[M]. 北京：清华大学出版社, 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数据交换接口实现 AutoCAD在激光加工中的应用[J]. 激光技术, 2005, 29(1)：32-34.

[4]龚清洪, 常智勇, 莫 蓉, 等. 基于 DXF文件的图元优化排序[J]. 计算机应用, 2006, 26(1)：169-173.

[5]刘晓东, 胡 兵, 何云贵, 等. 激光雕刻的数学模型及快速算法研究[J]. 计算机辅助设计与图形学学报,1999, 11(2)：151-153.

[6]王 伟. 激光图形切雕系统智能化应用研究[D]. 武汉：华中科技大学, 2006.

[7]胡胜红, 刘晓东. 基于 AutoCAD 面域的图形接口开发及其应用[J]. 工程图学学报, 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-），男，湖北武汉人，讲师，博士研究生，主要研究方向为激光先进制造技术。