## The Travelling Artist Problem

| |
[ 所属分类 前端（javascript） | 发布者 店小二03 | 时间 2017 | 作者 红领巾 ] 0人收藏点击收藏

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

. Repeat

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

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

tags: points,TSP,The,image,here

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。