Reduce travel time by solving open-loop TSP on paths

[sameer]

This is an idea I had from the very beginning, but requires a lot of time investment for questionable reward.

svg2gcode draws paths one by one with a naive DFS traversal of the SVG. There is a better way to do this that could be faster. Each path has a start and an end point. We could solve the open loop traveling salesman problem on the set of all paths to find the ordering that minimizes the total G0 move time.

It is a bit difficult as this is unfortunately not a Euclidean TSP, but some modification thereof due to the path start/stop points.

[thomaskole]

Perhaps a good place to start, I've had good experience with this:

https://xyzbots.com:4000/gcode-optimizer/

[timschmidt]

The hilbert crate can provide an approximate solution to this problem which preserves locality through the 2D->1D transformation: https://crates.io/crates/hilbert Because points in hilbert 1D space are also close to each other in 2D space and vice versa.

[kvdveer]

I'm going to have a stab at this. Don't let that dissuade other from trying too - I'm learning rust in the process, in my (rare) off-hours.

@sameer suggested using https://github.com/sameer/raster2svg/blob/main/src/graph/tsp.rs, I'll investigate that first. It's not going to be a drop-in solution, as gcode moves don't end where they start, and also they can be reversed. This makes the problem different than a point-to-point traveling salesman problem.