Re: [Inkscape-devel] Inkscape for embroidery

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 good results. 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. Best regards, Michael