algorithm.html

For simplicity, the algorithm is broken into two separate conceptual entities.

  1. DXF Vertex parser and polyline isolation algorithm
  2. Polyline outline generation algorithm

Part 1 sounds rather simple: given a file of vertices, determine which vertices form poly-line segments and from there, determine which polyline segments form polylines. I was quite green at DXF before I started, so I read up on the structure and cranked out a parser that was originally written in Perl. I soon realized, however, that I needed more horsepower if I was going to complete this monster, so I settled on my old favorite C++. Initially, I thought that the algorithm would include some type of tree structure with a recursive visitation of the nodes to expand the vertices and look for matches. I must admit that I banged my head against this problem for many days while the complexity went through the roof. Finally, I came up with a much simpler stack machine that kept track of the nodes and built polylines in a more robust manner. What about efficiency? Well, forget about O(log n)! It is more like O(n^3), which, considering the number of vertices that are being processed, is not too bad for a brute force algorithm. It took about two weeks of tinkering with this thing to convert the raw DXF to the 86 polylines on my three axis driver board.

Part 2 is a beautiful and frightening mess of trig equations. I sat down one night and tried to derive a few equations for an isolation path, and to my amazement, I remembered some math! I came up with most of the equations on the fly and later found a site on the web with similar results. I am sure there is an elegant vector solution to this problem as well, but I am not interested in writing a vector math library right now. I'll try to get the formulas and diagrams posted soon for you geeks.

I anticipate a Visual C++ package eventually, but for now, its just an old command line exe. I'll probably offer the whole thing, source code included, for about $20 once I get a front end built. This just covers a bit of my time and provides me with some funds to build something else!

Here is the much anticipated and elusive algorithm of the DXF to Gcode isolation tool path converter!

Part 1 algorithm:

Parse out all of the vertices from the DXF file and build vertex pairs (X1, Y1, X2, Y2)
foreach vertexPair
 if top of stack is not used 
 push the first vertexPair on the stack
  while the stack is not empty
    find all matches in vertexPair of top of stack X1, Y1
     if no matches found, process X2, Y2 
     else 
       foreach match
         if match == top of stack and not already a part of the current polyline
           push the top of the stack onto the current polyline list
           pop the stack
         else if match is not in current polyline list
           push match on the stack
    
    find all matches in vertexPair on top of stack X2, Y2  
      if no matches found, process X2, Y2 
      else 
       foreach match
         if match == top of stack and not already a part of the current polyline
           push the top of the stack onto the current polyline list
           pop the stack
         else if match is not in current polyline list
           push match on the stack
  if no match in X1, Y1 or X2, Y2 break out of while
  mark all polyline segments in segment list as used
  clear all the lists and get next vertex


Part 2 algorithm: Coming soon!