The Travelling Salesman Problem is a classic problem in mathematics. The objective of the problem is to find the shortest possible route between a number of cities that visits each city only once and returns to the starting point.
Below is a rendering of the text “MrReid.org” created by solving the Travelling Salesman Problem. If you look carefully you can see that in each case the text is composed of one single line, drawn “without lifting the pen from the page”.
Top to bottom: “MrReid.org” rendered using 1000, 2000, and 5000 nodes. Click to enlarge.
By taking a greyscale image, and turning it into a weighted Voronoi diagram (using Adrian Secord’s algorithm) it is possible to create a “map” in which the “cities” are placed closer together in dark areas and further apart in light ones.
Top: the original panda image. Bottom: weighted Voronoi diagram of panda image (10000 nodes).
By solving the Travelling Salesman Problem for this “map” (using the Nearest Neighbour algorithm for the first pass and and the 2-opt algorithm for subsequent optimisation) the following “route” is produced.
There isn’t really enough contrast between the background and foreground in the original panda image, but it works if you squint a little bit.
What language are you doing this coding in? Processing?
Originally I was using Concorde which is written in C, but now I’m using StippleGen2 which is indeed written in Processing.
Thank you for sharing. This is totally awesome.
For someone like me who is not fluent in programming, is there a way for me to generate these images on my computer, or do you need to have programming software already installed and know how to play around with it already?
If it’s the former, I can see myself becoming obsessed with these!
StippleGen2 by EMSL is what you’re looking for.
What software program did you use to make the image.?
what file type did you save it in.?
what software program did you use to convert the file into tsp lines.?
what file type did you save the tsp lines in.?
what software program did you use to open the tsp file and turn it into vectors.?
The travelling salesman solving was done by EMSL’s StippleGen. This was output as SVG, edited in Inkscape, and imported into GIMP.