kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
ANA-hash table sorting algorithm for curve objects in WEDM CAM
KTH, School of Industrial Engineering and Management (ITM), Production Engineering, Sustainable Production Systems. State Key Laboratory of Mechanical System and Vibration, School of Mechanical Engineering, Shanghai Jiao Tong University.ORCID iD: 0000-0002-7220-9271
Show 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

Available from: 2021-10-02 Created: 2021-10-02 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Chen, Mo

Search in DiVA

By author/editor
Chen, Mo
By organisation
Sustainable Production Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf