TSP Art

The Travelling salesman problem (TSP) can be used to generate pictures like:

We first need to generate a point cloud from an image. Here is the source image:

If we randomly generate points according to the grayscale value of the pixels in this source image, we get:

It is not a very beautiful picture. We’d like to have points with a more regular spacing.

We are using those initial points but we modify their positions using the following method.

New random points (attractors) are generated following the grayscale distribution of the source image. In the point cloud picture, we look for the points which are the closest to the attractor points we have just generated.

Those points are moved towards the attractors. Each point of the point cloud has a weight. The new position is weighted average between the point in the point cloud and the closest attractor point.

The weight of a point is increased after it is moved. So, a point which is moved often is less and less sensitive to the new attractor points which are randomly generated.

If we apply this method to the previous picture, we get something like:

It is a much better looking picture.

This picture is the one used for solving the TSP problem. I have used Mathematica to solve it.

Here is the final result:

We can also colorize the result using the colors of the original picture. And we can generate a video by following the path generated by the TSP problem.

Here is an example:

The original artwork used to compute this video is by Sephora Venites.

Thanks to Sephora Venites to allow me to use some photos and videos for experimenting with my algorithms.