TSP crossing

The question behind the “Traveling Salesman Problem” is basically, what’s the most efficient path through a large number of points? ¹  There are probably many important applications of this difficult mathematical problem, but the most interesting for me is line art.  If you’ve been following the progress of the MakerBot Unicorn or Egg-Bot projects, you’ve already seen some incredible examples of “TSP” line art.

Untitled by mifga

This thing brought to you by

Untitled by mifga

This thing brought to you by

Untitled by mifga

This thing brought to you by

The current process for converting a picture to TSP line art is pretty involved.  From the excellent TSP line art tutorial over at Evil Mad Scientist labs, the process involves converting the image to greyscale, converting it into a stippled image, putting the points through a TSP solver such as the Concorde TSP solver package to create the TSP line art from the stippled image and end up with an SVG file.  At that point you could probably use Schmarty’s Inkscape GCode extension. ²³

I would love to see this process become simplified.  I suspect the best method for doing so might lie in the creation of a GIMP⁴ plugin.  GIMP already has the mechanisms for many of the above steps.  A GIMP plugin could probably automate the “grayscale -> stippled image -> point puddle” process.⁵⁶  Once that was done, the resulting “point puddle” would still need to be fed through the TSP solver.  However, I suspect this might be able to be done by having GIMP call the Concorde TSP solver.  This would take it from “point puddle -> TSP solver -> SVG file” which could then be turned into GCode using the above Inkscape extension.

Besides my belief that there just isn’t enough TSP line art in the world, there are a bunch of reasons I’d love to see this plugin pop into existence.   The top three reasons being the Unicorn, the Egg-Bot, the CNC Etch-a-Sketch.    After that, I’d have to say – TSP line art renderings of photographs and old master works of art.  I would love to see a web cam hooked up to a Unicorn for instant TSP line art photobooth style sticky note generation!

1. Photo courtesy of robotson [↩]
2. Basically, image -> gray image -> point puddle -> TSP solver -> printable SVG path [↩]
3. I say point puddle since it’s not a 3D point cloud.  Just a 2D … puddle of points. [↩]
4. My favorite open source image manipulation/editing software [↩]
5. See note above last for explanation of “point puddle.” [↩]
6. “Point puddle” you heard it here first! [↩]