This is the second in a series of posts involving the travelling salesman problem, somehow even more frivolous than the first. This is no coincidence, as I have recently been reading the excellent book ‘In Pursuit of the Travelling Salesman‘, which goes into great detail on the history of the problem and algorithmic techniques for tackling it. The topic which caught my eye was decidedly less technical, as we shall see below.
The Travelling Salesman Problem, or TSP, involves finding the shortest path between a collection of points (‘cities’ in the TSP literature). For the purposes of this post the points are assumed to lie on the 2D Euclidean plane, though this need not be the case – see here for an impressive example involving non-Euclidean geometry.
Some bright spark decided to try distributing the points according more aesthetic rules such that their density approximated that of an image, and solve the resulting TSP problem. This has become known as TSP art, and you can see some great examples here.
I wanted to get in on this action, so I’ll outline the technique and show off some of my creations.
First we have to generate a series of points which approximate a given image. One way to do this is to think of an image as a 2D probability distribution, where dark areas represent high probability and light areas low. Points are then drawn from this distribution at random. I used an implementation on the Mathworks File Exchange here called ‘pinky’, which draws samples from arbitrary 2D distributions.
While this works, and in the limit of infinite samples would create a perfect grayscale image, it suffers from a bit too much randomness. Some points are more tightly clustered than others which looks a little uneven. It would be nice to spread the points more evenly, while maintaining the variation in point density which defines the image.
Clever TSP artists have naturally already considered this, having given us the technique of ‘weighted Voronoi stippling’. You can read an overview here, and the associated, quite readable, paper here. The idea is to
- Create a Voronoi diagram of the set of points
- Find the centre-of-mass of each Voronoi region
- Move the points to their centres of mass. If the image is and the Voronoi region of point is , then the centre of mass coordinates are and .
For a uniform image this works as expected – spreading the points out evenly:
For a non-uniform image the integration tends to push points towards areas of higher probability, or darker areas of the image:
So we have a method for creating a distribution of points, how about joining them up?
In possibly the least controversial statement I’ve ever written here, I’m not quite up to the task of writing a TSP solver. Fortunately for the algorithmically-challenged there are a number of codes out there.
The most famous is concorde, capable of finding the optimal path between tens of thousands of points. Given that the number of paths between points scales as this is a truly impressive statement.
For our purposes however an approximation to the optimal solution is fine – we are only interested in aesthetics here. In this case it is appropriate to use the LKH code (an abbreviation for the Lin-Kernighan heuristic), which works by swapping pairs or triplets of points at a time. The benefit is that LKH can be much quicker than concorde – from the plot below up to 50x quicker on my machine for small problems while finding a solution within 0.5% of optimal.
Enough description then, what does my TSP art look like? Let’s start with some simple images of piecewise uniform density:
This is working quite nicely, let’s try something more complex. Can you guess the famous faces below from their TSP art? (selected on the basis of the existence of a nice profile shot on Google images with a white background.) The answers are at the bottom.
It’s possible to make some nice TSP art, but what’s my additional contribution here? I’ve created a couple of looping TSP animations, simply TSP-ifying every frame of an animated GIF. This took a little longer, so I’ve stuck to a simple monochrome image where fewer stippling iterations are needed.
In the first format, each frame is treated independently of the others:
This is fine, but there’s a bit of flickering which might be unappealing to some. In this second version, the previous frame is used as an input to the current frame, which then undergoes a few iterations of stippling. The result is an animation which flows better, with the disadvantage that it can’t respond to sudden changes in the image.
The code to create these images is in my Github repository here. I have also uploaded the .eps files in case anyone would like to try cutting out this TSP art on a CNC machine or laser cutter. Let me know if you do 🙂
The faces are, of course
- Cara Delevingne
- David Tennant
- Natalie Portman (minus one point if you said Kiera Knightly)