I'm excited to see this breakthrough hit the website extensions
library.
But when it's done in due time :D
Martin,
On Mon, 2017-09-25 at 08:59 -0600, Ryan Gorley wrote:
> Sounds incredible. Well done!
>
>
> Ryan Gorley
> Managing Partner | Dijt
>
> On Fri, Sep 22, 2017 at 4:58 PM, Lex Neva <inkscape@...3585...> wrote:
> > 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@...3616...
> > > -Soegtrop.de> 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- conve
> > > > > rsion-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@...1784...sourceforge.net
> > > https://lists.sourceforge.net/lists/listinfo/inkscape-devel
> >
> > ------------------------------------------------------------ -----
> > -------------
> > 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@...1784...sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/inkscape-devel
> >
> ------------------------------------------------------------ -------
> -----------
> 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@...1784...sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/inkscape-devel
------------------------------------------------------------ ------------------
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@...1656...784...sourceforge.net
https://lists.sourceforge.net/lists/listinfo/inkscape-devel