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@...3615...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-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@...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