search

sameer / svg2gcode

Convert vector graphics to g-code for pen plotters, laser engravers, and other CNC machines
https://sameer.github.io/svg2gcode
MIT License
250 stars 50 forks source link

Reduce travel time by solving open-loop TSP on paths #13

Open sameer opened 3 years ago

sameer commented 3 years ago

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 commented 3 years ago

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

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

timschmidt commented 1 year ago

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 commented 6 months ago

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.