Merge lp:~msoegtrop/inkscape/embroidery into lp:~inkscape.dev/inkscape/trunk

Proposed by Michael Soegtrop on 2017-06-05
Status: Merged
Merged at revision: 15738
Proposed branch: lp:~msoegtrop/inkscape/embroidery
Merge into: lp:~inkscape.dev/inkscape/trunk
Diff against target: 2544 lines (+2417/-3)
11 files modified
astylerc (+4/-3)
po/POTFILES.in (+2/-0)
src/live_effects/CMakeLists.txt (+6/-0)
src/live_effects/effect-enum.h (+2/-0)
src/live_effects/effect.cpp (+10/-0)
src/live_effects/lpe-bool.cpp (+400/-0)
src/live_effects/lpe-bool.h (+63/-0)
src/live_effects/lpe-embrodery-stitch-ordering.cpp (+1139/-0)
src/live_effects/lpe-embrodery-stitch-ordering.h (+313/-0)
src/live_effects/lpe-embrodery-stitch.cpp (+400/-0)
src/live_effects/lpe-embrodery-stitch.h (+78/-0)
To merge this branch: bzr merge lp:~msoegtrop/inkscape/embroidery
Reviewer Review Type Date Requested Status
Jabiertxof code Approve on 2017-06-05
Jabiertxo 2017-06-05 Pending
Review via email: mp+325084@code.launchpad.net

Description of the change

Same as lpe-bool + an additional embroidery stitching LPE (the original reason why I wrote the bool LPE). The embroidery stuff doesn't change any existing file (except the few lines to link in the LPE) so it should be safe.

To post a comment you must log in.
Jabiertxof (jabiertxof) wrote :

Approve with some fixes in inline comment diff.
Very good work. Maybe too much complex to my maind :) Is great have you here!

review: Approve (code)
lp:~msoegtrop/inkscape/embroidery updated on 2017-06-05
14866. By Michael Soegtrop on 2017-06-05

fixed enum order + added cpp files to POFILES.in

Michael Soegtrop (msoegtrop) wrote :
Download full text (49.3 KiB)

Dear Jabier,

thanks :-) It is indeed quite complicated. The embroidery LPE typically
takes complicated structures of adjacent paths, typically created with
path interpolation and bool LPEs, and then cuts the path into stitches.
The complicated part is to order the resulting groups such that the
number / length of jump stitches is optimized. Since even simple designs
have 1000s of stitches, a straight forward TSP takes ages (TSP is
NP-complete). So I do complicated stuff like first grouping nearby
stitches together and then only connecting these groups with TSP style
algorithms. But this of cause makes the algorithm complicated. As is it
can handle many 1000 stitches in < 1 second. But it can still be improved.

I think the combination of path interpolation, bool LPE and stitching is
very powerful. It allows much more control than expensive commercial
embroidery SW (I have the one from Bernina, a few 1000 EUR and can't do
what I want).

I can send you some examples next weekend. I guess the embroidery LPE is
no so obvious.

Regarding your comment: I put in in the namespace for safety, because I
have a lot of global helper / utility function and wanted to avoid
collisions. But it is not required, it is just a habit in such
circumstances.

Thanks for your help! Please let me know if there is anything to be done
from my side. I will check my mail again in 15 minutes.

Best regards,

Michael

On 05.06.2017 20:26, Jabiertxof wrote:
> Review: Approve code
>
> Approve with some fixes in inline comment diff.
> Very good work. Maybe too much complex to my maind :) Is great have you here!
>
> Diff comments:
>
>> === modified file 'src/live_effects/effect-enum.h'
>> --- src/live_effects/effect-enum.h 2017-05-07 00:23:42 +0000
>> +++ src/live_effects/effect-enum.h 2017-06-05 14:13:17 +0000
>> @@ -42,6 +42,8 @@
>> TAPER_STROKE,
>> MIRROR_SYMMETRY,
>> COPY_ROTATE,
>> + EMBRODERY_STITCH,
> Set at same order than in effect.cpp, for example after the FILLET_CHAMFER, we use this enum values to access toExtended data defined in Effect.cpp and we need to be the same order
>
>> + BOOL_OP,
>> ATTACH_PATH,
>> FILL_BETWEEN_STROKES,
>> FILL_BETWEEN_MANY,
>>
>> === modified file 'src/live_effects/effect.cpp'
>> --- src/live_effects/effect.cpp 2017-05-29 00:09:29 +0000
>> +++ src/live_effects/effect.cpp 2017-06-05 14:13:17 +0000
>> @@ -116,6 +118,8 @@
>> {MIRROR_SYMMETRY, N_("Mirror symmetry"), "mirror_symmetry"},
>> {COPY_ROTATE, N_("Rotate copies"), "copy_rotate"},
>> /* Ponyscape -> Inkscape 0.92*/
>> + {EMBRODERY_STITCH, N_("Embrodery stitch"), "embrodery_stitch"},
> Put in 0.93 section
>
>> + {BOOL_OP, N_("Boolean operation"), "bool_op"},
>> {ATTACH_PATH, N_("Attach path"), "attach_path"},
>> {FILL_BETWEEN_STROKES, N_("Fill between strokes"), "fill_between_strokes"},
>> {FILL_BETWEEN_MANY, N_("Fill between many"), "fill_between_many"},
>>
>> === added file 'src/live_effects/lpe-embrodery-stitch-ordering.cpp'
>> --- src/live_effects/lpe-embrod...

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'astylerc'
2--- astylerc 2013-09-01 23:39:00 +0000
3+++ astylerc 2017-06-05 19:01:49 +0000
4@@ -1,8 +1,9 @@
5 # Inkscape coding style options for the Artistic Style formatter
6 # See http://astyle.sourceforge.net/
7+# See https://inkscape.org/de/develop/coding-style/
8
9 # Opening braces broken from functions only
10---brackets=stroustrup
11+--style=stroustrup
12
13 # Four-space indent; convert stray tabs
14 --indent=spaces=4
15@@ -15,7 +16,7 @@
16
17 # Attach pointers and references to variable names
18 --align-pointer=name
19-# --align-reference=name
20+--align-reference=name
21
22 # Add brackets to single-statement blocks
23 --add-brackets
24@@ -23,4 +24,4 @@
25 # Misc. options
26 --indent-preprocessor
27 --indent-col1-comments
28---suffix=none
29+
30
31=== modified file 'po/POTFILES.in'
32--- po/POTFILES.in 2017-05-08 01:43:41 +0000
33+++ po/POTFILES.in 2017-06-05 19:01:49 +0000
34@@ -119,6 +119,7 @@
35 src/live_effects/effect.cpp
36 src/live_effects/lpe-attach-path.cpp
37 src/live_effects/lpe-bendpath.cpp
38+src/live_effects/lpe-bool.cpp
39 src/live_effects/lpe-bounding-box.cpp
40 src/live_effects/lpe-bspline.cpp
41 src/live_effects/lpe-clone-original.cpp
42@@ -126,6 +127,7 @@
43 src/live_effects/lpe-copy_rotate.cpp
44 src/live_effects/lpe-curvestitch.cpp
45 src/live_effects/lpe-ellipse_5pts.cpp
46+src/live_effects/lpe-embrodery-stitch.cpp
47 src/live_effects/lpe-envelope.cpp
48 src/live_effects/lpe-extrude.cpp
49 src/live_effects/lpe-fill-between-many.cpp
50
51=== modified file 'src/live_effects/CMakeLists.txt'
52--- src/live_effects/CMakeLists.txt 2017-05-06 21:00:45 +0000
53+++ src/live_effects/CMakeLists.txt 2017-06-05 19:01:49 +0000
54@@ -53,6 +53,9 @@
55 lpegroupbbox.cpp
56 lpeobject-reference.cpp
57 lpe-vonkoch.cpp
58+ lpe-embrodery-stitch.cpp
59+ lpe-embrodery-stitch-ordering.cpp
60+ lpe-bool.cpp
61 lpeobject.cpp
62 spiro-converters.cpp
63 spiro.cpp
64@@ -136,6 +139,9 @@
65 lpe-test-doEffect-stack.h
66 lpe-text_label.h
67 lpe-vonkoch.h
68+ lpe-embrodery-stitch.h
69+ lpe-embrodery-stitch-ordering.h
70+ lpe-bool.h
71 lpegroupbbox.h
72 lpeobject-reference.h
73 lpeobject.h
74
75=== modified file 'src/live_effects/effect-enum.h'
76--- src/live_effects/effect-enum.h 2017-05-07 00:23:42 +0000
77+++ src/live_effects/effect-enum.h 2017-06-05 19:01:49 +0000
78@@ -49,6 +49,8 @@
79 BOUNDING_BOX,
80 MEASURE_LINE,
81 FILLET_CHAMFER,
82+ BOOL_OP,
83+ EMBRODERY_STITCH,
84 DOEFFECTSTACK_TEST,
85 ANGLE_BISECTOR,
86 CIRCLE_WITH_RADIUS,
87
88=== modified file 'src/live_effects/effect.cpp'
89--- src/live_effects/effect.cpp 2017-05-29 00:09:29 +0000
90+++ src/live_effects/effect.cpp 2017-06-05 19:01:49 +0000
91@@ -62,6 +62,8 @@
92 #include "live_effects/lpe-test-doEffect-stack.h"
93 #include "live_effects/lpe-text_label.h"
94 #include "live_effects/lpe-vonkoch.h"
95+#include "live_effects/lpe-embrodery-stitch.h"
96+#include "live_effects/lpe-bool.h"
97
98 #include "xml/node-event-vector.h"
99 #include "message-stack.h"
100@@ -124,6 +126,8 @@
101 /* 9.93 */
102 {MEASURE_LINE, N_("Measure Line"), "measure_line"},
103 {FILLET_CHAMFER, N_("Fillet/Chamfer"), "fillet_chamfer"},
104+ {BOOL_OP, N_("Boolean operation"), "bool_op"},
105+ {EMBRODERY_STITCH, N_("Embrodery stitch"), "embrodery_stitch"},
106 #ifdef LPE_ENABLE_TEST_EFFECTS
107 {DOEFFECTSTACK_TEST, N_("doEffect stack test"), "doeffectstacktest"},
108 {ANGLE_BISECTOR, N_("Angle bisector"), "angle_bisector"},
109@@ -164,6 +168,12 @@
110 {
111 Effect* neweffect = NULL;
112 switch (lpenr) {
113+ case EMBRODERY_STITCH:
114+ neweffect = static_cast<Effect*> ( new LPEEmbroderyStitch(lpeobj) );
115+ break;
116+ case BOOL_OP:
117+ neweffect = static_cast<Effect*> ( new LPEBool(lpeobj) );
118+ break;
119 case PATTERN_ALONG_PATH:
120 neweffect = static_cast<Effect*> ( new LPEPatternAlongPath(lpeobj) );
121 break;
122
123=== added file 'src/live_effects/lpe-bool.cpp'
124--- src/live_effects/lpe-bool.cpp 1970-01-01 00:00:00 +0000
125+++ src/live_effects/lpe-bool.cpp 2017-06-05 19:01:49 +0000
126@@ -0,0 +1,400 @@
127+/*
128+ * Boolean operation live path effect
129+ *
130+ * Copyright (C) 2016-2017 Michael Soegtrop
131+ *
132+ * Released under GNU GPL, read the file 'COPYING' for more information
133+ */
134+
135+#include <glibmm/i18n.h>
136+#include <math.h>
137+#include <string.h>
138+#include <algorithm>
139+
140+#include "live_effects/lpe-bool.h"
141+
142+#include "display/curve.h"
143+#include "sp-item.h"
144+#include "2geom/path.h"
145+#include "sp-shape.h"
146+#include "sp-text.h"
147+#include "2geom/bezier-curve.h"
148+#include "2geom/path-sink.h"
149+#include "2geom/affine.h"
150+#include "splivarot.h"
151+#include "helper/geom.h"
152+#include "livarot/Path.h"
153+#include "livarot/Shape.h"
154+#include "livarot/path-description.h"
155+#include "2geom/svg-path-parser.h"
156+
157+namespace Inkscape {
158+namespace LivePathEffect {
159+
160+// Define an extended boolean operation type
161+
162+static const Util::EnumData<LPEBool::bool_op_ex> BoolOpData[LPEBool::bool_op_ex_count] = {
163+ { LPEBool::bool_op_ex_union, N_("union"), "union" },
164+ { LPEBool::bool_op_ex_inters, N_("intersection"), "inters" },
165+ { LPEBool::bool_op_ex_diff, N_("difference"), "diff" },
166+ { LPEBool::bool_op_ex_symdiff, N_("symmetric difference"), "symdiff" },
167+ { LPEBool::bool_op_ex_cut, N_("division"), "cut" },
168+ // Note on naming of operations:
169+ // bool_op_cut is called "Division" in the manu, see sp_selected_path_cut
170+ // bool_op_slice is called "Cut path" in the menu, see sp_selected_path_slice
171+ { LPEBool::bool_op_ex_slice, N_("cut"), "slice" },
172+ { LPEBool::bool_op_ex_slice_inside, N_("cut inside"), "slice-inside" },
173+ { LPEBool::bool_op_ex_slice_outside, N_("cut outside"), "slice-outside" },
174+};
175+
176+static const Util::EnumDataConverter<LPEBool::bool_op_ex> BoolOpConverter(BoolOpData, sizeof(BoolOpData) / sizeof(*BoolOpData));
177+
178+static const Util::EnumData<fill_typ> FillTypeData[] = {
179+ { fill_oddEven, N_("odd-even"), "oddeven" },
180+ { fill_nonZero, N_("non-zero"), "nonzero" },
181+ { fill_positive, N_("positive"), "positive" },
182+ { fill_justDont, N_("from curve"), "from-curve" }
183+};
184+
185+static const Util::EnumDataConverter<fill_typ> FillTypeConverter(FillTypeData, sizeof(FillTypeData) / sizeof(*FillTypeData));
186+
187+static const Util::EnumData<fill_typ> FillTypeDataThis[] = {
188+ { fill_oddEven, N_("odd-even"), "oddeven" },
189+ { fill_nonZero, N_("non-zero"), "nonzero" },
190+ { fill_positive, N_("positive"), "positive" }
191+};
192+
193+static const Util::EnumDataConverter<fill_typ> FillTypeConverterThis(FillTypeDataThis, sizeof(FillTypeDataThis) / sizeof(*FillTypeDataThis));
194+
195+LPEBool::LPEBool(LivePathEffectObject *lpeobject) :
196+ Effect(lpeobject),
197+ operand_path(_("Operand path:"), _("Operand for the boolean operation"), "operand-path", &wr, this),
198+ bool_operation(_("Operation:"), _("Boolean Operation"), "operation", BoolOpConverter, &wr, this, bool_op_ex_union),
199+ swap_operands(_("Swap operands:"), _("Swap operands (useful e.g. for difference)"), "swap-operands", &wr, this),
200+ rmv_inner(_("Remove inner:"), _("For cut operations: remove inner (non-contour) lines of cutting path to avoid invisible extra points"), "rmv-inner", &wr, this),
201+ fill_type_this(_("Fill type this:"), _("Fill type (winding mode) for this path"), "filltype-this", FillTypeConverterThis, &wr, this, fill_oddEven),
202+ fill_type_operand(_("Fill type operand:"), _("Fill type (winding mode) for operand path"), "filltype-operand", FillTypeConverter, &wr, this, fill_justDont)
203+{
204+ registerParameter(&operand_path);
205+ registerParameter(&bool_operation);
206+ registerParameter(&swap_operands);
207+ registerParameter(&rmv_inner);
208+ registerParameter(&fill_type_this);
209+ registerParameter(&fill_type_operand);
210+
211+ show_orig_path = true;
212+}
213+
214+LPEBool::~LPEBool()
215+{
216+
217+}
218+
219+void LPEBool::resetDefaults(SPItem const * /*item*/)
220+{
221+}
222+
223+bool cmp_cut_position(const Path::cut_position &a, const Path::cut_position &b)
224+{
225+ return a.piece == b.piece ? a.t < b.t : a.piece < b.piece;
226+}
227+
228+Geom::PathVector
229+sp_pathvector_boolop_slice_intersect(Geom::PathVector const &pathva, Geom::PathVector const &pathvb, bool inside, fill_typ fra, fill_typ frb)
230+{
231+ // This is similar to sp_pathvector_boolop/bool_op_slice, but keeps only edges inside the cutter area.
232+ // The code is also based on sp_pathvector_boolop_slice.
233+ //
234+ // We have two paths on input
235+ // - a closed area which is used to cut out pieces from a contour (called area below)
236+ // - a contour which is cut into pieces by the border of thr area (called contour below)
237+ //
238+ // The code below works in the following steps
239+ // (a) Convert the area to a shape, so that we can ask the winding number for any point
240+ // (b) Add both, the contour and the area to a single shape and intersect them
241+ // (c) Find the intersection points between area border and contour (vector toCut)
242+ // (d) Split the original contour at the intersection points
243+ // (e) check for each contour edge in combined shape if its center is inside the area - if not discard it
244+ // (f) create a vector of all inside edges
245+ // (g) convert the piece numbers to the piece numbers after applying the cuts
246+ // (h) fill a bool vector with information which pieces are in
247+ // (i) filter the descr_cmd of the result path with this bool vector
248+ //
249+ // The main inefficieny here is step (e) because I use a winding function of the area-shape which goes
250+ // through teh complete edge list for each point I ask for, so effort is n-edges-contour * n-edges-area.
251+ // It is tricky to improve this without building into the livarot code.
252+ // One way might be to decide at the intersection points which edges touching the intersection points are
253+ // in by making a loop through all edges on the intersection vertex. Since this is a directed non intersecting
254+ // graph, this should provide sufficient information.
255+ // But since I anyway will change this to the new mechanism some time speed is fairly ok, I didn't look into this.
256+
257+
258+ // extract the livarot Paths from the source objects
259+ // also get the winding rule specified in the style
260+ // Livarot's outline of arcs is broken. So convert the path to linear and cubics only, for which the outline is created correctly.
261+ Path *contour_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathva));
262+ Path *area_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathvb));
263+
264+ // Shapes from above paths
265+ Shape *area_shape = new Shape;
266+ Shape *combined_shape = new Shape;
267+ Shape *combined_inters = new Shape;
268+
269+ // Add the area (process to intersection free shape)
270+ area_path->ConvertWithBackData(1.0);
271+ area_path->Fill(combined_shape, 1);
272+
273+ // Convert this to a shape with full winding information
274+ area_shape->ConvertToShape(combined_shape, frb);
275+
276+ // Add the contour to the combined path (just add, no winding processing)
277+ contour_path->ConvertWithBackData(1.0);
278+ contour_path->Fill(combined_shape, 0, true, false, false);
279+
280+ // Intersect the area and the contour - no fill processing
281+ combined_inters->ConvertToShape(combined_shape, fill_justDont);
282+
283+ // Result path
284+ Path *result_path = new Path;
285+ result_path->SetBackData(false);
286+
287+ // Cutting positions for contour
288+ std::vector<Path::cut_position> toCut;
289+
290+ if (combined_inters->hasBackData()) {
291+ // should always be the case, but ya never know
292+ {
293+ for (int i = 0; i < combined_inters->numberOfPoints(); i++) {
294+ if (combined_inters->getPoint(i).totalDegree() > 2) {
295+ // possibly an intersection
296+ // we need to check that at least one edge from the source path is incident to it
297+ // before we declare it's an intersection
298+ int cb = combined_inters->getPoint(i).incidentEdge[FIRST];
299+ int nbOrig = 0;
300+ int nbOther = 0;
301+ int piece = -1;
302+ float t = 0.0;
303+ while (cb >= 0 && cb < combined_inters->numberOfEdges()) {
304+ if (combined_inters->ebData[cb].pathID == 0) {
305+ // the source has an edge incident to the point, get its position on the path
306+ piece = combined_inters->ebData[cb].pieceID;
307+ if (combined_inters->getEdge(cb).st == i) {
308+ t = combined_inters->ebData[cb].tSt;
309+ } else {
310+ t = combined_inters->ebData[cb].tEn;
311+ }
312+ nbOrig++;
313+ }
314+ if (combined_inters->ebData[cb].pathID == 1) {
315+ nbOther++; // the cut is incident to this point
316+ }
317+ cb = combined_inters->NextAt(i, cb);
318+ }
319+ if (nbOrig > 0 && nbOther > 0) {
320+ // point incident to both path and cut: an intersection
321+ // note that you only keep one position on the source; you could have degenerate
322+ // cases where the source crosses itself at this point, and you wouyld miss an intersection
323+ Path::cut_position cutpos;
324+ cutpos.piece = piece;
325+ cutpos.t = t;
326+ toCut.push_back(cutpos);
327+ }
328+ }
329+ }
330+ }
331+ {
332+ // remove the edges from the intersection polygon
333+ int i = combined_inters->numberOfEdges() - 1;
334+ for (; i >= 0; i--) {
335+ if (combined_inters->ebData[i].pathID == 1) {
336+ combined_inters->SubEdge(i);
337+ } else {
338+ const Shape::dg_arete &edge = combined_inters->getEdge(i);
339+ const Shape::dg_point &start = combined_inters->getPoint(edge.st);
340+ const Shape::dg_point &end = combined_inters->getPoint(edge.en);
341+ Geom::Point mid = 0.5 * (start.x + end.x);
342+ int wind = area_shape->PtWinding(mid);
343+ if (wind == 0) {
344+ combined_inters->SubEdge(i);
345+ }
346+ }
347+ }
348+ }
349+ }
350+
351+ // create a vector of pieces, which are in the intersection
352+ std::vector<Path::cut_position> inside_pieces(combined_inters->numberOfEdges());
353+ for (int i = 0; i < combined_inters->numberOfEdges(); i++) {
354+ inside_pieces[i].piece = combined_inters->ebData[i].pieceID;
355+ // Use the t middle point, this is safe to compare with values from toCut in the presence of roundoff errors
356+ inside_pieces[i].t = 0.5 * (combined_inters->ebData[i].tSt + combined_inters->ebData[i].tEn);
357+ }
358+ std::sort(inside_pieces.begin(), inside_pieces.end(), cmp_cut_position);
359+
360+ // sort cut positions
361+ std::sort(toCut.begin(), toCut.end(), cmp_cut_position);
362+
363+ // Compute piece ids after ConvertPositionsToMoveTo
364+ {
365+ int idIncr = 0;
366+ std::vector<Path::cut_position>::iterator itPiece = inside_pieces.begin();
367+ std::vector<Path::cut_position>::iterator itCut = toCut.begin();
368+ while (itPiece != inside_pieces.end()) {
369+ while (itCut != toCut.end() && cmp_cut_position(*itCut, *itPiece)) {
370+ ++itCut;
371+ idIncr += 2;
372+ }
373+ itPiece->piece += idIncr;
374+ ++itPiece;
375+ }
376+ }
377+
378+ // Copy the original path to result and cut at the intersection points
379+ result_path->Copy(contour_path);
380+ result_path->ConvertPositionsToMoveTo(toCut.size(), toCut.data()); // cut where you found intersections
381+
382+ // Create an array of bools which states which pieces are in
383+ std::vector<bool> inside_flags(result_path->descr_cmd.size(), false);
384+ for (std::vector<Path::cut_position>::iterator itPiece = inside_pieces.begin(); itPiece != inside_pieces.end(); ++itPiece) {
385+ inside_flags[ itPiece->piece ] = true;
386+ // also enable the element -1 to get the MoveTo
387+ if (itPiece->piece >= 1) {
388+ inside_flags[ itPiece->piece - 1 ] = true;
389+ }
390+ }
391+
392+#if 0 // CONCEPT TESTING
393+ //Check if the inside/outside verdict is consistent - just for testing the concept
394+ // Retrieve the pieces
395+ int nParts = 0;
396+ Path **parts = result_path->SubPaths(nParts, false);
397+
398+ // Each piece should be either fully in or fully out
399+ int iPiece = 0;
400+ for (int iPart = 0; iPart < nParts; iPart++) {
401+ bool andsum = true;
402+ bool orsum = false;
403+ for (int iCmd = 0; iCmd < parts[iPart]->descr_cmd.size(); iCmd++, iPiece++) {
404+ andsum = andsum && inside_flags[ iPiece ];
405+ orsum = andsum || inside_flags[ iPiece ];
406+ }
407+
408+ if (andsum != orsum) {
409+ g_warning("Inconsistent inside/outside verdict for part=%d", iPart);
410+ }
411+ }
412+ g_free(parts);
413+#endif
414+
415+ // iterate over the commands of a path and keep those which are inside
416+ int iDest = 0;
417+ for (int iSrc = 0; iSrc < result_path->descr_cmd.size(); iSrc++) {
418+ if (inside_flags[iSrc] == inside) {
419+ result_path->descr_cmd[iDest++] = result_path->descr_cmd[iSrc];
420+ } else {
421+ delete result_path->descr_cmd[iSrc];
422+ }
423+ }
424+ result_path->descr_cmd.resize(iDest);
425+
426+ delete combined_inters;
427+ delete combined_shape;
428+ delete area_shape;
429+ delete contour_path;
430+ delete area_path;
431+
432+ gchar *result_str = result_path->svg_dump_path();
433+ Geom::PathVector outres = Geom::parse_svg_path(result_str);
434+ // CONCEPT TESTING g_warning( "%s", result_str );
435+ g_free(result_str);
436+ delete result_path;
437+
438+ return outres;
439+}
440+
441+// remove inner contours
442+Geom::PathVector
443+sp_pathvector_boolop_remove_inner(Geom::PathVector const &pathva, fill_typ fra)
444+{
445+ Geom::PathVector patht;
446+ Path *patha = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathva));
447+
448+ Shape *shape = new Shape;
449+ Shape *shapeshape = new Shape;
450+ Path *resultp = new Path;
451+ resultp->SetBackData(false);
452+
453+ patha->ConvertWithBackData(0.1);
454+ patha->Fill(shape, 0);
455+ shapeshape->ConvertToShape(shape, fra);
456+ shapeshape->ConvertToForme(resultp, 1, &patha);
457+
458+ delete shape;
459+ delete shapeshape;
460+ delete patha;
461+
462+ gchar *result_str = resultp->svg_dump_path();
463+ Geom::PathVector resultpv = Geom::parse_svg_path(result_str);
464+ g_free(result_str);
465+
466+ delete resultp;
467+ return resultpv;
468+}
469+
470+static fill_typ GetFillTyp(SPItem *item)
471+{
472+ SPCSSAttr *css = sp_repr_css_attr(item->getRepr(), "style");
473+ gchar const *val = sp_repr_css_property(css, "fill-rule", NULL);
474+ if (val && strcmp(val, "nonzero") == 0) {
475+ return fill_nonZero;
476+ } else if (val && strcmp(val, "evenodd") == 0) {
477+ return fill_oddEven;
478+ } else {
479+ return fill_nonZero;
480+ }
481+}
482+
483+void LPEBool::doEffect(SPCurve *curve)
484+{
485+ Geom::PathVector path_in = curve->get_pathvector();
486+
487+ if (operand_path.linksToPath() && operand_path.getObject()) {
488+ bool_op_ex op = bool_operation.get_value();
489+ bool swap = swap_operands.get_value();
490+
491+ Geom::PathVector path_a = swap ? operand_path.get_pathvector() : path_in;
492+ Geom::PathVector path_b = swap ? path_in : operand_path.get_pathvector();
493+
494+ // TODO: I would like to use the original objects fill rule if the UI selected rule is fill_justDont.
495+ // But it doesn't seem possible to access them from here, because SPCurve is not derived from SPItem.
496+ // The nearest function in the call stack, where this is available is SPLPEItem::performPathEffect (this is then an SPItem)
497+ // For the parameter curve, this is possible.
498+ // fill_typ fill_this = fill_type_this. get_value()!=fill_justDont ? fill_type_this.get_value() : GetFillTyp( curve ) ;
499+ fill_typ fill_this = fill_type_this.get_value();
500+ fill_typ fill_operand = fill_type_operand.get_value() != fill_justDont ? fill_type_operand.get_value() : GetFillTyp(operand_path.getObject());
501+
502+ fill_typ fill_a = swap ? fill_operand : fill_this;
503+ fill_typ fill_b = swap ? fill_this : fill_operand;
504+
505+ if (rmv_inner.get_value()) {
506+ path_b = sp_pathvector_boolop_remove_inner(path_b, fill_b);
507+ }
508+
509+ Geom::PathVector path_out;
510+
511+ if (op == bool_op_ex_slice) {
512+ // For slicing, the bool op is added to the line group which is sliced, not the cut path. This swapped order is correct.
513+ path_out = sp_pathvector_boolop(path_b, path_a, to_bool_op(op), fill_b, fill_a);
514+ } else if (op == bool_op_ex_slice_inside) {
515+ path_out = sp_pathvector_boolop_slice_intersect(path_a, path_b, true, fill_a, fill_b);
516+ } else if (op == bool_op_ex_slice_outside) {
517+ path_out = sp_pathvector_boolop_slice_intersect(path_a, path_b, false, fill_a, fill_b);
518+ } else {
519+ path_out = sp_pathvector_boolop(path_a, path_b, to_bool_op(op), fill_a, fill_b);
520+ }
521+ curve->set_pathvector(path_out);
522+ }
523+}
524+
525+} // namespace LivePathEffect
526+} /* namespace Inkscape */
527
528=== added file 'src/live_effects/lpe-bool.h'
529--- src/live_effects/lpe-bool.h 1970-01-01 00:00:00 +0000
530+++ src/live_effects/lpe-bool.h 2017-06-05 19:01:49 +0000
531@@ -0,0 +1,63 @@
532+/*
533+ * Boolean operation live path effect
534+ *
535+ * Copyright (C) 2016 Michael Soegtrop
536+ *
537+ * Released under GNU GPL, read the file 'COPYING' for more information
538+ */
539+
540+#ifndef INKSCAPE_LPE_BOOL_H
541+#define INKSCAPE_LPE_BOOL_H
542+
543+#include "live_effects/effect.h"
544+#include "live_effects/parameter/parameter.h"
545+#include "live_effects/parameter/originalpath.h"
546+#include "live_effects/parameter/bool.h"
547+#include "live_effects/parameter/enum.h"
548+#include "livarot/LivarotDefs.h"
549+
550+namespace Inkscape {
551+namespace LivePathEffect {
552+
553+class LPEBool : public Effect {
554+public:
555+ LPEBool(LivePathEffectObject *lpeobject);
556+ virtual ~LPEBool();
557+
558+ void doEffect(SPCurve *curve);
559+ virtual void resetDefaults(SPItem const *item);
560+
561+ enum bool_op_ex {
562+ bool_op_ex_union = bool_op_union,
563+ bool_op_ex_inters = bool_op_inters,
564+ bool_op_ex_diff = bool_op_diff,
565+ bool_op_ex_symdiff = bool_op_symdiff,
566+ bool_op_ex_cut = bool_op_cut,
567+ bool_op_ex_slice = bool_op_slice,
568+ bool_op_ex_slice_inside, // like bool_op_slice, but leaves only the contour pieces inside of the cut path
569+ bool_op_ex_slice_outside, // like bool_op_slice, but leaves only the contour pieces outside of the cut path
570+ bool_op_ex_count
571+ };
572+
573+ inline friend bool_op to_bool_op(bool_op_ex val)
574+ {
575+ assert(val <= bool_op_ex_slice);
576+ (bool_op) val;
577+ }
578+
579+private:
580+ LPEBool(const LPEBool &);
581+ LPEBool &operator=(const LPEBool &);
582+
583+ OriginalPathParam operand_path;
584+ EnumParam<bool_op_ex> bool_operation;
585+ EnumParam<fill_typ> fill_type_this;
586+ EnumParam<fill_typ> fill_type_operand;
587+ BoolParam swap_operands;
588+ BoolParam rmv_inner;
589+};
590+
591+}; //namespace LivePathEffect
592+}; //namespace Inkscape
593+
594+#endif
595
596=== added file 'src/live_effects/lpe-embrodery-stitch-ordering.cpp'
597--- src/live_effects/lpe-embrodery-stitch-ordering.cpp 1970-01-01 00:00:00 +0000
598+++ src/live_effects/lpe-embrodery-stitch-ordering.cpp 2017-06-05 19:01:49 +0000
599@@ -0,0 +1,1139 @@
600+/*
601+ * Sub-path Ordering functions for embroidery stitch LPE (Implementation)
602+ *
603+ * Copyright (C) 2016 Michael Soegtrop
604+ *
605+ * Released under GNU GPL, read the file 'COPYING' for more information
606+ */
607+
608+#include "live_effects/lpe-embrodery-stitch-ordering.h"
609+
610+#include <numeric>
611+
612+namespace Inkscape {
613+namespace LivePathEffect {
614+namespace LPEEmbroderyStitchOrdering {
615+
616+using namespace Geom;
617+
618+// ==================== Debug Trace Macros ====================
619+
620+// ATTENTION: both level and area macros must be enabled for tracing
621+
622+// These macros are for enabling certain levels of tracing
623+#define DebugTrace1(list) // g_warning list
624+#define DebugTrace2(list) // g_warning list
625+
626+// These macros are for enabling certain areas of tracing
627+#define DebugTraceGrouping(list) // list
628+#define DebugTraceTSP(list) // list
629+
630+// Combinations of above
631+#define DebugTrace1TSP(list) DebugTraceTSP( DebugTrace1(list) )
632+#define DebugTrace2TSP(list) DebugTraceTSP( DebugTrace2(list) )
633+
634+// ==================== Template Utilities ====================
635+
636+// Delete all objects pointed to by a vector and clear the vector
637+
638+template< typename T > void delete_and_clear(std::vector<T> &vector)
639+{
640+ for (typename std::vector<T>::iterator it = vector.begin(); it != vector.end(); ++it) {
641+ delete *it;
642+ }
643+ vector.clear();
644+}
645+
646+// Assert that there are no duplicates in a vector
647+
648+template< typename T > void assert_unique(std::vector<T> &vector)
649+{
650+ typename std::vector<T> copy = vector;
651+ std::sort(copy.begin(), copy.end());
652+ assert(std::unique(copy.begin(), copy.end()) == copy.end());
653+}
654+
655+// remove element(s) by value
656+
657+template< typename T > void remove_by_value(std::vector<T> *vector, const T &value)
658+{
659+ vector->erase(std::remove(vector->begin(), vector->end(), value), vector->end());
660+}
661+
662+// fill a vector with increasing elements (similar to C++11 iota)
663+// iota is included in some C++ libraries, not in other (it is always included for C++11)
664+// To avoid issues, use our own name (not iota)
665+
666+template<class OutputIterator, class Counter>
667+void fill_increasing(OutputIterator begin, OutputIterator end, Counter counter)
668+{
669+ while (begin != end) {
670+ *begin++ = counter++;
671+ }
672+}
673+
674+// check if an iteratable sequence contains an element
675+
676+template<class InputIterator, class Element>
677+bool contains(InputIterator begin, InputIterator end, const Element &elem)
678+{
679+ while (begin != end) {
680+ if (*begin == elem) {
681+ return true;
682+ }
683+ ++begin;
684+ }
685+ return false;
686+}
687+
688+// Check if a vector contains an element
689+
690+template<class Element>
691+bool contains(std::vector<Element> const &vector, const Element &elem)
692+{
693+ return contains(vector.begin(), vector.end(), elem);
694+}
695+
696+// ==================== Multi-dimensional iterator functions ====================
697+
698+// Below are 3 simple template functions to do triangle/pyramid iteration (without diagonal).
699+// Here is a sample of iterating over 5 elements in 3 dimensions:
700+//
701+// 0 1 2
702+// 0 1 3
703+// 0 1 4
704+// 0 2 3
705+// 0 2 4
706+// 1 2 4
707+// 1 3 4
708+// 2 3 4
709+// end end end
710+//
711+// If the number of elements is less then the number of dimensions, the number of dimensions is reduced automatically.
712+//
713+// I thought about creating an iterator class for this, but it doesn't match that well, so I used functions on iterator vectors.
714+
715+// Initialize a vector of iterators
716+
717+template<class Iterator>
718+void triangleit_begin(std::vector<Iterator> &iterators, Iterator const &begin, Iterator const &end, size_t n)
719+{
720+ iterators.clear();
721+ // limit number of dimensions to number of elements
722+ size_t n1 = end - begin;
723+ n = std::min(n, n1);
724+ if (n) {
725+ iterators.push_back(begin);
726+ for (int i = 1; i < n; i++) {
727+ iterators.push_back(iterators.back() + 1);
728+ }
729+ }
730+}
731+
732+// Increment a vector of iterators
733+
734+template<class Iterator>
735+void triangleit_incr(std::vector<Iterator> &iterators, Iterator const &end)
736+{
737+ size_t n = iterators.size();
738+
739+ for (int i = 0; i < n; i++) {
740+ iterators[n - 1 - i]++;
741+ // Each dimension ends at end-i, so that there are elements left for the i higher dimensions
742+ if (iterators[n - 1 - i] != end - i) {
743+ // Assign increasing numbers to the higher dimension
744+ for (int j = n - i; j < n; j++) {
745+ iterators[j] = iterators[j - 1] + 1;
746+ }
747+ return;
748+ }
749+ }
750+}
751+
752+// Check if a vector of iterators is at the end
753+
754+template<class Iterator>
755+bool triangleit_test(std::vector<Iterator> &iterators, Iterator const &end)
756+{
757+ if (iterators.empty()) {
758+ return false;
759+ } else {
760+ return iterators.back() != end;
761+ }
762+}
763+
764+// ==================== Trivial Ordering Functions ====================
765+
766+// Sub-path reordering: do nothing - keep original order
767+
768+void OrderingOriginal(std::vector<OrderingInfo> &infos)
769+{
770+}
771+
772+// Sub-path reordering: reverse every other sub path
773+
774+void OrderingZigZag(std::vector<OrderingInfo> &infos, bool revfirst)
775+{
776+ for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
777+ it->reverse = (it->index & 1) == (revfirst ? 0 : 1);
778+ }
779+}
780+
781+// Sub-path reordering: continue with the neartest start or end point of yet unused sub paths
782+
783+void OrderingClosest(std::vector<OrderingInfo> &infos, bool revfirst)
784+{
785+ std::vector<OrderingInfo> result;
786+ result.reserve(infos.size());
787+
788+ result.push_back(infos[0]);
789+ result.back().reverse = revfirst;
790+ Point p = result.back().GetEndRev();
791+
792+ infos[0].used = true;
793+
794+
795+ for (unsigned int iRnd = 1; iRnd < infos.size(); iRnd++) {
796+ // find closest point to p
797+ unsigned iBest = 0;
798+ bool revBest = false;
799+ Coord distBest = infinity();
800+
801+ for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
802+ it->index = it - infos.begin();
803+ it->reverse = (it->index & 1) != 0;
804+
805+ if (!it->used) {
806+ Coord dist = distance(p, it->GetBegOrig());
807+ if (dist < distBest) {
808+ distBest = dist;
809+ iBest = it - infos.begin();
810+ revBest = false;
811+ }
812+
813+ dist = distance(p, it->GetEndOrig());
814+ if (dist < distBest) {
815+ distBest = dist;
816+ iBest = it - infos.begin();
817+ revBest = true;
818+ }
819+ }
820+ }
821+
822+ result.push_back(infos[iBest]);
823+ result.back().reverse = revBest;
824+ p = result.back().GetEndRev();
825+ infos[iBest].used = true;
826+ }
827+
828+ infos = result;
829+}
830+
831+// ==================== Traveling Salesman k-opt Ordering Function and Utilities ====================
832+
833+// A Few notes on this:
834+// - This is a relatively simple Lin-type k-opt algorithm, but the grouping optimizations done make it already quite complex.
835+// - The main Ordering Function is OrderingAdvanced
836+// - Lines which start at the end of another line are connected and treated as one (struct OrderingInfoEx)
837+// - Groups of zig-zag OrderingInfoEx are grouped (struct OrderingGroup) if both ends of the segment mutually agree with a next neighbor.
838+// These groups are treated as a unit in the TSP algorithm.
839+// The only option is to reverse the first segment, so that a group has 4 end points, 2 of which are used externally.
840+// - Run a k-opt (k=2..5) Lin like Traveling Salesman Problem algorithm on the groups as a unit and the remaining edges.
841+// See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Iterative_improvement
842+// The algorithm uses a greedy nearest neighbor as start configuration and does not use repeated random starts.
843+// - The algorithm searches an open tour (rather than a closed one), so the longest segment in the closed path is ignored.
844+// - TODO: it might be faster to use k=3 with a few random starting patterns instead of k=5
845+// - TODO: it is surely wiser to implement e.g. Lin-Kenrighan TSP, but the simple k-opt works ok.
846+// - TODO(EASY): add a jump distance, above which threads are removed and make the length of this jump distance constant and large,
847+// so that mostly the number of jumps is optimized
848+
849+// Find 2 nearest points to given point
850+
851+void OrderingPoint::FindNearest2(const std::vector<OrderingInfoEx *> &infos)
852+{
853+ // This implementation is not terribly elegant (unSTLish).
854+ // But for the first 2 elements using e.g. partial_sort is not simpler.
855+
856+ Coord dist0 = infinity();
857+ Coord dist1 = infinity();
858+ nearest[0] = 0;
859+ nearest[1] = 0;
860+
861+ for (std::vector<OrderingInfoEx *>::const_iterator it = infos.begin(); it != infos.end(); ++it) {
862+ Coord dist = distance(point, (*it)->beg.point);
863+ if (dist < dist1) {
864+ if (&(*it)->beg != this && &(*it)->end != this) {
865+ if (dist < dist0) {
866+ nearest[1] = nearest[0];
867+ nearest[0] = &(*it)->beg;
868+ dist1 = dist0;
869+ dist0 = dist;
870+ } else {
871+ nearest[1] = &(*it)->beg;
872+ dist1 = dist;
873+ }
874+ }
875+ }
876+
877+ dist = distance(point, (*it)->end.point);
878+ if (dist < dist1) {
879+ if (&(*it)->beg != this && &(*it)->end != this) {
880+ if (dist < dist0) {
881+ nearest[1] = nearest[0];
882+ nearest[0] = &(*it)->end;
883+ dist1 = dist0;
884+ dist0 = dist;
885+ } else {
886+ nearest[1] = &(*it)->end;
887+ dist1 = dist;
888+ }
889+ }
890+ }
891+ }
892+}
893+
894+// Check if "this" is among the nearest of its nearest
895+
896+void OrderingPoint::EnforceMutual(void)
897+{
898+ if (nearest[0] && !(this == nearest[0]->nearest[0] || this == nearest[0]->nearest[1])) {
899+ nearest[0] = 0;
900+ }
901+
902+ if (nearest[1] && !(this == nearest[1]->nearest[0] || this == nearest[1]->nearest[1])) {
903+ nearest[1] = 0;
904+ }
905+
906+ if (nearest[1] && !nearest[0]) {
907+ nearest[0] = nearest[1];
908+ nearest[1] = 0;
909+ }
910+}
911+
912+// Check if the subpath indices of this and other are the same, otherwise zero both nearest
913+
914+void OrderingPoint::EnforceSymmetric(const OrderingPoint &other)
915+{
916+ if (nearest[0] && !(
917+ (other.nearest[0] && nearest[0]->infoex == other.nearest[0]->infoex) ||
918+ (other.nearest[1] && nearest[0]->infoex == other.nearest[1]->infoex)
919+ )) {
920+ nearest[0] = 0;
921+ }
922+
923+ if (nearest[1] && !(
924+ (other.nearest[0] && nearest[1]->infoex == other.nearest[0]->infoex) ||
925+ (other.nearest[1] && nearest[1]->infoex == other.nearest[1]->infoex)
926+ )) {
927+ nearest[1] = 0;
928+ }
929+
930+ if (nearest[1] && !nearest[0]) {
931+ nearest[0] = nearest[1];
932+ nearest[1] = 0;
933+ }
934+}
935+
936+void OrderingPoint::Dump(void)
937+{
938+ Coord dist0 = nearest[0] ? distance(point, nearest[0]->point) : -1.0;
939+ Coord dist1 = nearest[1] ? distance(point, nearest[1]->point) : -1.0;
940+ int idx0 = nearest[0] ? nearest[0]->infoex->idx : -1;
941+ int idx1 = nearest[1] ? nearest[1]->infoex->idx : -1;
942+ DebugTrace2(("I=%d X=%.5lf Y=%.5lf d1=%.3lf d2=%.3lf i1=%d i2=%d", infoex->idx, point.x(), 297.0 - point.y(), dist0, dist1, idx0, idx1));
943+}
944+
945+
946+// If this element can be grouped (has neighbours) but is not yet grouped, create a new group
947+
948+void OrderingInfoEx::MakeGroup(std::vector<OrderingInfoEx *> &infos, std::vector<OrderingGroup *> *groups)
949+{
950+ if (grouped || !beg.HasNearest() || !end.HasNearest()) {
951+ return;
952+ }
953+
954+ groups->push_back(new OrderingGroup(groups->size()));
955+
956+ // Add neighbors recursively
957+ AddToGroup(infos, groups->back());
958+}
959+
960+// Add this and all connected elements to the group
961+
962+void OrderingInfoEx::AddToGroup(std::vector<OrderingInfoEx *> &infos, OrderingGroup *group)
963+{
964+ if (grouped || !beg.HasNearest() || !end.HasNearest()) {
965+ return;
966+ }
967+
968+ group->items.push_back(this);
969+ grouped = true;
970+ // Note: beg and end neighbors have been checked to be symmetric
971+ if (beg.nearest[0]) {
972+ beg.nearest[0]->infoex->AddToGroup(infos, group);
973+ }
974+ if (beg.nearest[1]) {
975+ beg.nearest[1]->infoex->AddToGroup(infos, group);
976+ }
977+ if (end.nearest[0]) {
978+ end.nearest[0]->infoex->AddToGroup(infos, group);
979+ }
980+ if (end.nearest[1]) {
981+ end.nearest[1]->infoex->AddToGroup(infos, group);
982+ }
983+}
984+
985+// Constructor
986+
987+OrderingGroupNeighbor::OrderingGroupNeighbor(OrderingGroupPoint *me, OrderingGroupPoint *other) :
988+ point(other),
989+ distance(Geom::distance(me->point, other->point))
990+{
991+}
992+
993+// Comparison function for sorting by distance
994+
995+bool OrderingGroupNeighbor::Compare(const OrderingGroupNeighbor &a, const OrderingGroupNeighbor &b)
996+{
997+ return a.distance < b.distance;
998+}
999+
1000+// Find the nearest unused neighbor point
1001+
1002+OrderingGroupNeighbor *OrderingGroupPoint::FindNearestUnused(void)
1003+{
1004+ for (std::vector<OrderingGroupNeighbor>::iterator it = nearest.begin(); it != nearest.end(); ++it) {
1005+ if (!it->point->used) {
1006+ DebugTrace1TSP(("Nearest: group %d, size %d, point %d, nghb %d, xFrom %.4lf, yFrom %.4lf, xTo %.4lf, yTo %.4lf, dist %.4lf",
1007+ it->point->group->index, it->point->group->items.size(), it->point->indexInGroup, it - nearest.begin(),
1008+ point.x(), 297 - point.y(),
1009+ it->point->point.x(), 297 - it->point->point.y(),
1010+ it->distance));
1011+ return &*it;
1012+ }
1013+ }
1014+
1015+ // it shouldn't happen that we can't find any point at all
1016+ assert(0);
1017+ return 0;
1018+}
1019+
1020+// Return the other end in the group of the point
1021+
1022+OrderingGroupPoint *OrderingGroupPoint::GetOtherEndGroup(void)
1023+{
1024+ return group->endpoints[ indexInGroup ^ 1 ];
1025+}
1026+
1027+// Return the alternate point (if one exists), 0 otherwise
1028+
1029+OrderingGroupPoint *OrderingGroupPoint::GetAltPointGroup(void)
1030+{
1031+ if (group->nEndPoints < 4) {
1032+ return 0;
1033+ }
1034+
1035+ OrderingGroupPoint *alt = group->endpoints[ indexInGroup ^ 2 ];
1036+ return alt->used ? 0 : alt;
1037+}
1038+
1039+
1040+// Sets the rev flags in the group assuming that the group starts with this point
1041+
1042+void OrderingGroupPoint::SetRevInGroup(void)
1043+{
1044+ // If this is not a front point, the item list needs to be reversed
1045+ group->revItemList = !front;
1046+
1047+ // If this is not a begin point, the items need to be reversed
1048+ group->revItems = !begin;
1049+}
1050+
1051+// Mark an end point as used and also mark the two other alternating points as used
1052+// Returns the used point
1053+
1054+void OrderingGroupPoint::UsePoint(void)
1055+{
1056+ group->UsePoint(indexInGroup);
1057+}
1058+
1059+// Mark an end point as unused and possibly also mark the two other alternating points as unused
1060+// Returns the used point
1061+
1062+void OrderingGroupPoint::UnusePoint(void)
1063+{
1064+ group->UnusePoint(indexInGroup);
1065+}
1066+
1067+// Return the other end in the connection
1068+OrderingGroupPoint *OrderingGroupPoint::GetOtherEndConnection(void)
1069+{
1070+ assert(connection);
1071+ assert(connection->points[ indexInConnection ] == this);
1072+ assert(connection->points[ indexInConnection ^ 1 ]);
1073+
1074+ return connection->points[ indexInConnection ^ 1 ];
1075+}
1076+
1077+
1078+// Set the end points of a group from the items
1079+
1080+void OrderingGroup::SetEndpoints(void)
1081+{
1082+ assert(items.size() >= 1);
1083+
1084+ if (items.size() == 1) {
1085+ // A simple line:
1086+ //
1087+ // b0-front--e1
1088+
1089+ nEndPoints = 2;
1090+ endpoints[0] = new OrderingGroupPoint(items.front()->beg.point, this, 0, true, true);
1091+ endpoints[1] = new OrderingGroupPoint(items.front()->end.point, this, 1, false, true);
1092+ } else {
1093+ // If the number of elements is even, the group is
1094+ // either from items.front().beg to items.back().beg
1095+ // or from items.front().end to items.back().end:
1096+ // Below: b=beg, e=end, numbers are end point indices
1097+ //
1098+ // b0-front--e b0-front--e2
1099+ // | |
1100+ // b---------e b---------e
1101+ // | |
1102+ // b---------e b---------e
1103+ // | |
1104+ // b1-back---e b1-back---e3
1105+ //
1106+ //
1107+ // if the number of elements is odd, it is crossed:
1108+ //
1109+ // b0-front--e b--front--e2
1110+ // | |
1111+ // b---------e b---------e
1112+ // | |
1113+ // b--back---e1 b3-back---e
1114+ //
1115+ // TODO: this is not true with the following kind of pattern
1116+ //
1117+ // b--front--e
1118+ // b---------e
1119+ // b--------e
1120+ // b--back--e
1121+ //
1122+ // Here only one connection is possible, from front.end to back.beg
1123+ //
1124+ // TODO: also this is not true if segment direction is alternating
1125+ //
1126+ // TOTO: => Just see where you end up from front().begin and front().end
1127+ //
1128+ // the numbering is such that either end points 0 and 1 are used or 2 and 3.
1129+ int cross = items.size() & 1 ? 2 : 0;
1130+ nEndPoints = 4;
1131+
1132+ endpoints[0 ] = new OrderingGroupPoint(items.front()->beg.point, this, 0, true, true);
1133+ endpoints[1 ^ cross] = new OrderingGroupPoint(items.back() ->beg.point, this, 1 ^ cross, true, false);
1134+ endpoints[2 ] = new OrderingGroupPoint(items.front()->end.point, this, 2, false, true);
1135+ endpoints[3 ^ cross] = new OrderingGroupPoint(items.back() ->end.point, this, 3 ^ cross, false, false);
1136+ }
1137+}
1138+
1139+// Add all points from another group as neighbors
1140+
1141+void OrderingGroup::AddNeighbors(OrderingGroup *nghb)
1142+{
1143+ for (int iThis = 0; iThis < nEndPoints; iThis++) {
1144+ for (int iNghb = 0; iNghb < nghb->nEndPoints; iNghb++) {
1145+ endpoints[iThis]->nearest.push_back(OrderingGroupNeighbor(endpoints[iThis], nghb->endpoints[iNghb]));
1146+ }
1147+ }
1148+}
1149+
1150+// Mark an end point as used and also mark the two other alternating points as used
1151+// Returns the used point
1152+
1153+OrderingGroupPoint *OrderingGroup::UsePoint(int index)
1154+{
1155+ assert(index < nEndPoints);
1156+ assert(!endpoints[index]->used);
1157+ endpoints[index]->used = true;
1158+ if (nEndPoints == 4) {
1159+ int offs = index < 2 ? 2 : 0;
1160+ endpoints[0 + offs]->used = true;
1161+ endpoints[1 + offs]->used = true;
1162+ }
1163+
1164+ return endpoints[index];
1165+}
1166+
1167+// Mark an end point as unused and possibly also mark the two other alternating points as unused
1168+// Returns the used point
1169+
1170+void OrderingGroup::UnusePoint(int index)
1171+{
1172+ assert(index < nEndPoints);
1173+ assert(endpoints[index]->used);
1174+ endpoints[index]->used = false;
1175+
1176+ if (nEndPoints == 4 && !endpoints[index ^ 1]->used) {
1177+ int offs = index < 2 ? 2 : 0;
1178+ endpoints[0 + offs]->used = false;
1179+ endpoints[1 + offs]->used = false;
1180+ }
1181+}
1182+
1183+// Add an end point
1184+void OrderingSegment::AddPoint(OrderingGroupPoint *point)
1185+{
1186+ assert(point);
1187+ assert(nEndPoints < 4);
1188+ endpoints[ nEndPoints++ ] = point;
1189+
1190+ // If both ends of a group are added and the group has 4 points, add the other two as well
1191+ if (nEndPoints == 2 && endpoints[0]->group == endpoints[1]->group) {
1192+ OrderingGroup *group = endpoints[0]->group;
1193+ if (group->nEndPoints == 4) {
1194+ for (int i = 0; i < 4; i++) {
1195+ endpoints[i] = group->endpoints[i];
1196+ }
1197+ nEndPoints = 4;
1198+ }
1199+ }
1200+}
1201+
1202+// Get begin point (taking swap and end bit into account
1203+OrderingGroupPoint *OrderingSegment::GetBeginPoint(unsigned int iSwap, unsigned int iEnd)
1204+{
1205+ int iPoint = ((iEnd >> endbit) & 1) + (((iSwap >> swapbit) & 1) << 1);
1206+ assert(iPoint < nEndPoints);
1207+ return endpoints[iPoint];
1208+}
1209+
1210+// Get end point (taking swap and end bit into account
1211+OrderingGroupPoint *OrderingSegment::GetEndPoint(unsigned int iSwap, unsigned int iEnd)
1212+{
1213+ int iPoint = (((iEnd >> endbit) & 1) ^ 1) + (((iSwap >> swapbit) & 1) << 1);
1214+ assert(iPoint < nEndPoints);
1215+ return endpoints[iPoint];
1216+}
1217+
1218+
1219+// Find the next unused point in list
1220+std::vector<OrderingGroupPoint *>::iterator FindUnusedAndUse(std::vector<OrderingGroupPoint *> *unusedPoints, std::vector<OrderingGroupPoint *>::iterator const from)
1221+{
1222+ for (std::vector<OrderingGroupPoint *>::iterator it = from; it != unusedPoints->end(); ++it) {
1223+ if (!(*it)->used) {
1224+ (*it)->UsePoint();
1225+ return it;
1226+ }
1227+ }
1228+ return unusedPoints->end();
1229+}
1230+
1231+// Find the shortest reconnect between the given points
1232+
1233+bool FindShortestReconnect(std::vector<OrderingSegment> &segments, std::vector<OrderingGroupConnection *> &connections, std::vector<OrderingGroupConnection *> &allconnections, OrderingGroupConnection **longestConnect, Coord *total, Coord olddist)
1234+{
1235+ // Find the longest connection outside of the active set
1236+ // The longest segment is then the longest of this longest outside segment and all inside segments
1237+ OrderingGroupConnection *longestOutside = 0;
1238+
1239+ if (contains(connections, *longestConnect)) {
1240+ // The longest connection is inside the active set, so we need to search for the longest outside
1241+ Coord length = 0.0;
1242+ for (std::vector<OrderingGroupConnection *>::iterator it = allconnections.begin(); it != allconnections.end(); it++) {
1243+ if ((*it)->Distance() > length) {
1244+ if (!contains(connections, *it)) {
1245+ longestOutside = *it;
1246+ length = (*it)->Distance();
1247+ }
1248+ }
1249+ }
1250+ } else {
1251+ longestOutside = *longestConnect;
1252+ }
1253+
1254+ // length of longestConnect outside
1255+ Coord longestOutsideLength = longestOutside ? longestOutside->Distance() : 0.0;
1256+
1257+ // We measure length without the longest, so subtract the longest length from the old distance
1258+ olddist -= (*longestConnect)->Distance();
1259+
1260+ // Assign a swap bit and end bit to each active connection
1261+ int nEndBits = 0;
1262+ int nSwapBits = 0;
1263+ for (std::vector<OrderingSegment>::iterator it = segments.begin(); it != segments.end(); it++) {
1264+ it->endbit = nEndBits++;
1265+ if (it->nEndPoints == 4) {
1266+ it->swapbit = nSwapBits++;
1267+ } else {
1268+ // bit 32 should always be 0
1269+ it->swapbit = 31;
1270+ }
1271+ }
1272+
1273+ unsigned int swapMask = (1U << nSwapBits) - 1;
1274+ unsigned int endMask = (1U << nEndBits) - 1;
1275+
1276+ // Create a permutation vector
1277+ std::vector<int> permutation(segments.size());
1278+ fill_increasing(permutation.begin(), permutation.end(), 0);
1279+
1280+ // best improvement
1281+ bool improved = false;
1282+ Coord distBest = olddist;
1283+ std::vector<int> permutationBest;
1284+ unsigned int iSwapBest;
1285+ unsigned int iEndBest;
1286+ int nTrials = 0;
1287+
1288+ // Loop over the permutations
1289+ do {
1290+ // Loop over the swap bits
1291+ unsigned int iSwap = 0;
1292+ do {
1293+ // Loop over the end bits
1294+ unsigned int iEnd = 0;
1295+ do {
1296+ // Length of all active connections
1297+ Coord lengthTotal = 0;
1298+ // Length of longest connection (active or inactive)
1299+ Coord lengthLongest = longestOutsideLength;
1300+
1301+ // Close the loop with the end point of the last segment
1302+ OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
1303+ for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
1304+ OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
1305+ Coord length = Geom::distance(thisbeg->point, prevend->point);
1306+ lengthTotal += length;
1307+ if (length > lengthLongest) {
1308+ lengthLongest = length;
1309+ }
1310+ prevend = segments[*it].GetEndPoint(iSwap, iEnd);
1311+ }
1312+ lengthTotal -= lengthLongest;
1313+
1314+ // If there is an improvement, remember the best selection
1315+ if (lengthTotal + 1e-6 < distBest) {
1316+ improved = true;
1317+ distBest = lengthTotal;
1318+ permutationBest = permutation;
1319+ iSwapBest = iSwap;
1320+ iEndBest = iEnd;
1321+
1322+ // Just debug printing
1323+ OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
1324+ for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
1325+ OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
1326+ DebugTrace2TSP(("IMP 0F=%d %d %.6lf", thisbeg->group->index, thisbeg->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
1327+ DebugTrace2TSP(("IMP 0T=%d %d %.6lf", prevend->group->index, prevend->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
1328+ prevend = segments[*it].GetEndPoint(iSwap, iEnd);
1329+ }
1330+ }
1331+
1332+ nTrials++;
1333+
1334+ // bit 0 is always 0, because the first segment is kept fixed
1335+ iEnd += 2;
1336+ } while (iEnd & endMask);
1337+ iSwap++;
1338+ } while (iSwap & swapMask);
1339+ // first segment is kept fixed
1340+ } while (std::next_permutation(permutation.begin() + 1, permutation.end()));
1341+
1342+ if (improved) {
1343+ DebugTrace2TSP(("Improvement %lf->%lf in %d", olddist, distBest, nTrials));
1344+ // change the connections
1345+
1346+ for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
1347+ DebugTrace2TSP(("WAS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
1348+ DebugTrace2TSP(("WAS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
1349+ }
1350+ DebugTrace2TSP(("OLDDIST %.6lf delta %.6lf", olddist, olddist - (*longestConnect)->Distance()));
1351+ DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
1352+ DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
1353+
1354+ int perm = permutationBest.back();
1355+
1356+ for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
1357+ (*it)->Connect(1, segments[ perm ].GetEndPoint(iSwapBest, iEndBest));
1358+ perm = permutationBest[ it - connections.begin() ];
1359+ (*it)->Connect(0, segments[ perm ].GetBeginPoint(iSwapBest, iEndBest));
1360+
1361+ }
1362+
1363+ for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
1364+ DebugTrace2TSP(("IS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
1365+ DebugTrace2TSP(("IS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
1366+ }
1367+
1368+ (*longestConnect) = longestOutside;
1369+ for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
1370+ if ((*it)->Distance() > (*longestConnect)->Distance()) {
1371+ *longestConnect = *it;
1372+ }
1373+ }
1374+ DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
1375+ DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
1376+ }
1377+
1378+ return improved;
1379+}
1380+
1381+// Check if connections form a tour
1382+void AssertIsTour(std::vector<OrderingGroup *> &groups, std::vector<OrderingGroupConnection *> &connections, OrderingGroupConnection *longestConnection)
1383+{
1384+ for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); it++) {
1385+ for (int i = 0; i < 2; i++) {
1386+ OrderingGroupPoint *pnt = (*it)->points[i];
1387+ assert(pnt->connection == *it);
1388+ assert(pnt->connection->points[pnt->indexInConnection] == pnt);
1389+ assert(pnt->group->endpoints[pnt->indexInGroup] == pnt);
1390+ }
1391+ }
1392+
1393+ Coord length1 = 0;
1394+ Coord longest1 = 0;
1395+ OrderingGroupPoint *current = connections.front()->points[0];
1396+
1397+ for (unsigned int n = 0; n < connections.size(); n++) {
1398+ DebugTrace2TSP(("Tour test 1 %p g=%d/%d c=%d/%d %p %p %.6lf %.3lf %.3lf %d %d %d", current, current->group->index, current->indexInGroup, current->connection->index, current->indexInConnection, current->connection->points[0], current->connection->points[1], current->connection->Distance(), current->point.x(), 297 - current->point.y(), current->begin, current->front, current->group->items.size()));
1399+ Coord length = current->connection->Distance();
1400+ length1 += length;
1401+ longest1 = std::max(length, longest1);
1402+ current = current->GetOtherEndConnection();
1403+
1404+ DebugTrace2TSP(("Tour test 2 %p g=%d/%d c=%d/%d %p %p %.6lf %.3lf %.3lf %d %d %d", current, current->group->index, current->indexInGroup, current->connection->index, current->indexInConnection, current->connection->points[0], current->connection->points[1], current->connection->Distance(), current->point.x(), 297 - current->point.y(), current->begin, current->front, current->group->items.size()));
1405+ current = current->GetOtherEndGroup();
1406+ }
1407+ DebugTrace2TSP(("Tour test 3 %p g=%d/%d c=%d/%d %p %p", current, current->group->index, current->indexInGroup, current->connection->index, current->indexInConnection, current->connection->points[0], current->connection->points[1]));
1408+ assert(current == connections.front()->points[0]);
1409+
1410+ // The other direction
1411+ Coord length2 = 0;
1412+ Coord longest2 = 0;
1413+ current = connections.front()->points[0];
1414+ for (unsigned int n = 0; n < connections.size(); n++) {
1415+ current = current->GetOtherEndGroup();
1416+ Coord length = current->connection->Distance();
1417+ length2 += length;
1418+ longest2 = std::max(length, longest2);
1419+ current = current->GetOtherEndConnection();
1420+ }
1421+ assert(current == connections.front()->points[0]);
1422+
1423+ DebugTrace1TSP(("Tour length %.6lf(%.6lf) longest %.6lf(%.6lf) remaining %.6lf(%.6lf)", length1, length2, longest1, longest2, length1 - longest1, length2 - longest2));
1424+}
1425+
1426+// Bring a tour into linear order after a modification
1427+
1428+/* I would like to avoid this.
1429+ * It is no problem to travel a tour with changing directions using the GetOtherEnd functions,
1430+ * but it is difficult to know the segments, that is which endpoint of a connection is connected to which by the unmodified pieces of the tour.
1431+ * In the end it is probably better to implement the Lin-Kernighan algorithm which avoids this problem by creating connected changes. */
1432+
1433+void LinearizeTour(std::vector<OrderingGroupConnection *> &connections)
1434+{
1435+ OrderingGroupPoint *current = connections.front()->points[0];
1436+
1437+ for (unsigned int iNew = 0; iNew < connections.size(); iNew++) {
1438+ // swap the connection at location n with the current connection
1439+ OrderingGroupConnection *connection = current->connection;
1440+ unsigned int iOld = connection->index;
1441+ assert(connections[iOld] == connection);
1442+
1443+ connections[iOld] = connections[iNew];
1444+ connections[iNew] = connection;
1445+ connections[iOld]->index = iOld;
1446+ connections[iNew]->index = iNew;
1447+
1448+ // swap the points of a connection
1449+ assert(current == connection->points[0] || current == connection->points[1]);
1450+ if (current != connection->points[0]) {
1451+ connection->points[1] = connection->points[0];
1452+ connection->points[0] = current;
1453+ connection->points[1]->indexInConnection = 1;
1454+ connection->points[0]->indexInConnection = 0;
1455+ }
1456+
1457+ current = current->GetOtherEndConnection();
1458+ current = current->GetOtherEndGroup();
1459+ }
1460+}
1461+
1462+// Use some Traveling Salesman Problem (TSP) like heuristics to bring several groups into a
1463+// order with as short as possible interconnection paths
1464+
1465+void OrderGroups(std::vector<OrderingGroup *> *groups, const int nDims)
1466+{
1467+ // There is no point in ordering just one group
1468+ if (groups->size() <= 1) {
1469+ return;
1470+ }
1471+
1472+ // Initialize the endpoints for all groups
1473+ for (std::vector<OrderingGroup *>::iterator it = groups->begin(); it != groups->end(); ++it) {
1474+ (*it)->SetEndpoints();
1475+ }
1476+
1477+ // Find the neighboring points for all end points of all groups and sort by distance
1478+ for (std::vector<OrderingGroup *>::iterator itThis = groups->begin(); itThis != groups->end(); ++itThis) {
1479+ for (int i = 0; i < (*itThis)->nEndPoints; i++) {
1480+ // This can be up to 2x too large, but still better than incrementing the size
1481+ (*itThis)->endpoints[i]->nearest.reserve(4 * groups->size());
1482+ }
1483+
1484+ for (std::vector<OrderingGroup *>::iterator itNghb = groups->begin(); itNghb != groups->end(); ++itNghb) {
1485+ if (itThis != itNghb) {
1486+ (*itThis)->AddNeighbors(*itNghb);
1487+ }
1488+ }
1489+
1490+ for (int i = 0; i < (*itThis)->nEndPoints; i++) {
1491+ std::sort((*itThis)->endpoints[i]->nearest.begin(), (*itThis)->endpoints[i]->nearest.end(), OrderingGroupNeighbor::Compare);
1492+ }
1493+ }
1494+
1495+ // =========== Step 1: Create a simple nearest neighbor chain ===========
1496+
1497+ // Vector of connection points
1498+ std::vector<OrderingGroupConnection *> connections;
1499+ connections.reserve(groups->size());
1500+ // Total Jump Distance
1501+ Coord total = 0.0;
1502+
1503+ // Start with the first group and connect always with nearest unused point
1504+ OrderingGroupPoint *crnt = groups->front()->endpoints[0];
1505+
1506+ // The longest connection is ignored (we don't want cycles)
1507+ OrderingGroupConnection *longestConnect = 0;
1508+
1509+ for (unsigned int nConnected = 0; nConnected < groups->size(); nConnected++) {
1510+ // Mark both end points of the current segment as used
1511+ crnt->UsePoint();
1512+ crnt = crnt->GetOtherEndGroup();
1513+ crnt->UsePoint();
1514+
1515+ // if this is the last segment, Mark start point of first segment as unused,
1516+ // so that the end can connect to it
1517+ if (nConnected == groups->size() - 1) {
1518+ groups->front()->endpoints[0]->UnusePoint();
1519+ }
1520+
1521+ // connect to next segment
1522+ OrderingGroupNeighbor *nghb = crnt->FindNearestUnused();
1523+ connections.push_back(new OrderingGroupConnection(crnt, nghb->point, connections.size()));
1524+ total += nghb->distance;
1525+ crnt = nghb->point;
1526+
1527+ if (!longestConnect || nghb->distance > longestConnect->Distance()) {
1528+ longestConnect = connections.back();
1529+ }
1530+ }
1531+
1532+ DebugTrace1TSP(("Total jump distance %.3lf (closed)", total));
1533+ DebugTrace1TSP(("Total jump distance %.3lf (open)", total - longestConnect->Distance()));
1534+
1535+ AssertIsTour(*groups, connections, longestConnect);
1536+
1537+ // =========== Step 2: Choose nDims segments to clear and reconnect ===========
1538+
1539+ bool improvement;
1540+ int nRuns = 0;
1541+ int nTrials = 0;
1542+ int nImprovements = 0;
1543+
1544+ do {
1545+ improvement = false;
1546+ nRuns ++;
1547+ std::vector< std::vector<OrderingGroupConnection *>::iterator > iterators;
1548+
1549+ for (
1550+ triangleit_begin(iterators, connections.begin(), connections.end(), nDims);
1551+ triangleit_test(iterators, connections.end());
1552+ triangleit_incr(iterators, connections.end())
1553+ ) {
1554+ nTrials ++;
1555+
1556+ Coord dist = 0;
1557+
1558+ std::vector<OrderingSegment> segments(iterators.size());
1559+ std::vector<OrderingGroupConnection *> changedconnections;
1560+ changedconnections.reserve(3);
1561+ OrderingGroupConnection *prev = *iterators.back();
1562+
1563+
1564+ for (size_t i = 0; i < iterators.size(); i++) {
1565+ dist += (*iterators[i])->Distance();
1566+ segments[i].AddPoint(prev->points[1]);
1567+ segments[i].AddPoint((*iterators[i])->points[0]);
1568+ prev = *iterators[i];
1569+ changedconnections.push_back(*iterators[i]);
1570+ }
1571+
1572+ if (FindShortestReconnect(segments, changedconnections, connections, &longestConnect, &total, dist)) {
1573+ nImprovements ++;
1574+
1575+ AssertIsTour(*groups, connections, longestConnect);
1576+ LinearizeTour(connections);
1577+ AssertIsTour(*groups, connections, longestConnect);
1578+ improvement = true;
1579+ }
1580+ }
1581+ } while (improvement && nRuns < 10);
1582+
1583+ DebugTrace1TSP(("Finished after %d rounds, %d trials, %d improvements", nRuns, nTrials, nImprovements));
1584+
1585+ // =========== Step N: Create vector of groups from vector of connection points ===========
1586+
1587+ std::vector<OrderingGroup *> result;
1588+ result.reserve(groups->size());
1589+
1590+ // Go through the groups starting with the longest connection (which is this way left out)
1591+ {
1592+ OrderingGroupPoint *current = longestConnect->points[1];
1593+
1594+ for (unsigned int n = 0; n < connections.size(); n++) {
1595+ result.push_back(current->group);
1596+ current->SetRevInGroup();
1597+ current = current->GetOtherEndGroup();
1598+ current = current->GetOtherEndConnection();
1599+ }
1600+ }
1601+
1602+ assert(result.size() == groups->size());
1603+ assert_unique(result);
1604+
1605+ delete_and_clear(connections);
1606+
1607+ *groups = result;
1608+}
1609+
1610+// Global optimization of path length
1611+
1612+void OrderingAdvanced(std::vector<OrderingInfo> &infos, int nDims)
1613+{
1614+ if (infos.size() < 3) {
1615+ return;
1616+ }
1617+
1618+ // Create extended ordering info vector and copy data from normal ordering info
1619+ std::vector<OrderingInfoEx *> infoex;
1620+ infoex.reserve(infos.size());
1621+
1622+ for (std::vector<OrderingInfo>::const_iterator it = infos.begin(); it != infos.end();) {
1623+ // Note: This assumes that the index in the OrderingInfo matches the vector index!
1624+ infoex.push_back(new OrderingInfoEx(*it, infoex.size()));
1625+ ++it;
1626+ while (it != infos.end() && it->begOrig == infoex.back()->end.point) {
1627+ infoex.back()->end.point = it->endOrig;
1628+ infoex.back()->origIndices.push_back(it->index);
1629+ ++it;
1630+ }
1631+ }
1632+
1633+ // Find closest 2 points for each point and enforce that 2nd nearest is not further away than 1.8xthe nearest
1634+ // If this is not the case, clear nearest and 2nd nearest point
1635+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1636+ (*it)->beg.FindNearest2(infoex);
1637+ (*it)->end.FindNearest2(infoex);
1638+ }
1639+
1640+ DebugTraceGrouping(
1641+ DebugTrace2(("STEP1"));
1642+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1643+ (*it)->beg.Dump();
1644+ (*it)->end.Dump();
1645+ }
1646+ )
1647+
1648+ // Make sure the nearest points are mutual
1649+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1650+ (*it)->beg.EnforceMutual();
1651+ (*it)->end.EnforceMutual();
1652+ }
1653+
1654+ DebugTraceGrouping(
1655+ DebugTrace2(("STEP2"));
1656+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1657+ (*it)->beg.Dump();
1658+ (*it)->end.Dump();
1659+ }
1660+ )
1661+
1662+ // Make sure the nearest points for begin and end lead to the same sub-path (same index)
1663+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1664+ (*it)->beg.EnforceSymmetric((*it)->end);
1665+ (*it)->end.EnforceSymmetric((*it)->beg);
1666+ }
1667+
1668+ DebugTraceGrouping(
1669+ DebugTrace2(("STEP3"));
1670+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1671+ (*it)->beg.Dump();
1672+ (*it)->end.Dump();
1673+ }
1674+ )
1675+
1676+ // The remaining nearest neighbors should be 100% non ambiguous, so group them
1677+ std::vector<OrderingGroup *> groups;
1678+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1679+ (*it)->MakeGroup(infoex, &groups);
1680+ }
1681+
1682+ // Create single groups for ungrouped lines
1683+ std::vector<OrderingInfo> result;
1684+ result.reserve(infos.size());
1685+ int nUngrouped = 0;
1686+ for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
1687+ if (!(*it)->grouped) {
1688+ groups.push_back(new OrderingGroup(groups.size()));
1689+ groups.back()->items.push_back(*it);
1690+ nUngrouped++;
1691+ }
1692+ }
1693+
1694+ DebugTraceGrouping(
1695+ DebugTrace2(("Ungrouped lines = %d", nUngrouped));
1696+ DebugTrace2(("%d Groups found", groups.size()));
1697+ for (std::vector<OrderingGroup *>::iterator it = groups.begin(); it != groups.end(); ++it) {
1698+ DebugTrace2(("Group size %d", (*it)->items.size()));
1699+ }
1700+ )
1701+
1702+ // Order groups, so that the connection path gets shortest
1703+ OrderGroups(&groups, nDims);
1704+
1705+ // Copy grouped lines to output
1706+ for (std::vector<OrderingGroup *>::iterator itGroup = groups.begin(); itGroup != groups.end(); ++itGroup) {
1707+ for (unsigned int iItem = 0; iItem < (*itGroup)->items.size(); iItem++) {
1708+ unsigned int iItemRev = (*itGroup)->revItemList ? (*itGroup)->items.size() - 1 - iItem : iItem;
1709+ OrderingInfoEx *item = (*itGroup)->items[iItemRev];
1710+
1711+ // If revItems is false, even items shall have reverse=false
1712+ // In this case ( ( iItem & 1 ) == 0 )== true, revItems=false, (true==false) == false
1713+ bool reverse = ((iItem & 1) == 0) == (*itGroup)->revItems;
1714+ if (!reverse) {
1715+ for (std::vector<int>::iterator itOrig = item->origIndices.begin(); itOrig != item->origIndices.end(); ++itOrig) {
1716+ result.push_back(infos[*itOrig]);
1717+ result.back().reverse = false;
1718+ }
1719+ } else {
1720+ for (std::vector<int>::reverse_iterator itOrig = item->origIndices.rbegin(); itOrig != item->origIndices.rend(); ++itOrig) {
1721+ result.push_back(infos[*itOrig]);
1722+ result.back().reverse = true;
1723+ }
1724+ }
1725+ }
1726+ result.back().connect = true;
1727+ }
1728+
1729+
1730+ delete_and_clear(groups);
1731+ delete_and_clear(infoex);
1732+
1733+ infos = result;
1734+}
1735+
1736+} // namespace LPEEmbroderyStitchOrdering
1737+} // namespace LivePathEffect
1738+} // namespace Inkscape
1739
1740=== added file 'src/live_effects/lpe-embrodery-stitch-ordering.h'
1741--- src/live_effects/lpe-embrodery-stitch-ordering.h 1970-01-01 00:00:00 +0000
1742+++ src/live_effects/lpe-embrodery-stitch-ordering.h 2017-06-05 19:01:49 +0000
1743@@ -0,0 +1,313 @@
1744+/*
1745+ * Sub-path Ordering functions for embroidery stitch LPE
1746+ *
1747+ * Copyright (C) 2016 Michael Soegtrop
1748+ *
1749+ * Released under GNU GPL, read the file 'COPYING' for more information
1750+ */
1751+
1752+#ifndef INKSCAPE_LPE_EMBRODERY_STITCH_ORDERING_H
1753+#define INKSCAPE_LPE_EMBRODERY_STITCH_ORDERING_H
1754+
1755+#include "live_effects/effect.h"
1756+
1757+namespace Inkscape {
1758+namespace LivePathEffect {
1759+namespace LPEEmbroderyStitchOrdering {
1760+
1761+// Structure keeping information on the ordering and reversing of sub paths
1762+// Used for simple ordering functions like zig-zag
1763+
1764+struct OrderingInfo {
1765+ int index;
1766+ bool reverse;
1767+ bool used;
1768+ bool connect;
1769+ Geom::Point begOrig; // begin point in original orientation
1770+ Geom::Point endOrig; // end point in original orientation
1771+
1772+ Geom::Point GetBegOrig() const
1773+ {
1774+ return begOrig;
1775+ }
1776+ Geom::Point GetEndOrig() const
1777+ {
1778+ return endOrig;
1779+ }
1780+ Geom::Point GetBegRev() const
1781+ {
1782+ return reverse ? endOrig : begOrig;
1783+ }
1784+ Geom::Point GetEndRev() const
1785+ {
1786+ return reverse ? begOrig : endOrig;
1787+ }
1788+};
1789+
1790+// Structure for a path end-point in OrderingInfoEx.
1791+// This keeps information about the two nearest neighbor points.
1792+
1793+struct OrderingInfoEx;
1794+
1795+struct OrderingPoint {
1796+ OrderingPoint(const Geom::Point &pointIn, OrderingInfoEx *infoexIn, bool beginIn) :
1797+ point(pointIn),
1798+ infoex(infoexIn),
1799+ begin(beginIn)
1800+ {
1801+ nearest[0] = nearest[1] = 0;
1802+ }
1803+
1804+ // Check if both nearest values are valid
1805+ bool IsNearestValid() const
1806+ {
1807+ return nearest[0] && nearest[1];
1808+ }
1809+ // Check if at least one nearest values are valid
1810+ bool HasNearest() const
1811+ {
1812+ return nearest[0] || nearest[1];
1813+ }
1814+ // Find 2 nearest points to given point
1815+ void FindNearest2(const std::vector<OrderingInfoEx *> &infos);
1816+ // Check if "this" is among the nearest of its nearest
1817+ void EnforceMutual(void);
1818+ // Check if the subpath indices of this and other are the same, otherwise zero both nearest
1819+ void EnforceSymmetric(const OrderingPoint &other);
1820+ // Dump point information
1821+ void Dump(void);
1822+
1823+ Geom::Point point;
1824+ OrderingInfoEx *infoex;
1825+ bool begin;
1826+ const OrderingPoint *nearest[2];
1827+};
1828+
1829+// Structure keeping information on the ordering and reversing of sub paths
1830+// Used for advanced ordering functions with block creation and Traveling Salesman Problem Optimization
1831+// A OrderingInfoEx may contain several original sub-paths in case sub-paths are directly connected.
1832+// Directly connected sub-paths happen e.g. after a slice boolean operation.
1833+
1834+struct OrderingGroup;
1835+
1836+struct OrderingInfoEx {
1837+ OrderingInfoEx(const OrderingInfo &infoIn, int idxIn) :
1838+ beg(infoIn.begOrig, this, true),
1839+ end(infoIn.endOrig, this, false),
1840+ idx(idxIn),
1841+ grouped(false)
1842+ {
1843+ origIndices.push_back(infoIn.index);
1844+ }
1845+
1846+ // If this element can be grouped (has neighbours) but is not yet grouped, create a new group
1847+ void MakeGroup(std::vector<OrderingInfoEx *> &infos, std::vector<OrderingGroup *> *groups);
1848+ // Add this and all connected elements to the group
1849+ void AddToGroup(std::vector<OrderingInfoEx *> &infos, OrderingGroup *group);
1850+
1851+ int idx;
1852+ bool grouped; // true if this element has been grouped
1853+ OrderingPoint beg; // begin point in original orientation
1854+ OrderingPoint end; // end point in original orientation
1855+ std::vector<int> origIndices; // Indices of the original OrderInfos (more than 1 if directly connected
1856+};
1857+
1858+// Neighbor information for OrderingGroupPoint - a distance and a OrderingGroupPoint
1859+
1860+struct OrderingGroupPoint;
1861+
1862+struct OrderingGroupNeighbor {
1863+ OrderingGroupNeighbor(OrderingGroupPoint *me, OrderingGroupPoint *other);
1864+
1865+ // Distance from owner of this neighbor info
1866+ Geom::Coord distance;
1867+ // Neighbor point (which in turn contains a pointer to the neighbor group
1868+ OrderingGroupPoint *point;
1869+
1870+ // Comparison function for sorting by distance
1871+ static bool Compare(const OrderingGroupNeighbor &a, const OrderingGroupNeighbor &b);
1872+};
1873+
1874+// An end point in an OrderingGroup, with nearest neighbor information
1875+
1876+struct OrderingGroupConnection;
1877+
1878+struct OrderingGroupPoint {
1879+ OrderingGroupPoint(const Geom::Point &pointIn, OrderingGroup *groupIn, int indexIn, bool beginIn, bool frontIn) :
1880+ point(pointIn),
1881+ group(groupIn),
1882+ indexInGroup(indexIn),
1883+ connection(0),
1884+ indexInConnection(0),
1885+ begin(beginIn),
1886+ front(frontIn),
1887+ used(false)
1888+ {
1889+ }
1890+
1891+ // Find the nearest unused neighbor point
1892+ OrderingGroupNeighbor *FindNearestUnused(void);
1893+ // Return the other end in the group of the point
1894+ OrderingGroupPoint *GetOtherEndGroup(void);
1895+ // Return the alternate point (if one exists), 0 otherwise
1896+ OrderingGroupPoint *GetAltPointGroup(void);
1897+ // Sets the rev flags in the group assuming that the group starts with this point
1898+ void SetRevInGroup(void);
1899+ // Mark an end point as used and also mark the two other alternating points as used
1900+ // Returns the used point
1901+ void UsePoint(void);
1902+ // Mark an end point as unused and possibly also mark the two other alternating points as unused
1903+ // Returns the used point
1904+ void UnusePoint(void);
1905+ // Return the other end in the connection
1906+ OrderingGroupPoint *GetOtherEndConnection(void);
1907+
1908+ // The coordinates of the point
1909+ Geom::Point point;
1910+ // The group to which the point belongs
1911+ OrderingGroup *group;
1912+ // The end-point index within the group
1913+ int indexInGroup;
1914+ // The connection, which connects this point
1915+ OrderingGroupConnection *connection;
1916+ // The end point index in the connection
1917+ int indexInConnection;
1918+ // True if this is a begin point (rather than an end point)
1919+ bool begin;
1920+ // True if this is a front point (rather than a back point)
1921+ bool front;
1922+ // True if the point is used/connected to another point
1923+ bool used;
1924+ // The nearest neighbors, to which this group end point may connect
1925+ std::vector<OrderingGroupNeighbor> nearest;
1926+};
1927+
1928+// A connection between two points/groups
1929+struct OrderingGroupConnection {
1930+ OrderingGroupConnection(OrderingGroupPoint *fromIn, OrderingGroupPoint *toIn, int indexIn) :
1931+ index(indexIn)
1932+ {
1933+ assert(fromIn->connection == 0);
1934+ assert(toIn->connection == 0);
1935+ points[0] = 0;
1936+ points[1] = 0;
1937+ Connect(0, fromIn);
1938+ Connect(1, toIn);
1939+ }
1940+
1941+ // Connect one of the conection endpoints to the given point
1942+ void Connect(int index, OrderingGroupPoint *point)
1943+ {
1944+ assert(point);
1945+ points[index] = point;
1946+ point->connection = this;
1947+ point->indexInConnection = index;
1948+ }
1949+
1950+ // Get length of connection
1951+ Geom::Coord Distance()
1952+ {
1953+ return Geom::distance(points[0]->point, points[1]->point);
1954+ }
1955+
1956+ OrderingGroupPoint *points[2];
1957+ // index of connection in the connections vector (just for debugging)
1958+ int index;
1959+};
1960+
1961+// A group of OrderingInfoEx, which build a block in path interconnect length optimization.
1962+// A block can have two sets of endpoints.
1963+// If a block has 2 sets of endpoints, one can swap between the two sets.
1964+
1965+struct OrderingGroup {
1966+ OrderingGroup(int indexIn) :
1967+ nEndPoints(0),
1968+ revItemList(false),
1969+ revItems(false),
1970+ index(indexIn)
1971+ {
1972+ for (int i = 0; i < sizeof(endpoints) / sizeof(*endpoints); i++) {
1973+ endpoints[i] = 0;
1974+ }
1975+ }
1976+
1977+ ~OrderingGroup()
1978+ {
1979+ for (int i = 0; i < nEndPoints; i++) {
1980+ delete endpoints[i];
1981+ }
1982+ }
1983+
1984+ // Set the endpoints of a group from the items
1985+ void SetEndpoints(void);
1986+ // Add all points from another group as neighbors
1987+ void AddNeighbors(OrderingGroup *nghb);
1988+ // Mark an end point as used and also mark the two other alternating points as used
1989+ // Returns the used point
1990+ OrderingGroupPoint *UsePoint(int index);
1991+ // Mark an end point as unused and possibly also mark the two other alternating points as unused
1992+ // Returns the used point
1993+ void UnusePoint(int index);
1994+
1995+ // Items on the group
1996+ std::vector<OrderingInfoEx *> items;
1997+ // End points of the group
1998+ OrderingGroupPoint *endpoints[4];
1999+ // Number of endpoints used (either 2 or 4)
2000+ int nEndPoints;
2001+ // Index of the group (just for debugging purposes)
2002+ int index;
2003+ // If true, the items in the group shall be output from back to front.
2004+ bool revItemList;
2005+ // If false, the individual items are output alternatingly normal-reversed
2006+ // If true, the individual items are output alternatingly reversed-normal
2007+ bool revItems;
2008+};
2009+
2010+// A segment is either a OrderingGroup or a series of groups and connections.
2011+// Usually a segment has just 2 end points.
2012+// If a segment is just one ordering group, it has the same number of end points as the ordering group
2013+// A main difference between a segment and a group is that the segment does not own the end points.
2014+
2015+struct OrderingSegment {
2016+ OrderingSegment() :
2017+ nEndPoints(0),
2018+ endbit(0),
2019+ swapbit(0)
2020+ {}
2021+
2022+ // Add an end point
2023+ void AddPoint(OrderingGroupPoint *point);
2024+ // Get begin point (taking swap and end bit into account
2025+ OrderingGroupPoint *GetBeginPoint(unsigned int iSwap, unsigned int iEnd);
2026+ // Get end point (taking swap and end bit into account
2027+ OrderingGroupPoint *GetEndPoint(unsigned int iSwap, unsigned int iEnd);
2028+
2029+ // End points of the group
2030+ OrderingGroupPoint *endpoints[4];
2031+ // Number of endpoints used (either 2 or 4)
2032+ int nEndPoints;
2033+ // bit index in the end counter
2034+ int endbit;
2035+ // bit index in the swap counter
2036+ int swapbit;
2037+};
2038+
2039+
2040+// Sub-path reordering: do nothing - keep original order
2041+void OrderingOriginal(std::vector<OrderingInfo> &infos);
2042+
2043+// Sub-path reordering: reverse every other sub path
2044+void OrderingZigZag(std::vector<OrderingInfo> &infos, bool revfirst);
2045+
2046+// Sub-path reordering: continue with the neartest start or end point of yet unused sub paths
2047+void OrderingClosest(std::vector<OrderingInfo> &infos, bool revfirst);
2048+
2049+// Global optimization of path length
2050+void OrderingAdvanced(std::vector<OrderingInfo> &infos, int nDims);
2051+
2052+} //LPEEmbroderyStitchOrdering
2053+} //namespace LivePathEffect
2054+} //namespace Inkscape
2055+
2056+#endif
2057
2058=== added file 'src/live_effects/lpe-embrodery-stitch.cpp'
2059--- src/live_effects/lpe-embrodery-stitch.cpp 1970-01-01 00:00:00 +0000
2060+++ src/live_effects/lpe-embrodery-stitch.cpp 2017-06-05 19:01:49 +0000
2061@@ -0,0 +1,400 @@
2062+/*
2063+ * Embroidery stitch live path effect (Implementation)
2064+ *
2065+ * Copyright (C) 2016 Michael Soegtrop
2066+ *
2067+ * Released under GNU GPL, read the file 'COPYING' for more information
2068+ */
2069+
2070+#include "ui/widget/scalar.h"
2071+#include <glibmm/i18n.h>
2072+
2073+#include "live_effects/lpe-embrodery-stitch.h"
2074+#include "live_effects/lpe-embrodery-stitch-ordering.h"
2075+
2076+#include <2geom/path.h>
2077+#include <2geom/piecewise.h>
2078+#include <2geom/sbasis.h>
2079+#include <2geom/sbasis-geometric.h>
2080+#include <2geom/bezier-to-sbasis.h>
2081+#include <2geom/sbasis-to-bezier.h>
2082+
2083+namespace Inkscape {
2084+namespace LivePathEffect {
2085+
2086+using namespace Geom;
2087+using namespace LPEEmbroderyStitchOrdering;
2088+
2089+static const Util::EnumData<LPEEmbroderyStitch::order_method> OrderMethodData[LPEEmbroderyStitch::order_method_count] = {
2090+ { LPEEmbroderyStitch::order_method_no_reorder, N_("no reordering"), "no-reorder" },
2091+ { LPEEmbroderyStitch::order_method_zigzag, N_("zig-zag"), "zig-zag" },
2092+ { LPEEmbroderyStitch::order_method_zigzag_rev_first, N_("zig-zag, reverse first"), "zig-zag-rev-first" },
2093+ { LPEEmbroderyStitch::order_method_closest, N_("closest"), "closest" },
2094+ { LPEEmbroderyStitch::order_method_closest_rev_first, N_("closest, reverse first"), "closest-rev-first" },
2095+ { LPEEmbroderyStitch::order_method_tsp_kopt_2, N_("traveling salesman 2-opt (fast, bad)"), "tsp-2opt" },
2096+ { LPEEmbroderyStitch::order_method_tsp_kopt_3, N_("traveling salesman 3-opt (fast, ok)"), "tsp-3opt" },
2097+ { LPEEmbroderyStitch::order_method_tsp_kopt_4, N_("traveling salesman 4-opt (seconds)"), "tsp-4opt" },
2098+ { LPEEmbroderyStitch::order_method_tsp_kopt_5, N_("traveling salesman 5-opt (miutes)"), "tsp-5opt" }
2099+};
2100+
2101+static const Util::EnumDataConverter<LPEEmbroderyStitch::order_method>
2102+OrderMethodConverter(OrderMethodData, sizeof(OrderMethodData) / sizeof(*OrderMethodData));
2103+
2104+static const Util::EnumData<LPEEmbroderyStitch::connect_method> ConnectMethodData[LPEEmbroderyStitch::connect_method_count] = {
2105+ { LPEEmbroderyStitch::connect_method_line, N_("straight line"), "line" },
2106+ { LPEEmbroderyStitch::connect_method_move_point_from, N_("move to begin"), "move-begin" },
2107+ { LPEEmbroderyStitch::connect_method_move_point_mid, N_("move to middle"), "move-middle" },
2108+ { LPEEmbroderyStitch::connect_method_move_point_to, N_("move to end"), "move-end" }
2109+};
2110+
2111+static const Util::EnumDataConverter<LPEEmbroderyStitch::connect_method>
2112+ConnectMethodConverter(ConnectMethodData, sizeof(ConnectMethodData) / sizeof(*ConnectMethodData));
2113+
2114+LPEEmbroderyStitch::LPEEmbroderyStitch(LivePathEffectObject *lpeobject) :
2115+ Effect(lpeobject),
2116+ ordering(_("Ordering method"), _("Method used to order sub paths"), "ordering", OrderMethodConverter, &wr, this, order_method_no_reorder),
2117+ connection(_("Connection method"), _("Method to connect end points of sub paths"), "connection", ConnectMethodConverter, &wr, this, connect_method_line),
2118+ stitch_length(_("Stitch length"), _("If not 0, linearize path with given step length"), "stitch-length", &wr, this, 10.0),
2119+ stitch_min_length(_("Minimum stitch length [%]"), _("Combine steps shorter than this [%]"), "stitch-min-length", &wr, this, 25.0),
2120+ stitch_pattern(_("Stitch pattern"), _("Select between different stitch patterns"), "stitch_pattern", &wr, this, 0),
2121+ show_stitches(_("Show stitches"), _("Show stitches as small gaps (just for inspection - don't use for output)"), "show-stitches", &wr, this, false),
2122+ show_stitch_gap(_("Show stitch gap"), _("Gap between stitches when showing stitches"), "show-stitch-gap", &wr, this, 0.5),
2123+ jump_if_longer(_("Jump if longer"), _("Jump connection if longer than"), "jump-if-longer", &wr, this, 100)
2124+{
2125+ registerParameter(dynamic_cast<Parameter *>(&ordering));
2126+ registerParameter(dynamic_cast<Parameter *>(&connection));
2127+ registerParameter(dynamic_cast<Parameter *>(&stitch_length));
2128+ registerParameter(dynamic_cast<Parameter *>(&stitch_min_length));
2129+ registerParameter(dynamic_cast<Parameter *>(&stitch_pattern));
2130+ registerParameter(dynamic_cast<Parameter *>(&show_stitches));
2131+ registerParameter(dynamic_cast<Parameter *>(&show_stitch_gap));
2132+ registerParameter(dynamic_cast<Parameter *>(&jump_if_longer));
2133+
2134+ stitch_length.param_set_digits(1);
2135+ stitch_length.param_set_range(1, 10000);
2136+ stitch_min_length.param_set_digits(1);
2137+ stitch_min_length.param_set_range(0, 100);
2138+ stitch_pattern.param_make_integer();
2139+ stitch_pattern.param_set_range(0, 2);
2140+ show_stitch_gap.param_set_range(0.001, 10);
2141+ jump_if_longer.param_set_range(0.0, 1000000);
2142+}
2143+
2144+LPEEmbroderyStitch::~LPEEmbroderyStitch()
2145+{
2146+
2147+}
2148+
2149+double LPEEmbroderyStitch::GetPatternInitialStep(int pattern, int line)
2150+{
2151+ switch (pattern) {
2152+ case 0:
2153+ return 0.0;
2154+
2155+ case 1:
2156+ switch (line % 4) {
2157+ case 0:
2158+ return 0.0;
2159+ case 1:
2160+ return 0.25;
2161+ case 2:
2162+ return 0.50;
2163+ case 3:
2164+ return 0.75;
2165+ }
2166+ return 0.0;
2167+
2168+ case 2:
2169+ switch (line % 4) {
2170+ case 0:
2171+ return 0.0;
2172+ case 1:
2173+ return 0.5;
2174+ case 2:
2175+ return 0.75;
2176+ case 3:
2177+ return 0.25;
2178+ }
2179+ return 0.0;
2180+
2181+ default:
2182+ return 0.0;
2183+ }
2184+
2185+}
2186+
2187+Point LPEEmbroderyStitch::GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
2188+{
2189+ Point start_this = info[i].GetBegRev();
2190+
2191+ if (i == 0) {
2192+ return start_this;
2193+ }
2194+
2195+ if (!info[i - 1].connect) {
2196+ return start_this;
2197+ }
2198+
2199+ Point end_prev = info[i - 1].GetEndRev();
2200+
2201+ switch (connection.get_value()) {
2202+ case connect_method_line:
2203+ return start_this;
2204+ case connect_method_move_point_from:
2205+ return end_prev;
2206+ case connect_method_move_point_mid:
2207+ return 0.5 * start_this + 0.5 * end_prev;
2208+ case connect_method_move_point_to:
2209+ return start_this;
2210+ default:
2211+ return start_this;
2212+ }
2213+}
2214+Point LPEEmbroderyStitch::GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
2215+{
2216+ Point end_this = info[i].GetEndRev();
2217+
2218+ if (i + 1 == info.size()) {
2219+ return end_this;
2220+ }
2221+
2222+ if (!info[i].connect) {
2223+ return end_this;
2224+ }
2225+
2226+ Point start_next = info[i + 1].GetBegRev();
2227+
2228+ switch (connection.get_value()) {
2229+ case connect_method_line:
2230+ return end_this;
2231+ case connect_method_move_point_from:
2232+ return end_this;
2233+ case connect_method_move_point_mid:
2234+ return 0.5 * start_next + 0.5 * end_this;
2235+ case connect_method_move_point_to:
2236+ return start_next;
2237+ default:
2238+ return end_this;
2239+ }
2240+}
2241+
2242+Point LPEEmbroderyStitch::GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
2243+{
2244+ if (info[i].reverse) {
2245+ return GetEndPointInterpolAfterRev(info, i);
2246+ } else {
2247+ return GetStartPointInterpolAfterRev(info, i);
2248+ }
2249+}
2250+
2251+Point LPEEmbroderyStitch::GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
2252+{
2253+ if (info[i].reverse) {
2254+ return GetStartPointInterpolAfterRev(info, i);
2255+ } else {
2256+ return GetEndPointInterpolAfterRev(info, i);
2257+ }
2258+}
2259+
2260+PathVector LPEEmbroderyStitch::doEffect_path(PathVector const &path_in)
2261+{
2262+ if (path_in.size() >= 2) {
2263+ PathVector path_out;
2264+
2265+ // Create vectors with start and end points
2266+ std::vector<OrderingInfo> orderinginfos(path_in.size());
2267+ // connect next path to this one
2268+ bool connect_with_previous = false;
2269+
2270+ for (PathVector::const_iterator it = path_in.begin(); it != path_in.end(); ++it) {
2271+ OrderingInfo &info = orderinginfos[ it - path_in.begin() ];
2272+ info.index = it - path_in.begin();
2273+ info.reverse = false;
2274+ info.used = false;
2275+ info.connect = true;
2276+ info.begOrig = it->front().initialPoint();
2277+ info.endOrig = it->back().finalPoint();
2278+ }
2279+
2280+ // Compute sub-path ordering
2281+ switch (ordering.get_value()) {
2282+ case order_method_no_reorder:
2283+ OrderingOriginal(orderinginfos);
2284+ break;
2285+
2286+ case order_method_zigzag:
2287+ OrderingZigZag(orderinginfos, false);
2288+ break;
2289+
2290+ case order_method_zigzag_rev_first:
2291+ OrderingZigZag(orderinginfos, true);
2292+ break;
2293+
2294+ case order_method_closest:
2295+ OrderingClosest(orderinginfos, false);
2296+ break;
2297+
2298+ case order_method_closest_rev_first:
2299+ OrderingClosest(orderinginfos, true);
2300+ break;
2301+
2302+ case order_method_tsp_kopt_2:
2303+ OrderingAdvanced(orderinginfos, 2);
2304+ break;
2305+
2306+ case order_method_tsp_kopt_3:
2307+ OrderingAdvanced(orderinginfos, 3);
2308+ break;
2309+
2310+ case order_method_tsp_kopt_4:
2311+ OrderingAdvanced(orderinginfos, 4);
2312+ break;
2313+
2314+ case order_method_tsp_kopt_5:
2315+ OrderingAdvanced(orderinginfos, 5);
2316+ break;
2317+
2318+ }
2319+
2320+ // Iterate over sub-paths in order found above
2321+ // Divide paths into stitches (currently always equidistant)
2322+ // Interpolate between neighboring paths, so that their ends coincide
2323+ for (std::vector<OrderingInfo>::const_iterator it = orderinginfos.begin(); it != orderinginfos.end(); ++it) {
2324+ // info index
2325+ unsigned iInfo = it - orderinginfos.begin();
2326+ // subpath index
2327+ unsigned iPath = it->index;
2328+ // decide of path shall be reversed
2329+ bool reverse = it->reverse;
2330+ // minimum stitch length in absolute measure
2331+ double stitch_min_length_abs = stitch_min_length * 0.01 * stitch_length;
2332+
2333+ // convert path to piecewise
2334+ Piecewise<D2<SBasis> > pwOrig = path_in[iPath].toPwSb();
2335+ // make piecewise equidistant in time
2336+ Piecewise<D2<SBasis> > pwEqdist = arc_length_parametrization(pwOrig);
2337+ Piecewise<D2<SBasis> > pwStitch;
2338+
2339+ // cut into stitches
2340+ double cutpos = 0.0;
2341+ Interval pwdomain = pwEqdist.domain();
2342+
2343+ // step length of first stitch
2344+ double step = GetPatternInitialStep(stitch_pattern, iInfo) * stitch_length;
2345+ if (step < stitch_min_length_abs) {
2346+ step += stitch_length;
2347+ }
2348+
2349+ bool last = false;
2350+ bool first = true;
2351+ double posnext;
2352+ for (double pos = pwdomain.min(); !last; pos = posnext, cutpos += 1.0) {
2353+ // start point
2354+ Point p1;
2355+ if (first) {
2356+ p1 = GetStartPointInterpolBeforeRev(orderinginfos, iInfo);
2357+ first = false;
2358+ } else {
2359+ p1 = pwEqdist.valueAt(pos);
2360+ }
2361+
2362+ // end point of this stitch
2363+ Point p2;
2364+ posnext = pos + step;
2365+ // last stitch is to end
2366+ if (posnext >= pwdomain.max() - stitch_min_length_abs) {
2367+ p2 = GetEndPointInterpolBeforeRev(orderinginfos, iInfo);
2368+ last = true;
2369+ } else {
2370+ p2 = pwEqdist.valueAt(posnext);
2371+ }
2372+
2373+ pwStitch.push_cut(cutpos);
2374+ pwStitch.push_seg(D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y]))));
2375+
2376+ // stitch length for all except first step
2377+ step = stitch_length;
2378+ }
2379+ pwStitch.push_cut(cutpos);
2380+
2381+ if (reverse) {
2382+ pwStitch = Geom::reverse(pwStitch);
2383+ }
2384+
2385+ if (it->connect && iInfo != orderinginfos.size() - 1) {
2386+ // Connect this segment with the previous segment by a straight line
2387+ Point end = pwStitch.lastValue();
2388+ Point start_next = GetStartPointInterpolAfterRev(orderinginfos, iInfo + 1);
2389+ // connect end and start point
2390+ if (end != start_next && distance(end, start_next) <= jump_if_longer) {
2391+ cutpos += 1.0;
2392+ pwStitch.push_seg(D2<SBasis>(SBasis(Linear(end[X], start_next[X])), SBasis(Linear(end[Y], start_next[Y]))));
2393+ pwStitch.push_cut(cutpos);
2394+ }
2395+ }
2396+
2397+ if (show_stitches) {
2398+ for (std::vector< D2<SBasis> >::iterator it = pwStitch.segs.begin(); it != pwStitch.segs.end(); ++it) {
2399+ // Create anew piecewise with just one segment
2400+ Piecewise<D2<SBasis> > pwOne;
2401+ pwOne.push_cut(0);
2402+ pwOne.push_seg(*it);
2403+ pwOne.push_cut(1);
2404+
2405+ // make piecewise equidistant in time
2406+ Piecewise<D2<SBasis> > pwOneEqdist = arc_length_parametrization(pwOne);
2407+ Interval pwdomain = pwOneEqdist.domain();
2408+
2409+ // Compute the points of teh shortened piece
2410+ Coord len = pwdomain.max() - pwdomain.min();
2411+ Coord offs = 0.5 * (show_stitch_gap < 0.5 * len ? show_stitch_gap : 0.5 * len);
2412+ Point p1 = pwOneEqdist.valueAt(pwdomain.min() + offs);
2413+ Point p2 = pwOneEqdist.valueAt(pwdomain.max() - offs);
2414+ Piecewise<D2<SBasis> > pwOneGap;
2415+
2416+ // Create Linear SBasis
2417+ D2<SBasis> sbasis = D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y])));
2418+
2419+ // Convert to path and add to path list
2420+ Geom::Path path = path_from_sbasis(sbasis , LPE_CONVERSION_TOLERANCE, false);
2421+ path_out.push_back(path);
2422+ }
2423+ } else {
2424+ PathVector pathv = path_from_piecewise(pwStitch, LPE_CONVERSION_TOLERANCE);
2425+ for (size_t ipv = 0; ipv < pathv.size(); ipv++) {
2426+ if (connect_with_previous) {
2427+ path_out.back().append(pathv[ipv]);
2428+ } else {
2429+ path_out.push_back(pathv[ipv]);
2430+ }
2431+ }
2432+ }
2433+
2434+ connect_with_previous = it->connect;
2435+ }
2436+
2437+ return path_out;
2438+ } else {
2439+ return path_in;
2440+ }
2441+}
2442+
2443+void
2444+LPEEmbroderyStitch::resetDefaults(SPItem const *item)
2445+{
2446+ Effect::resetDefaults(item);
2447+}
2448+
2449+
2450+/** /todo check whether this special case is necessary. It seems to "bug" editing behavior:
2451+ * scaling an object with transforms preserved behaves differently from scaling with
2452+ * transforms optimized (difference caused by this special method).
2453+ * special casing is probably needed, because rotation should not be propagated to the strokepath.
2454+ */
2455+void
2456+LPEEmbroderyStitch::transform_multiply(Affine const &postmul, bool set)
2457+{
2458+}
2459+
2460+} //namespace LivePathEffect
2461+} /* namespace Inkscape */
2462
2463=== added file 'src/live_effects/lpe-embrodery-stitch.h'
2464--- src/live_effects/lpe-embrodery-stitch.h 1970-01-01 00:00:00 +0000
2465+++ src/live_effects/lpe-embrodery-stitch.h 2017-06-05 19:01:49 +0000
2466@@ -0,0 +1,78 @@
2467+/*
2468+ * Embroidery stitch live path effect
2469+ *
2470+ * Copyright (C) 2016 Michael Soegtrop
2471+ *
2472+ * Released under GNU GPL, read the file 'COPYING' for more information
2473+ */
2474+
2475+#ifndef INKSCAPE_LPE_EMBRODERY_STITCH_H
2476+#define INKSCAPE_LPE_EMBRODERY_STITCH_H
2477+
2478+#include "live_effects/effect.h"
2479+#include "live_effects/parameter/parameter.h"
2480+#include "live_effects/parameter/bool.h"
2481+#include "live_effects/parameter/enum.h"
2482+#include "live_effects/lpe-embrodery-stitch-ordering.h"
2483+
2484+namespace Inkscape {
2485+namespace LivePathEffect {
2486+
2487+using namespace LPEEmbroderyStitchOrdering;
2488+
2489+class LPEEmbroderyStitch : public Effect {
2490+public:
2491+
2492+ LPEEmbroderyStitch(LivePathEffectObject *lpeobject);
2493+ virtual ~LPEEmbroderyStitch();
2494+
2495+ virtual Geom::PathVector doEffect_path(Geom::PathVector const &path_in);
2496+
2497+ virtual void resetDefaults(SPItem const *item);
2498+
2499+ virtual void transform_multiply(Geom::Affine const &postmul, bool set);
2500+
2501+ enum order_method {
2502+ order_method_no_reorder,
2503+ order_method_zigzag,
2504+ order_method_zigzag_rev_first,
2505+ order_method_closest,
2506+ order_method_closest_rev_first,
2507+ order_method_tsp_kopt_2,
2508+ order_method_tsp_kopt_3,
2509+ order_method_tsp_kopt_4,
2510+ order_method_tsp_kopt_5,
2511+ order_method_count
2512+ };
2513+ enum connect_method {
2514+ connect_method_line,
2515+ connect_method_move_point_from,
2516+ connect_method_move_point_mid,
2517+ connect_method_move_point_to,
2518+ connect_method_count
2519+ };
2520+
2521+private:
2522+ EnumParam<order_method> ordering;
2523+ EnumParam<connect_method> connection;
2524+ ScalarParam stitch_length;
2525+ ScalarParam stitch_min_length;
2526+ ScalarParam stitch_pattern;
2527+ BoolParam show_stitches;
2528+ ScalarParam show_stitch_gap;
2529+ ScalarParam jump_if_longer;
2530+
2531+ LPEEmbroderyStitch(const LPEEmbroderyStitch &);
2532+ LPEEmbroderyStitch &operator=(const LPEEmbroderyStitch &);
2533+
2534+ double GetPatternInitialStep(int pattern, int line);
2535+ Geom::Point GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i);
2536+ Geom::Point GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i);
2537+ Geom::Point GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i);
2538+ Geom::Point GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i);
2539+};
2540+
2541+} //namespace LivePathEffect
2542+} //namespace Inkscape
2543+
2544+#endif