Dear Inkscape Developer-Team,
I just wanted to give an update on the embroidery functionality.
Essentially it works, but there is one open end.
The open end is a function to reorder the cut pieces such that a minimal
number of longer jumps is needed in between (jumps are expensive in
embroidery because the thread needs to be cut and knot). This is
essentially a traveling salesman problem with a few additional complexities.
1.) I don't connect points as in a usual TSP, but lines, and the tour
needs to visit each line exactly once. This is similar to a usual TSP
where pairs of cities have a 0 distance connection, but the difference
is that I need a guarantee that the 0 distance paths are all taken. When
I use a usual TSP algorithm, this is likely but not guaranteed.
2.) For performance reasons I collect groups of lines where both end
points have a mutual nearest neighbor (think of a zig-zag pattern). This
is a very common situation in embroidery patterns and cuts down the
number of segments by more than a factor of 10, which is a substantial
saving for a TSP algorithm. These zig-zag blocks results in block with 4
end points and 2 choices of 2 points. So I don't connect just lines, but
this kind of blocks with 2 choices of endpoints.
3.) Since I usually want an open path, I can ignore the longest connection.
Points 1 and 2 work with something like a variable k "Lin" algorithm.
Maybe later I will implement a Lin-Kernighan algorithm, if the Lin
algorithm is too slow, but with k=3 it is quite fast (fraction of a
second) even for quite complex patterns (29 zig zag blocks) and gives
What I am struggling with is point 3, which is essential to get good
results (or at least I believe so). I thought this would be easy, but it
is either slow or results in complex book keeping.