SOLVED!
This is a pretty huge breakthrough for me. I've been puzzling away at this problem for over a year now. I'm excited to say that I've solved it. More details below for those curious.
My solution can fill a complex region with arbitrary holes quite quickly (sub-second in my tests). It travels around the borders of the fill region (either the outer border or the borders of the holes). Any given section of the border is stitched over a maximum of twice. No jump stitches are required.
I owe it all to this paper, "Approximation algorithms for lawn mowing and milling":
http://www.sciencedirect.com/science/article/pii/S0925772100000158
I'd previously reviewed the paper for ideas but I hadn't fully grasped the one key aspect to their milling algorithm. They build a graph of all of the rows and outlines -- that much makes sense. The ridiculously clever part is duplicating some of the edges in order to make a graph that must have an Eulerian Path in it. Then you just find such a path using a well-known algorithm, and you've created your milling path (or stitching, in my case).
It still required the addition of several heuristics to make the stitching come out nicely and the pathfinding complete quickly. Any old eulerian path solution would technically work, but it's going to be weird if you stitch a row here, another one way down there, etc.
Anyway, bottom line is, "a solution exists". I'm still in the process of converting from the graph-theoretical solution to the actual stitching, but at this point the algorithm is sound and the rest is busywork.
Thanks everyone for the tips and for being a sounding board! --Lex
On 8/28/2017 3:01 PM, Lex wrote:
Ah, I see. My machine (a Brother SE400) can't cut the thread and continue stitching. It's a pretty difficult limitation to work with. I try to avoid jumps whenever possible, and when I have to, I place jumps such that they're easy to trim by hand.
On August 28, 2017 1:45:33 PM Michael Soegtrop <MSoegtrop@...3339...> wrote:
Dear Lex,
yes, in case there is a large distance, the TSP solver makes a jump. My machine can actually do jumps (knot the threads and cut them at both ends), so my main goal is to optimize the number of jumps.
What one should do is try to order the groups such that connections can be hidden below other stitching, but this is complicated, especially when you don't have the concept of an area (my stuff just works on open paths).
Best regards,
Michael
On 25.08.2017 21:05, Lex Neva wrote:
Hi! Sorry for going dark there -- everyday life intrudes fairly often.
Neato, and thanks for the explanation! It does indeed look like your stuff follows a similar method to inkscape-embroidery. A few minor differences:
- The extension handles creating a "grating" of lines automatically and
intersects them with the fill region using Shapely (a Python extension).
- The fill pattern is handled automatically through the insertion of
extra nodes as you mentioned. Currently there's only one pattern: a sort of stair-step/staggered pattern that is visually pleasing. I cribbed it off of a pattern I bought online that was made using a commercial embroidery design program. I'd love to understand how to code more complex patterns, but I haven't given much thought to it yet.
- The extension used to have a TSP solver of its own, but it really
didn't do a particularly good job. I started off trying to fix bugs and ultimately just ripped it out. Instead, I carefully order paths in Inkscape. The new Objects panel is key for this, and it's a hugely awesome addition to Inkscape! The only part I struggle with is that Inkscape doesn't want to let you reorder objects relative to each other if they don't intersect (or nearly intersect).
Ultimately, the problem I brought up for discussion boils down to the same problem you're solving with the your TSP algorithm. *Question: *what does your code do if it needs to get from one section to another that is distant? Does it just jump-stitch?
Here's a brief description of how to use EmbroiderModder2's libembroidery to convert between formats: https://github.com/lexelby/inkscape-embroidery#optional-conversion-program
I'd suggest that your code simply output a CSV in the format libembroidery understands, and then you can make use of its knowledge of pretty much every manufacturer format to convert it to a format compatible with your machine.
--Lex
On 7/30/2017 11:47 AM, Michael Soegtrop wrote:
Dear Lex,
I guess we are trying to solve the same problem, but differently. I wanted to have more control than semi automated fillers provide, so I added 3 LPEs, which are in Inkscape 0.92.2:
1.) A bool LPE to do intersections / unions, ... of areas, so that one can construct the areas to stitch from drawing areas.
2.) A path / path group trimmer LPE, which restricts a set of paths to an area (or oustide of an area. There are already two path interpolation LPEs which allow to create sets of paths with fine control over local direction and density.
3.) An LPE to convert a set of paths into stitches. This includes an almost reasonable traveling salesman problem (TSP) variant solver for ordering groups of stitches to minimize the traveling in between. It can still be improved. It is a bit more complicated than standard TSP solvers, because it looks into groups of parallel stitches which have 4 possible ends.
My approach is as follows
1.) Make a drawing
2.) Use the bool op LPE to create (in a new layer) the areas to fill with each color / stitch style.
3.) Create a set of path to control density and direction using path interpolation LPEs. This allows a great deal of control, e.g. for hair. I don't think any commercial tool allows this amount of control.
4.) Use the path trim/cut LPE to trim the paths created in 3.) to the areas created in 2.)
5.) Use the embroidery stitch LPE to convert the paths to stitches.
Sometimes I use the cut / trim filter also to create intermediate nodes in paths to create special stitching patterns. These nodes are not visible in normal drawing, but after stitching they are visible.
Of cause for simple cases, it would help to extend it with a more automated approach, which is what you appear to be working at.
I am very interested in the import/export library you mentioned.
It would be great to work together on this.
Best regards,
Michael
--
= Dipl. Phys. Michael Sögtrop = Datenerfassungs- und Informationssysteme = Steuerungs- und Automatisierungstechnik = = Anzinger Str. 10c = 85586 Poing = = Tel.: (08121) 972433 = Fax.: (08121) 972434 ===========================================
Check out the vibrant tech community on one of the world's most engaging tech sites, Slashdot.org! http://sdm.link/slashdot _______________________________________________ Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel