电火花线切割CAM线对象类哈希表排序算法

【作者】 秦岭； 张敏； 陈默； 奚学程； 赵万生；

【机构】 上海交通大学机械与动力工程学院机械系统与振动国家重点实验室；

【摘要】 在电火花线切割数控系统中,将CAD图纸转化成加工指令(例如G代码)是CAM软件的核心功能。而图纸的线对象(直线和圆弧)数据结构是按照绘图顺序储存的,与加工路径没有直接联系,几乎是随机的,所以将线对象从绘图顺序排列成加工顺序是关键的步骤之一。传统遍历算法是对所有线对象的端点进行遍历,以完善一个大小为n×n的邻接矩阵,从而找出线对象之间的邻接关系,然后排序得到加工路径。因为矩阵中的n×n个元素都需要单独计算,所以这样做的复杂度是O(n2),当线对象很多时排序时间累积明显。一个复杂的线切割图纸可以有超过10000个线对象,传统遍历要进行约5×107次比较计算和花费约30秒的处理时间,严重降低了系统的操作效率和流畅度。因此线对象的排序速度,直接决定了CAM软件的工作效率。根据线切割路径的加工路径均为无重复点的欧拉闭迹的特点,提出了线对象类哈希表排序算法。哈希表算法是根据关键码值而直接进行访问的数据结构。通过把关键码值映射为一个地址来访问记录,当检索此数据时直接按照映射规则访问储存地址,以达到加快查找速度的目的。但可能存在碰撞的问题,即不同的数据的映射值相同,这是哈希表要避免的。在本问题的数据结构中,原本就存在完全相同的数据,即拥有相同二维坐标的顶点,这样的数据无论如何进行映射都会碰撞,而完善邻接矩阵时正是要找出这些碰撞的数据。考虑到顶点的坐标可以视为特殊的二维地址,可能发生碰撞的数据也拥有相同或相近的地址,对其地址进行预先分类可以极大提高检索效率。将哈希表概念中的表单元扩展为桶,桶的数据储存边界按照整张图纸的尺寸进行均匀划分,即把一张图按坐标划分为数张小图,将所有顶点数据存入对应的桶中,对桶中的数据进行分别比较计算,可极大地减小运算量。每个顶点只需与其所在桶中的其他数据对比,因为目标序列是无重复点的欧拉闭迹,所以顶点在找到与其碰撞的顶点后便可退出计算,时间复杂度从O(n2)降低为O(nlogn)。在嵌入式平台Firefly-RK3288使用类哈希表算法对CAD图纸进行测试,测试对象包含的线对象数量从500到10000不等,根据图纸的尺寸差异,使用合适大小的桶进行分类,相比传统遍历算法节省的时间均在90%以上,且图纸中线对象数目越多,节省的时间越多。线对象数目超过10000时,传统遍历算法需要的时间已接近30s,而使用类哈希表算法仍可在100ms内完成,节省时间超过99%,极大提升了操作线切割数控系统时的效率和流畅度。更多还原