Painting Software - The Path Maker

"The Path Maker" takes in a stippled image (produced by Painting Software - The Stippler) and outputs an image showing the shortest path that connects all these stipples. The path solves (approximately) the Traveling Salesman Problem (TSP), that is, it is the shortest possible route that visits each city (stipple point) and returns to the origin city (stipple point). At some point somebody figured out that solving the TSP on a stippled image creates a cool effect, mainly, because there is supposed to be no intersection. That's how "TSP art" was born.

Now, the crux of the problem is the (approximate) solution of the Traveling Salesman Problem (TSP) given a set of points (in our case, a whole bunch of stipples). I didn't code that part (it's a tough one) but the guys at Concorde TSP Solver did, and very well. Linkern is an implementation of the Chained-Lin-Kernighan heuristic for the TSP. The Path Maker uses the cycle/tour generated by linkern to produce the output image.

The software (for the windows 64 bit operating system) is available to download on dropbox at thepathmaker-x64.rar. It contains both linkern and The Path Maker. Concorde's linkern is used to get the tracing path as a cycle/tour (in text file form) and The Path Maker is used only to get the output image representing that tracing path.

After having extracted the archive, I invite you to go to the "jimi_hendrix" folder. There you will see a file named "linkern.bat" which needs to be edited (using notepad or wordpad or whatever editor you like) so that the path to the executable, linkern.exe, is the correct one for your installation. The software is run by double-clicking on "linkern.bat". The output from linkern (sample.cyc) is a tour/cycle of the points contained in the file sample.tsp. The file sample.tsp is the output from Painting Software - The Stippler. In the "jimi_hendrix" directory, there is also a file named "thepathmaker.bat" which needs to be edited (using notepad or wordpad or whatever editor you like) so that the path to the executable, thepathmaker.exe, is the correct one for your installation. The software is run by double-clicking on "thepathmaker.bat". The output from The Path Maker is an image showing the cycle/tour in image form.

The Path Maker's behavior is controlled by the input file named "thepathmaker_input.txt". The following shows what's in "thepathmaker_input.txt" in the "jimi_hendrix" directory:

source image = source_image.png
tracing path points = sample.tsp
tracing path segments = sample.cyc
output image = output_image.png
dot radius = 1
dot radius 2 (antialiasing) = 3

The source image is the reference photograph. It can be either tiff, png, or jpg. It can be either grayscale or full color. It should be the same one you used when running Painting Software - The Stippler.

The file containing the tracing path points (sample.tsp) is the output from Painting Software - The Stippler.

The file containing the tracing path segments (sample.cyc) is the output from linkern.

The output image contains the tracing path (black over white). It can be either tiff, png, or jpg.

Dot radius controls the size of the stipple dots. Dot radius 2 controls the amount of antialiasing. Dot radius 2 has to be greater than or equal to dot radius. Note that if dot radius 2 is equal to dot radius, there is no antialiasing in the output image.

Source image.

Output image.

Because Concorde can not be used for commercial purposes (actually, it's supposed to be used for academic research only), The Path Maker cannot be used for commercial purposes either. At some point, if there is a lot of interest for TSP art (which I doubt very much), I might implement my own version of an approximate TSP solver (based on the Lin-Kernighan TSP heuristic) but not at the moment as linkern does an excellent job.

Here's a tutorial video:



Source code: thepathmaker on github.