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:
After we ran our code we got:
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.