The Travelling Artist Problem

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.

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.

FootballExample.png
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 technique of ‘weighted Voronoi stippling’. You can read an overview here, and the associated, quite readable, paper here. The idea is to

  1. Create a Voronoi diagram of the set of points
  2. Find the centre-of-mass of each Voronoi region
  3. Move the points to their centres of mass. If the image is I(x,y) and the Voronoi region of point i is V_i, then the centre of mass coordinates (x_c, y_c) are x_c = \iint_{V_i} xI(x,y)\,\text{d}x\text{d}y/\iint_{V_i} I(x,y)\,\text{d}x\text{d}y and y_c = \iint_{V_i} yI(x,y)\,\text{d}x\text{d}y/\iint_{V_i} I(x,y)\,\text{d}x\text{d}y.
  4. Repeat

For a uniform image this works as expected – spreading the points out evenly:

voronoi
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:

VoronoiNonUniform.gif
Here there are 50 points spread over the function I(x,y) = \sin^2(x)\sin^2(y).

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 n points scales as n! 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.

Benchmark.png
Here \tau refers to the running time of the code, and \ell 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.png
Britain (not the UK! Sorry NI)
Earth.png
The world
IC_TSP.png
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.

FaceF_10000.png
Face #1. 10,000 points.
FaceM_10000.png
Face #2. 10,000 points.
FaceF2_5000.png
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:

YinYangAnimSmall.gif
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 animation which flows better, with the disadvantage that it can’t respond to sudden changes in the image.

YinYangAnimAdiabaticSmall.gif
Another disadvantage is that the looping isn’t as effective.

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 🙂

Happy travels!

Answers

The faces are, of course

  1. Cara Delevingne
  2. David Tennant
  3. Natalie Portman (minus one point if you said Kiera Knightly)

 

Advertisements

6 thoughts on “The Travelling Artist Problem

    1. Hi Robert, thanks! I hadn’t seen your site actually, thanks for the link. I have seen some of your work before though, it must have featured in Cook’s TSP book?

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s