The Travelling Salesman Portrait
This article is originally published at https://fronkonstin.com
I have noticed even people who claim everything is predestined, and that we can do nothing to change it, look before they cross the road (Stephen Hawking)
Imagine a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge is finding the route which minimizes the total length of the trip. This is the Travelling Salesman Problem (TSP): one of the most profoundly studied questions in computational mathematics. Since you can find a huge amount of articles about the TSP in the Internet, I will not give more details about it here.
In this experiment I apply an heuristic algorithm to solve the TSP to draw a portrait. The idea is pretty simple:
- Load a photo
- Convert it to black and white
- Choose a sample of black points
- Solve the TSP to calculate a route among the points
- Plot the route
The result is a single line drawing of the image that you loaded. To solve the TSP I used the arbitrary insertion heuristic algorithm (Rosenkrantz et al. 1977), which is quite efficient.
To illustrate the idea, I have used again this image of Frankenstein (I used it before in this other experiment). This is the result:
You can find the code here.
Thanks for visiting r-craft.org
This article is originally published at https://fronkonstin.com
Please visit source website for post related comments.
