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.

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 $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$ .
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:

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

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.

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.

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:

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.

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

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

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

7 thoughts on “The Travelling Artist Problem”

gaurish says:

January 3, 2017 at 5:03 am

Awesome!

LikeLike

1. jasmcole says:
  
  January 3, 2017 at 1:49 pm
  
  Thanks!
  
  LikeLike
  
mfkasim says:

April 7, 2017 at 2:24 pm

I love your blog! I also wrote similar post to this: http://sp.mfkasim.com/2016/12/06/stippling-pictures-with-lloyds-algorithm/

LikeLike

Robert Bosch says:

May 14, 2017 at 5:52 pm

Nice work! If you haven’t see it already, check out the TSP Art portion of my website

http://www.dominoartwork.com/tspart.html

LikeLike

1. jasmcole says:
  
  May 14, 2017 at 7:35 pm
  
  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?
  
  LikeLike
  
  1. Robert Bosch says:
    
    May 14, 2017 at 11:28 pm
    
    Yes, Bill was kind enough to include a few of my pieces in his lovely book. One of them is a photo of my sculpture Embrace, which was made with a computer controlled water jet cutter. Here’s a link to a photo and description:
    
    http://www.ams.org/mathimagery/displayimage.php?pid=274
    
    LikeLike
nealagordon says:

June 28, 2017 at 3:54 am

fun post, and, as usual, amazing animations!

LikeLike