Ana-Hash Table Sorting Algorithm for Curve Objects in WEDM CAM

Converting tool path geometries of a computer-aided design (CAD) file to computerized numerical control (CNC) commands is the core functionality of a computer aided manufacturing (CAM) software for wire electrical discharge machining (WEDM). The number of curve objects (such as lines and arcs) for a complex tool path can reach more than 20000. However, curve objects in a CAD file are sorted by drawing sequence instead of processing sequence, and slow sorting will cause an increase in elapsed time (more than 120 seconds accordingly) and a hanging consequence to the running of the embedded CNC system. Finding adjacencies of curve objects is a key step in curve sequence sorting. Conventional algorithms targeted at adjacencies traverse all vertexes of CAD files, whose complexity is O(n2). According to the characteristics of a WEDM processing path, Ana-Hash Table Sorting algorithm is proposed to reduce the elapsed sorting time. This algorithm classifies vertexes into corresponding buckets in advance according to the coordinates, and adjacencies are judged among specific buckets, so that most useless traversals can be avoided. The complexity of the algorithm is O(nlogn). Noticing that the sorting acceleration ratio varies widely in table parameters, the optimization of table generating rules is given. The proposed algorithm works efficiently when the number of buckets per row is 1% to 1.5% of the number of curve objects. And the elapsed sorting time can be dramatically reduced by 99% as compared to the conventional traversal algorithm.