Inventables Community Forum

TSP Art App

Hi All,

I’m working on a new type off app for generating TSP Art (Traveling Salesman Problem.)

The whole idea is to turn a picture into a single line drawing for use with the CNC.

Example:

I tried it out last night and got pretty good results:

The app seems to work ok. Right now I get the best results from using black-and-white clip-art. I am working on a photo version that stipples the image first then performs the traveling salesman on it.

The base TSP version is based on this:
http://www.kristenwebster.net/projects/algorithmic-art-case-study.html

The stippling version is based on this:


If there is any interest in this app, please let me know!

Cheers,
Ethan

8 Likes

Interesting work. I’m curious about why I see more “links” than I expected between the shapes. I guess there are constraints I can’t see.

So the algorithms work towards a stable point. Given enough time, there would be no “links” in the art. That’s kinda the fun and frustrating thing about the traveling salesman problem, there’s likely a shorter route, we just don’t know know what it is.

The program works in this case by swapping the paths and making the route shorter and shorter until one of the swaps makes it longer again, then it stops. The program implements 2-opt to prevent the paths from overlapping, but it doesn’t necessarily force it to have the shortest path.

I’ll probably add an option to remove paths longer than x length. You wouldn’t have a single path anymore, but you wouldn’t have those “links” either.

1 Like

I’ve seen similar work with Sierpinski traverses. Someone did a Sierpinski portrait of Sierpinski. You could also do a Hilbert traverse.

I’d love to see the Stipling version. I could see doing that with a Vbit making little hole marks on two-layered materials to create the contrast in a picture. Are you working on making a Stipling app?

Yes, I’m also working on a halftoning app, a stippling app, and the TSP app. Here are some examples from the halftone:

The thing i’m running into is how to allow the user to further process the image to get a better result dynamically.

Here is a test i’m working on to allow the program to run as long as the user wants:
com-resize

So if I can get this to work well with the stippling app, we may have a winner.

3 Likes

Seriously wish I had your talent.

1 Like

Awesome Ethan.
Can similar be applied to an existing project to take individual lines and make it continuous?

For example https://easel.inventables.com/projects/EZgyOiDvh_0YvxvA8v259g

I started with a pic of a geranium and traced in Autocad with polylines. I attempted to make as many long continuous runs of “tool in work” as I could stand to spend time on. I include even a few places of “go out and back” just to try and reduce tool lifts.

I also ran it through that xyzbots optimizer (had to edit the file afterward to make it compatible with Easel - mainly just changing to all caps) to try and reduce the amount of “tool out of work” traveling.

Would your algorithm (with tweaks) be capable of “glueing” together more of the lines. Even having short backtracks is likely shorter time to cut than the Traveling Salesman code generated by Easel.

It might be possible if every line were subdivided into a series of points then apply the TSP algorithm to that set of points and remove all lines / moves longer than a given threshold limit. It should give you the same output with a reduced number of tool lifts.

that is going to be killer! can i assume that the traverse lines between fill areas can be overcome?

Yeah, I’ll have to put a routine in the program that removes lines longer than a specified threshold. As a result you may no longer have one continuous path, but I doubt anyone would ever notice.

Looking forward to seeing this available, THANKS!

seriously impressive! I’m thinking it will be cool to export to svg, then have it laser-scored. It will be fun to watch the action, but it will probably burn out the servos.

I’ve done some “fractal” puzzles on the laser. It seems your app might also be adapted for that also.

Would love to use it.

This looks amazing! I would love to use it… is there a way for me to use it now?

Unfortunately, no. It’s only accessible to the development team right now. And I have a few… bugs… to work out :slight_smile:. But if you have a specific use in mind that you’d want me to run it on and send to you, you can PM me and I’d be happy to do that.

ha, no worries, i understand how these things work.

I don’t have a specific need right now, more of an interest to play around with it.

If you need someone to help test, please let me know if I can help.

1 Like

Impressive and useful. Can’t wait!

Hej @EthanKinney,
is there any progress on this app. What I saw here looks quite impressive :slight_smile:

Hey Christopher!

I’ll hit up inventables development team on a list of apps I wanted them to approve earlier this spring. When those get released I’ll push to get the TSP art app and heightmap app approved and released too.

Thanks!

2 Likes