Minimize travel moves

Threw together a little prototype using the neat or-tools optimization library from Google.

It uses G00 (move) commands as delimiters to separate a file into re-orderable segments and then solves traveling salesman to minimize the distance spent on travel moves between those segments. Some but unfortunately not all of the gcode I’m interested in follows that rule; straight lines longer than a certain length would be another easy heuristic to split on.

This Inkscape tracing of a diffusion-reaction pattern erases itself with vertical travel moves.

But if we optimize it without reversing any of the segments (traversing them all start-to-end) then we get

And if we duplicate all the segments with reversed versions (tracing the line end-to-start instead of start-to-end) and tell the optimizer that the duplicate is mutually exclusive with its twin then we get the very neat

Artistically the second one happens to look the best on sand even though it travels a bit more.

diffuse_ortools2.gcode (713.1 KB)

1 Like

Something I’ve noticed in TSP art drawings is that the curve never crosses itself. This makes sense because if it did cross itself, it could be made shorter by exchanging two points and reversing half the curve.

Anyway another possibility for your case would be to decompose the curves into a large number of points along the curve and then throw the whole thing (now a large set of points) into a TSP solver. It should reconstruct almost all the lines and hop between them in a minimal fashion.

1 Like

You might be thinking about https://www.evilmadscientist.com/2012/stipplegen2/ which stipples and then generates a path between the points. I haven’t tried this with sand but got good results when testing the same plotter mechanism with a pen.

Breaking them into line segments would make it be able to leave in the middle of a path to join another path. That would certainly help it come up with something shorter.

Yes, exactly.