<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/the-travelling-salesman-portrait/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://fronkonstin.com/2018/04/04/the-travelling-salesman-portrait/"> R – Fronkonstin</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<div class="twitter-share"><a rel="nofollow" href="https://twitter.com/intent/tweet?url=https%3A%2F%2Ffronkonstin.com%2F2018%2F04%2F04%2Fthe-travelling-salesman-portrait%2F&via=aschinchon" class="twitter-share-button" target="_blank">Tweet</a></div>
<blockquote>
<p>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)</p>
</blockquote>
<p>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 <a rel="nofollow" href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" target="_blank">Travelling Salesman Problem (TSP)</a>: one of the most profoundly studied <em>questions</em> 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.</p>
<p>In this experiment I apply an heuristic algorithm to solve the TSP to <em>draw</em> a portrait. The idea is pretty simple:</p>
<ul>
<li>Load a photo</li>
<li>Convert it to black and white</li>
<li>Choose a sample of <em>black</em> points</li>
<li>Solve the TSP to calculate a route among the points</li>
<li>Plot the route</li>
</ul>
<p>The result is a <em>single line drawing</em> 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.</p>
<p>To illustrate the idea, I have used again <a rel="nofollow" href="http://ereaderbackgrounds.com/movies/bw/Frankenstein.jpg" target="_blank">this image</a> of Frankenstein (I used it before in <a rel="nofollow" href="https://fronkonstin.com/2017/03/07/frankenstein/" target="_blank">this other experiment</a>). This is the result:</p>
<p><img data-orig-file="https://i1.wp.com/fronkonstin.com/wp-content/uploads/2018/04/frankyTSP.png?fit=2400%2C3000&amp;ssl=1" data-orig-size="2400,3000" data-medium-file="https://i1.wp.com/fronkonstin.com/wp-content/uploads/2018/04/frankyTSP.png?fit=240%2C300&amp;ssl=1" data-attachment-id="4470" data-image-meta="{" data-image-description="" src="https://i1.wp.com/fronkonstin.com/wp-content/uploads/2018/04/frankyTSP.png?resize=604%2C755&ssl=1" data-permalink="https://fronkonstin.com/2018/04/04/the-travelling-salesman-portrait/frankytsp/" data-large-file="https://i1.wp.com/fronkonstin.com/wp-content/uploads/2018/04/frankyTSP.png?fit=604%2C755&amp;ssl=1" alt="" data-image-title="frankyTSP" sizes="(max-width: 604px) 100vw, 604px" width="450" data-comments-opened="1" class="wp-image-4470" data-recalc-dims="1"></p>
<p>You can find the code <a rel="nofollow" href="https://github.com/aschinchon/travelling-salesman-portrait" target="_blank">here</a>.</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://fronkonstin.com/2018/04/04/the-travelling-salesman-portrait/"> R – Fronkonstin</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/BSPcSbD_8aY" height="1"></a></div>