Editing TSP art

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 1: Line 1:
{{EggBotDocs}}
 
 
 
 
http://wiki.evilmadscience.com/s3/eggbot/tspart/mona-lisa-tsp.png
 
http://wiki.evilmadscience.com/s3/eggbot/tspart/mona-lisa-tsp.png
  
Line 12: Line 9:
 
Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....
 
Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....
  
Welcome to "TSP art" in which an image's tonal quality is reproduced with a '''single''', continuous path.  This single path meanders over the entire canvas.  Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image.  And, fewer segments of the path in lighter regions.  But how and where do we choose to draw this path?  By treating this question as a [http://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling Salesman Problem (TSP)], a suitable path may be determined.  To do so, we first produce a stippled representation of the image.  We then  ask, "What is the shortest possible path that visits each and every stipple exactly once and then returns to the starting point?"  That is precisely the Travelling Salesman problem with cities in the salesperson's journey replaced by stipples on our canvas.  Determining an answer to the TSP is actually very hard (NP-hard).  But, even fast approximate answers work well for TSP art.  See the image at the top of this page for an example.
+
Welcome to "TSP art" in which an image's tonal quality is reproduced with a '''single''', continuous path.  This single path meanders over the entire canvas.  Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image.  And, fewer segments of the path in lighter regions.  But how and where do we choose to draw this path?  By treating this question as a [http://en.wikipedia.org/wiki/Travelling_salesman_problem Travelling Salesman Problem (TSP)], a suitable path may be determined.  To do so, we first produce a stippled representation of the image.  We then  ask, "What is the shortest possible path that visits each and every stipple exactly once and then returns to the starting point?"  That is precisely the Travelling Salesman problem with cities in the salesperson's journey replaced by stipples on our canvas.  Determining an answer to the TSP is actually very hard (NP-hard).  But, even fast approximate answers work well for TSP art.  See the image at the top of this page for an example.
 
 
TSP Art was first developed by [http://www.oberlin.edu/math/faculty/bosch/tspart-page.html Robert Bosch], who (together with [http://www.cgl.uwaterloo.ca/~csk/ Craig S. Kaplan]) is also responsible for applying this method to the results of stippled images [5,6].
 
 
 
 
 
Resources on this wiki for making your own TSP Art:
 
 
 
* [[StippleGen|Using StippleGen to Generate TSP art]]
 
 
 
For those wishing to understand more about the mechanics of generating TSP art using an older, alternate tool chain, review these pages:
 
  
 
* [[Obtaining a TSP solver]]
 
* [[Obtaining a TSP solver]]
Line 29: Line 17:
 
* [[Color TSP art]]
 
* [[Color TSP art]]
  
http://wiki.evilmadscience.com/s3/eggbot/tspart/starrynight.jpg
+
hhttp://wiki.evilmadscience.com/s3/eggbot/tspart/starrynight.jpg
  
 
== Notes ==
 
== Notes ==
Line 37: Line 25:
 
[3] A brief introduction to stippling can be found in the Wikipedia article [http://en.wikipedia.org/wiki/Stipple Stipple].<br/>
 
[3] A brief introduction to stippling can be found in the Wikipedia article [http://en.wikipedia.org/wiki/Stipple Stipple].<br/>
 
[4] To prevent mushrooming of your pen tips, select a reasonable value for your Eggbot's "pen lowering speed" in the "Timing" tab of the "Eggbot Control" extension.<br/>
 
[4] To prevent mushrooming of your pen tips, select a reasonable value for your Eggbot's "pen lowering speed" in the "Timing" tab of the "Eggbot Control" extension.<br/>
[5] "Continuous Line Drawings via the Traveling Salesman Problem" (Robert Bosch and Adrianne Herman), ''Operations Research Letters'' '''32''' (2004) 302-303.<br/>
+
[#] Starry Night by Vincent van Gogh.  Digital copy of Starry Night converted to a CMYK color space and then each color layer separated.  Each individual layer was stippled with Gimp as per [[Producing a stippled image with Gimp]] and then TSP solutions for each stippled layer produced following the directions from [[Generating TSP art from a stippled image]].  The four resulting SVG files were then combined to make the resulting (scaled down) image shown above.
[6] "TSP Art" (Robert Bosch and Craig S. Kaplan), ''Proceedings of Bridges 2005'' (2005) 303-310.<br/>
 
 
 
 
 
[#] Starry Night by Vincent van Gogh.  Digital copy of Starry Night converted to a CMYK color space and then each color layer separated.  Each individual layer was stippled with Gimp as per [[Producing a stippled image with Gimp]] and then TSP solutions for each stippled layer produced following the directions from [[Generating TSP art from a stippled image]].  The four resulting SVG files were then combined to make the resulting (scaled down) image shown above.  A larger copy may be seen at http://www.flickr.com/photos/46175218@N02/5348523884/in/photostream/.
 

Please note that all contributions to Evil Mad Scientist Wiki are considered to be released under the GNU Free Documentation License 1.3 (see Evil Mad Scientist Wiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel | Editing help (opens in new window)

Template used on this page: