Single Line Art / Traveling Salesman Problem Tutorial

MakerBot Replicator TSP Single Line Drawing

MakerBot Replicator TSP Single Line Drawing

The “Traveling Salesman Problem” (“TSP”) is a problem studied in mathematics where one tries to figure out the shortest path through a number of points.  Solving for the absolute shortest route can take a lot of processing power and time, but getting a pretty good approximation can be very quick.  The Eggbot, MakerBot Unicorn, and drawing robots are particularly well suited to these kinds of drawings.

Recently I tried to create some of my own single line / TSP art based using the awesome Evil Mad Science TSP guide.  In doing so I think I may have figured out a way simplify the process slightly for Windows users. 1  The EMS guide has the user install Cygwin in order to provide certain elements of Unix for running the Concorde or Linkern TSP solvers.  However, I accidentally discovered that once you have the “cygwin1.dll” out of the Cygwin installation, all you need to do is create a batch file for automating the TSP conversion.  So, start to finish, here’s how I do it:

Programs / Scripts

  1. Download and install the free open source Python programming language
  2. Download and install the free open source GIMP image manipulation software2
  3. Download the Evil Mad Scientist Eggbot scripts for creating TSP vector art.  You’ll want the file named, “tsp_art_tools_0_8_3.zip”
  4. Download the Linkern TSP solver from Georgia Tech’s website
  5. Download the “cygwin1.dll” file for running the Linkern TSP solver on a Windows platform

Install Scripts

  1. Put the “cygwin1.dll”, “linkern.exe”, “tspart.py” , “tspbitcity.py”, “tspsolution.py” into a folder location of your choice

Make a Grayscale Image

  1. Open your image in GIMP
  2. Turn the color information monochrome “Image -> Mode -> Grayscale
  3. Open the color levels “Colors -> Levels
  4. Wash out the image by adjusting “All Channels” in the pop-up window to some value to 2003

Make a Stippled Image

  1. Turn the washed out grayscale image into a stippled image “Create Image->Mode->Indexed
  2. Select these options in the pop-up window
    • Use black and white (1-bit) palette): Checked
    • Remove unused colors from colormap: Checked
    • Color dithering: Floyd-Steinberg (normal)
  3. Click “Convert
  4. Save the file in the “Portable Bit Map” format “File->Save As” and saving the file with the extension “.pbm
    • If given the option, choose to save the PBM file in the “Raw” format

Create a Batch file to automate the Stippled Image to a TSP Line Drawing conversion

  1. Open “tspart.py” with your favorite text editor4 and change line 76
    • From:      LINKERN = ‘C:\linkern.exe’
    • To:    LINKERN = ‘C:\FILELOCATION\linkern.exe’
    • Save “tspart.py”
  2. The command for converting the PBM file takes three parts, the location of Python, the location of “tspart.py” and the location of your PBM file.  Here are where my files are located:
    • My Python directory is located at “c:\python\python”
    • My scripts are located in a subdirectory on my desktop “c:\python\python C:\Users\MakerBlock\Desktop\TSP\scripts\tspart.py”
    • My PBM file is also located on my desktop “C:\Users\MakerBlock\Desktop\TSP\images\drawing.pbm”
  3. Open a text editor and copy these three locations into one line as follows:
    • c:\python\python C:\Users\MakerBlock\Desktop\TSP\scripts\tspart.py C:\Users\MakerBlock\Desktop\TSP\images\drawing.pbm
  4. Save the text as a batch file named “convert2tsp.bat”

Use the Batch file to convert the Stippled Image to a TSP Line Drawing

  1. Double-clicking the batch file will convert “drawing.pbm” into “drawing.svg”
  2. To convert your next file, you can either name it to “drawing.pbm” or edit the Batch file to reflect a different PBM file name.

If you haven’t tried to create some single-line-artwork yet, give it a shot today!  It’s a lot easier than it looks and the results are really satisfying!

Once you’ve gone through the above process once, it goes super quickly the second time.  You basically make your image grayscale, wash it out, save as a stipple file format, and then run the batch file.  The entire process takes about two minutes once you get the hang of it – with a full minute and a half or so just devoted to letting the TSP program do its thing.

Error - could not find Thing 19042.

  1. I know.  I’m trying to give it up too… []
  2. I like the PortableApps.com version []
  3. Values between 180 and 245 should work well []
  4. I like the PortableApps.com version of Notepad++ []