+1 Thanks for helping make Inkscape more useful to a broader audience! If you'd favour us with some photos of the extension working, the Vectors team can prepare a press release to celebrate the new extension on our social networks.

I think it's a cool enough feature to make some noise about. :)

On 25 Sep 2017 4:17 p.m., "Martin Owens" <doctormo@...400...> wrote:
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