TSP Art

The traveling salesman problem (TSP) is a well-known NP-complete problem. It has appeared in diverse field of human knowledge. Different heuristics have been developed to generate approximate solutions for TSP. In this project, we used 3 different heuristics for TSP to implement a half toning algorithm. We followed the 3 steps below to implement a half toning algorithm.

Given any input image,

• If the image is a color image, convert it into a black & white image.
• Now we generate the "cities"/vertices of a complete graph on which TSP algorithm will be applied. We distribute cities with a density that locally approximates the darkness of a source image.
• Now we run nearest neighbor, greedy and 2-opt heuristics for TSP on the "cities". This produces a single closed path that resembles the original image.

Development Platform

This project was developed in C# 2.0 using Microsoft Visual Studio 2008.

View Screenshots

Report

The project report can be found here.

SVN Repository

The source code repository is hosted at code.google.com. You can checkout the source code from here.