Wednesday, November 01, 2006

While trying to figure out ways to half-tone an image with a continuous line, I had the brainwave that traversing stipple points in Travelling Salesman Problem order might be an interesting way to do it. The travelling salesman problem is a famous optimization problem, famous for being famous, and famous for being computationally intractable. It's also famous for being easy to state as it is hard to solve: given a set of cities, what is the shortest route that goes through each of them? My thought was that the geometrically optimal line which joined all my stipple pts might also be aesthetically optimal.

So I went poking about the net for TSP software, and found out that a fellow named Craig S. Kaplan published a paper on this very technique about a year ago. You can check out the link here. I was a bit bummed to find someone had beaten me to the punch, but I wrote an implementation anyway. The pic above is a typical example. Enjoy. The effect avoids the lattice artifacts of the Sierpinski approach (though perhaps that's part of the charm?), and looks smoother overall.


Post a Comment

<< Home