The workflow I use for generating TSP art is as follows:
- convert to grayscale;
- approximate the image by weighted Voronoi stippling; and
- heuristically "solve" the TSP.
Voronoi stippling chooses points which are at the centroids of their respective Voronoi cells, i.e., it uses a centroidal Voronoi tessellation. I used Lloyd's algorithm to find such points. Centroidal Voronoi tessellations can be viewed as energy minimizers and in this context Lloyd's algorithm is essentially gradient descent.
One might instead minimize a different energy function or use a second order quasi-Newton method. The main advantage of Lloyd's algorithm is that it has relatively low computational requirements: one only needs to repeatedly compute Voronoi diagrams. For this I used libvoronoi with a few modifications. (In particular, I fixed an overflow bug so that it could handle megapixel images and upwards of 100,000 points.) The library computes Voronoi diagrams using GPU acceleration, which is pretty neat.
To solve the TSPs I used Concorde. This package includes both a heuristic solver and a linear programming routine for proving rigorous bounds. Using the two one might hope to exactly solve the salesman problem, thus giving an NP-hardness-defying work of art.
TSP art, by definition, can be drawn with one continuous series of strokes. As such it has found use in applications as diverse as egg decoration. The examples below use relatively few points to emphasize this piecewise linearity.
