While working on an industrial optimisation problem involving very large scale instances of the
Travelling Salesman Problem,
I thought it would be an interesting expermient to generate a tour over a set of points obtained
from image dithering. It turned out that this had
been done before by Craig S. Kaplan and
Robert Bosch, who produced
excellent results using a combination of Voronoi Stippling
and the Concorde TSP Solver. Nonetheless,
having started the project; thought it would be fun to continue.

To generate a set of points from an image, I implemented the Floyd-Steinberg
dithering algorithm using Lisp. Next,
using these points, I applied the 2-Opt heuristic to
produce a reasonable "two optimal" tour. For this step I implemented Jon Bentley's
research on 2-Opt, with my own
improvements in Java, and as an excersise,
in Lisp.

Some results are shown below and a time-lapse video (25fps) showing the optimisation process to the left.
I'm using 2 Mucha artworks as input here simply because I thought they would produce interesting results.

The first example was chosen for it's contrast, which the algorithm reproduces nicely on the right. The
second example was chosen for it's shadow - I thought it may produce a Chiaroscuro
like effect. However, the initial dithering results in very dense regions of points, which makes Floyd-Steinberg
better suited to the higher contrast example in this case. Note that Bosch and Kaplan's results are superior to mine
as they use Voronoi Stippling which results in a reduced and better distribution of points, which is good from
both a visual and computational point of view.