Posts for Tag: traveling salesman problem

Van Gogh As Drawn By A Traveling Salesman

Posted In: Fun | Math
Van Gogh Portrait Line Drawing

This “art project”, like the Mona Lisa one, draws a portrait of Vincent Van Gogh as a single continuous line. When it’s on the slow setting, is oddly satisfying and calming to watch the picture get drawn.

Click the “Draw Van Gogh” button below to see his famous self portrait drawn with a single continuous line with 120,000 segments.

The traveling salesman problem (TSP) is a classic problem in operations research and mathematical programming. It seeks to answer the question, given a set of destinations, what is the shortest possible travel route someone could take to visit them all. It is a notoriously challenging problem to solve when the number of destinations grows. A picture of the famous Van Gogh self-portrait was converted to 120,000 dots and a challenge was created to find the most optimal solution to visiting each of these 120 thousand points (i.e. drawing the shortest continuous line that goes through each and every point.

The current most-optimal solution that has been found to this Van Gogh self-portrait challenge was calculated in 2013 by Honda, Nagata and Ono. I used the order of destinations (also called the “tour) that he developed and animated the line segments to create an animated drawing of the portrait as a single continuous line.

Here an analogous TSP drawing for the Mona Lisa.

Each time you click on the “Draw Van Gogh” button, it chooses a different starting point but follows the same order of destination points, looping around until all the points are visited.

You can also change the speed at which the individual line segments are drawn. It is surprisingly relaxing and satisfying to watch the line wind its way around the screen to fill in the famous Van Gogh self-portrait.

For a very high res version of the entire photo click here (around 4 MB file size).

Data and Tools:
I downloaded the 120,000 points and the tour from Honda, Nagata and Ono that is currently the shortest that has so far been calculated from the TSP Art website and the University of Waterloo.
Javascript was used to draw on the HTML canvas and animate the process.

van gogh tsp

The Mona Lisa As Drawn By A Traveling Salesman

Posted In: Fun | Math
Mona Lisa TSP

The traveling salesman problem (TSP) is a classic problem in operations research and mathematical programming. It seeks to answer the question, given a set of destinations, what is the shortest possible travel route someone could take to visit them all. It is a notoriously challenging problem to solve when the number of destinations grows. A picture of the famous Mona Lisa was converted to 100,000 dots and a challenge was created to find the most optimal solution to visiting each of these 100 thousand points (i.e. drawing the shortest continuous line that goes through each and every point.
The current most-optimal solution that has been found to this Mona Lisa challenge was calculated in 2009 by Yuichi Nagata. This art is created using the order of destinations (also called the “tour) that he developed.

Click the “Draw Mona Lisa” button below to see the famous painting drawn with a single continuous line with 100,000 segments.

Each time you click on the “Draw Mona Lisa” button, it chooses a different starting point but follows the same order of destination points, looping around until all the points are visited.

You can also change the speed at which the individual line segments are drawn. It is surprisingly relaxing and satisfying to watch the line wind its way around the screen to fill in the famous picture of the Mona Lisa.

For a very high res version of the entire photo click here (around 4 MB file size).

Data and Tools:
I downloaded the 100,000 points and optimal tour from Yuichi Nagata from the TSP Art website and the University of Waterloo.
Javascript was used to draw on the HTML canvas and animate the process.

mona lisa tsp