基于LibreCAD的电火花线切割CAM实体排序算法研究

沈桂旭，夏蔚文，陶旭牧野，赵万生

（上海交通大学机械与动力工程学院，机械系统与振动国家重点实验室，上海200240）

基于LibreCAD的电火花线切割CAM实体排序算法研究

沈桂旭，夏蔚文，陶旭牧野，赵万生

（上海交通大学机械与动力工程学院，机械系统与振动国家重点实验室，上海200240）

在电火花线切割CAM软件的开发过程中，针对DXF文件的实体排序问题，提出了基于LibreCAD文件读取的实体排序算法，可同时实现封闭图形、非封闭图形及多图形文件的实体排序。通过分析DXF文件中实体自身的排序特点，提出了一种用于处理大数据量实体搜索的记忆搜索算法，基于前一步搜索的实体进行区域内智能搜索。经过数值计算及实际测试对比，记忆搜索算法能实现高适应性、高准确率、高效率的实体搜索与排序。

电火花线切割加工；CAM软件；DXF文件；实体排序；记忆搜索算法

电火花线切割常用于加工淬火钢和硬质合金等高熔点、高硬度的特殊金属材料，在模具制造、刀具加工、精密复杂零件加工等领域得到广泛应用[1]。其中，往复走丝电火花线切割机床因其结构简单、性价比高，在我国应用广泛。随着智能制造深入发展，对传统往复走丝线切割加工的控制技术也提出了更高的要求。在线切割数控编程中，多采用DXF文件写入加工图形，线切割CAM软件通过处理DXF文件，获取零件的几何信息，规划加工路径，最后输出加工G代码，以实现零件的加工。CAM软件的重要功能之一是对DXF文件中的实体按加工方向重新排序，将实体首尾相连。由于线切割加工图形具有多样性、复杂性的特点，且在几何建模时的顺序也可能随机，故准确、高效的实体排序算法显得尤为重要，且能直接决定线切割CAM软件轨迹规划的准确度和效率。

线切割图形大多由直线和圆弧组成，读取DXF文件中的实体段可获取单个实体的起始与终止位置，从而进行连接性判断与排序。在线切割CAM软件开发过程中，相关科研机构与学者也提出了相应的实体排序算法。邢海蛟通过端点距离比对的方式，获取与上一实体距离最近的实体，实现图形中实体的连续排序[2]。张为民通过结点搜索的方式，遍历所有实体对象，将搜索到的连续实体逐一存入结点，进行封闭图形实体的重新排序[3]。曹琨等通过传统循环遍历算法实现首尾相连实体的排序，并采用逐步从搜索列表中移除已排序实体的方式，在一定程度上提高了搜索与排序的效率[4]。

在线切割加工的轨迹规划过程中，当DXF文件中同时存在封闭与非封闭图形时，传统排序方式并未进行区分处理，且对于大数据量的实体图形，如何进行高效完备的排序也非常关键。本文针对线切割加工轨迹规划的这些特点，基于开源软件Libre CAD的DXF实体读取API（application programming interface，应用程序编程接口），设计了实体排序新算法，有效地进行多图形文件的单独图形实体排序，统一处理封闭、非封闭图形的实体排序。通过分析DXF文件中原实体的排序特点，提出了记忆搜索的新算法，极大地提高了大数据量图形（如数万个实体的图形）的轨迹规划效率。

1 LibreCAD与DXF文件读取

LibreCAD是一款轻量级开源CAD软件，支持Windows、Mac 及 Linux 系统[5]，支持 DXF、DWG 等图形文件的导入与读取，具备丰富的平面图形绘制功能。LibreCAD底层采用Qt C++编写[6]，开放二次开发的编程接口，基于其提供的实体读取API，可方便地实现对DXF文件中几何实体数据信息的读取。

DXF是一种用于二维图形数据交换的标准文件格式，广泛用于处理和记录二维CAD数据，特别是在不同的CAD平台之间进行数据交换时起到了很好的桥梁作用。DXF文件是由可读的ASCII字符组成的文本文件，其结构见图1，其实体段部分包含了图形中所有几何实体的信息[7]。通过LibreCAD源码开放的getAllEntities函数，可获取DXF文件中所有的实体，并读取实体段记录的具体数据信息。

图1 DXF文件结构

2 多图形实体排序算法

针对存在多个图形的线切割图形文件，若选择某个图形实体（Entity）对象（以下简称“实体”）作为起始段，需从所有实体中将包含起始段实体在内的独立图形搜索出来，并按加工顺序对实体排序。

为了进行连续实体搜索，需确定实体的端点坐标，以用于判断实体间是否连接。对于直线段，实体段中记录了起点及终点坐标等信息；对于圆弧，实体段中记录了圆心坐标、半径、圆弧起始与终止角度、顺逆时针等信息，由此可计算得到圆弧的起点及终点坐标。

假设圆弧圆心坐标为（X，Y），半径为R，起始角为 α，终止角为 β，设圆弧起点坐标为（X1，Y1），则：

设圆弧终点坐标为（X2，Y2），则：

采用二元数据结构对搜索到的实体进行存储，两个数据位分别记录实体对象及方向标识。其中，方向标识为布尔值，实体本身方向为从起点到终点，当实体方向与加工方向一致时，方向标识为真，反之，方向标识为假。按照加工方向搜索时，由方向标识确定当前实体参与搜索的端点，以便搜索下一实体。此外，方向标识在生成加工代码阶段也起着重要作用。图2是排序算法实现过程，通过不断搜索与当前端点连接的下一段实体，进而实现完整图形的搜索与实体排序。

图2 排序算法实现过程

封闭图形搜索的终止条件是：当前搜索端点连接至起始实体。非封闭图形搜索的终止条件是：未找到连接实体，即当前搜索端点为断点。达到任意终止条件，则单个图形的所有实体排序完成，不再进行实体搜索，由此实现多图形文件中单独图形的实体排序。同时，根据终止条件类型可判断当前图形的封闭性。

3 记忆搜索算法

线切割加工的复杂图形通常由大量的直线或圆弧拟合而成，在规划这类大数据量实体图形时，传统的遍历算法效率低，会造成CAM软件运行卡顿甚至卡死的情况。通过分析发现，DXF文件中的几何实体是按照图形绘制时的顺序排列，对于大数据量实体图形，尤其是区块化明显的图形，区域内的小线段往往连续绘制，在遍历时最大程度上优先搜索区域内的连续实体，可极大地提高排序效率。

在搜索过程中采用记忆搜索算法，即每个搜索循环结束时，记录当次搜索到的实体在实体表中的序号，并从表中移除该实体；下一循环优先从表中该实体原前、后相邻的实体开始搜索，找到相连实体则结束当次搜索循环，否则依次遍历实体，直至找到相连实体或达到终止条件。

假设某个区域内的图形为连续绘制，即该区域内所有实体均与实体表中前、后实体相接，此时搜索与该实体n相连接的实体。传统遍历算法的搜索过程为：

实体1与实体n比对

实体2与实体n比对

……

实体n-1与实体n比对

实体n+1与实体n比对

……

若实体n-1与实体n按加工方向相连，该次搜索共比对n-1次；若实体n+1与实体n按加工方向相连，该次搜索共比对n次。

记忆搜索算法的搜索过程为：

实体n-1与实体n比对

实体n+1与实体n比对

……

若实体n-1与实体n按加工方向相连，该次搜索共比对1次；若实体n+1与实体n按加工方向相连，该次搜索共比对2次。

假设该区域内实体总数s为10 000，选择其中第n个实体开始进行排序，完成全部排序过程的总搜索次数记为Z。

若加工方向与原实体表排序方向相同，传统遍历算法有：

当n=1或n=10 000时，搜索比对次数最少，为9999次；当n=5000时，搜索比对次数最多，为25004999次。

而记忆搜索算法有：

若加工方向与原实体表排序方向相反，传统遍历算法有：

当n=5000时，搜索比对次数最少，为2.5×107次；当n=1或n=10 000时，搜索比对次数最多，为50005000次。

而对于记忆搜索算法有：

绘制由10 000条小线段顺序连接拟合成的圆，以Qt C++编写传统遍历搜索算法和记忆搜索算法测试程序。在表1所示的测试环境下，按圆的顺、逆时针方向分别进行搜索与排序，进行两种算法的对比测试，搜索过程用时对比见表2。

表1 搜索算法测试环境

表2 顺序连接图形的不同搜索算法用时对比

从上述数值计算及实际测试对比中可看出，相比传统遍历搜索算法，记忆搜索算法具有以下特点：①显著减少搜索次数，大幅提高搜索效率；②不受起始实体位置影响，受切割方向影响小，稳定性较强；③实体数量增加，与传统遍历算法的搜索次数呈几何增加不同，记忆搜索算法的搜索次数呈线性增加，具有较好的适应性；④存在多个图形时，能较好地避开无关实体搜索，保证搜索效率。

在实际线切割加工中，大实体量图形通常不会完全按照连接顺序绘制，而是区域内顺序绘制，由多个图形区域最终组成完整图形。如图3所示，“双马”图形总计11 061段实体，为分区域连续绘制而成。以该图形为例，对其进行算法搜索效率对比，测试环境同表1所示。

图3 “双马”图形

选择多个起始位置进行测试，两种算法搜索用时对比见表3。可见，记忆搜索算法在处理更具一般性的图形时，实现了区域内的最优搜索，保证了搜索效率。

表3 “双马”图形的不同搜索算法用时对比

4 结束语

针对电火花线切割CAM软件加工代码生成的需要，提出了一种利用LibreCAD进行文件读取的DXF实体排序算法，同时提出了一种记忆搜索算法用于处理大数据量实体搜索。通过数值计算及实际测试对比，记忆搜索算法能实现高适应性、高准确率、高效率的实体搜索与排序。与传统实体排序算法相比，记忆搜索排序算法具有以下优点：①封闭、非封闭图形可统一进行搜索与排序；②可逐一处理多图形文件中的单独图形实体搜索与排序；③大幅提高了实体搜索效率，避免了实体数量巨大时搜索次数的几何增长；④避免了起始加工位置不同或文件中存在多个图形引起的搜索效率波动。

记忆搜索算法已成功应用于基于LibreCAD的线切割CAD/CAM软件系统，对于包含大量几何实体的DXF文件的线切割加工路径规划、加工G代码生成任务，均具有快速、精准的处理效果。目前，采用记忆搜索算法的线切割CAD/CAM软件系统已可用于生产，具有线切割G代码生成功能，并支持多次切割、变锥度切割、上下异形面切割、非封闭图形切割等高端往复走丝电火花线切割加工所必备的高级处理功能。

[1]蒋秋生.高速走丝电火花线切割CAD/CAM系统关键技术研究[D].广州：广东工业大学，2005.

[2]邢海蛟.基于AutoCAD图形数控切割的应用研究[D].哈尔滨：哈尔滨理工大学，2015.

[3]张为民.电火花线切割CAD/CAM集成系统关键技术研究[D].杭州：浙江大学，2004.

[4]曹琨，范益民，罗凌，等.基于Linux的图形交互线切割加工CAM软件关键技术 [J].电加工与模具，2010（2）：20-23.

[5]陈俊聪.基于Linux数控系统的CAD二次开发研究与实现[D].广州：华南理工大学，2016.

[6]赵永光.使用LibreCAD开发纸包装结构辅助设计软件的研究[J].印刷杂志，2016（11）：45-48.

[7]李芳珍，许伦辉.DXF文件格式及其外部接口的研究[J].兵工自动化，2008，27（7）：83-85.

Study on Entity Sorting Algorithm for WEDM CAM Based on LibreCAD

SHEN Guixu，XIA Weiwen，TAO Xumuye，ZHAO Wansheng
（ State Key Laboratory of Mechanical System and Vibration，School of Mechanical Engineering，Shanghai Jiao Tong University，Shanghai 200240，China ）

In the development process of WEDM CAM，a new entity sorting algorithm based on LibreCAD file reading is designed to solve the entity sorting problem of DXF file which contains huge number of geometric entities.Through the new algorithm，the entity sorting of closed geometry file，nonclosed geometry file and multi-geometry files can be realized at the same time.Based on the analysis of the sorting characteristics of the entities in a DXF file，a memory search algorithm is proposed to deal with the large data volume entity search.Based on the previous search，the intelligent search is carried out.Through the numerical calculation and the actual test comparison，the memory search algorithm can achieve high adaptability，high accuracy and high efficiency entity search and sorting.

WEDM；CAM software；DXF file；entity sorting；memory search algorithm

TG661

A

1009－279X（2017）05－0022-04

2017-08-03

沈桂旭，男，1992年生，硕士研究生。