The Travelling Artist Problem
This is the second in a series of posts involving the travelling salesman problem, somehow even more frivolous than thefirst. 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.TSP Art
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.The process
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.
Here there are 2,000 points.
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 techniqueof ‘weighted Voronoi stippling’. You can read an overview here , and the associated, quite readable, paper here . The idea is toCreate 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
For a uniform image this works as expected spreading the points out evenly:
Here there are 50 points on a uniform image over 25 iterations.
For a non-uniform image the integration tends to push points towards areas of higher probability, or darker areas of the image:
Here there are 50 points spread over the function
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 theLin-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.
Here refers to the running time of the code, and to the total length of the optimal path. 10 repetitions were performed for each problem size. The art
Enough description then, what does my TSP art look like? Let’s start with some simple images of piecewise uniform density:
Britain (not the UK! Sorry NI)
The world’s most dull university logo. Note the tasteful variation in density between the upper and lower lines.
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.
Face #1. 10,000 points.
Face #2. 10,000 points.
Face #3. 5,000 points. TSP Animation
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:
Forgive the artefacts from the GIF optimisation. 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 ani