Seeing how useful Matlab is in a number of combinatorial/optimization problems, I would like to know if it can be used to solve my problem as well. The problem at hand is cross-stitching. As you might know, in cross-stitching one embroiders the pattern onto a suitable cloth (generally this is a so-called “Aida” cloth, although the quality of the base textile is irrelevant in the problem posed – it can have some indirect scope in, say, calculating total yarn usage) with a continuous yarn. The pattern is generated by forming X-es, between the weave gaps of the base textile. A sample pattern is here, with a basic floral pattern.
..X...
..XX.XX..
XX.X.X.XX
.XX.X.XX.
...
.XX.X.XX.
XX.X.X.XX
..XX.XX..
..X...
In the attached pattern, dot means a space left empty, while an X means a place cross-stitched. A multicolour cross-stitch pattern is, for all purposes, just a sum of its elements, so it can be optimised discretely for each of the colours involved – but seeing such functionality is not something I am interested in or expecting at all.
In cross-stitching, the following constraints are observed:
- All X-es are executed in the same order. That is, depending on the decision of the program or embroiderer, first the \ (top-left to bottom-right or bottom-right to top-left) stitches are executed, then the / (bottom-left to top-right or top-right to bottom left), overlapping the previously laid \. This however does not mean that all such occurrences (pattern-wide) need to be separated, doing all \’s first then all /’s second; only that within the scope of an isolated cross-stitch of the pattern, there is ordered execution, but one easily might leave half of it done, then execute the other half somewhere in the middle, instead of separating the execution of the whole pattern into two strictly oriented phases. The execution order is relatively highly weighted, one can put a (say) +10.0 penalty on execution of a stitch in a wrong order (while it is possible to lead the needle and yarn under the previous stitch on the front side, it generally adds much to the difficulty of execution, and usually it comes out looking less neat.) The execution direction of a given sub-stitch of the X is essentially uninteresting (that is, no penalty for doing a \ stitch from top to bottom instead of bottom to top.) This is the route priority mentioned in the topic.
- The back side should preferably consist of unit-distance orthogonal steps. Of course, in case of a pattern more spread and disjoint, it is impossible to execute them without larger jumps, but these should be minimised, and preferably these should be also orthogonal. A suggested simple penalty metric is (distance travelled on backside)^2 – 1. Incidentally, the preferred execution by human hobbyists appears to give more weight to one axis over another (say, preferring vertical back side stitches over horizontal), but this, if any, should be given only very small penalty, on the scale of 0.025*(total count of back side orthogonal stitches in the wrong direction) or so.
- The front side is strictly not permitted to have any parts of the cross double-stitched (the yarn going the same front side subpath twice, regardless of direction).
- The back side is permitted to have the parts double-stitched (yarn going the same subpath twice), although this is discouraged. A suggested penalty metric would be (length of yarn overlapping) * 1.0.
From what I know, there was no research whatsoever on execution of cross-stitch patterns, neither is there any software that I know of (commercial or otherwise) that can do any optimisation or planning on the execution of a cross-stitch pattern. Since the research and functionality on executing these cross-stitch patterns might prove useful (for hobbyists or for software companies), I would like to know some suggestions, code or feedback on it. For a reasonable visual representation, the end solution should be presented in a “step-by-step” manner, with each step, presenting the consecutive front-side stitches (subpaths), showing its direction (maybe with a small arrow?), and showing the incoming and outgoing backside stitches in a lighter shade.
Generally, showing all backside stitches would result in a rather crowded display which would be a terrible mental gymnastics to interpret, so it is to be avoided – perhaps a separate summary output for showing general overlap in the end solution is something that could prove useful, showing possibly a 0.2 units wide yarn, and colouring the total overlaps with either a shaded weighted representation or the common green-yellow-red (“traffic light”) weighted representation. Possible extensions of the basic cross-stitched execution involve front-side half-stitches (only \ or / done instead of the full X, this could probably be relatively easily coded and executed, both in notation as well as programming), orthogonal stitches on the front side, or other stitches of varied length and angle – but all these are beyond the scope of my request, and I believe putting it all in would be a much more challenging task (not to mention they’d need a more intricate notation, one that I wouldn’t undertake inventing. But sure enough, if you feel the original constrained problem is too simple, why not generalise it...)
Thank you for your help in advance
Peter Sisak
