# The Travelling Salesman Portrait

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.

## 11 thoughts on “The Travelling Salesman Portrait”

1. PhilliP Paul says:

I follow your R-bloggers post. Love it.
Today you wrote “A simple definition of laminar flow is when a fluid flows through a pipe in parallel layers with no disruptions between these layers” Look at wikipedia Kármán vortex street for an example of laminar flow. Laminar flow is not turbulent flow where turbulent flow is chaotic.

2. Atmajit says:

Hi Antonio,

Thank you for sharing your code.

I was trying to reproduce your plot but am having some issue with the code. I think its when you use row_number() it gives me an error.

data.frame(id=solution) %>%
mutate(order=row_number()) -> order

so i updated your code to

data.frame(id=solution) %>%
dplyr::mutate(order=row_number()) -> order

and am able to generate the plot but my plot looks like a lot of lines and no where close to frakenstein. Any idea what could be the issue. Thanks.

Regards,
Atmajit

3. nicolas says:

Hi,

I have the following error message:

data.frame(id=solution) %>%
+ mutate(order=row_number()) -> order
Error in rank(x, ties.method = “first”, na.last = “keep”) :
argument “x” is missing, with no default

any idea of whats wrong?

Best regards and many thanks for your code

4. Nick says:

Cool! But I think this post is a trap to get nerds to say “Frankenstein is the name of the scientist, not the monster”, and I won’t be falling for that.

5. Andrew says:

Very cool, as always 🙂

6. Aria says:

Hi 🙂 thank you for your code. This is really cool however no matter what image I upload, I still always get Frankenstein back. I was trying to get a Rhinoceros but I still end up with Frankenstein in the end. Is this because the TSP algorithm is linked to the Frankenstein image?

Here is a sample of my code:

install.packages(“imager”)
install.packages(“magrittr”)
install.packages(“dplyr”)
install.packages(“ggplot2”)
install.packages(“scales”)
install.packages(“TSP”)
install.packages(“stringi”)

library(imager)
library(dplyr)
library(ggplot2)
library(scales)
library(TSP)

urlfile=”https://www.conservationmagazine.org/wp-content/uploads/2014/02/white-rhino.jpg&#8221;
file=”white-rhino.jpg”
if(!file.exists(file)) download.file(urlfile, destfile = file, mode = ‘wb’)
load.image(file) %>%
grayscale() %>%
threshold(“45%”) %>%
as.cimg() %>%
as.data.frame() %>%
sample_n(8000, weight=(1-value)) %>%
select(x,y) -> data

as.TSP(dist(data)) %>%
solve_TSP(method = “arbitrary_insertion”) %>%
as.integer() -> solution

data_to_plot <- data[solution,]

ggplot(data_to_plot, aes(x,y))+
geom_path() +
scale_y_continuous(trans=reverse_trans())+
coord_fixed()+
theme_void()

ggsave("rhinoTSP.png", dpi = 600, width = 4, height = 5)

1. @aschinchon says:

Hi, thanks! No, it’s not linked. Did you restarted Rstudio session? If still doesnt work, let me know.