search

t-oster / VisiCut

A userfriendly tool to prepare, save and send Jobs to Lasercutters
https://visicut.org
Other
233 stars 114 forks source link

TSP VectorOptimizer #226

Closed renebohne closed 6 years ago

renebohne commented 9 years ago

One group of students implemented a TSP VectorOptimizer. At the moment, it is based on scpsolver.

We all know that TSP is a hard problem and that the optimisation will need resources and a lot of computing time. But the result will improve cutting time. Therefore, we need to make sure, that the result is saved into an SVG or PLF file, so that the calculation can happen at home and the results can be opened in the fab lab (using sorting "FILE").

I will attach some images later...

Problems:

renebohne commented 9 years ago

tsp1 tsp2 tsp3

mgmax commented 9 years ago

sounds nice, but in practice it is also very important that inside holes are cut first.

Most SVG files have connected paths, where the current implementation of INNER_FIRST sorting works. If a path is split, we have problem #203 that the sorting is theoretically correct inside-out, but a huge waste of time.

It would be interesting to see how large the potential for improvement actually is - I doubt we can reach more than 10% in real-world files and that the "path-optimal solution" is optimal to what the user wants.

t-oster commented 9 years ago

I cannot see the TSP as optimizer in VisiCut, after (locally) merging #241 . Is this feature fully implemented?

feklee commented 9 years ago

What's the status of the optimizer?

I'm running 1.7-245-g89a10cd.

Remarks and questions:

mgmax commented 9 years ago

I have a completely opposite opinion regarding "inner holes first": I have seen many projects that fail or become imprecise with a "as fast as possible" sorting. Just think of a slightly bent piece of wood - it will easily move one millimeter when being cut.

But of course, the current primitive inside-out algorithm doesn't work with split paths (and was never supposed to do that, but rather needs a preprocessor).

Can you explain "sort by center of gravity" in more detail? Can this somehow take "inside" and "outside" into account?

feklee commented 9 years ago

Can you explain "sort by center of gravity" in more detail? Can this somehow take "inside" and "outside" into account?

To be honest, I didn't realize that Visicut does sorting already - should have read the comments properly. So I just proposed the first thing that came into my mind and that is easy to describe.

As VisiCut does sorting, it's weird that I've seen the laser jump wildly over the entire board today. I assume, though I'm not certain, that the latest stable version of Visicut was used (Fab Lab Berlin). May try to cut something tomorrow, from my machine, with 1.7-245-g89a10cd.

t-oster commented 9 years ago

Well... the fetaure seems to be somewhere in the code, since LibLaserCut does not compile without the library (and on the travis CI server, it does not compile because it can't find it), but I do not see it anywhere. If there is not much interest or progress for that feature in the near future, maybe we should remove it in order to keep dependencies and code base small?

t-oster commented 8 years ago

So.... anyone interested in this feature? If not, I am going to remove it, because I cannot see an improvement, which would justify adding a big library and bloating the code

thinkl33t commented 8 years ago

I think its of more academic interest than a useful feature - i've never managed to make it actually work.

renebohne commented 8 years ago

you can remove it. But I hoped that people will look at the code and find a way to actually use it in one way or the other. Visicut was the first laser cutter software that used TSP when mankind did not know how to solve NP-hard problems in linear time

mgmax commented 6 years ago

As it has been removed and will not probably come back again soon, can we please close this issue?