Editing TSP art
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 12: | Line 12: | ||
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. This form of artwork was first developed by [http://www.oberlin.edu/math/faculty/bosch/tspart-page.html Robert Bosch], who is also responsible for applying it to the results of stippled images [5,6]. |
− | |||
− | |||
− | |||
− | |||
− | |||
* [[StippleGen|Using StippleGen to Generate TSP art]] | * [[StippleGen|Using StippleGen to Generate TSP art]] |