-
-
Notifications
You must be signed in to change notification settings - Fork 47
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Reduce travel time by solving open-loop TSP on paths #13
Comments
Perhaps a good place to start, I've had good experience with this: |
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. |
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. |
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.
The text was updated successfully, but these errors were encountered: