Continuous toolpath generation

We’re currently working on a project that need an optimal tool path given an input image. Unlike most 2-D controllers, we can’t issue a command to raise and lower the tool – it has to be a continuous path, so it makes for an interesting problem! This is the problem of drawing a picture without lifting the pen from the page.

I’ve written some code to use a “nearest neighbour” approach to the travelling salesman problem. It’s not the optimal solution, but it works ok. The key problem being the algorithm’s inability to use a pixel more than once. It’s also quite slow but that’s not a big deal and could be easily optimised using a grid search if necessary.

Our test input image was:

Test image for pathing

After we ran our code we got:

line path solution

While it’s obvious that there’s lots of extra paths we can get rid of if we fix up the algorithm I think it’s a great first pass! We now just need to treat the problem as something less restrictive than the travelling salesman problem.

Leave a Reply