ANA-hash table sorting algorithm for curve objects in WEDM CAMShow others and affiliations
2020 (English)In: Procedia CIRP, Elsevier B.V. , 2020, p. 371-376Conference paper, Published paper (Refereed)
Abstract [en]
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.
Place, publisher, year, edition, pages
Elsevier B.V. , 2020. p. 371-376
Keywords [en]
Ana-Hash Table, Curve objects sorting, Embedded CAM software, Wire electrical discharge machining (WEDM), Computational complexity, Computer aided design, Computer aided manufacturing, Computer software, Data structures, Electric discharges, Computeraided design, Curve object sorting, Design files, Embedded computer aided manufacturing software, Hashtable, Sorting algorithm, Table sorting, Wire electrical discharge machining, Electric discharge machining
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-302882DOI: 10.1016/j.procir.2020.02.290Scopus ID: 2-s2.0-85102021965OAI: oai:DiVA.org:kth-302882DiVA, id: diva2:1599894
Conference
20th CIRP Conference on Electro Physical and Chemical Machining, ISEM 2020, 19 January 2021 through 21 January 2021
Note
QC 20211002
2021-10-022021-10-022022-06-25Bibliographically approved