Inkscape

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

embroidery
Merge into 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
Related bugs:	Link a bug report

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.

Revision history for this message

Jabiertxof (jabiertxof) wrote on 2017-06-05:

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

Revision history for this message

Michael Soegtrop (msoegtrop) wrote on 2017-06-05:

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

Dear Jabier,

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

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-embrodery-stitch-ordering.cpp	1970-01-01 00:00:00 +0000
>> +++ src/live_effects/lpe-embrodery-stitch-ordering.cpp	2017-06-05 14:13:17 +0000
>> @@ -0,0 +1,1139 @@
>> +/*
>> + * Sub-path Ordering functions for embroidery stitch LPE (Implementation)
>> + *
>> + * Copyright (C) 2016 Michael Soegtrop
>> + *
>> + * Released under GNU GPL, read the file 'COPYING' for more information
>> + */
>> +
>> +#include "live_effects/lpe-embrodery-stitch-ordering.h"
>> +
>> +#include <numeric>
>> +
>> +namespace Inkscape {
>> +namespace LivePathEffect {
>> +namespace LPEEmbroderyStitchOrdering {
> Is necasary the LPEEmbroderyStitchOrdering namespace? I recall a conversation about dont want a deeper namespace structure in general.
>
>> +
>> +using namespace Geom;
>> +
>> +// ==================== Debug Trace Macros ====================
>> +
>> +// ATTENTION: both level and area macros must be enabled for tracing
>> +
>> +// These macros are for enabling certain levels of tracing
>> +#define DebugTrace1(list) // g_warning list
>> +#define DebugTrace2(list) // g_warning list
>> +
>> +// These macros are for enabling certain areas of tracing
>> +#define DebugTraceGrouping(list) // list
>> +#define DebugTraceTSP(list)      // list
>> +
>> +// Combinations of above
>> +#define DebugTrace1TSP(list) DebugTraceTSP( DebugTrace1(list) )
>> +#define DebugTrace2TSP(list) DebugTraceTSP( DebugTrace2(list) )
>> +
>> +// ==================== Template Utilities ====================
>> +
>> +// Delete all objects pointed to by a vector and clear the vector
>> +
>> +template< typename T > void delete_and_clear(std::vector<T> &vector)
>> +{
>> +    for (typename std::vector<T>::iterator it = vector.begin(); it != vector.end(); ++it) {
>> +        delete *it;
>> +    }
>> +    vector.clear();
>> +}
>> +
>> +// Assert that there are no duplicates in a vector
>> +
>> +template< typename T > void assert_unique(std::vector<T> &vector)
>> +{
>> +    typename std::vector<T> copy = vector;
>> +    std::sort(copy.begin(), copy.end());
>> +    assert(std::unique(copy.begin(), copy.end()) == copy.end());
>> +}
>> +
>> +// remove element(s) by value
>> +
>> +template< typename T > void remove_by_value(std::vector<T> *vector, const T &value)
>> +{
>> +    vector->erase(std::remove(vector->begin(), vector->end(), value), vector->end());
>> +}
>> +
>> +// fill a vector with increasing elements (similar to C++11 iota)
>> +// iota is included in some C++ libraries, not in other (it is always included for C++11)
>> +// To avoid issues, use our own name (not iota)
>> +
>> +template<class OutputIterator, class Counter>
>> +void fill_increasing(OutputIterator begin, OutputIterator end, Counter counter)
>> +{
>> +    while (begin != end) {
>> +        *begin++ = counter++;
>> +    }
>> +}
>> +
>> +// check if an iteratable sequence contains an element
>> +
>> +template<class InputIterator, class Element>
>> +bool contains(InputIterator begin, InputIterator end, const Element &elem)
>> +{
>> +    while (begin != end) {
>> +        if (*begin == elem) {
>> +            return true;
>> +        }
>> +        ++begin;
>> +    }
>> +    return false;
>> +}
>> +
>> +// Check if a vector contains an element
>> +
>> +template<class Element>
>> +bool contains(std::vector<Element> const &vector, const Element &elem)
>> +{
>> +    return contains(vector.begin(), vector.end(), elem);
>> +}
>> +
> cool utilities!!!
>
>> +// ==================== Multi-dimensional iterator functions ====================
>> +
>> +// Below are 3 simple template functions to do triangle/pyramid iteration (without diagonal).
>> +// Here is a sample of iterating over 5 elements in 3 dimensions:
>> +//
>> +// 0 1 2
>> +// 0 1 3
>> +// 0 1 4
>> +// 0 2 3
>> +// 0 2 4
>> +// 1 2 4
>> +// 1 3 4
>> +// 2 3 4
>> +// end end end
>> +//
>> +// If the number of elements is less then the number of dimensions, the number of dimensions is reduced automatically.
>> +//
>> +// I thought about creating an iterator class for this, but it doesn't match that well, so I used functions on iterator vectors.
>> +
>> +// Initialize a vector of iterators
>> +
>> +template<class Iterator>
>> +void triangleit_begin(std::vector<Iterator> &iterators, Iterator const &begin, Iterator const &end, size_t n)
>> +{
>> +    iterators.clear();
>> +    // limit number of dimensions to number of elements
>> +    size_t n1 = end - begin;
>> +    n = std::min(n, n1);
>> +    if (n) {
>> +        iterators.push_back(begin);
>> +        for (int i = 1; i < n; i++) {
>> +            iterators.push_back(iterators.back() + 1);
>> +        }
>> +    }
>> +}
>> +
>> +// Increment a vector of iterators
>> +
>> +template<class Iterator>
>> +void triangleit_incr(std::vector<Iterator> &iterators, Iterator const &end)
>> +{
>> +    size_t n = iterators.size();
>> +
>> +    for (int i = 0; i < n; i++) {
>> +        iterators[n - 1 - i]++;
>> +        // Each dimension ends at end-i, so that there are elements left for the i higher dimensions
>> +        if (iterators[n - 1 - i] != end - i) {
>> +            // Assign increasing numbers to the higher dimension
>> +            for (int j = n - i; j < n; j++) {
>> +                iterators[j] = iterators[j - 1] + 1;
>> +            }
>> +            return;
>> +        }
>> +    }
>> +}
>> +
>> +// Check if a vector of iterators is at the end
>> +
>> +template<class Iterator>
>> +bool triangleit_test(std::vector<Iterator> &iterators, Iterator const &end)
>> +{
>> +    if (iterators.empty()) {
>> +        return false;
>> +    } else {
>> +        return iterators.back() != end;
>> +    }
>> +}
>> +
>> +// ==================== Trivial Ordering Functions ====================
>> +
>> +// Sub-path reordering: do nothing - keep original order
>> +
>> +void OrderingOriginal(std::vector<OrderingInfo> &infos)
>> +{
>> +}
>> +
>> +// Sub-path reordering: reverse every other sub path
>> +
>> +void OrderingZigZag(std::vector<OrderingInfo> &infos, bool revfirst)
>> +{
>> +    for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
>> +        it->reverse = (it->index & 1) == (revfirst ? 0 : 1);
>> +    }
>> +}
>> +
>> +// Sub-path reordering: continue with the neartest start or end point of yet unused sub paths
>> +
>> +void OrderingClosest(std::vector<OrderingInfo> &infos, bool revfirst)
>> +{
>> +    std::vector<OrderingInfo> result;
>> +    result.reserve(infos.size());
>> +
>> +    result.push_back(infos[0]);
>> +    result.back().reverse = revfirst;
>> +    Point p = result.back().GetEndRev();
>> +
>> +    infos[0].used = true;
>> +
>> +
>> +    for (unsigned int iRnd = 1; iRnd < infos.size(); iRnd++) {
>> +        // find closest point to p
>> +        unsigned iBest = 0;
>> +        bool revBest = false;
>> +        Coord distBest = infinity();
>> +
>> +        for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
>> +            it->index = it - infos.begin();
>> +            it->reverse = (it->index & 1) != 0;
>> +
>> +            if (!it->used) {
>> +                Coord dist = distance(p, it->GetBegOrig());
>> +                if (dist < distBest) {
>> +                    distBest = dist;
>> +                    iBest = it - infos.begin();
>> +                    revBest = false;
>> +                }
>> +
>> +                dist = distance(p, it->GetEndOrig());
>> +                if (dist < distBest) {
>> +                    distBest = dist;
>> +                    iBest = it - infos.begin();
>> +                    revBest = true;
>> +                }
>> +            }
>> +        }
>> +
>> +        result.push_back(infos[iBest]);
>> +        result.back().reverse = revBest;
>> +        p = result.back().GetEndRev();
>> +        infos[iBest].used = true;
>> +    }
>> +
>> +    infos = result;
>> +}
>> +
>> +// ==================== Traveling Salesman k-opt Ordering Function and Utilities ====================
>> +
>> +// A Few notes on this:
>> +// - This is a relatively simple Lin-type k-opt algorithm, but the grouping optimizations done make it already quite complex.
>> +// - The main Ordering Function is OrderingAdvanced
>> +// - Lines which start at the end of another line are connected and treated as one (struct OrderingInfoEx)
>> +// - Groups of zig-zag OrderingInfoEx are grouped (struct OrderingGroup) if both ends of the segment mutually agree with a next neighbor.
>> +//   These groups are treated as a unit in the TSP algorithm.
>> +//   The only option is to reverse the first segment, so that a group has 4 end points, 2 of which are used externally.
>> +// - Run a k-opt (k=2..5) Lin like Traveling Salesman Problem algorithm on the groups as a unit and the remaining edges.
>> +//   See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Iterative_improvement
>> +//   The algorithm uses a greedy nearest neighbor as start configuration and does not use repeated random starts.
>> +// - The algorithm searches an open tour (rather than a closed one), so the longest segment in the closed path is ignored.
>> +// - TODO: it might be faster to use k=3 with a few random starting patterns instead of k=5
>> +// - TODO: it is surely wiser to implement e.g. Lin-Kenrighan TSP, but the simple k-opt works ok.
>> +// - TODO(EASY): add a jump distance, above which threads are removed and make the length of this jump distance constant and large,
>> +//   so that mostly the number of jumps is optimized
>> +
>> +// Find 2 nearest points to given point
>> +
>> +void OrderingPoint::FindNearest2(const std::vector<OrderingInfoEx *> &infos)
>> +{
>> +    // This implementation is not terribly elegant (unSTLish).
>> +    // But for the first 2 elements using e.g. partial_sort is not simpler.
>> +
>> +    Coord dist0 = infinity();
>> +    Coord dist1 = infinity();
>> +    nearest[0] = 0;
>> +    nearest[1] = 0;
>> +
>> +    for (std::vector<OrderingInfoEx *>::const_iterator it = infos.begin(); it != infos.end(); ++it) {
>> +        Coord dist = distance(point, (*it)->beg.point);
>> +        if (dist < dist1) {
>> +            if (&(*it)->beg != this && &(*it)->end != this) {
>> +                if (dist < dist0) {
>> +                    nearest[1] = nearest[0];
>> +                    nearest[0] = &(*it)->beg;
>> +                    dist1 = dist0;
>> +                    dist0 = dist;
>> +                } else {
>> +                    nearest[1] = &(*it)->beg;
>> +                    dist1 = dist;
>> +                }
>> +            }
>> +        }
>> +
>> +        dist = distance(point, (*it)->end.point);
>> +        if (dist < dist1) {
>> +            if (&(*it)->beg != this && &(*it)->end != this) {
>> +                if (dist < dist0) {
>> +                    nearest[1] = nearest[0];
>> +                    nearest[0] = &(*it)->end;
>> +                    dist1 = dist0;
>> +                    dist0 = dist;
>> +                } else {
>> +                    nearest[1] = &(*it)->end;
>> +                    dist1 = dist;
>> +                }
>> +            }
>> +        }
>> +    }
>> +}
>> +
>> +// Check if "this" is among the nearest of its nearest
>> +
>> +void OrderingPoint::EnforceMutual(void)
>> +{
>> +    if (nearest[0] && !(this == nearest[0]->nearest[0] || this == nearest[0]->nearest[1])) {
>> +        nearest[0] = 0;
>> +    }
>> +
>> +    if (nearest[1] && !(this == nearest[1]->nearest[0] || this == nearest[1]->nearest[1])) {
>> +        nearest[1] = 0;
>> +    }
>> +
>> +    if (nearest[1] && !nearest[0]) {
>> +        nearest[0] = nearest[1];
>> +        nearest[1] = 0;
>> +    }
>> +}
>> +
>> +// Check if the subpath indices of this and other are the same, otherwise zero both nearest
>> +
>> +void OrderingPoint::EnforceSymmetric(const OrderingPoint &other)
>> +{
>> +    if (nearest[0] && !(
>> +                (other.nearest[0] && nearest[0]->infoex == other.nearest[0]->infoex) ||
>> +                (other.nearest[1] && nearest[0]->infoex == other.nearest[1]->infoex)
>> +            )) {
>> +        nearest[0] = 0;
>> +    }
>> +
>> +    if (nearest[1] && !(
>> +                (other.nearest[0] && nearest[1]->infoex == other.nearest[0]->infoex) ||
>> +                (other.nearest[1] && nearest[1]->infoex == other.nearest[1]->infoex)
>> +            )) {
>> +        nearest[1] = 0;
>> +    }
>> +
>> +    if (nearest[1] && !nearest[0]) {
>> +        nearest[0] = nearest[1];
>> +        nearest[1] = 0;
>> +    }
>> +}
>> +
>> +void OrderingPoint::Dump(void)
>> +{
>> +    Coord dist0 = nearest[0] ? distance(point, nearest[0]->point) : -1.0;
>> +    Coord dist1 = nearest[1] ? distance(point, nearest[1]->point) : -1.0;
>> +    int idx0 = nearest[0] ? nearest[0]->infoex->idx : -1;
>> +    int idx1 = nearest[1] ? nearest[1]->infoex->idx : -1;
>> +    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));
>> +}
>> +
>> +
>> +// If this element can be grouped (has neighbours) but is not yet grouped, create a new group
>> +
>> +void OrderingInfoEx::MakeGroup(std::vector<OrderingInfoEx *> &infos, std::vector<OrderingGroup *> *groups)
>> +{
>> +    if (grouped || !beg.HasNearest() || !end.HasNearest()) {
>> +        return;
>> +    }
>> +
>> +    groups->push_back(new OrderingGroup(groups->size()));
>> +
>> +    // Add neighbors recursively
>> +    AddToGroup(infos, groups->back());
>> +}
>> +
>> +// Add this and all connected elements to the group
>> +
>> +void OrderingInfoEx::AddToGroup(std::vector<OrderingInfoEx *> &infos, OrderingGroup *group)
>> +{
>> +    if (grouped || !beg.HasNearest() || !end.HasNearest()) {
>> +        return;
>> +    }
>> +
>> +    group->items.push_back(this);
>> +    grouped = true;
>> +    // Note: beg and end neighbors have been checked to be symmetric
>> +    if (beg.nearest[0]) {
>> +        beg.nearest[0]->infoex->AddToGroup(infos, group);
>> +    }
>> +    if (beg.nearest[1]) {
>> +        beg.nearest[1]->infoex->AddToGroup(infos, group);
>> +    }
>> +    if (end.nearest[0]) {
>> +        end.nearest[0]->infoex->AddToGroup(infos, group);
>> +    }
>> +    if (end.nearest[1]) {
>> +        end.nearest[1]->infoex->AddToGroup(infos, group);
>> +    }
>> +}
>> +
>> +// Constructor
>> +
>> +OrderingGroupNeighbor::OrderingGroupNeighbor(OrderingGroupPoint *me, OrderingGroupPoint *other) :
>> +    point(other),
>> +    distance(Geom::distance(me->point, other->point))
>> +{
>> +}
>> +
>> +// Comparison function for sorting by distance
>> +
>> +bool OrderingGroupNeighbor::Compare(const OrderingGroupNeighbor &a, const OrderingGroupNeighbor &b)
>> +{
>> +    return a.distance < b.distance;
>> +}
>> +
>> +// Find the nearest unused neighbor point
>> +
>> +OrderingGroupNeighbor *OrderingGroupPoint::FindNearestUnused(void)
>> +{
>> +    for (std::vector<OrderingGroupNeighbor>::iterator it = nearest.begin(); it != nearest.end(); ++it) {
>> +        if (!it->point->used) {
>> +            DebugTrace1TSP(("Nearest: group %d, size %d, point %d, nghb %d, xFrom %.4lf, yFrom %.4lf, xTo %.4lf, yTo %.4lf, dist %.4lf",
>> +                            it->point->group->index, it->point->group->items.size(), it->point->indexInGroup, it - nearest.begin(),
>> +                            point.x(), 297 - point.y(),
>> +                            it->point->point.x(), 297 - it->point->point.y(),
>> +                            it->distance));
>> +            return &*it;
>> +        }
>> +    }
>> +
>> +    // it shouldn't happen that we can't find any point at all
>> +    assert(0);
>> +    return 0;
>> +}
>> +
>> +// Return the other end in the group of the point
>> +
>> +OrderingGroupPoint *OrderingGroupPoint::GetOtherEndGroup(void)
>> +{
>> +    return group->endpoints[ indexInGroup ^ 1 ];
>> +}
>> +
>> +// Return the alternate point (if one exists), 0 otherwise
>> +
>> +OrderingGroupPoint *OrderingGroupPoint::GetAltPointGroup(void)
>> +{
>> +    if (group->nEndPoints < 4) {
>> +        return 0;
>> +    }
>> +
>> +    OrderingGroupPoint *alt = group->endpoints[ indexInGroup ^ 2 ];
>> +    return alt->used ? 0 : alt;
>> +}
>> +
>> +
>> +// Sets the rev flags in the group assuming that the group starts with this point
>> +
>> +void OrderingGroupPoint::SetRevInGroup(void)
>> +{
>> +    // If this is not a front point, the item list needs to be reversed
>> +    group->revItemList = !front;
>> +
>> +    // If this is not a begin point, the items need to be reversed
>> +    group->revItems = !begin;
>> +}
>> +
>> +// Mark an end point as used and also mark the two other alternating points as used
>> +// Returns the used point
>> +
>> +void OrderingGroupPoint::UsePoint(void)
>> +{
>> +    group->UsePoint(indexInGroup);
>> +}
>> +
>> +// Mark an end point as unused and possibly also mark the two other alternating points as unused
>> +// Returns the used point
>> +
>> +void OrderingGroupPoint::UnusePoint(void)
>> +{
>> +    group->UnusePoint(indexInGroup);
>> +}
>> +
>> +// Return the other end in the connection
>> +OrderingGroupPoint *OrderingGroupPoint::GetOtherEndConnection(void)
>> +{
>> +    assert(connection);
>> +    assert(connection->points[ indexInConnection ] == this);
>> +    assert(connection->points[ indexInConnection ^ 1 ]);
>> +
>> +    return connection->points[ indexInConnection ^ 1 ];
>> +}
>> +
>> +
>> +// Set the end points of a group from the items
>> +
>> +void OrderingGroup::SetEndpoints(void)
>> +{
>> +    assert(items.size() >= 1);
>> +
>> +    if (items.size() == 1) {
>> +        // A simple line:
>> +        //
>> +        // b0-front--e1
>> +
>> +        nEndPoints = 2;
>> +        endpoints[0] = new OrderingGroupPoint(items.front()->beg.point, this, 0, true,  true);
>> +        endpoints[1] = new OrderingGroupPoint(items.front()->end.point, this, 1, false, true);
>> +    } else {
>> +        // If the number of elements is even, the group is
>> +        // either from items.front().beg to items.back().beg
>> +        // or from     items.front().end to items.back().end:
>> +        // Below: b=beg, e=end, numbers are end point indices
>> +        //
>> +        // b0-front--e     b0-front--e2
>> +        //           |     |
>> +        // b---------e     b---------e
>> +        // |                         |
>> +        // b---------e     b---------e
>> +        //           |     |
>> +        // b1-back---e     b1-back---e3
>> +        //
>> +        //
>> +        // if the number of elements is odd, it is crossed:
>> +        //
>> +        // b0-front--e     b--front--e2
>> +        //           |     |
>> +        // b---------e     b---------e
>> +        // |                         |
>> +        // b--back---e1    b3-back---e
>> +        //
>> +        // TODO: this is not true with the following kind of pattern
>> +        //
>> +        // b--front--e
>> +        // b---------e
>> +        //           b--------e
>> +        //           b--back--e
>> +        //
>> +        // Here only one connection is possible, from front.end to back.beg
>> +        //
>> +        // TODO: also this is not true if segment direction is alternating
>> +        //
>> +        // TOTO: => Just see where you end up from front().begin and front().end
>> +        //
>> +        // the numbering is such that either end points 0 and 1 are used or 2 and 3.
>> +        int cross = items.size() & 1 ? 2 : 0;
>> +        nEndPoints = 4;
>> +
>> +        endpoints[0      ] = new OrderingGroupPoint(items.front()->beg.point, this, 0,       true,  true);
>> +        endpoints[1 ^ cross] = new OrderingGroupPoint(items.back() ->beg.point, this, 1 ^ cross, true,  false);
>> +        endpoints[2      ] = new OrderingGroupPoint(items.front()->end.point, this, 2,       false, true);
>> +        endpoints[3 ^ cross] = new OrderingGroupPoint(items.back() ->end.point, this, 3 ^ cross, false, false);
>> +    }
>> +}
>> +
>> +// Add all points from another group as neighbors
>> +
>> +void OrderingGroup::AddNeighbors(OrderingGroup *nghb)
>> +{
>> +    for (int iThis = 0; iThis < nEndPoints; iThis++) {
>> +        for (int iNghb = 0; iNghb < nghb->nEndPoints; iNghb++) {
>> +            endpoints[iThis]->nearest.push_back(OrderingGroupNeighbor(endpoints[iThis], nghb->endpoints[iNghb]));
>> +        }
>> +    }
>> +}
>> +
>> +// Mark an end point as used and also mark the two other alternating points as used
>> +// Returns the used point
>> +
>> +OrderingGroupPoint *OrderingGroup::UsePoint(int index)
>> +{
>> +    assert(index < nEndPoints);
>> +    assert(!endpoints[index]->used);
>> +    endpoints[index]->used = true;
>> +    if (nEndPoints == 4) {
>> +        int offs = index < 2 ? 2 : 0;
>> +        endpoints[0 + offs]->used = true;
>> +        endpoints[1 + offs]->used = true;
>> +    }
>> +
>> +    return endpoints[index];
>> +}
>> +
>> +// Mark an end point as unused and possibly also mark the two other alternating points as unused
>> +// Returns the used point
>> +
>> +void OrderingGroup::UnusePoint(int index)
>> +{
>> +    assert(index < nEndPoints);
>> +    assert(endpoints[index]->used);
>> +    endpoints[index]->used = false;
>> +
>> +    if (nEndPoints == 4 && !endpoints[index ^ 1]->used) {
>> +        int offs = index < 2 ? 2 : 0;
>> +        endpoints[0 + offs]->used = false;
>> +        endpoints[1 + offs]->used = false;
>> +    }
>> +}
>> +
>> +// Add an end point
>> +void OrderingSegment::AddPoint(OrderingGroupPoint *point)
>> +{
>> +    assert(point);
>> +    assert(nEndPoints < 4);
>> +    endpoints[ nEndPoints++ ] = point;
>> +
>> +    // If both ends of a group are added and the group has 4 points, add the other two as well
>> +    if (nEndPoints == 2 && endpoints[0]->group == endpoints[1]->group) {
>> +        OrderingGroup *group = endpoints[0]->group;
>> +        if (group->nEndPoints == 4) {
>> +            for (int i = 0; i < 4; i++) {
>> +                endpoints[i] = group->endpoints[i];
>> +            }
>> +            nEndPoints = 4;
>> +        }
>> +    }
>> +}
>> +
>> +// Get begin point (taking swap and end bit into account
>> +OrderingGroupPoint *OrderingSegment::GetBeginPoint(unsigned int iSwap, unsigned int iEnd)
>> +{
>> +    int iPoint = ((iEnd >> endbit) & 1) + (((iSwap >> swapbit) & 1) << 1);
>> +    assert(iPoint < nEndPoints);
>> +    return endpoints[iPoint];
>> +}
>> +
>> +// Get end point (taking swap and end bit into account
>> +OrderingGroupPoint *OrderingSegment::GetEndPoint(unsigned int iSwap, unsigned int iEnd)
>> +{
>> +    int iPoint = (((iEnd >> endbit) & 1) ^ 1) + (((iSwap >> swapbit) & 1) << 1);
>> +    assert(iPoint < nEndPoints);
>> +    return endpoints[iPoint];
>> +}
>> +
>> +
>> +// Find the next unused point in list
>> +std::vector<OrderingGroupPoint *>::iterator FindUnusedAndUse(std::vector<OrderingGroupPoint *> *unusedPoints, std::vector<OrderingGroupPoint *>::iterator const from)
>> +{
>> +    for (std::vector<OrderingGroupPoint *>::iterator it = from; it != unusedPoints->end(); ++it) {
>> +        if (!(*it)->used) {
>> +            (*it)->UsePoint();
>> +            return it;
>> +        }
>> +    }
>> +    return unusedPoints->end();
>> +}
>> +
>> +// Find the shortest reconnect between the given points
>> +
>> +bool FindShortestReconnect(std::vector<OrderingSegment> &segments, std::vector<OrderingGroupConnection *> &connections, std::vector<OrderingGroupConnection *> &allconnections, OrderingGroupConnection **longestConnect, Coord *total, Coord olddist)
>> +{
>> +    // Find the longest connection outside of the active set
>> +    // The longest segment is then the longest of this longest outside segment and all inside segments
>> +    OrderingGroupConnection *longestOutside = 0;
>> +
>> +    if (contains(connections, *longestConnect)) {
>> +        // The longest connection is inside the active set, so we need to search for the longest outside
>> +        Coord length = 0.0;
>> +        for (std::vector<OrderingGroupConnection *>::iterator it = allconnections.begin(); it != allconnections.end(); it++) {
>> +            if ((*it)->Distance() > length) {
>> +                if (!contains(connections, *it)) {
>> +                    longestOutside = *it;
>> +                    length = (*it)->Distance();
>> +                }
>> +            }
>> +        }
>> +    } else {
>> +        longestOutside = *longestConnect;
>> +    }
>> +
>> +    // length of longestConnect outside
>> +    Coord longestOutsideLength = longestOutside ? longestOutside->Distance() : 0.0;
>> +
>> +    // We measure length without the longest, so subtract the longest length from the old distance
>> +    olddist -= (*longestConnect)->Distance();
>> +
>> +    // Assign a swap bit and end bit to each active connection
>> +    int nEndBits = 0;
>> +    int nSwapBits = 0;
>> +    for (std::vector<OrderingSegment>::iterator it = segments.begin(); it != segments.end(); it++) {
>> +        it->endbit = nEndBits++;
>> +        if (it->nEndPoints == 4) {
>> +            it->swapbit = nSwapBits++;
>> +        } else {
>> +            // bit 32 should always be 0
>> +            it->swapbit = 31;
>> +        }
>> +    }
>> +
>> +    unsigned int swapMask = (1U << nSwapBits) - 1;
>> +    unsigned int endMask = (1U << nEndBits) - 1;
>> +
>> +    // Create a permutation vector
>> +    std::vector<int> permutation(segments.size());
>> +    fill_increasing(permutation.begin(), permutation.end(), 0);
>> +
>> +    // best improvement
>> +    bool improved = false;
>> +    Coord distBest = olddist;
>> +    std::vector<int> permutationBest;
>> +    unsigned int iSwapBest;
>> +    unsigned int iEndBest;
>> +    int nTrials = 0;
>> +
>> +    // Loop over the permutations
>> +    do {
>> +        // Loop over the swap bits
>> +        unsigned int iSwap = 0;
>> +        do {
>> +            // Loop over the end bits
>> +            unsigned int iEnd = 0;
>> +            do {
>> +                // Length of all active connections
>> +                Coord lengthTotal = 0;
>> +                // Length of longest connection (active or inactive)
>> +                Coord lengthLongest = longestOutsideLength;
>> +
>> +                // Close the loop with the end point of the last segment
>> +                OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
>> +                for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
>> +                    OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
>> +                    Coord length = Geom::distance(thisbeg->point, prevend->point);
>> +                    lengthTotal += length;
>> +                    if (length > lengthLongest) {
>> +                        lengthLongest = length;
>> +                    }
>> +                    prevend = segments[*it].GetEndPoint(iSwap, iEnd);
>> +                }
>> +                lengthTotal -= lengthLongest;
>> +
>> +                // If there is an improvement, remember the best selection
>> +                if (lengthTotal + 1e-6 < distBest) {
>> +                    improved = true;
>> +                    distBest = lengthTotal;
>> +                    permutationBest = permutation;
>> +                    iSwapBest = iSwap;
>> +                    iEndBest = iEnd;
>> +
>> +                    // Just debug printing
>> +                    OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
>> +                    for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
>> +                        OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
>> +                        DebugTrace2TSP(("IMP 0F=%d %d %.6lf", thisbeg->group->index, thisbeg->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
>> +                        DebugTrace2TSP(("IMP 0T=%d %d %.6lf", prevend->group->index, prevend->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
>> +                        prevend = segments[*it].GetEndPoint(iSwap, iEnd);
>> +                    }
>> +                }
>> +
>> +                nTrials++;
>> +
>> +                // bit 0 is always 0, because the first segment is kept fixed
>> +                iEnd += 2;
>> +            } while (iEnd & endMask);
>> +            iSwap++;
>> +        } while (iSwap & swapMask);
>> +        // first segment is kept fixed
>> +    } while (std::next_permutation(permutation.begin() + 1, permutation.end()));
>> +
>> +    if (improved) {
>> +        DebugTrace2TSP(("Improvement %lf->%lf in %d", olddist, distBest, nTrials));
>> +        // change the connections
>> +
>> +        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
>> +            DebugTrace2TSP(("WAS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
>> +            DebugTrace2TSP(("WAS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
>> +        }
>> +        DebugTrace2TSP(("OLDDIST %.6lf delta %.6lf", olddist, olddist - (*longestConnect)->Distance()));
>> +        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
>> +        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
>> +
>> +        int perm = permutationBest.back();
>> +
>> +        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
>> +            (*it)->Connect(1, segments[ perm ].GetEndPoint(iSwapBest, iEndBest));
>> +            perm = permutationBest[ it - connections.begin() ];
>> +            (*it)->Connect(0, segments[ perm ].GetBeginPoint(iSwapBest, iEndBest));
>> +
>> +        }
>> +
>> +        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
>> +            DebugTrace2TSP(("IS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
>> +            DebugTrace2TSP(("IS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
>> +        }
>> +
>> +        (*longestConnect) = longestOutside;
>> +        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
>> +            if ((*it)->Distance() > (*longestConnect)->Distance()) {
>> +                *longestConnect = *it;
>> +            }
>> +        }
>> +        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
>> +        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
>> +    }
>> +
>> +    return improved;
>> +}
>> +
>> +// Check if connections form a tour
>> +void AssertIsTour(std::vector<OrderingGroup *> &groups, std::vector<OrderingGroupConnection *> &connections, OrderingGroupConnection *longestConnection)
>> +{
>> +    for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); it++) {
>> +        for (int i = 0; i < 2; i++) {
>> +            OrderingGroupPoint *pnt = (*it)->points[i];
>> +            assert(pnt->connection == *it);
>> +            assert(pnt->connection->points[pnt->indexInConnection] == pnt);
>> +            assert(pnt->group->endpoints[pnt->indexInGroup] == pnt);
>> +        }
>> +    }
>> +
>> +    Coord length1 = 0;
>> +    Coord longest1 = 0;
>> +    OrderingGroupPoint *current = connections.front()->points[0];
>> +
>> +    for (unsigned int n = 0; n < connections.size(); n++) {
>> +        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()));
>> +        Coord length = current->connection->Distance();
>> +        length1 += length;
>> +        longest1 = std::max(length, longest1);
>> +        current = current->GetOtherEndConnection();
>> +
>> +        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()));
>> +        current = current->GetOtherEndGroup();
>> +    }
>> +    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]));
>> +    assert(current == connections.front()->points[0]);
>> +
>> +    // The other direction
>> +    Coord length2 = 0;
>> +    Coord longest2 = 0;
>> +    current = connections.front()->points[0];
>> +    for (unsigned int n = 0; n < connections.size(); n++) {
>> +        current = current->GetOtherEndGroup();
>> +        Coord length = current->connection->Distance();
>> +        length2 += length;
>> +        longest2 = std::max(length, longest2);
>> +        current = current->GetOtherEndConnection();
>> +    }
>> +    assert(current == connections.front()->points[0]);
>> +
>> +    DebugTrace1TSP(("Tour length %.6lf(%.6lf) longest %.6lf(%.6lf) remaining %.6lf(%.6lf)", length1, length2, longest1, longest2, length1 - longest1, length2 - longest2));
>> +}
>> +
>> +// Bring a tour into linear order after a modification
>> +
>> +/* I would like to avoid this.
>> + * It is no problem to travel a tour with changing directions using the GetOtherEnd functions,
>> + * 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.
>> + * In the end it is probably better to implement the Lin-Kernighan algorithm which avoids this problem by creating connected changes.  */
>> +
>> +void LinearizeTour(std::vector<OrderingGroupConnection *> &connections)
>> +{
>> +    OrderingGroupPoint *current = connections.front()->points[0];
>> +
>> +    for (unsigned int iNew = 0; iNew < connections.size(); iNew++) {
>> +        // swap the connection at location n with the current connection
>> +        OrderingGroupConnection *connection = current->connection;
>> +        unsigned int iOld = connection->index;
>> +        assert(connections[iOld] == connection);
>> +
>> +        connections[iOld] = connections[iNew];
>> +        connections[iNew] = connection;
>> +        connections[iOld]->index = iOld;
>> +        connections[iNew]->index = iNew;
>> +
>> +        // swap the points of a connection
>> +        assert(current == connection->points[0] || current == connection->points[1]);
>> +        if (current != connection->points[0]) {
>> +            connection->points[1] = connection->points[0];
>> +            connection->points[0] = current;
>> +            connection->points[1]->indexInConnection = 1;
>> +            connection->points[0]->indexInConnection = 0;
>> +        }
>> +
>> +        current = current->GetOtherEndConnection();
>> +        current = current->GetOtherEndGroup();
>> +    }
>> +}
>> +
>> +// Use some Traveling Salesman Problem (TSP) like heuristics to bring several groups into a
>> +// order with as short as possible interconnection paths
>> +
>> +void OrderGroups(std::vector<OrderingGroup *> *groups, const int nDims)
>> +{
>> +    // There is no point in ordering just one group
>> +    if (groups->size() <= 1) {
>> +        return;
>> +    }
>> +
>> +    // Initialize the endpoints for all groups
>> +    for (std::vector<OrderingGroup *>::iterator it = groups->begin(); it != groups->end(); ++it) {
>> +        (*it)->SetEndpoints();
>> +    }
>> +
>> +    // Find the neighboring points for all end points of all groups and sort by distance
>> +    for (std::vector<OrderingGroup *>::iterator itThis = groups->begin(); itThis != groups->end(); ++itThis) {
>> +        for (int i = 0; i < (*itThis)->nEndPoints; i++) {
>> +            // This can be up to 2x too large, but still better than incrementing the size
>> +            (*itThis)->endpoints[i]->nearest.reserve(4 * groups->size());
>> +        }
>> +
>> +        for (std::vector<OrderingGroup *>::iterator itNghb = groups->begin(); itNghb != groups->end(); ++itNghb) {
>> +            if (itThis != itNghb) {
>> +                (*itThis)->AddNeighbors(*itNghb);
>> +            }
>> +        }
>> +
>> +        for (int i = 0; i < (*itThis)->nEndPoints; i++) {
>> +            std::sort((*itThis)->endpoints[i]->nearest.begin(), (*itThis)->endpoints[i]->nearest.end(), OrderingGroupNeighbor::Compare);
>> +        }
>> +    }
>> +
>> +    // =========== Step 1: Create a simple nearest neighbor chain ===========
>> +
>> +    // Vector of connection points
>> +    std::vector<OrderingGroupConnection *> connections;
>> +    connections.reserve(groups->size());
>> +    // Total Jump Distance
>> +    Coord total = 0.0;
>> +
>> +    // Start with the first group and connect always with nearest unused point
>> +    OrderingGroupPoint *crnt = groups->front()->endpoints[0];
>> +
>> +    // The longest connection is ignored (we don't want cycles)
>> +    OrderingGroupConnection *longestConnect = 0;
>> +
>> +    for (unsigned int nConnected = 0; nConnected < groups->size(); nConnected++) {
>> +        // Mark both end points of the current segment as used
>> +        crnt->UsePoint();
>> +        crnt = crnt->GetOtherEndGroup();
>> +        crnt->UsePoint();
>> +
>> +        // if this is the last segment, Mark start point of first segment as unused,
>> +        // so that the end can connect to it
>> +        if (nConnected == groups->size() - 1) {
>> +            groups->front()->endpoints[0]->UnusePoint();
>> +        }
>> +
>> +        // connect to next segment
>> +        OrderingGroupNeighbor *nghb = crnt->FindNearestUnused();
>> +        connections.push_back(new OrderingGroupConnection(crnt, nghb->point, connections.size()));
>> +        total += nghb->distance;
>> +        crnt = nghb->point;
>> +
>> +        if (!longestConnect || nghb->distance > longestConnect->Distance()) {
>> +            longestConnect = connections.back();
>> +        }
>> +    }
>> +
>> +    DebugTrace1TSP(("Total jump distance %.3lf (closed)", total));
>> +    DebugTrace1TSP(("Total jump distance %.3lf (open)", total - longestConnect->Distance()));
>> +
>> +    AssertIsTour(*groups, connections, longestConnect);
>> +
>> +    // =========== Step 2: Choose nDims segments to clear and reconnect ===========
>> +
>> +    bool improvement;
>> +    int nRuns = 0;
>> +    int nTrials = 0;
>> +    int nImprovements = 0;
>> +
>> +    do {
>> +        improvement = false;
>> +        nRuns ++;
>> +        std::vector< std::vector<OrderingGroupConnection *>::iterator > iterators;
>> +
>> +        for (
>> +            triangleit_begin(iterators, connections.begin(), connections.end(), nDims);
>> +            triangleit_test(iterators, connections.end());
>> +            triangleit_incr(iterators, connections.end())
>> +        ) {
>> +            nTrials ++;
>> +
>> +            Coord dist = 0;
>> +
>> +            std::vector<OrderingSegment> segments(iterators.size());
>> +            std::vector<OrderingGroupConnection *> changedconnections;
>> +            changedconnections.reserve(3);
>> +            OrderingGroupConnection *prev = *iterators.back();
>> +
>> +
>> +            for (size_t i = 0; i < iterators.size(); i++) {
>> +                dist += (*iterators[i])->Distance();
>> +                segments[i].AddPoint(prev->points[1]);
>> +                segments[i].AddPoint((*iterators[i])->points[0]);
>> +                prev = *iterators[i];
>> +                changedconnections.push_back(*iterators[i]);
>> +            }
>> +
>> +            if (FindShortestReconnect(segments, changedconnections, connections, &longestConnect, &total, dist)) {
>> +                nImprovements ++;
>> +
>> +                AssertIsTour(*groups, connections, longestConnect);
>> +                LinearizeTour(connections);
>> +                AssertIsTour(*groups, connections, longestConnect);
>> +                improvement = true;
>> +            }
>> +        }
>> +    } while (improvement && nRuns < 10);
>> +
>> +    DebugTrace1TSP(("Finished after %d rounds, %d trials, %d improvements", nRuns, nTrials, nImprovements));
>> +
>> +    // =========== Step N: Create vector of groups from vector of connection points ===========
>> +
>> +    std::vector<OrderingGroup *> result;
>> +    result.reserve(groups->size());
>> +
>> +    // Go through the groups starting with the longest connection (which is this way left out)
>> +    {
>> +        OrderingGroupPoint *current = longestConnect->points[1];
>> +
>> +        for (unsigned int n = 0; n < connections.size(); n++) {
>> +            result.push_back(current->group);
>> +            current->SetRevInGroup();
>> +            current = current->GetOtherEndGroup();
>> +            current = current->GetOtherEndConnection();
>> +        }
>> +    }
>> +
>> +    assert(result.size() == groups->size());
>> +    assert_unique(result);
>> +
>> +    delete_and_clear(connections);
>> +
>> +    *groups = result;
>> +}
>> +
>> +// Global optimization of path length
>> +
>> +void OrderingAdvanced(std::vector<OrderingInfo> &infos, int nDims)
>> +{
>> +    if (infos.size() < 3) {
>> +        return;
>> +    }
>> +
>> +    // Create extended ordering info vector and copy data from normal ordering info
>> +    std::vector<OrderingInfoEx *> infoex;
>> +    infoex.reserve(infos.size());
>> +
>> +    for (std::vector<OrderingInfo>::const_iterator it = infos.begin(); it != infos.end();) {
>> +        // Note: This assumes that the index in the OrderingInfo matches the vector index!
>> +        infoex.push_back(new OrderingInfoEx(*it, infoex.size()));
>> +        ++it;
>> +        while (it != infos.end() && it->begOrig == infoex.back()->end.point) {
>> +            infoex.back()->end.point = it->endOrig;
>> +            infoex.back()->origIndices.push_back(it->index);
>> +            ++it;
>> +        }
>> +    }
>> +
>> +    // Find closest 2 points for each point and enforce that 2nd nearest is not further away than 1.8xthe nearest
>> +    // If this is not the case, clear nearest and 2nd nearest point
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +        (*it)->beg.FindNearest2(infoex);
>> +        (*it)->end.FindNearest2(infoex);
>> +    }
>> +
>> +    DebugTraceGrouping(
>> +        DebugTrace2(("STEP1"));
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +    (*it)->beg.Dump();
>> +        (*it)->end.Dump();
>> +    }
>> +    )
>> +
>> +    // Make sure the nearest points are mutual
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +        (*it)->beg.EnforceMutual();
>> +        (*it)->end.EnforceMutual();
>> +    }
>> +
>> +    DebugTraceGrouping(
>> +        DebugTrace2(("STEP2"));
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +    (*it)->beg.Dump();
>> +        (*it)->end.Dump();
>> +    }
>> +    )
>> +
>> +    // Make sure the nearest points for begin and end lead to the same sub-path (same index)
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +        (*it)->beg.EnforceSymmetric((*it)->end);
>> +        (*it)->end.EnforceSymmetric((*it)->beg);
>> +    }
>> +
>> +    DebugTraceGrouping(
>> +        DebugTrace2(("STEP3"));
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +    (*it)->beg.Dump();
>> +        (*it)->end.Dump();
>> +    }
>> +    )
>> +
>> +    // The remaining nearest neighbors should be 100% non ambiguous, so group them
>> +    std::vector<OrderingGroup *> groups;
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +        (*it)->MakeGroup(infoex, &groups);
>> +    }
>> +
>> +    // Create single groups for ungrouped lines
>> +    std::vector<OrderingInfo> result;
>> +    result.reserve(infos.size());
>> +    int nUngrouped = 0;
>> +    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
>> +        if (!(*it)->grouped) {
>> +            groups.push_back(new OrderingGroup(groups.size()));
>> +            groups.back()->items.push_back(*it);
>> +            nUngrouped++;
>> +        }
>> +    }
>> +
>> +    DebugTraceGrouping(
>> +        DebugTrace2(("Ungrouped lines = %d", nUngrouped));
>> +        DebugTrace2(("%d Groups found", groups.size()));
>> +    for (std::vector<OrderingGroup *>::iterator it = groups.begin(); it != groups.end(); ++it) {
>> +    DebugTrace2(("Group size %d", (*it)->items.size()));
>> +    }
>> +    )
>> +
>> +    // Order groups, so that the connection path gets shortest
>> +    OrderGroups(&groups, nDims);
>> +
>> +    // Copy grouped lines to output
>> +    for (std::vector<OrderingGroup *>::iterator itGroup = groups.begin(); itGroup != groups.end(); ++itGroup) {
>> +        for (unsigned int iItem = 0; iItem < (*itGroup)->items.size(); iItem++) {
>> +            unsigned int iItemRev = (*itGroup)->revItemList ? (*itGroup)->items.size() - 1 - iItem : iItem;
>> +            OrderingInfoEx *item = (*itGroup)->items[iItemRev];
>> +
>> +            // If revItems is false, even items shall have reverse=false
>> +            // In this case ( ( iItem & 1 ) == 0 )== true, revItems=false, (true==false) == false
>> +            bool reverse = ((iItem & 1) == 0) == (*itGroup)->revItems;
>> +            if (!reverse) {
>> +                for (std::vector<int>::iterator itOrig = item->origIndices.begin(); itOrig != item->origIndices.end(); ++itOrig) {
>> +                    result.push_back(infos[*itOrig]);
>> +                    result.back().reverse = false;
>> +                }
>> +            } else {
>> +                for (std::vector<int>::reverse_iterator itOrig = item->origIndices.rbegin(); itOrig != item->origIndices.rend(); ++itOrig) {
>> +                    result.push_back(infos[*itOrig]);
>> +                    result.back().reverse = true;
>> +                }
>> +            }
>> +        }
>> +        result.back().connect = true;
>> +    }
>> +
>> +
>> +    delete_and_clear(groups);
>> +    delete_and_clear(infoex);
>> +
>> +    infos = result;
>> +}
>> +
>> +} // namespace LPEEmbroderyStitchOrdering
>> +} // namespace LivePathEffect
>> +} // namespace Inkscape
>

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk

Subscribers

People subscribed via source and target branches

to all changes:

Abhinav Vishwa

Alex Valavanis

David Evans

Diederik van Lierop

Jabiertxof

Jon A. Cruz

Krzysztof Kosinski

Lord Delta

Michael Soegtrop

OCHi

Ryan Lerch

ScislaC

Shlikstr

Ted Gould

hermes ramirez

jazzynico

larscwallin

su_v

theAdib

uwesch

方鸿儒

to status/vote changes:

Aurium

UaHummer

 === modified file 'astylerc'
 --- astylerc	2013-09-01 23:39:00 +0000
 +++ astylerc	2017-06-05 19:01:49 +0000
@@ -1,8 +1,9 @@
  # Inkscape coding style options for the Artistic Style formatter
  # See http://astyle.sourceforge.net/
++# See https://inkscape.org/de/develop/coding-style/
  # Opening braces broken from functions only
----brackets=stroustrup
++--style=stroustrup
  # Four-space indent; convert stray tabs
  --indent=spaces=4
@@ -15,7 +16,7 @@
  # Attach pointers and references to variable names
  --align-pointer=name
--# --align-reference=name
++--align-reference=name
  # Add brackets to single-statement blocks
  --add-brackets
@@ -23,4 +24,4 @@
  # Misc. options
  --indent-preprocessor
  --indent-col1-comments
----suffix=none
++
 === modified file 'po/POTFILES.in'
 --- po/POTFILES.in	2017-05-08 01:43:41 +0000
 +++ po/POTFILES.in	2017-06-05 19:01:49 +0000
@@ -119,6 +119,7 @@
  src/live_effects/effect.cpp
  src/live_effects/lpe-attach-path.cpp
  src/live_effects/lpe-bendpath.cpp
++src/live_effects/lpe-bool.cpp
  src/live_effects/lpe-bounding-box.cpp
  src/live_effects/lpe-bspline.cpp
  src/live_effects/lpe-clone-original.cpp
@@ -126,6 +127,7 @@
  src/live_effects/lpe-copy_rotate.cpp
  src/live_effects/lpe-curvestitch.cpp
  src/live_effects/lpe-ellipse_5pts.cpp
++src/live_effects/lpe-embrodery-stitch.cpp
  src/live_effects/lpe-envelope.cpp
  src/live_effects/lpe-extrude.cpp
  src/live_effects/lpe-fill-between-many.cpp
 === modified file 'src/live_effects/CMakeLists.txt'
 --- src/live_effects/CMakeLists.txt	2017-05-06 21:00:45 +0000
 +++ src/live_effects/CMakeLists.txt	2017-06-05 19:01:49 +0000
@@ -53,6 +53,9 @@
  	lpegroupbbox.cpp
  	lpeobject-reference.cpp
  	lpe-vonkoch.cpp
++	lpe-embrodery-stitch.cpp
++	lpe-embrodery-stitch-ordering.cpp
++	lpe-bool.cpp
  	lpeobject.cpp
  	spiro-converters.cpp
  	spiro.cpp
@@ -136,6 +139,9 @@
  	lpe-test-doEffect-stack.h
  	lpe-text_label.h
  	lpe-vonkoch.h
++	lpe-embrodery-stitch.h
++	lpe-embrodery-stitch-ordering.h
++	lpe-bool.h
  	lpegroupbbox.h
  	lpeobject-reference.h
  	lpeobject.h
 === 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 19:01:49 +0000
@@ -49,6 +49,8 @@
      BOUNDING_BOX,
      MEASURE_LINE,
      FILLET_CHAMFER,
++    BOOL_OP,
++    EMBRODERY_STITCH,
      DOEFFECTSTACK_TEST,
      ANGLE_BISECTOR,
      CIRCLE_WITH_RADIUS,
 === 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 19:01:49 +0000
@@ -62,6 +62,8 @@
  #include "live_effects/lpe-test-doEffect-stack.h"
  #include "live_effects/lpe-text_label.h"
  #include "live_effects/lpe-vonkoch.h"
++#include "live_effects/lpe-embrodery-stitch.h"
++#include "live_effects/lpe-bool.h"
  #include "xml/node-event-vector.h"
  #include "message-stack.h"
@@ -124,6 +126,8 @@
  /* 9.93 */
      {MEASURE_LINE,          N_("Measure Line"),                    "measure_line"},
      {FILLET_CHAMFER,        N_("Fillet/Chamfer"),                  "fillet_chamfer"},
++    {BOOL_OP,               N_("Boolean operation"),               "bool_op"},
++    {EMBRODERY_STITCH,      N_("Embrodery stitch"),                "embrodery_stitch"},
  #ifdef LPE_ENABLE_TEST_EFFECTS
      {DOEFFECTSTACK_TEST,    N_("doEffect stack test"),             "doeffectstacktest"},
      {ANGLE_BISECTOR,        N_("Angle bisector"),                  "angle_bisector"},
@@ -164,6 +168,12 @@
+ {
      Effect* neweffect = NULL;
      switch (lpenr) {
++        case EMBRODERY_STITCH:
++            neweffect = static_cast<Effect*> ( new LPEEmbroderyStitch(lpeobj) );
++            break;
++        case BOOL_OP:
++            neweffect = static_cast<Effect*> ( new LPEBool(lpeobj) );
++            break;
          case PATTERN_ALONG_PATH:
              neweffect = static_cast<Effect*> ( new LPEPatternAlongPath(lpeobj) );
              break;
 === added file 'src/live_effects/lpe-bool.cpp'
 --- src/live_effects/lpe-bool.cpp	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-bool.cpp	2017-06-05 19:01:49 +0000
@@ -0,0 +1,400 @@
++/*
++ * Boolean operation live path effect
++ *
++ * Copyright (C) 2016-2017 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#include <glibmm/i18n.h>
++#include <math.h>
++#include <string.h>
++#include <algorithm>
++
++#include "live_effects/lpe-bool.h"
++
++#include "display/curve.h"
++#include "sp-item.h"
++#include "2geom/path.h"
++#include "sp-shape.h"
++#include "sp-text.h"
++#include "2geom/bezier-curve.h"
++#include "2geom/path-sink.h"
++#include "2geom/affine.h"
++#include "splivarot.h"
++#include "helper/geom.h"
++#include "livarot/Path.h"
++#include "livarot/Shape.h"
++#include "livarot/path-description.h"
++#include "2geom/svg-path-parser.h"
++
++namespace Inkscape {
++namespace LivePathEffect {
++
++// Define an extended boolean operation type
++
++static const Util::EnumData<LPEBool::bool_op_ex> BoolOpData[LPEBool::bool_op_ex_count] = {
++    { LPEBool::bool_op_ex_union, N_("union"), "union" },
++    { LPEBool::bool_op_ex_inters, N_("intersection"), "inters" },
++    { LPEBool::bool_op_ex_diff, N_("difference"), "diff" },
++    { LPEBool::bool_op_ex_symdiff, N_("symmetric difference"), "symdiff" },
++    { LPEBool::bool_op_ex_cut, N_("division"), "cut" },
++    // Note on naming of operations:
++    // bool_op_cut is called "Division" in the manu, see sp_selected_path_cut
++    // bool_op_slice is called "Cut path" in the menu, see sp_selected_path_slice
++    { LPEBool::bool_op_ex_slice, N_("cut"), "slice" },
++    { LPEBool::bool_op_ex_slice_inside, N_("cut inside"), "slice-inside" },
++    { LPEBool::bool_op_ex_slice_outside, N_("cut outside"), "slice-outside" },
++};
++
++static const Util::EnumDataConverter<LPEBool::bool_op_ex> BoolOpConverter(BoolOpData, sizeof(BoolOpData) / sizeof(*BoolOpData));
++
++static const Util::EnumData<fill_typ> FillTypeData[] = {
++    { fill_oddEven, N_("odd-even"), "oddeven" },
++    { fill_nonZero, N_("non-zero"), "nonzero" },
++    { fill_positive, N_("positive"), "positive" },
++    { fill_justDont, N_("from curve"), "from-curve" }
++};
++
++static const Util::EnumDataConverter<fill_typ> FillTypeConverter(FillTypeData, sizeof(FillTypeData) / sizeof(*FillTypeData));
++
++static const Util::EnumData<fill_typ> FillTypeDataThis[] = {
++    { fill_oddEven, N_("odd-even"), "oddeven" },
++    { fill_nonZero, N_("non-zero"), "nonzero" },
++    { fill_positive, N_("positive"), "positive" }
++};
++
++static const Util::EnumDataConverter<fill_typ> FillTypeConverterThis(FillTypeDataThis, sizeof(FillTypeDataThis) / sizeof(*FillTypeDataThis));
++
++LPEBool::LPEBool(LivePathEffectObject *lpeobject) :
++    Effect(lpeobject),
++    operand_path(_("Operand path:"), _("Operand for the boolean operation"), "operand-path", &wr, this),
++    bool_operation(_("Operation:"), _("Boolean Operation"), "operation", BoolOpConverter, &wr, this, bool_op_ex_union),
++    swap_operands(_("Swap operands:"), _("Swap operands (useful e.g. for difference)"), "swap-operands", &wr, this),
++    rmv_inner(_("Remove inner:"), _("For cut operations: remove inner (non-contour) lines of cutting path to avoid invisible extra points"), "rmv-inner", &wr, this),
++    fill_type_this(_("Fill type this:"), _("Fill type (winding mode) for this path"), "filltype-this", FillTypeConverterThis, &wr, this, fill_oddEven),
++    fill_type_operand(_("Fill type operand:"), _("Fill type (winding mode) for operand path"), "filltype-operand", FillTypeConverter, &wr, this, fill_justDont)
++{
++    registerParameter(&operand_path);
++    registerParameter(&bool_operation);
++    registerParameter(&swap_operands);
++    registerParameter(&rmv_inner);
++    registerParameter(&fill_type_this);
++    registerParameter(&fill_type_operand);
++
++    show_orig_path = true;
++}
++
++LPEBool::~LPEBool()
++{
++
++}
++
++void LPEBool::resetDefaults(SPItem const * /*item*/)
++{
++}
++
++bool cmp_cut_position(const Path::cut_position &a, const Path::cut_position &b)
++{
++    return a.piece == b.piece ? a.t < b.t : a.piece < b.piece;
++}
++
++Geom::PathVector
++sp_pathvector_boolop_slice_intersect(Geom::PathVector const &pathva, Geom::PathVector const &pathvb, bool inside, fill_typ fra, fill_typ frb)
++{
++    // This is similar to sp_pathvector_boolop/bool_op_slice, but keeps only edges inside the cutter area.
++    // The code is also based on sp_pathvector_boolop_slice.
++    //
++    // We have two paths on input
++    // - a closed area which is used to cut out pieces from a contour (called area below)
++    // - a contour which is cut into pieces by the border of thr area (called contour below)
++    //
++    // The code below works in the following steps
++    // (a) Convert the area to a shape, so that we can ask the winding number for any point
++    // (b) Add both, the contour and the area to a single shape and intersect them
++    // (c) Find the intersection points between area border and contour (vector toCut)
++    // (d) Split the original contour at the intersection points
++    // (e) check for each contour edge in combined shape if its center is inside the area - if not discard it
++    // (f) create a vector of all inside edges
++    // (g) convert the piece numbers to the piece numbers after applying the cuts
++    // (h) fill a bool vector with information which pieces are in
++    // (i) filter the descr_cmd of the result path with this bool vector
++    //
++    // The main inefficieny here is step (e) because I use a winding function of the area-shape which goes
++    // through teh complete edge list for each point I ask for, so effort is n-edges-contour * n-edges-area.
++    // It is tricky to improve this without building into the livarot code.
++    // One way might be to decide at the intersection points which edges touching the intersection points are
++    // in by making a loop through all edges on the intersection vertex. Since this is a directed non intersecting
++    // graph, this should provide sufficient information.
++    // But since I anyway will change this to the new mechanism some time speed is fairly ok, I didn't look into this.
++
++
++    // extract the livarot Paths from the source objects
++    // also get the winding rule specified in the style
++    // Livarot's outline of arcs is broken. So convert the path to linear and cubics only, for which the outline is created correctly.
++    Path *contour_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathva));
++    Path *area_path = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathvb));
++
++    // Shapes from above paths
++    Shape *area_shape = new Shape;
++    Shape *combined_shape = new Shape;
++    Shape *combined_inters = new Shape;
++
++    // Add the area (process to intersection free shape)
++    area_path->ConvertWithBackData(1.0);
++    area_path->Fill(combined_shape, 1);
++
++    // Convert this to a shape with full winding information
++    area_shape->ConvertToShape(combined_shape, frb);
++
++    // Add the contour to the combined path (just add, no winding processing)
++    contour_path->ConvertWithBackData(1.0);
++    contour_path->Fill(combined_shape, 0, true, false, false);
++
++    // Intersect the area and the contour - no fill processing
++    combined_inters->ConvertToShape(combined_shape, fill_justDont);
++
++    // Result path
++    Path *result_path = new Path;
++    result_path->SetBackData(false);
++
++    // Cutting positions for contour
++    std::vector<Path::cut_position> toCut;
++
++    if (combined_inters->hasBackData()) {
++        // should always be the case, but ya never know
++        {
++            for (int i = 0; i < combined_inters->numberOfPoints(); i++) {
++                if (combined_inters->getPoint(i).totalDegree() > 2) {
++                    // possibly an intersection
++                    // we need to check that at least one edge from the source path is incident to it
++                    // before we declare it's an intersection
++                    int cb = combined_inters->getPoint(i).incidentEdge[FIRST];
++                    int   nbOrig = 0;
++                    int   nbOther = 0;
++                    int   piece = -1;
++                    float t = 0.0;
++                    while (cb >= 0 && cb < combined_inters->numberOfEdges()) {
++                        if (combined_inters->ebData[cb].pathID == 0) {
++                            // the source has an edge incident to the point, get its position on the path
++                            piece = combined_inters->ebData[cb].pieceID;
++                            if (combined_inters->getEdge(cb).st == i) {
++                                t = combined_inters->ebData[cb].tSt;
++                            } else {
++                                t = combined_inters->ebData[cb].tEn;
++                            }
++                            nbOrig++;
++                        }
++                        if (combined_inters->ebData[cb].pathID == 1) {
++                            nbOther++;    // the cut is incident to this point
++                        }
++                        cb = combined_inters->NextAt(i, cb);
++                    }
++                    if (nbOrig > 0 && nbOther > 0) {
++                        // point incident to both path and cut: an intersection
++                        // note that you only keep one position on the source; you could have degenerate
++                        // cases where the source crosses itself at this point, and you wouyld miss an intersection
++                        Path::cut_position cutpos;
++                        cutpos.piece = piece;
++                        cutpos.t = t;
++                        toCut.push_back(cutpos);
++                    }
++                }
++            }
++        }
++        {
++            // remove the edges from the intersection polygon
++            int i = combined_inters->numberOfEdges() - 1;
++            for (; i >= 0; i--) {
++                if (combined_inters->ebData[i].pathID == 1) {
++                    combined_inters->SubEdge(i);
++                } else {
++                    const Shape::dg_arete &edge = combined_inters->getEdge(i);
++                    const Shape::dg_point &start = combined_inters->getPoint(edge.st);
++                    const Shape::dg_point &end = combined_inters->getPoint(edge.en);
++                    Geom::Point mid = 0.5 * (start.x + end.x);
++                    int wind = area_shape->PtWinding(mid);
++                    if (wind == 0) {
++                        combined_inters->SubEdge(i);
++                    }
++                }
++            }
++        }
++    }
++
++    // create a vector of pieces, which are in the intersection
++    std::vector<Path::cut_position> inside_pieces(combined_inters->numberOfEdges());
++    for (int i = 0; i < combined_inters->numberOfEdges(); i++) {
++        inside_pieces[i].piece = combined_inters->ebData[i].pieceID;
++        // Use the t middle point, this is safe to compare with values from toCut in the presence of roundoff errors
++        inside_pieces[i].t = 0.5 * (combined_inters->ebData[i].tSt + combined_inters->ebData[i].tEn);
++    }
++    std::sort(inside_pieces.begin(), inside_pieces.end(), cmp_cut_position);
++
++    // sort cut positions
++    std::sort(toCut.begin(), toCut.end(), cmp_cut_position);
++
++    // Compute piece ids after ConvertPositionsToMoveTo
++    {
++        int idIncr = 0;
++        std::vector<Path::cut_position>::iterator itPiece = inside_pieces.begin();
++        std::vector<Path::cut_position>::iterator itCut = toCut.begin();
++        while (itPiece != inside_pieces.end()) {
++            while (itCut != toCut.end() && cmp_cut_position(*itCut, *itPiece)) {
++                ++itCut;
++                idIncr += 2;
++            }
++            itPiece->piece += idIncr;
++            ++itPiece;
++        }
++    }
++
++    // Copy the original path to result and cut at the intersection points
++    result_path->Copy(contour_path);
++    result_path->ConvertPositionsToMoveTo(toCut.size(), toCut.data());   // cut where you found intersections
++
++    // Create an array of bools which states which pieces are in
++    std::vector<bool> inside_flags(result_path->descr_cmd.size(), false);
++    for (std::vector<Path::cut_position>::iterator itPiece = inside_pieces.begin(); itPiece != inside_pieces.end(); ++itPiece) {
++        inside_flags[ itPiece->piece ] = true;
++        // also enable the element -1 to get the MoveTo
++        if (itPiece->piece >= 1) {
++            inside_flags[ itPiece->piece - 1 ] = true;
++        }
++    }
++
++#if 0 // CONCEPT TESTING
++    //Check if the inside/outside verdict is consistent - just for testing the concept
++    // Retrieve the pieces
++    int nParts = 0;
++    Path **parts = result_path->SubPaths(nParts, false);
++
++    // Each piece should be either fully in or fully out
++    int iPiece = 0;
++    for (int iPart = 0; iPart < nParts; iPart++) {
++        bool andsum = true;
++        bool orsum = false;
++        for (int iCmd = 0; iCmd < parts[iPart]->descr_cmd.size(); iCmd++, iPiece++) {
++            andsum = andsum && inside_flags[ iPiece ];
++            orsum = andsum || inside_flags[ iPiece ];
++        }
++
++        if (andsum != orsum) {
++            g_warning("Inconsistent inside/outside verdict for part=%d", iPart);
++        }
++    }
++    g_free(parts);
++#endif
++
++    // iterate over the commands of a path and keep those which are inside
++    int iDest = 0;
++    for (int iSrc = 0; iSrc < result_path->descr_cmd.size(); iSrc++) {
++        if (inside_flags[iSrc] == inside) {
++            result_path->descr_cmd[iDest++] = result_path->descr_cmd[iSrc];
++        } else {
++            delete result_path->descr_cmd[iSrc];
++        }
++    }
++    result_path->descr_cmd.resize(iDest);
++
++    delete combined_inters;
++    delete combined_shape;
++    delete area_shape;
++    delete contour_path;
++    delete area_path;
++
++    gchar *result_str = result_path->svg_dump_path();
++    Geom::PathVector outres =  Geom::parse_svg_path(result_str);
++    // CONCEPT TESTING g_warning( "%s", result_str );
++    g_free(result_str);
++    delete result_path;
++
++    return outres;
++}
++
++// remove inner contours
++Geom::PathVector
++sp_pathvector_boolop_remove_inner(Geom::PathVector const &pathva, fill_typ fra)
++{
++    Geom::PathVector patht;
++    Path *patha = Path_for_pathvector(pathv_to_linear_and_cubic_beziers(pathva));
++
++    Shape *shape = new Shape;
++    Shape *shapeshape = new Shape;
++    Path *resultp = new Path;
++    resultp->SetBackData(false);
++
++    patha->ConvertWithBackData(0.1);
++    patha->Fill(shape, 0);
++    shapeshape->ConvertToShape(shape, fra);
++    shapeshape->ConvertToForme(resultp, 1, &patha);
++
++    delete shape;
++    delete shapeshape;
++    delete patha;
++
++    gchar *result_str = resultp->svg_dump_path();
++    Geom::PathVector resultpv =  Geom::parse_svg_path(result_str);
++    g_free(result_str);
++
++    delete resultp;
++    return resultpv;
++}
++
++static fill_typ GetFillTyp(SPItem *item)
++{
++    SPCSSAttr *css = sp_repr_css_attr(item->getRepr(), "style");
++    gchar const *val = sp_repr_css_property(css, "fill-rule", NULL);
++    if (val && strcmp(val, "nonzero") == 0) {
++        return fill_nonZero;
++    } else if (val && strcmp(val, "evenodd") == 0) {
++        return fill_oddEven;
++    } else {
++        return fill_nonZero;
++    }
++}
++
++void LPEBool::doEffect(SPCurve *curve)
++{
++    Geom::PathVector path_in = curve->get_pathvector();
++
++    if (operand_path.linksToPath() && operand_path.getObject()) {
++        bool_op_ex op = bool_operation.get_value();
++        bool swap =  swap_operands.get_value();
++
++        Geom::PathVector path_a = swap ? operand_path.get_pathvector() : path_in;
++        Geom::PathVector path_b = swap ? path_in : operand_path.get_pathvector();
++
++        // TODO: I would like to use the original objects fill rule if the UI selected rule is fill_justDont.
++        // But it doesn't seem possible to access them from here, because SPCurve is not derived from SPItem.
++        // The nearest function in the call stack, where this is available is SPLPEItem::performPathEffect (this is then an SPItem)
++        // For the parameter curve, this is possible.
++        // fill_typ fill_this    = fill_type_this.   get_value()!=fill_justDont ? fill_type_this.get_value()    : GetFillTyp( curve ) ;
++        fill_typ fill_this    = fill_type_this.get_value();
++        fill_typ fill_operand = fill_type_operand.get_value() != fill_justDont ? fill_type_operand.get_value() : GetFillTyp(operand_path.getObject());
++
++        fill_typ fill_a = swap ? fill_operand : fill_this;
++        fill_typ fill_b = swap ? fill_this : fill_operand;
++
++        if (rmv_inner.get_value()) {
++            path_b = sp_pathvector_boolop_remove_inner(path_b, fill_b);
++        }
++
++        Geom::PathVector path_out;
++
++        if (op == bool_op_ex_slice) {
++            // For slicing, the bool op is added to the line group which is sliced, not the cut path. This swapped order is correct.
++            path_out = sp_pathvector_boolop(path_b, path_a, to_bool_op(op), fill_b, fill_a);
++        } else if (op == bool_op_ex_slice_inside) {
++            path_out = sp_pathvector_boolop_slice_intersect(path_a, path_b, true, fill_a, fill_b);
++        } else if (op == bool_op_ex_slice_outside) {
++            path_out = sp_pathvector_boolop_slice_intersect(path_a, path_b, false, fill_a, fill_b);
++        } else {
++            path_out = sp_pathvector_boolop(path_a, path_b, to_bool_op(op), fill_a, fill_b);
++        }
++        curve->set_pathvector(path_out);
++    }
++}
++
++} // namespace LivePathEffect
++} /* namespace Inkscape */
 === added file 'src/live_effects/lpe-bool.h'
 --- src/live_effects/lpe-bool.h	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-bool.h	2017-06-05 19:01:49 +0000
@@ -0,0 +1,63 @@
++/*
++ * Boolean operation live path effect
++ *
++ * Copyright (C) 2016 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#ifndef INKSCAPE_LPE_BOOL_H
++#define INKSCAPE_LPE_BOOL_H
++
++#include "live_effects/effect.h"
++#include "live_effects/parameter/parameter.h"
++#include "live_effects/parameter/originalpath.h"
++#include "live_effects/parameter/bool.h"
++#include "live_effects/parameter/enum.h"
++#include "livarot/LivarotDefs.h"
++
++namespace Inkscape {
++namespace LivePathEffect {
++
++class LPEBool : public Effect {
++public:
++    LPEBool(LivePathEffectObject *lpeobject);
++    virtual ~LPEBool();
++
++    void doEffect(SPCurve *curve);
++    virtual void resetDefaults(SPItem const *item);
++
++    enum bool_op_ex {
++        bool_op_ex_union     = bool_op_union,
++        bool_op_ex_inters    = bool_op_inters,
++        bool_op_ex_diff      = bool_op_diff,
++        bool_op_ex_symdiff   = bool_op_symdiff,
++        bool_op_ex_cut       = bool_op_cut,
++        bool_op_ex_slice     = bool_op_slice,
++        bool_op_ex_slice_inside,            // like bool_op_slice, but leaves only the contour pieces inside of the cut path
++        bool_op_ex_slice_outside,           // like bool_op_slice, but leaves only the contour pieces outside of the cut path
++        bool_op_ex_count
++    };
++
++    inline friend bool_op to_bool_op(bool_op_ex val)
++    {
++        assert(val <= bool_op_ex_slice);
++        (bool_op) val;
++    }
++
++private:
++    LPEBool(const LPEBool &);
++    LPEBool &operator=(const LPEBool &);
++
++    OriginalPathParam operand_path;
++    EnumParam<bool_op_ex> bool_operation;
++    EnumParam<fill_typ> fill_type_this;
++    EnumParam<fill_typ> fill_type_operand;
++    BoolParam swap_operands;
++    BoolParam rmv_inner;
++};
++
++}; //namespace LivePathEffect
++}; //namespace Inkscape
++
++#endif
 === added file 'src/live_effects/lpe-embrodery-stitch-ordering.cpp'
 --- src/live_effects/lpe-embrodery-stitch-ordering.cpp	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-embrodery-stitch-ordering.cpp	2017-06-05 19:01:49 +0000
@@ -0,0 +1,1139 @@
++/*
++ * Sub-path Ordering functions for embroidery stitch LPE (Implementation)
++ *
++ * Copyright (C) 2016 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#include "live_effects/lpe-embrodery-stitch-ordering.h"
++
++#include <numeric>
++
++namespace Inkscape {
++namespace LivePathEffect {
++namespace LPEEmbroderyStitchOrdering {
++
++using namespace Geom;
++
++// ==================== Debug Trace Macros ====================
++
++// ATTENTION: both level and area macros must be enabled for tracing
++
++// These macros are for enabling certain levels of tracing
++#define DebugTrace1(list) // g_warning list
++#define DebugTrace2(list) // g_warning list
++
++// These macros are for enabling certain areas of tracing
++#define DebugTraceGrouping(list) // list
++#define DebugTraceTSP(list)      // list
++
++// Combinations of above
++#define DebugTrace1TSP(list) DebugTraceTSP( DebugTrace1(list) )
++#define DebugTrace2TSP(list) DebugTraceTSP( DebugTrace2(list) )
++
++// ==================== Template Utilities ====================
++
++// Delete all objects pointed to by a vector and clear the vector
++
++template< typename T > void delete_and_clear(std::vector<T> &vector)
++{
++    for (typename std::vector<T>::iterator it = vector.begin(); it != vector.end(); ++it) {
++        delete *it;
++    }
++    vector.clear();
++}
++
++// Assert that there are no duplicates in a vector
++
++template< typename T > void assert_unique(std::vector<T> &vector)
++{
++    typename std::vector<T> copy = vector;
++    std::sort(copy.begin(), copy.end());
++    assert(std::unique(copy.begin(), copy.end()) == copy.end());
++}
++
++// remove element(s) by value
++
++template< typename T > void remove_by_value(std::vector<T> *vector, const T &value)
++{
++    vector->erase(std::remove(vector->begin(), vector->end(), value), vector->end());
++}
++
++// fill a vector with increasing elements (similar to C++11 iota)
++// iota is included in some C++ libraries, not in other (it is always included for C++11)
++// To avoid issues, use our own name (not iota)
++
++template<class OutputIterator, class Counter>
++void fill_increasing(OutputIterator begin, OutputIterator end, Counter counter)
++{
++    while (begin != end) {
++        *begin++ = counter++;
++    }
++}
++
++// check if an iteratable sequence contains an element
++
++template<class InputIterator, class Element>
++bool contains(InputIterator begin, InputIterator end, const Element &elem)
++{
++    while (begin != end) {
++        if (*begin == elem) {
++            return true;
++        }
++        ++begin;
++    }
++    return false;
++}
++
++// Check if a vector contains an element
++
++template<class Element>
++bool contains(std::vector<Element> const &vector, const Element &elem)
++{
++    return contains(vector.begin(), vector.end(), elem);
++}
++
++// ==================== Multi-dimensional iterator functions ====================
++
++// Below are 3 simple template functions to do triangle/pyramid iteration (without diagonal).
++// Here is a sample of iterating over 5 elements in 3 dimensions:
++//
++// 0 1 2
++// 0 1 3
++// 0 1 4
++// 0 2 3
++// 0 2 4
++// 1 2 4
++// 1 3 4
++// 2 3 4
++// end end end
++//
++// If the number of elements is less then the number of dimensions, the number of dimensions is reduced automatically.
++//
++// I thought about creating an iterator class for this, but it doesn't match that well, so I used functions on iterator vectors.
++
++// Initialize a vector of iterators
++
++template<class Iterator>
++void triangleit_begin(std::vector<Iterator> &iterators, Iterator const &begin, Iterator const &end, size_t n)
++{
++    iterators.clear();
++    // limit number of dimensions to number of elements
++    size_t n1 = end - begin;
++    n = std::min(n, n1);
++    if (n) {
++        iterators.push_back(begin);
++        for (int i = 1; i < n; i++) {
++            iterators.push_back(iterators.back() + 1);
++        }
++    }
++}
++
++// Increment a vector of iterators
++
++template<class Iterator>
++void triangleit_incr(std::vector<Iterator> &iterators, Iterator const &end)
++{
++    size_t n = iterators.size();
++
++    for (int i = 0; i < n; i++) {
++        iterators[n - 1 - i]++;
++        // Each dimension ends at end-i, so that there are elements left for the i higher dimensions
++        if (iterators[n - 1 - i] != end - i) {
++            // Assign increasing numbers to the higher dimension
++            for (int j = n - i; j < n; j++) {
++                iterators[j] = iterators[j - 1] + 1;
++            }
++            return;
++        }
++    }
++}
++
++// Check if a vector of iterators is at the end
++
++template<class Iterator>
++bool triangleit_test(std::vector<Iterator> &iterators, Iterator const &end)
++{
++    if (iterators.empty()) {
++        return false;
++    } else {
++        return iterators.back() != end;
++    }
++}
++
++// ==================== Trivial Ordering Functions ====================
++
++// Sub-path reordering: do nothing - keep original order
++
++void OrderingOriginal(std::vector<OrderingInfo> &infos)
++{
++}
++
++// Sub-path reordering: reverse every other sub path
++
++void OrderingZigZag(std::vector<OrderingInfo> &infos, bool revfirst)
++{
++    for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
++        it->reverse = (it->index & 1) == (revfirst ? 0 : 1);
++    }
++}
++
++// Sub-path reordering: continue with the neartest start or end point of yet unused sub paths
++
++void OrderingClosest(std::vector<OrderingInfo> &infos, bool revfirst)
++{
++    std::vector<OrderingInfo> result;
++    result.reserve(infos.size());
++
++    result.push_back(infos[0]);
++    result.back().reverse = revfirst;
++    Point p = result.back().GetEndRev();
++
++    infos[0].used = true;
++
++
++    for (unsigned int iRnd = 1; iRnd < infos.size(); iRnd++) {
++        // find closest point to p
++        unsigned iBest = 0;
++        bool revBest = false;
++        Coord distBest = infinity();
++
++        for (std::vector<OrderingInfo>::iterator it = infos.begin(); it != infos.end(); ++it) {
++            it->index = it - infos.begin();
++            it->reverse = (it->index & 1) != 0;
++
++            if (!it->used) {
++                Coord dist = distance(p, it->GetBegOrig());
++                if (dist < distBest) {
++                    distBest = dist;
++                    iBest = it - infos.begin();
++                    revBest = false;
++                }
++
++                dist = distance(p, it->GetEndOrig());
++                if (dist < distBest) {
++                    distBest = dist;
++                    iBest = it - infos.begin();
++                    revBest = true;
++                }
++            }
++        }
++
++        result.push_back(infos[iBest]);
++        result.back().reverse = revBest;
++        p = result.back().GetEndRev();
++        infos[iBest].used = true;
++    }
++
++    infos = result;
++}
++
++// ==================== Traveling Salesman k-opt Ordering Function and Utilities ====================
++
++// A Few notes on this:
++// - This is a relatively simple Lin-type k-opt algorithm, but the grouping optimizations done make it already quite complex.
++// - The main Ordering Function is OrderingAdvanced
++// - Lines which start at the end of another line are connected and treated as one (struct OrderingInfoEx)
++// - Groups of zig-zag OrderingInfoEx are grouped (struct OrderingGroup) if both ends of the segment mutually agree with a next neighbor.
++//   These groups are treated as a unit in the TSP algorithm.
++//   The only option is to reverse the first segment, so that a group has 4 end points, 2 of which are used externally.
++// - Run a k-opt (k=2..5) Lin like Traveling Salesman Problem algorithm on the groups as a unit and the remaining edges.
++//   See https://en.wikipedia.org/wiki/Travelling_salesman_problem#Iterative_improvement
++//   The algorithm uses a greedy nearest neighbor as start configuration and does not use repeated random starts.
++// - The algorithm searches an open tour (rather than a closed one), so the longest segment in the closed path is ignored.
++// - TODO: it might be faster to use k=3 with a few random starting patterns instead of k=5
++// - TODO: it is surely wiser to implement e.g. Lin-Kenrighan TSP, but the simple k-opt works ok.
++// - TODO(EASY): add a jump distance, above which threads are removed and make the length of this jump distance constant and large,
++//   so that mostly the number of jumps is optimized
++
++// Find 2 nearest points to given point
++
++void OrderingPoint::FindNearest2(const std::vector<OrderingInfoEx *> &infos)
++{
++    // This implementation is not terribly elegant (unSTLish).
++    // But for the first 2 elements using e.g. partial_sort is not simpler.
++
++    Coord dist0 = infinity();
++    Coord dist1 = infinity();
++    nearest[0] = 0;
++    nearest[1] = 0;
++
++    for (std::vector<OrderingInfoEx *>::const_iterator it = infos.begin(); it != infos.end(); ++it) {
++        Coord dist = distance(point, (*it)->beg.point);
++        if (dist < dist1) {
++            if (&(*it)->beg != this && &(*it)->end != this) {
++                if (dist < dist0) {
++                    nearest[1] = nearest[0];
++                    nearest[0] = &(*it)->beg;
++                    dist1 = dist0;
++                    dist0 = dist;
++                } else {
++                    nearest[1] = &(*it)->beg;
++                    dist1 = dist;
++                }
++            }
++        }
++
++        dist = distance(point, (*it)->end.point);
++        if (dist < dist1) {
++            if (&(*it)->beg != this && &(*it)->end != this) {
++                if (dist < dist0) {
++                    nearest[1] = nearest[0];
++                    nearest[0] = &(*it)->end;
++                    dist1 = dist0;
++                    dist0 = dist;
++                } else {
++                    nearest[1] = &(*it)->end;
++                    dist1 = dist;
++                }
++            }
++        }
++    }
++}
++
++// Check if "this" is among the nearest of its nearest
++
++void OrderingPoint::EnforceMutual(void)
++{
++    if (nearest[0] && !(this == nearest[0]->nearest[0] || this == nearest[0]->nearest[1])) {
++        nearest[0] = 0;
++    }
++
++    if (nearest[1] && !(this == nearest[1]->nearest[0] || this == nearest[1]->nearest[1])) {
++        nearest[1] = 0;
++    }
++
++    if (nearest[1] && !nearest[0]) {
++        nearest[0] = nearest[1];
++        nearest[1] = 0;
++    }
++}
++
++// Check if the subpath indices of this and other are the same, otherwise zero both nearest
++
++void OrderingPoint::EnforceSymmetric(const OrderingPoint &other)
++{
++    if (nearest[0] && !(
++                (other.nearest[0] && nearest[0]->infoex == other.nearest[0]->infoex) ||
++                (other.nearest[1] && nearest[0]->infoex == other.nearest[1]->infoex)
++            )) {
++        nearest[0] = 0;
++    }
++
++    if (nearest[1] && !(
++                (other.nearest[0] && nearest[1]->infoex == other.nearest[0]->infoex) ||
++                (other.nearest[1] && nearest[1]->infoex == other.nearest[1]->infoex)
++            )) {
++        nearest[1] = 0;
++    }
++
++    if (nearest[1] && !nearest[0]) {
++        nearest[0] = nearest[1];
++        nearest[1] = 0;
++    }
++}
++
++void OrderingPoint::Dump(void)
++{
++    Coord dist0 = nearest[0] ? distance(point, nearest[0]->point) : -1.0;
++    Coord dist1 = nearest[1] ? distance(point, nearest[1]->point) : -1.0;
++    int idx0 = nearest[0] ? nearest[0]->infoex->idx : -1;
++    int idx1 = nearest[1] ? nearest[1]->infoex->idx : -1;
++    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));
++}
++
++
++// If this element can be grouped (has neighbours) but is not yet grouped, create a new group
++
++void OrderingInfoEx::MakeGroup(std::vector<OrderingInfoEx *> &infos, std::vector<OrderingGroup *> *groups)
++{
++    if (grouped || !beg.HasNearest() || !end.HasNearest()) {
++        return;
++    }
++
++    groups->push_back(new OrderingGroup(groups->size()));
++
++    // Add neighbors recursively
++    AddToGroup(infos, groups->back());
++}
++
++// Add this and all connected elements to the group
++
++void OrderingInfoEx::AddToGroup(std::vector<OrderingInfoEx *> &infos, OrderingGroup *group)
++{
++    if (grouped || !beg.HasNearest() || !end.HasNearest()) {
++        return;
++    }
++
++    group->items.push_back(this);
++    grouped = true;
++    // Note: beg and end neighbors have been checked to be symmetric
++    if (beg.nearest[0]) {
++        beg.nearest[0]->infoex->AddToGroup(infos, group);
++    }
++    if (beg.nearest[1]) {
++        beg.nearest[1]->infoex->AddToGroup(infos, group);
++    }
++    if (end.nearest[0]) {
++        end.nearest[0]->infoex->AddToGroup(infos, group);
++    }
++    if (end.nearest[1]) {
++        end.nearest[1]->infoex->AddToGroup(infos, group);
++    }
++}
++
++// Constructor
++
++OrderingGroupNeighbor::OrderingGroupNeighbor(OrderingGroupPoint *me, OrderingGroupPoint *other) :
++    point(other),
++    distance(Geom::distance(me->point, other->point))
++{
++}
++
++// Comparison function for sorting by distance
++
++bool OrderingGroupNeighbor::Compare(const OrderingGroupNeighbor &a, const OrderingGroupNeighbor &b)
++{
++    return a.distance < b.distance;
++}
++
++// Find the nearest unused neighbor point
++
++OrderingGroupNeighbor *OrderingGroupPoint::FindNearestUnused(void)
++{
++    for (std::vector<OrderingGroupNeighbor>::iterator it = nearest.begin(); it != nearest.end(); ++it) {
++        if (!it->point->used) {
++            DebugTrace1TSP(("Nearest: group %d, size %d, point %d, nghb %d, xFrom %.4lf, yFrom %.4lf, xTo %.4lf, yTo %.4lf, dist %.4lf",
++                            it->point->group->index, it->point->group->items.size(), it->point->indexInGroup, it - nearest.begin(),
++                            point.x(), 297 - point.y(),
++                            it->point->point.x(), 297 - it->point->point.y(),
++                            it->distance));
++            return &*it;
++        }
++    }
++
++    // it shouldn't happen that we can't find any point at all
++    assert(0);
++    return 0;
++}
++
++// Return the other end in the group of the point
++
++OrderingGroupPoint *OrderingGroupPoint::GetOtherEndGroup(void)
++{
++    return group->endpoints[ indexInGroup ^ 1 ];
++}
++
++// Return the alternate point (if one exists), 0 otherwise
++
++OrderingGroupPoint *OrderingGroupPoint::GetAltPointGroup(void)
++{
++    if (group->nEndPoints < 4) {
++        return 0;
++    }
++
++    OrderingGroupPoint *alt = group->endpoints[ indexInGroup ^ 2 ];
++    return alt->used ? 0 : alt;
++}
++
++
++// Sets the rev flags in the group assuming that the group starts with this point
++
++void OrderingGroupPoint::SetRevInGroup(void)
++{
++    // If this is not a front point, the item list needs to be reversed
++    group->revItemList = !front;
++
++    // If this is not a begin point, the items need to be reversed
++    group->revItems = !begin;
++}
++
++// Mark an end point as used and also mark the two other alternating points as used
++// Returns the used point
++
++void OrderingGroupPoint::UsePoint(void)
++{
++    group->UsePoint(indexInGroup);
++}
++
++// Mark an end point as unused and possibly also mark the two other alternating points as unused
++// Returns the used point
++
++void OrderingGroupPoint::UnusePoint(void)
++{
++    group->UnusePoint(indexInGroup);
++}
++
++// Return the other end in the connection
++OrderingGroupPoint *OrderingGroupPoint::GetOtherEndConnection(void)
++{
++    assert(connection);
++    assert(connection->points[ indexInConnection ] == this);
++    assert(connection->points[ indexInConnection ^ 1 ]);
++
++    return connection->points[ indexInConnection ^ 1 ];
++}
++
++
++// Set the end points of a group from the items
++
++void OrderingGroup::SetEndpoints(void)
++{
++    assert(items.size() >= 1);
++
++    if (items.size() == 1) {
++        // A simple line:
++        //
++        // b0-front--e1
++
++        nEndPoints = 2;
++        endpoints[0] = new OrderingGroupPoint(items.front()->beg.point, this, 0, true,  true);
++        endpoints[1] = new OrderingGroupPoint(items.front()->end.point, this, 1, false, true);
++    } else {
++        // If the number of elements is even, the group is
++        // either from items.front().beg to items.back().beg
++        // or from     items.front().end to items.back().end:
++        // Below: b=beg, e=end, numbers are end point indices
++        //
++        // b0-front--e     b0-front--e2
++        //           |     |
++        // b---------e     b---------e
++        // |                         |
++        // b---------e     b---------e
++        //           |     |
++        // b1-back---e     b1-back---e3
++        //
++        //
++        // if the number of elements is odd, it is crossed:
++        //
++        // b0-front--e     b--front--e2
++        //           |     |
++        // b---------e     b---------e
++        // |                         |
++        // b--back---e1    b3-back---e
++        //
++        // TODO: this is not true with the following kind of pattern
++        //
++        // b--front--e
++        // b---------e
++        //           b--------e
++        //           b--back--e
++        //
++        // Here only one connection is possible, from front.end to back.beg
++        //
++        // TODO: also this is not true if segment direction is alternating
++        //
++        // TOTO: => Just see where you end up from front().begin and front().end
++        //
++        // the numbering is such that either end points 0 and 1 are used or 2 and 3.
++        int cross = items.size() & 1 ? 2 : 0;
++        nEndPoints = 4;
++
++        endpoints[0      ] = new OrderingGroupPoint(items.front()->beg.point, this, 0,       true,  true);
++        endpoints[1 ^ cross] = new OrderingGroupPoint(items.back() ->beg.point, this, 1 ^ cross, true,  false);
++        endpoints[2      ] = new OrderingGroupPoint(items.front()->end.point, this, 2,       false, true);
++        endpoints[3 ^ cross] = new OrderingGroupPoint(items.back() ->end.point, this, 3 ^ cross, false, false);
++    }
++}
++
++// Add all points from another group as neighbors
++
++void OrderingGroup::AddNeighbors(OrderingGroup *nghb)
++{
++    for (int iThis = 0; iThis < nEndPoints; iThis++) {
++        for (int iNghb = 0; iNghb < nghb->nEndPoints; iNghb++) {
++            endpoints[iThis]->nearest.push_back(OrderingGroupNeighbor(endpoints[iThis], nghb->endpoints[iNghb]));
++        }
++    }
++}
++
++// Mark an end point as used and also mark the two other alternating points as used
++// Returns the used point
++
++OrderingGroupPoint *OrderingGroup::UsePoint(int index)
++{
++    assert(index < nEndPoints);
++    assert(!endpoints[index]->used);
++    endpoints[index]->used = true;
++    if (nEndPoints == 4) {
++        int offs = index < 2 ? 2 : 0;
++        endpoints[0 + offs]->used = true;
++        endpoints[1 + offs]->used = true;
++    }
++
++    return endpoints[index];
++}
++
++// Mark an end point as unused and possibly also mark the two other alternating points as unused
++// Returns the used point
++
++void OrderingGroup::UnusePoint(int index)
++{
++    assert(index < nEndPoints);
++    assert(endpoints[index]->used);
++    endpoints[index]->used = false;
++
++    if (nEndPoints == 4 && !endpoints[index ^ 1]->used) {
++        int offs = index < 2 ? 2 : 0;
++        endpoints[0 + offs]->used = false;
++        endpoints[1 + offs]->used = false;
++    }
++}
++
++// Add an end point
++void OrderingSegment::AddPoint(OrderingGroupPoint *point)
++{
++    assert(point);
++    assert(nEndPoints < 4);
++    endpoints[ nEndPoints++ ] = point;
++
++    // If both ends of a group are added and the group has 4 points, add the other two as well
++    if (nEndPoints == 2 && endpoints[0]->group == endpoints[1]->group) {
++        OrderingGroup *group = endpoints[0]->group;
++        if (group->nEndPoints == 4) {
++            for (int i = 0; i < 4; i++) {
++                endpoints[i] = group->endpoints[i];
++            }
++            nEndPoints = 4;
++        }
++    }
++}
++
++// Get begin point (taking swap and end bit into account
++OrderingGroupPoint *OrderingSegment::GetBeginPoint(unsigned int iSwap, unsigned int iEnd)
++{
++    int iPoint = ((iEnd >> endbit) & 1) + (((iSwap >> swapbit) & 1) << 1);
++    assert(iPoint < nEndPoints);
++    return endpoints[iPoint];
++}
++
++// Get end point (taking swap and end bit into account
++OrderingGroupPoint *OrderingSegment::GetEndPoint(unsigned int iSwap, unsigned int iEnd)
++{
++    int iPoint = (((iEnd >> endbit) & 1) ^ 1) + (((iSwap >> swapbit) & 1) << 1);
++    assert(iPoint < nEndPoints);
++    return endpoints[iPoint];
++}
++
++
++// Find the next unused point in list
++std::vector<OrderingGroupPoint *>::iterator FindUnusedAndUse(std::vector<OrderingGroupPoint *> *unusedPoints, std::vector<OrderingGroupPoint *>::iterator const from)
++{
++    for (std::vector<OrderingGroupPoint *>::iterator it = from; it != unusedPoints->end(); ++it) {
++        if (!(*it)->used) {
++            (*it)->UsePoint();
++            return it;
++        }
++    }
++    return unusedPoints->end();
++}
++
++// Find the shortest reconnect between the given points
++
++bool FindShortestReconnect(std::vector<OrderingSegment> &segments, std::vector<OrderingGroupConnection *> &connections, std::vector<OrderingGroupConnection *> &allconnections, OrderingGroupConnection **longestConnect, Coord *total, Coord olddist)
++{
++    // Find the longest connection outside of the active set
++    // The longest segment is then the longest of this longest outside segment and all inside segments
++    OrderingGroupConnection *longestOutside = 0;
++
++    if (contains(connections, *longestConnect)) {
++        // The longest connection is inside the active set, so we need to search for the longest outside
++        Coord length = 0.0;
++        for (std::vector<OrderingGroupConnection *>::iterator it = allconnections.begin(); it != allconnections.end(); it++) {
++            if ((*it)->Distance() > length) {
++                if (!contains(connections, *it)) {
++                    longestOutside = *it;
++                    length = (*it)->Distance();
++                }
++            }
++        }
++    } else {
++        longestOutside = *longestConnect;
++    }
++
++    // length of longestConnect outside
++    Coord longestOutsideLength = longestOutside ? longestOutside->Distance() : 0.0;
++
++    // We measure length without the longest, so subtract the longest length from the old distance
++    olddist -= (*longestConnect)->Distance();
++
++    // Assign a swap bit and end bit to each active connection
++    int nEndBits = 0;
++    int nSwapBits = 0;
++    for (std::vector<OrderingSegment>::iterator it = segments.begin(); it != segments.end(); it++) {
++        it->endbit = nEndBits++;
++        if (it->nEndPoints == 4) {
++            it->swapbit = nSwapBits++;
++        } else {
++            // bit 32 should always be 0
++            it->swapbit = 31;
++        }
++    }
++
++    unsigned int swapMask = (1U << nSwapBits) - 1;
++    unsigned int endMask = (1U << nEndBits) - 1;
++
++    // Create a permutation vector
++    std::vector<int> permutation(segments.size());
++    fill_increasing(permutation.begin(), permutation.end(), 0);
++
++    // best improvement
++    bool improved = false;
++    Coord distBest = olddist;
++    std::vector<int> permutationBest;
++    unsigned int iSwapBest;
++    unsigned int iEndBest;
++    int nTrials = 0;
++
++    // Loop over the permutations
++    do {
++        // Loop over the swap bits
++        unsigned int iSwap = 0;
++        do {
++            // Loop over the end bits
++            unsigned int iEnd = 0;
++            do {
++                // Length of all active connections
++                Coord lengthTotal = 0;
++                // Length of longest connection (active or inactive)
++                Coord lengthLongest = longestOutsideLength;
++
++                // Close the loop with the end point of the last segment
++                OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
++                for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
++                    OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
++                    Coord length = Geom::distance(thisbeg->point, prevend->point);
++                    lengthTotal += length;
++                    if (length > lengthLongest) {
++                        lengthLongest = length;
++                    }
++                    prevend = segments[*it].GetEndPoint(iSwap, iEnd);
++                }
++                lengthTotal -= lengthLongest;
++
++                // If there is an improvement, remember the best selection
++                if (lengthTotal + 1e-6 < distBest) {
++                    improved = true;
++                    distBest = lengthTotal;
++                    permutationBest = permutation;
++                    iSwapBest = iSwap;
++                    iEndBest = iEnd;
++
++                    // Just debug printing
++                    OrderingGroupPoint *prevend = segments[permutation.back()].GetEndPoint(iSwap, iEnd);
++                    for (std::vector<int>::iterator it = permutation.begin(); it != permutation.end(); it++) {
++                        OrderingGroupPoint *thisbeg = segments[*it].GetBeginPoint(iSwap, iEnd);
++                        DebugTrace2TSP(("IMP 0F=%d %d %.6lf", thisbeg->group->index, thisbeg->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
++                        DebugTrace2TSP(("IMP 0T=%d %d %.6lf", prevend->group->index, prevend->indexInGroup, Geom::distance(thisbeg->point, prevend->point)));
++                        prevend = segments[*it].GetEndPoint(iSwap, iEnd);
++                    }
++                }
++
++                nTrials++;
++
++                // bit 0 is always 0, because the first segment is kept fixed
++                iEnd += 2;
++            } while (iEnd & endMask);
++            iSwap++;
++        } while (iSwap & swapMask);
++        // first segment is kept fixed
++    } while (std::next_permutation(permutation.begin() + 1, permutation.end()));
++
++    if (improved) {
++        DebugTrace2TSP(("Improvement %lf->%lf in %d", olddist, distBest, nTrials));
++        // change the connections
++
++        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
++            DebugTrace2TSP(("WAS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
++            DebugTrace2TSP(("WAS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
++        }
++        DebugTrace2TSP(("OLDDIST %.6lf delta %.6lf", olddist, olddist - (*longestConnect)->Distance()));
++        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
++        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
++
++        int perm = permutationBest.back();
++
++        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
++            (*it)->Connect(1, segments[ perm ].GetEndPoint(iSwapBest, iEndBest));
++            perm = permutationBest[ it - connections.begin() ];
++            (*it)->Connect(0, segments[ perm ].GetBeginPoint(iSwapBest, iEndBest));
++
++        }
++
++        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
++            DebugTrace2TSP(("IS 0F=%d %d %.6lf", (*it)->points[0]->group->index, (*it)->points[0]->indexInGroup, (*it)->Distance()));
++            DebugTrace2TSP(("IS 0T=%d %d %.6lf", (*it)->points[1]->group->index, (*it)->points[1]->indexInGroup, (*it)->Distance()));
++        }
++
++        (*longestConnect) = longestOutside;
++        for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); ++it) {
++            if ((*it)->Distance() > (*longestConnect)->Distance()) {
++                *longestConnect = *it;
++            }
++        }
++        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[0]->group->index, (*longestConnect)->points[0]->indexInGroup, (*longestConnect)->Distance()));
++        DebugTrace2TSP(("LONG =%d %d %.6lf", (*longestConnect)->points[1]->group->index, (*longestConnect)->points[1]->indexInGroup, (*longestConnect)->Distance()));
++    }
++
++    return improved;
++}
++
++// Check if connections form a tour
++void AssertIsTour(std::vector<OrderingGroup *> &groups, std::vector<OrderingGroupConnection *> &connections, OrderingGroupConnection *longestConnection)
++{
++    for (std::vector<OrderingGroupConnection *>::iterator it = connections.begin(); it != connections.end(); it++) {
++        for (int i = 0; i < 2; i++) {
++            OrderingGroupPoint *pnt = (*it)->points[i];
++            assert(pnt->connection == *it);
++            assert(pnt->connection->points[pnt->indexInConnection] == pnt);
++            assert(pnt->group->endpoints[pnt->indexInGroup] == pnt);
++        }
++    }
++
++    Coord length1 = 0;
++    Coord longest1 = 0;
++    OrderingGroupPoint *current = connections.front()->points[0];
++
++    for (unsigned int n = 0; n < connections.size(); n++) {
++        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()));
++        Coord length = current->connection->Distance();
++        length1 += length;
++        longest1 = std::max(length, longest1);
++        current = current->GetOtherEndConnection();
++
++        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()));
++        current = current->GetOtherEndGroup();
++    }
++    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]));
++    assert(current == connections.front()->points[0]);
++
++    // The other direction
++    Coord length2 = 0;
++    Coord longest2 = 0;
++    current = connections.front()->points[0];
++    for (unsigned int n = 0; n < connections.size(); n++) {
++        current = current->GetOtherEndGroup();
++        Coord length = current->connection->Distance();
++        length2 += length;
++        longest2 = std::max(length, longest2);
++        current = current->GetOtherEndConnection();
++    }
++    assert(current == connections.front()->points[0]);
++
++    DebugTrace1TSP(("Tour length %.6lf(%.6lf) longest %.6lf(%.6lf) remaining %.6lf(%.6lf)", length1, length2, longest1, longest2, length1 - longest1, length2 - longest2));
++}
++
++// Bring a tour into linear order after a modification
++
++/* I would like to avoid this.
++ * It is no problem to travel a tour with changing directions using the GetOtherEnd functions,
++ * 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.
++ * In the end it is probably better to implement the Lin-Kernighan algorithm which avoids this problem by creating connected changes.  */
++
++void LinearizeTour(std::vector<OrderingGroupConnection *> &connections)
++{
++    OrderingGroupPoint *current = connections.front()->points[0];
++
++    for (unsigned int iNew = 0; iNew < connections.size(); iNew++) {
++        // swap the connection at location n with the current connection
++        OrderingGroupConnection *connection = current->connection;
++        unsigned int iOld = connection->index;
++        assert(connections[iOld] == connection);
++
++        connections[iOld] = connections[iNew];
++        connections[iNew] = connection;
++        connections[iOld]->index = iOld;
++        connections[iNew]->index = iNew;
++
++        // swap the points of a connection
++        assert(current == connection->points[0] || current == connection->points[1]);
++        if (current != connection->points[0]) {
++            connection->points[1] = connection->points[0];
++            connection->points[0] = current;
++            connection->points[1]->indexInConnection = 1;
++            connection->points[0]->indexInConnection = 0;
++        }
++
++        current = current->GetOtherEndConnection();
++        current = current->GetOtherEndGroup();
++    }
++}
++
++// Use some Traveling Salesman Problem (TSP) like heuristics to bring several groups into a
++// order with as short as possible interconnection paths
++
++void OrderGroups(std::vector<OrderingGroup *> *groups, const int nDims)
++{
++    // There is no point in ordering just one group
++    if (groups->size() <= 1) {
++        return;
++    }
++
++    // Initialize the endpoints for all groups
++    for (std::vector<OrderingGroup *>::iterator it = groups->begin(); it != groups->end(); ++it) {
++        (*it)->SetEndpoints();
++    }
++
++    // Find the neighboring points for all end points of all groups and sort by distance
++    for (std::vector<OrderingGroup *>::iterator itThis = groups->begin(); itThis != groups->end(); ++itThis) {
++        for (int i = 0; i < (*itThis)->nEndPoints; i++) {
++            // This can be up to 2x too large, but still better than incrementing the size
++            (*itThis)->endpoints[i]->nearest.reserve(4 * groups->size());
++        }
++
++        for (std::vector<OrderingGroup *>::iterator itNghb = groups->begin(); itNghb != groups->end(); ++itNghb) {
++            if (itThis != itNghb) {
++                (*itThis)->AddNeighbors(*itNghb);
++            }
++        }
++
++        for (int i = 0; i < (*itThis)->nEndPoints; i++) {
++            std::sort((*itThis)->endpoints[i]->nearest.begin(), (*itThis)->endpoints[i]->nearest.end(), OrderingGroupNeighbor::Compare);
++        }
++    }
++
++    // =========== Step 1: Create a simple nearest neighbor chain ===========
++
++    // Vector of connection points
++    std::vector<OrderingGroupConnection *> connections;
++    connections.reserve(groups->size());
++    // Total Jump Distance
++    Coord total = 0.0;
++
++    // Start with the first group and connect always with nearest unused point
++    OrderingGroupPoint *crnt = groups->front()->endpoints[0];
++
++    // The longest connection is ignored (we don't want cycles)
++    OrderingGroupConnection *longestConnect = 0;
++
++    for (unsigned int nConnected = 0; nConnected < groups->size(); nConnected++) {
++        // Mark both end points of the current segment as used
++        crnt->UsePoint();
++        crnt = crnt->GetOtherEndGroup();
++        crnt->UsePoint();
++
++        // if this is the last segment, Mark start point of first segment as unused,
++        // so that the end can connect to it
++        if (nConnected == groups->size() - 1) {
++            groups->front()->endpoints[0]->UnusePoint();
++        }
++
++        // connect to next segment
++        OrderingGroupNeighbor *nghb = crnt->FindNearestUnused();
++        connections.push_back(new OrderingGroupConnection(crnt, nghb->point, connections.size()));
++        total += nghb->distance;
++        crnt = nghb->point;
++
++        if (!longestConnect || nghb->distance > longestConnect->Distance()) {
++            longestConnect = connections.back();
++        }
++    }
++
++    DebugTrace1TSP(("Total jump distance %.3lf (closed)", total));
++    DebugTrace1TSP(("Total jump distance %.3lf (open)", total - longestConnect->Distance()));
++
++    AssertIsTour(*groups, connections, longestConnect);
++
++    // =========== Step 2: Choose nDims segments to clear and reconnect ===========
++
++    bool improvement;
++    int nRuns = 0;
++    int nTrials = 0;
++    int nImprovements = 0;
++
++    do {
++        improvement = false;
++        nRuns ++;
++        std::vector< std::vector<OrderingGroupConnection *>::iterator > iterators;
++
++        for (
++            triangleit_begin(iterators, connections.begin(), connections.end(), nDims);
++            triangleit_test(iterators, connections.end());
++            triangleit_incr(iterators, connections.end())
++        ) {
++            nTrials ++;
++
++            Coord dist = 0;
++
++            std::vector<OrderingSegment> segments(iterators.size());
++            std::vector<OrderingGroupConnection *> changedconnections;
++            changedconnections.reserve(3);
++            OrderingGroupConnection *prev = *iterators.back();
++
++
++            for (size_t i = 0; i < iterators.size(); i++) {
++                dist += (*iterators[i])->Distance();
++                segments[i].AddPoint(prev->points[1]);
++                segments[i].AddPoint((*iterators[i])->points[0]);
++                prev = *iterators[i];
++                changedconnections.push_back(*iterators[i]);
++            }
++
++            if (FindShortestReconnect(segments, changedconnections, connections, &longestConnect, &total, dist)) {
++                nImprovements ++;
++
++                AssertIsTour(*groups, connections, longestConnect);
++                LinearizeTour(connections);
++                AssertIsTour(*groups, connections, longestConnect);
++                improvement = true;
++            }
++        }
++    } while (improvement && nRuns < 10);
++
++    DebugTrace1TSP(("Finished after %d rounds, %d trials, %d improvements", nRuns, nTrials, nImprovements));
++
++    // =========== Step N: Create vector of groups from vector of connection points ===========
++
++    std::vector<OrderingGroup *> result;
++    result.reserve(groups->size());
++
++    // Go through the groups starting with the longest connection (which is this way left out)
++    {
++        OrderingGroupPoint *current = longestConnect->points[1];
++
++        for (unsigned int n = 0; n < connections.size(); n++) {
++            result.push_back(current->group);
++            current->SetRevInGroup();
++            current = current->GetOtherEndGroup();
++            current = current->GetOtherEndConnection();
++        }
++    }
++
++    assert(result.size() == groups->size());
++    assert_unique(result);
++
++    delete_and_clear(connections);
++
++    *groups = result;
++}
++
++// Global optimization of path length
++
++void OrderingAdvanced(std::vector<OrderingInfo> &infos, int nDims)
++{
++    if (infos.size() < 3) {
++        return;
++    }
++
++    // Create extended ordering info vector and copy data from normal ordering info
++    std::vector<OrderingInfoEx *> infoex;
++    infoex.reserve(infos.size());
++
++    for (std::vector<OrderingInfo>::const_iterator it = infos.begin(); it != infos.end();) {
++        // Note: This assumes that the index in the OrderingInfo matches the vector index!
++        infoex.push_back(new OrderingInfoEx(*it, infoex.size()));
++        ++it;
++        while (it != infos.end() && it->begOrig == infoex.back()->end.point) {
++            infoex.back()->end.point = it->endOrig;
++            infoex.back()->origIndices.push_back(it->index);
++            ++it;
++        }
++    }
++
++    // Find closest 2 points for each point and enforce that 2nd nearest is not further away than 1.8xthe nearest
++    // If this is not the case, clear nearest and 2nd nearest point
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++        (*it)->beg.FindNearest2(infoex);
++        (*it)->end.FindNearest2(infoex);
++    }
++
++    DebugTraceGrouping(
++        DebugTrace2(("STEP1"));
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++    (*it)->beg.Dump();
++        (*it)->end.Dump();
++    }
++    )
++
++    // Make sure the nearest points are mutual
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++        (*it)->beg.EnforceMutual();
++        (*it)->end.EnforceMutual();
++    }
++
++    DebugTraceGrouping(
++        DebugTrace2(("STEP2"));
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++    (*it)->beg.Dump();
++        (*it)->end.Dump();
++    }
++    )
++
++    // Make sure the nearest points for begin and end lead to the same sub-path (same index)
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++        (*it)->beg.EnforceSymmetric((*it)->end);
++        (*it)->end.EnforceSymmetric((*it)->beg);
++    }
++
++    DebugTraceGrouping(
++        DebugTrace2(("STEP3"));
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++    (*it)->beg.Dump();
++        (*it)->end.Dump();
++    }
++    )
++
++    // The remaining nearest neighbors should be 100% non ambiguous, so group them
++    std::vector<OrderingGroup *> groups;
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++        (*it)->MakeGroup(infoex, &groups);
++    }
++
++    // Create single groups for ungrouped lines
++    std::vector<OrderingInfo> result;
++    result.reserve(infos.size());
++    int nUngrouped = 0;
++    for (std::vector<OrderingInfoEx *>::iterator it = infoex.begin(); it != infoex.end(); ++it) {
++        if (!(*it)->grouped) {
++            groups.push_back(new OrderingGroup(groups.size()));
++            groups.back()->items.push_back(*it);
++            nUngrouped++;
++        }
++    }
++
++    DebugTraceGrouping(
++        DebugTrace2(("Ungrouped lines = %d", nUngrouped));
++        DebugTrace2(("%d Groups found", groups.size()));
++    for (std::vector<OrderingGroup *>::iterator it = groups.begin(); it != groups.end(); ++it) {
++    DebugTrace2(("Group size %d", (*it)->items.size()));
++    }
++    )
++
++    // Order groups, so that the connection path gets shortest
++    OrderGroups(&groups, nDims);
++
++    // Copy grouped lines to output
++    for (std::vector<OrderingGroup *>::iterator itGroup = groups.begin(); itGroup != groups.end(); ++itGroup) {
++        for (unsigned int iItem = 0; iItem < (*itGroup)->items.size(); iItem++) {
++            unsigned int iItemRev = (*itGroup)->revItemList ? (*itGroup)->items.size() - 1 - iItem : iItem;
++            OrderingInfoEx *item = (*itGroup)->items[iItemRev];
++
++            // If revItems is false, even items shall have reverse=false
++            // In this case ( ( iItem & 1 ) == 0 )== true, revItems=false, (true==false) == false
++            bool reverse = ((iItem & 1) == 0) == (*itGroup)->revItems;
++            if (!reverse) {
++                for (std::vector<int>::iterator itOrig = item->origIndices.begin(); itOrig != item->origIndices.end(); ++itOrig) {
++                    result.push_back(infos[*itOrig]);
++                    result.back().reverse = false;
++                }
++            } else {
++                for (std::vector<int>::reverse_iterator itOrig = item->origIndices.rbegin(); itOrig != item->origIndices.rend(); ++itOrig) {
++                    result.push_back(infos[*itOrig]);
++                    result.back().reverse = true;
++                }
++            }
++        }
++        result.back().connect = true;
++    }
++
++
++    delete_and_clear(groups);
++    delete_and_clear(infoex);
++
++    infos = result;
++}
++
++} // namespace LPEEmbroderyStitchOrdering
++} // namespace LivePathEffect
++} // namespace Inkscape
 === added file 'src/live_effects/lpe-embrodery-stitch-ordering.h'
 --- src/live_effects/lpe-embrodery-stitch-ordering.h	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-embrodery-stitch-ordering.h	2017-06-05 19:01:49 +0000
@@ -0,0 +1,313 @@
++/*
++ * Sub-path Ordering functions for embroidery stitch LPE
++ *
++ * Copyright (C) 2016 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#ifndef INKSCAPE_LPE_EMBRODERY_STITCH_ORDERING_H
++#define INKSCAPE_LPE_EMBRODERY_STITCH_ORDERING_H
++
++#include "live_effects/effect.h"
++
++namespace Inkscape {
++namespace LivePathEffect {
++namespace LPEEmbroderyStitchOrdering {
++
++// Structure keeping information on the ordering and reversing of sub paths
++// Used for simple ordering functions like zig-zag
++
++struct OrderingInfo {
++    int   index;
++    bool  reverse;
++    bool  used;
++    bool  connect;
++    Geom::Point begOrig; // begin point in original orientation
++    Geom::Point endOrig; // end point in original orientation
++
++    Geom::Point GetBegOrig() const
++    {
++        return begOrig;
++    }
++    Geom::Point GetEndOrig() const
++    {
++        return endOrig;
++    }
++    Geom::Point GetBegRev() const
++    {
++        return reverse ? endOrig : begOrig;
++    }
++    Geom::Point GetEndRev() const
++    {
++        return reverse ? begOrig : endOrig;
++    }
++};
++
++// Structure for a path end-point in OrderingInfoEx.
++// This keeps information about the two nearest neighbor points.
++
++struct OrderingInfoEx;
++
++struct OrderingPoint {
++    OrderingPoint(const Geom::Point &pointIn, OrderingInfoEx *infoexIn, bool beginIn) :
++        point(pointIn),
++        infoex(infoexIn),
++        begin(beginIn)
++    {
++        nearest[0] = nearest[1] = 0;
++    }
++
++    // Check if both nearest values are valid
++    bool IsNearestValid() const
++    {
++        return nearest[0] && nearest[1];
++    }
++    // Check if at least one nearest values are valid
++    bool HasNearest() const
++    {
++        return nearest[0] || nearest[1];
++    }
++    // Find 2 nearest points to given point
++    void FindNearest2(const std::vector<OrderingInfoEx *> &infos);
++    // Check if "this" is among the nearest of its nearest
++    void EnforceMutual(void);
++    // Check if the subpath indices of this and other are the same, otherwise zero both nearest
++    void EnforceSymmetric(const OrderingPoint &other);
++    // Dump point information
++    void Dump(void);
++
++    Geom::Point point;
++    OrderingInfoEx *infoex;
++    bool  begin;
++    const OrderingPoint *nearest[2];
++};
++
++// Structure keeping information on the ordering and reversing of sub paths
++// Used for advanced ordering functions with block creation and Traveling Salesman Problem Optimization
++// A OrderingInfoEx may contain several original sub-paths in case sub-paths are directly connected.
++// Directly connected sub-paths happen e.g. after a slice boolean operation.
++
++struct OrderingGroup;
++
++struct OrderingInfoEx {
++    OrderingInfoEx(const OrderingInfo &infoIn, int idxIn) :
++        beg(infoIn.begOrig, this, true),
++        end(infoIn.endOrig, this, false),
++        idx(idxIn),
++        grouped(false)
++    {
++        origIndices.push_back(infoIn.index);
++    }
++
++    // If this element can be grouped (has neighbours) but is not yet grouped, create a new group
++    void MakeGroup(std::vector<OrderingInfoEx *> &infos, std::vector<OrderingGroup *> *groups);
++    // Add this and all connected elements to the group
++    void AddToGroup(std::vector<OrderingInfoEx *> &infos, OrderingGroup *group);
++
++    int idx;
++    bool grouped;      // true if this element has been grouped
++    OrderingPoint beg; // begin point in original orientation
++    OrderingPoint end; // end point in original orientation
++    std::vector<int> origIndices; // Indices of the original OrderInfos (more than 1 if directly connected
++};
++
++// Neighbor information for OrderingGroupPoint - a distance and a OrderingGroupPoint
++
++struct OrderingGroupPoint;
++
++struct OrderingGroupNeighbor {
++    OrderingGroupNeighbor(OrderingGroupPoint *me, OrderingGroupPoint *other);
++
++    // Distance from owner of this neighbor info
++    Geom::Coord distance;
++    // Neighbor point (which in turn contains a pointer to the neighbor group
++    OrderingGroupPoint *point;
++
++    // Comparison function for sorting by distance
++    static bool Compare(const OrderingGroupNeighbor &a, const OrderingGroupNeighbor &b);
++};
++
++// An end point in an OrderingGroup, with nearest neighbor information
++
++struct OrderingGroupConnection;
++
++struct OrderingGroupPoint {
++    OrderingGroupPoint(const Geom::Point &pointIn, OrderingGroup *groupIn, int indexIn, bool beginIn, bool frontIn) :
++        point(pointIn),
++        group(groupIn),
++        indexInGroup(indexIn),
++        connection(0),
++        indexInConnection(0),
++        begin(beginIn),
++        front(frontIn),
++        used(false)
++    {
++    }
++
++    // Find the nearest unused neighbor point
++    OrderingGroupNeighbor *FindNearestUnused(void);
++    // Return the other end in the group of the point
++    OrderingGroupPoint *GetOtherEndGroup(void);
++    // Return the alternate point (if one exists), 0 otherwise
++    OrderingGroupPoint *GetAltPointGroup(void);
++    // Sets the rev flags in the group assuming that the group starts with this point
++    void SetRevInGroup(void);
++    // Mark an end point as used and also mark the two other alternating points as used
++    // Returns the used point
++    void UsePoint(void);
++    // Mark an end point as unused and possibly also mark the two other alternating points as unused
++    // Returns the used point
++    void UnusePoint(void);
++    // Return the other end in the connection
++    OrderingGroupPoint *GetOtherEndConnection(void);
++
++    // The coordinates of the point
++    Geom::Point point;
++    // The group to which the point belongs
++    OrderingGroup *group;
++    // The end-point index within the group
++    int indexInGroup;
++    // The connection, which connects this point
++    OrderingGroupConnection *connection;
++    // The end point index in the connection
++    int indexInConnection;
++    // True if this is a begin point (rather than an end point)
++    bool begin;
++    // True if this is a front point (rather than a back point)
++    bool front;
++    // True if the point is used/connected to another point
++    bool used;
++    // The nearest neighbors, to which this group end point may connect
++    std::vector<OrderingGroupNeighbor> nearest;
++};
++
++// A connection between two points/groups
++struct OrderingGroupConnection {
++    OrderingGroupConnection(OrderingGroupPoint *fromIn, OrderingGroupPoint *toIn, int indexIn) :
++        index(indexIn)
++    {
++        assert(fromIn->connection == 0);
++        assert(toIn->connection == 0);
++        points[0] = 0;
++        points[1] = 0;
++        Connect(0, fromIn);
++        Connect(1, toIn);
++    }
++
++    // Connect one of the conection endpoints to the given point
++    void Connect(int index, OrderingGroupPoint *point)
++    {
++        assert(point);
++        points[index] = point;
++        point->connection = this;
++        point->indexInConnection = index;
++    }
++
++    // Get length of connection
++    Geom::Coord Distance()
++    {
++        return Geom::distance(points[0]->point, points[1]->point);
++    }
++
++    OrderingGroupPoint *points[2];
++    // index of connection in the connections vector (just for debugging)
++    int index;
++};
++
++// A group of OrderingInfoEx, which build a block in path interconnect length optimization.
++// A block can have two sets of endpoints.
++// If a block has 2 sets of endpoints, one can swap between the two sets.
++
++struct OrderingGroup {
++    OrderingGroup(int indexIn) :
++        nEndPoints(0),
++        revItemList(false),
++        revItems(false),
++        index(indexIn)
++    {
++        for (int i = 0; i < sizeof(endpoints) / sizeof(*endpoints); i++) {
++            endpoints[i] = 0;
++        }
++    }
++
++    ~OrderingGroup()
++    {
++        for (int i = 0; i < nEndPoints; i++) {
++            delete endpoints[i];
++        }
++    }
++
++    // Set the endpoints of a group from the items
++    void SetEndpoints(void);
++    // Add all points from another group as neighbors
++    void AddNeighbors(OrderingGroup *nghb);
++    // Mark an end point as used and also mark the two other alternating points as used
++    // Returns the used point
++    OrderingGroupPoint *UsePoint(int index);
++    // Mark an end point as unused and possibly also mark the two other alternating points as unused
++    // Returns the used point
++    void UnusePoint(int index);
++
++    // Items on the group
++    std::vector<OrderingInfoEx *> items;
++    // End points of the group
++    OrderingGroupPoint *endpoints[4];
++    // Number of endpoints used (either 2 or 4)
++    int nEndPoints;
++    // Index of the group (just for debugging purposes)
++    int index;
++    // If true, the items in the group shall be output from back to front.
++    bool revItemList;
++    // If false, the individual items are output alternatingly normal-reversed
++    // If true, the individual items are output alternatingly reversed-normal
++    bool revItems;
++};
++
++// A segment is either a OrderingGroup or a series of groups and connections.
++// Usually a segment has just 2 end points.
++// If a segment is just one ordering group, it has the same number of end points as the ordering group
++// A main difference between a segment and a group is that the segment does not own the end points.
++
++struct OrderingSegment {
++    OrderingSegment() :
++        nEndPoints(0),
++        endbit(0),
++        swapbit(0)
++    {}
++
++    // Add an end point
++    void AddPoint(OrderingGroupPoint *point);
++    // Get begin point (taking swap and end bit into account
++    OrderingGroupPoint *GetBeginPoint(unsigned int iSwap, unsigned int iEnd);
++    // Get end point (taking swap and end bit into account
++    OrderingGroupPoint *GetEndPoint(unsigned int iSwap, unsigned int iEnd);
++
++    // End points of the group
++    OrderingGroupPoint *endpoints[4];
++    // Number of endpoints used (either 2 or 4)
++    int nEndPoints;
++    // bit index in the end counter
++    int endbit;
++    // bit index in the swap counter
++    int swapbit;
++};
++
++
++// Sub-path reordering: do nothing - keep original order
++void OrderingOriginal(std::vector<OrderingInfo> &infos);
++
++// Sub-path reordering: reverse every other sub path
++void OrderingZigZag(std::vector<OrderingInfo> &infos, bool revfirst);
++
++// Sub-path reordering: continue with the neartest start or end point of yet unused sub paths
++void OrderingClosest(std::vector<OrderingInfo> &infos, bool revfirst);
++
++// Global optimization of path length
++void OrderingAdvanced(std::vector<OrderingInfo> &infos, int nDims);
++
++} //LPEEmbroderyStitchOrdering
++} //namespace LivePathEffect
++} //namespace Inkscape
++
++#endif
 === added file 'src/live_effects/lpe-embrodery-stitch.cpp'
 --- src/live_effects/lpe-embrodery-stitch.cpp	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-embrodery-stitch.cpp	2017-06-05 19:01:49 +0000
@@ -0,0 +1,400 @@
++/*
++ * Embroidery stitch live path effect (Implementation)
++ *
++ * Copyright (C) 2016 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#include "ui/widget/scalar.h"
++#include <glibmm/i18n.h>
++
++#include "live_effects/lpe-embrodery-stitch.h"
++#include "live_effects/lpe-embrodery-stitch-ordering.h"
++
++#include <2geom/path.h>
++#include <2geom/piecewise.h>
++#include <2geom/sbasis.h>
++#include <2geom/sbasis-geometric.h>
++#include <2geom/bezier-to-sbasis.h>
++#include <2geom/sbasis-to-bezier.h>
++
++namespace Inkscape {
++namespace LivePathEffect {
++
++using namespace Geom;
++using namespace LPEEmbroderyStitchOrdering;
++
++static const Util::EnumData<LPEEmbroderyStitch::order_method> OrderMethodData[LPEEmbroderyStitch::order_method_count] = {
++    { LPEEmbroderyStitch::order_method_no_reorder, N_("no reordering"),                                "no-reorder" },
++    { LPEEmbroderyStitch::order_method_zigzag,            N_("zig-zag"),                               "zig-zag" },
++    { LPEEmbroderyStitch::order_method_zigzag_rev_first,  N_("zig-zag, reverse first"),                "zig-zag-rev-first" },
++    { LPEEmbroderyStitch::order_method_closest,           N_("closest"),                               "closest" },
++    { LPEEmbroderyStitch::order_method_closest_rev_first, N_("closest, reverse first"),                "closest-rev-first" },
++    { LPEEmbroderyStitch::order_method_tsp_kopt_2,        N_("traveling salesman 2-opt (fast, bad)"),  "tsp-2opt" },
++    { LPEEmbroderyStitch::order_method_tsp_kopt_3,        N_("traveling salesman 3-opt (fast, ok)"),   "tsp-3opt" },
++    { LPEEmbroderyStitch::order_method_tsp_kopt_4,        N_("traveling salesman 4-opt (seconds)"),    "tsp-4opt" },
++    { LPEEmbroderyStitch::order_method_tsp_kopt_5,        N_("traveling salesman 5-opt (miutes)"),     "tsp-5opt" }
++};
++
++static const Util::EnumDataConverter<LPEEmbroderyStitch::order_method>
++OrderMethodConverter(OrderMethodData, sizeof(OrderMethodData) / sizeof(*OrderMethodData));
++
++static const Util::EnumData<LPEEmbroderyStitch::connect_method> ConnectMethodData[LPEEmbroderyStitch::connect_method_count] = {
++    { LPEEmbroderyStitch::connect_method_line, N_("straight line"), "line" },
++    { LPEEmbroderyStitch::connect_method_move_point_from, N_("move to begin"), "move-begin" },
++    { LPEEmbroderyStitch::connect_method_move_point_mid, N_("move to middle"), "move-middle" },
++    { LPEEmbroderyStitch::connect_method_move_point_to, N_("move to end"), "move-end" }
++};
++
++static const Util::EnumDataConverter<LPEEmbroderyStitch::connect_method>
++ConnectMethodConverter(ConnectMethodData, sizeof(ConnectMethodData) / sizeof(*ConnectMethodData));
++
++LPEEmbroderyStitch::LPEEmbroderyStitch(LivePathEffectObject *lpeobject) :
++    Effect(lpeobject),
++    ordering(_("Ordering method"), _("Method used to order sub paths"), "ordering", OrderMethodConverter, &wr, this, order_method_no_reorder),
++    connection(_("Connection method"), _("Method to connect end points of sub paths"), "connection", ConnectMethodConverter, &wr, this, connect_method_line),
++    stitch_length(_("Stitch length"), _("If not 0, linearize path with given step length"), "stitch-length", &wr, this, 10.0),
++    stitch_min_length(_("Minimum stitch length [%]"), _("Combine steps shorter than this [%]"), "stitch-min-length", &wr, this, 25.0),
++    stitch_pattern(_("Stitch pattern"), _("Select between different stitch patterns"), "stitch_pattern", &wr, this, 0),
++    show_stitches(_("Show stitches"), _("Show stitches as small gaps (just for inspection - don't use for output)"), "show-stitches", &wr, this, false),
++    show_stitch_gap(_("Show stitch gap"), _("Gap between stitches when showing stitches"), "show-stitch-gap", &wr, this, 0.5),
++    jump_if_longer(_("Jump if longer"), _("Jump connection if longer than"), "jump-if-longer", &wr, this, 100)
++{
++    registerParameter(dynamic_cast<Parameter *>(&ordering));
++    registerParameter(dynamic_cast<Parameter *>(&connection));
++    registerParameter(dynamic_cast<Parameter *>(&stitch_length));
++    registerParameter(dynamic_cast<Parameter *>(&stitch_min_length));
++    registerParameter(dynamic_cast<Parameter *>(&stitch_pattern));
++    registerParameter(dynamic_cast<Parameter *>(&show_stitches));
++    registerParameter(dynamic_cast<Parameter *>(&show_stitch_gap));
++    registerParameter(dynamic_cast<Parameter *>(&jump_if_longer));
++
++    stitch_length.param_set_digits(1);
++    stitch_length.param_set_range(1, 10000);
++    stitch_min_length.param_set_digits(1);
++    stitch_min_length.param_set_range(0, 100);
++    stitch_pattern.param_make_integer();
++    stitch_pattern.param_set_range(0, 2);
++    show_stitch_gap.param_set_range(0.001, 10);
++    jump_if_longer.param_set_range(0.0, 1000000);
++}
++
++LPEEmbroderyStitch::~LPEEmbroderyStitch()
++{
++
++}
++
++double LPEEmbroderyStitch::GetPatternInitialStep(int pattern, int line)
++{
++    switch (pattern) {
++    case 0:
++        return 0.0;
++
++    case 1:
++        switch (line % 4) {
++        case 0:
++            return 0.0;
++        case 1:
++            return 0.25;
++        case 2:
++            return 0.50;
++        case 3:
++            return 0.75;
++        }
++        return 0.0;
++
++    case 2:
++        switch (line % 4) {
++        case 0:
++            return 0.0;
++        case 1:
++            return 0.5;
++        case 2:
++            return 0.75;
++        case 3:
++            return 0.25;
++        }
++        return 0.0;
++
++    default:
++        return 0.0;
++    }
++
++}
++
++Point LPEEmbroderyStitch::GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
++{
++    Point start_this = info[i].GetBegRev();
++
++    if (i == 0) {
++        return start_this;
++    }
++
++    if (!info[i - 1].connect) {
++        return start_this;
++    }
++
++    Point end_prev = info[i - 1].GetEndRev();
++
++    switch (connection.get_value()) {
++    case connect_method_line:
++        return start_this;
++    case connect_method_move_point_from:
++        return end_prev;
++    case connect_method_move_point_mid:
++        return 0.5 * start_this + 0.5 * end_prev;
++    case connect_method_move_point_to:
++        return start_this;
++    default:
++        return start_this;
++    }
++}
++Point LPEEmbroderyStitch::GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i)
++{
++    Point end_this = info[i].GetEndRev();
++
++    if (i + 1 == info.size()) {
++        return end_this;
++    }
++
++    if (!info[i].connect) {
++        return end_this;
++    }
++
++    Point start_next = info[i + 1].GetBegRev();
++
++    switch (connection.get_value()) {
++    case connect_method_line:
++        return end_this;
++    case connect_method_move_point_from:
++        return end_this;
++    case connect_method_move_point_mid:
++        return 0.5 * start_next + 0.5 * end_this;
++    case connect_method_move_point_to:
++        return start_next;
++    default:
++        return end_this;
++    }
++}
++
++Point LPEEmbroderyStitch::GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
++{
++    if (info[i].reverse) {
++        return GetEndPointInterpolAfterRev(info, i);
++    } else {
++        return GetStartPointInterpolAfterRev(info, i);
++    }
++}
++
++Point LPEEmbroderyStitch::GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i)
++{
++    if (info[i].reverse) {
++        return GetStartPointInterpolAfterRev(info, i);
++    } else {
++        return GetEndPointInterpolAfterRev(info, i);
++    }
++}
++
++PathVector LPEEmbroderyStitch::doEffect_path(PathVector const &path_in)
++{
++    if (path_in.size() >= 2) {
++        PathVector path_out;
++
++        // Create vectors with start and end points
++        std::vector<OrderingInfo> orderinginfos(path_in.size());
++        // connect next path to this one
++        bool connect_with_previous = false;
++
++        for (PathVector::const_iterator it = path_in.begin(); it != path_in.end(); ++it) {
++            OrderingInfo &info = orderinginfos[ it - path_in.begin() ];
++            info.index = it - path_in.begin();
++            info.reverse = false;
++            info.used = false;
++            info.connect = true;
++            info.begOrig = it->front().initialPoint();
++            info.endOrig = it->back().finalPoint();
++        }
++
++        // Compute sub-path ordering
++        switch (ordering.get_value()) {
++        case order_method_no_reorder:
++            OrderingOriginal(orderinginfos);
++            break;
++
++        case order_method_zigzag:
++            OrderingZigZag(orderinginfos, false);
++            break;
++
++        case order_method_zigzag_rev_first:
++            OrderingZigZag(orderinginfos, true);
++            break;
++
++        case order_method_closest:
++            OrderingClosest(orderinginfos, false);
++            break;
++
++        case order_method_closest_rev_first:
++            OrderingClosest(orderinginfos, true);
++            break;
++
++        case order_method_tsp_kopt_2:
++            OrderingAdvanced(orderinginfos, 2);
++            break;
++
++        case order_method_tsp_kopt_3:
++            OrderingAdvanced(orderinginfos, 3);
++            break;
++
++        case order_method_tsp_kopt_4:
++            OrderingAdvanced(orderinginfos, 4);
++            break;
++
++        case order_method_tsp_kopt_5:
++            OrderingAdvanced(orderinginfos, 5);
++            break;
++
++        }
++
++        // Iterate over sub-paths in order found above
++        // Divide paths into stitches (currently always equidistant)
++        // Interpolate between neighboring paths, so that their ends coincide
++        for (std::vector<OrderingInfo>::const_iterator it = orderinginfos.begin(); it != orderinginfos.end(); ++it) {
++            // info index
++            unsigned iInfo = it - orderinginfos.begin();
++            // subpath index
++            unsigned iPath = it->index;
++            // decide of path shall be reversed
++            bool reverse = it->reverse;
++            // minimum stitch length in absolute measure
++            double stitch_min_length_abs = stitch_min_length * 0.01 * stitch_length;
++
++            // convert path to piecewise
++            Piecewise<D2<SBasis> > pwOrig = path_in[iPath].toPwSb();
++            // make piecewise equidistant in time
++            Piecewise<D2<SBasis> > pwEqdist = arc_length_parametrization(pwOrig);
++            Piecewise<D2<SBasis> > pwStitch;
++
++            // cut into stitches
++            double cutpos = 0.0;
++            Interval pwdomain = pwEqdist.domain();
++
++            // step length of first stitch
++            double step = GetPatternInitialStep(stitch_pattern, iInfo) * stitch_length;
++            if (step < stitch_min_length_abs) {
++                step += stitch_length;
++            }
++
++            bool last = false;
++            bool first = true;
++            double posnext;
++            for (double pos = pwdomain.min(); !last; pos = posnext, cutpos += 1.0) {
++                // start point
++                Point p1;
++                if (first) {
++                    p1 = GetStartPointInterpolBeforeRev(orderinginfos, iInfo);
++                    first = false;
++                } else {
++                    p1 =  pwEqdist.valueAt(pos);
++                }
++
++                // end point of this stitch
++                Point p2;
++                posnext = pos + step;
++                // last stitch is to end
++                if (posnext >= pwdomain.max() - stitch_min_length_abs) {
++                    p2 = GetEndPointInterpolBeforeRev(orderinginfos, iInfo);
++                    last = true;
++                } else {
++                    p2 = pwEqdist.valueAt(posnext);
++                }
++
++                pwStitch.push_cut(cutpos);
++                pwStitch.push_seg(D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y]))));
++
++                // stitch length for all except first step
++                step = stitch_length;
++            }
++            pwStitch.push_cut(cutpos);
++
++            if (reverse) {
++                pwStitch = Geom::reverse(pwStitch);
++            }
++
++            if (it->connect && iInfo != orderinginfos.size() - 1) {
++                // Connect this segment with the previous segment by a straight line
++                Point end = pwStitch.lastValue();
++                Point start_next = GetStartPointInterpolAfterRev(orderinginfos, iInfo + 1);
++                // connect end and start point
++                if (end != start_next && distance(end, start_next) <= jump_if_longer) {
++                    cutpos += 1.0;
++                    pwStitch.push_seg(D2<SBasis>(SBasis(Linear(end[X], start_next[X])), SBasis(Linear(end[Y], start_next[Y]))));
++                    pwStitch.push_cut(cutpos);
++                }
++            }
++
++            if (show_stitches) {
++                for (std::vector< D2<SBasis> >::iterator it = pwStitch.segs.begin(); it != pwStitch.segs.end(); ++it) {
++                    // Create  anew piecewise with just one segment
++                    Piecewise<D2<SBasis> > pwOne;
++                    pwOne.push_cut(0);
++                    pwOne.push_seg(*it);
++                    pwOne.push_cut(1);
++
++                    // make piecewise equidistant in time
++                    Piecewise<D2<SBasis> > pwOneEqdist = arc_length_parametrization(pwOne);
++                    Interval pwdomain = pwOneEqdist.domain();
++
++                    // Compute the points of teh shortened piece
++                    Coord len = pwdomain.max() - pwdomain.min();
++                    Coord offs = 0.5 * (show_stitch_gap < 0.5 * len ? show_stitch_gap : 0.5 * len);
++                    Point p1 = pwOneEqdist.valueAt(pwdomain.min() + offs);
++                    Point p2 = pwOneEqdist.valueAt(pwdomain.max() - offs);
++                    Piecewise<D2<SBasis> > pwOneGap;
++
++                    // Create Linear SBasis
++                    D2<SBasis> sbasis = D2<SBasis>(SBasis(Linear(p1[X], p2[X])), SBasis(Linear(p1[Y], p2[Y])));
++
++                    // Convert to path and add to path list
++                    Geom::Path path = path_from_sbasis(sbasis , LPE_CONVERSION_TOLERANCE, false);
++                    path_out.push_back(path);
++                }
++            } else {
++                PathVector pathv = path_from_piecewise(pwStitch, LPE_CONVERSION_TOLERANCE);
++                for (size_t ipv = 0; ipv < pathv.size(); ipv++) {
++                    if (connect_with_previous) {
++                        path_out.back().append(pathv[ipv]);
++                    } else {
++                        path_out.push_back(pathv[ipv]);
++                    }
++                }
++            }
++
++            connect_with_previous = it->connect;
++        }
++
++        return path_out;
++    } else {
++        return path_in;
++    }
++}
++
++void
++LPEEmbroderyStitch::resetDefaults(SPItem const *item)
++{
++    Effect::resetDefaults(item);
++}
++
++
++/** /todo check whether this special case is necessary. It seems to "bug" editing behavior:
++ * scaling an object with transforms preserved behaves differently from scaling with
++ * transforms optimized (difference caused by this special method).
++ * special casing is probably needed, because rotation should not be propagated to the strokepath.
++ */
++void
++LPEEmbroderyStitch::transform_multiply(Affine const &postmul, bool set)
++{
++}
++
++} //namespace LivePathEffect
++} /* namespace Inkscape */
 === added file 'src/live_effects/lpe-embrodery-stitch.h'
 --- src/live_effects/lpe-embrodery-stitch.h	1970-01-01 00:00:00 +0000
 +++ src/live_effects/lpe-embrodery-stitch.h	2017-06-05 19:01:49 +0000
@@ -0,0 +1,78 @@
++/*
++ *  Embroidery stitch live path effect
++ *
++ * Copyright (C) 2016 Michael Soegtrop
++ *
++ * Released under GNU GPL, read the file 'COPYING' for more information
++ */
++
++#ifndef INKSCAPE_LPE_EMBRODERY_STITCH_H
++#define INKSCAPE_LPE_EMBRODERY_STITCH_H
++
++#include "live_effects/effect.h"
++#include "live_effects/parameter/parameter.h"
++#include "live_effects/parameter/bool.h"
++#include "live_effects/parameter/enum.h"
++#include "live_effects/lpe-embrodery-stitch-ordering.h"
++
++namespace Inkscape {
++namespace LivePathEffect {
++
++using namespace LPEEmbroderyStitchOrdering;
++
++class LPEEmbroderyStitch : public Effect {
++public:
++
++    LPEEmbroderyStitch(LivePathEffectObject *lpeobject);
++    virtual ~LPEEmbroderyStitch();
++
++    virtual Geom::PathVector doEffect_path(Geom::PathVector const &path_in);
++
++    virtual void resetDefaults(SPItem const *item);
++
++    virtual void transform_multiply(Geom::Affine const &postmul, bool set);
++
++    enum order_method {
++        order_method_no_reorder,
++        order_method_zigzag,
++        order_method_zigzag_rev_first,
++        order_method_closest,
++        order_method_closest_rev_first,
++        order_method_tsp_kopt_2,
++        order_method_tsp_kopt_3,
++        order_method_tsp_kopt_4,
++        order_method_tsp_kopt_5,
++        order_method_count
++    };
++    enum connect_method {
++        connect_method_line,
++        connect_method_move_point_from,
++        connect_method_move_point_mid,
++        connect_method_move_point_to,
++        connect_method_count
++    };
++
++private:
++    EnumParam<order_method> ordering;
++    EnumParam<connect_method> connection;
++    ScalarParam stitch_length;
++    ScalarParam stitch_min_length;
++    ScalarParam stitch_pattern;
++    BoolParam show_stitches;
++    ScalarParam show_stitch_gap;
++    ScalarParam jump_if_longer;
++
++    LPEEmbroderyStitch(const LPEEmbroderyStitch &);
++    LPEEmbroderyStitch &operator=(const LPEEmbroderyStitch &);
++
++    double GetPatternInitialStep(int pattern, int line);
++    Geom::Point GetStartPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i);
++    Geom::Point GetEndPointInterpolAfterRev(std::vector<OrderingInfo> const &info, unsigned i);
++    Geom::Point GetStartPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i);
++    Geom::Point GetEndPointInterpolBeforeRev(std::vector<OrderingInfo> const &info, unsigned i);
++};
++
++} //namespace LivePathEffect
++} //namespace Inkscape
++
++#endif

Inkscape

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

Commit message

Description of the change

Preview Diff

Subscribers