# Converting an undirected graph to optimal G-code paths

I am developing an image to gcode program, that would recognize edges and generate corresponding G-code to be sent to a plotter. I was able to detect edges using the Sobel operator; then the edges are converted to an undirected graph using a search heuristic of my creation. Converting a graph to functional gcode is not difficult: depth first search does the job. The issue is that using this method the generated paths for the plotter are far from optimal, since they contain many movements that could be removed or shortened just by printing paths in a different order. This can be seen clearly in the images below.

Is there an algorithm that can convert an undirected graph to optimal G-code paths? Otherwise, if there are none or the problem is NP complete, what heuristics can be used to generate almost-optimal gcode (e.g. the ones used in programs such as Inkscape)?

The graph on the left is converted to the gcode on the right using depth first search on the connected component of the graph. The white and red lines represent, respectively, the visible writes and the invisible movements of the plotter. The G-code can be found here.

• Pretty sure it is NP-complete (equivalent to travelling salesman problem), no? Feb 5 '20 at 22:04
• @R.. TSP is NP-hard, since it's something like O(n!) Feb 7 '20 at 21:26
• Is this just a learning project, or do you actually have something to print? Mar 19 '20 at 21:36
• Yes, this is a learning project Dec 14 '20 at 14:26

Quote of comment of R.. GitHub STOP HELPING ICE on question reads:

Pretty sure it is NP-complete (equivalent to travelling salesman problem), no? –

This is correct; this is route optimization at its purest, and is by no means a new problem. You want to travel the shortest total distance between all vertices of what's essentially a totally-interconnected graph; there are no inherent limitations on going from anywhere, to anywhere. The TSP is the general-case statement of this problem, which your problem specializes only slightly by predefining certain movements along edges as being required in the final path (but those edges can be traversed in either direction and in any order.

What makes this complex on its face is the sheer number of possibilities that an exhaustive solution to the TSP like Held-Karp has to evaluate. You have no real constraints regarding which points to travel between; you can go from anywhere, to anywhere. Only a relatively small number of edges (your extrusion lines) are known requisites, and those can theoretically be traced in any order.

If I'm reading your graph right, you start near the top center, then go to the top left, then to the s-curve, then you jump to the main shape and start traversing it from the "right arm", turning downward through the "body" and "left foot" of the central shape, then up to the "right hip", through that leg to the foot, then back up to the "left shoulder", through that "arm", etc.

If I have that right, then you definitely have "endpoint detection", where you are identifying points in the graph that are part of only one line segment (and therefore will require a travel move to get to or from them), and are planning travel moves to and from those points. Very smart. I would be interested in knowing exactly how you choose the next one to travel to. Obviously the closest endpoint of an undrawn line is a natural choice, but your algorithm doesn't seem to be doing that. Right from the off it chooses a relatively further point to extrude and then comes back to the rest of the shape. That actually seems to be the most efficient move in the overall graph, because if you don't get it early you will very likely make a big move to get back to it later, but making that decision in a non-exhaustive way doesn't seem intuitive.

Anyway, your algorithm was doing pretty well at path choice, up until it finished drawing the "right leg". The most efficient move from there would be to go to the bottom of the "Y" looking shape to the right of the main figure and trace through that. When that's done, the closest undrawn line segment will be back at the left shoulder of the main figure, which will lead you to the small dots, and you'll end in this region with relatively small travel moves. Overall, I think that a "closest remaining endpoint" strategy would be near-optimal at every turn; when you reach the end of a drawn line, look for the endpoint that is closest to your current location. It would make most of the decisions your existing algorithm does, and a few better ones. It's not always the best choice (case in point, the dot at the upper left, which is never closest to the end of any other move and so will be ignored until it's the last one left) but more often than not it is.

My programmer savvy says you also have some recursive intersection tracing ("tree-walking"); the algorithm sees that there are multiple paths to draw from a single point, remembers that point and then picks a path. When it reaches an end of a chain of extruded lines, it goes back to the most recently-encountered intersection, re-evaluates available paths, and picks the next one until all paths from that intersection are drawn. Then you skip back to the previous intersection, and so on in a recursive LIFO fashion.

While that's also generally a smart way to approach it, it makes a couple obviously inefficient moves, such as from the "right foot" of the main figure back to the "shoulder" (which is the most recent intersection visited but not fully drawn by that point). The more efficient move is simply the closest remaining endpoint, the bottom of the wonky-looking Y to the right of the main figure.

How you choose intersection paths to prioritize is also key. In general, taking the route that will lead you to the closest intersection or endpoint will reduce the possible backtracking you have to do. However your algorithm seems to prefer the longest path from a fork (or the one with the most forks along it) and that turns out not to be a terrible way to do it in this particular graph.

Now, having drawn the "left arm" of the main figure, it is totally beyond me why your algorithm chose to cross the graph to draw the wonky Y, then cross back over to the left side. That is by far the least efficient move it makes and the one you're probably pointing to yourself. The most efficient path from the end of the left arm of the main figure given what's left to draw is straight-up closest-endpoint, filling in dots and lines on the left side, then making one move across the graph to the wonky Y. Closest-endpoint would actually have already filled in that Y as covered earlier, and you'd end your graph traversal in the left region of dots and small lines. You may have one or maybe two relatively inefficient moves between corners of this region on the left of the graph depending on the closest point calculation, but those are minor compared to the moves made across the graph. If your algorithm is producing deterministic results for this graph, I'd debug it and step through to that point, and figure out why on Earth it thought that sequence was preferable. Optimizing that decision may very well be the key to a near-optimal overall graph-walking strategy.

If you can save your plot as a dxf, you can use Repetrel to generate gcode with our "find nearest neighbor" optimizing. You can download it from http://hyrel3d.net - the full install instructions start at http://hyrel3d.net/wiki/index.php/Installation_Overview

See the process in this video:

Disclaimer: I work for Hyrel 3D. Licensing only required on the actual printer, not the software install.

Note: This will generate gcode paths, but every printing move will have an E value of 1, so it's fine for lasering or ink-jetting, or running with the Hyrel native E calculations, but probably not useful for other 3d printers.

• Are you allowed to provide an explanation of the "find nearest neighbor" optimizing? Thank you :-) Feb 5 '20 at 19:03
• How it is done is beyond me - I'm not the coder. Sorry.
– Davo
Feb 5 '20 at 21:45