Adding upstream version 1.2.2.upstream/1.2.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1141 insertions, 0 deletions

diff --git a/src/live_effects/lpe-embrodery-stitch-ordering.cpp b/src/live_effects/lpe-embrodery-stitch-ordering.cpp
new file mode 100644
index 0000000..06129b2
--- /dev/null
+++ b/src/live_effects/lpe-embrodery-stitch-ordering.cpp
@@ -0,0 +1,1141 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Sub-path Ordering functions for embroidery stitch LPE (Implementation)
+ *
+ * Copyright (C) 2016 Michael Soegtrop
+ *
+ * Released under GNU GPL v2+, 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 iterable 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 (auto & info : infos) {
+        info.reverse = (info.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 = Geom::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 = Geom::infinity();
+    Coord dist1 = Geom::infinity();
+    nearest[0] = nullptr;
+    nearest[1] = nullptr;
+
+    for (auto info : infos) {
+        Coord dist = distance(point, info->beg.point);
+        if (dist < dist1) {
+            if (&info->beg != this && &info->end != this) {
+                if (dist < dist0) {
+                    nearest[1] = nearest[0];
+                    nearest[0] = &info->beg;
+                    dist1 = dist0;
+                    dist0 = dist;
+                } else {
+                    nearest[1] = &info->beg;
+                    dist1 = dist;
+                }
+            }
+        }
+
+        dist = distance(point, info->end.point);
+        if (dist < dist1) {
+            if (&info->beg != this && &info->end != this) {
+                if (dist < dist0) {
+                    nearest[1] = nearest[0];
+                    nearest[0] = &info->end;
+                    dist1 = dist0;
+                    dist0 = dist;
+                } else {
+                    nearest[1] = &info->end;
+                    dist1 = dist;
+                }
+            }
+        }
+    }
+}
+
+// Check if "this" is among the nearest of its nearest
+
+void OrderingPoint::EnforceMutual()
+{
+    if (nearest[0] && !(this == nearest[0]->nearest[0] || this == nearest[0]->nearest[1])) {
+        nearest[0] = nullptr;
+    }
+
+    if (nearest[1] && !(this == nearest[1]->nearest[0] || this == nearest[1]->nearest[1])) {
+        nearest[1] = nullptr;
+    }
+
+    if (nearest[1] && !nearest[0]) {
+        nearest[0] = nearest[1];
+        nearest[1] = nullptr;
+    }
+}
+
+// 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] = nullptr;
+    }
+
+    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] = nullptr;
+    }
+
+    if (nearest[1] && !nearest[0]) {
+        nearest[0] = nearest[1];
+        nearest[1] = nullptr;
+    }
+}
+
+void OrderingPoint::Dump()
+{
+    // COMMENTED TO SUPPRESS WARNING UNUSED AUTHOR TAKE IT UNCOMMENTED
+    // 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()
+{
+    for (auto & it : nearest) {
+        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 nullptr;
+}
+
+// Return the other end in the group of the point
+
+OrderingGroupPoint *OrderingGroupPoint::GetOtherEndGroup()
+{
+    return group->endpoints[ indexInGroup ^ 1 ];
+}
+
+// Return the alternate point (if one exists), 0 otherwise
+
+OrderingGroupPoint *OrderingGroupPoint::GetAltPointGroup()
+{
+    if (group->nEndPoints < 4) {
+        return nullptr;
+    }
+
+    OrderingGroupPoint *alt = group->endpoints[ indexInGroup ^ 2 ];
+    return alt->used ? nullptr : alt;
+}
+
+
+// Sets the rev flags in the group assuming that the group starts with this point
+
+void OrderingGroupPoint::SetRevInGroup()
+{
+    // 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()
+{
+    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()
+{
+    group->UnusePoint(indexInGroup);
+}
+
+// Return the other end in the connection
+OrderingGroupPoint *OrderingGroupPoint::GetOtherEndConnection()
+{
+    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()
+{
+    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.emplace_back(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 = nullptr;
+
+    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 (auto & allconnection : allconnections) {
+            if (allconnection->Distance() > length) {
+                if (!contains(connections, allconnection)) {
+                    longestOutside = allconnection;
+                    length = allconnection->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 (auto & segment : segments) {
+        segment.endbit = nEndBits++;
+        if (segment.nEndPoints == 4) {
+            segment.swapbit = nSwapBits++;
+        } else {
+            // bit 32 should always be 0
+            segment.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 (int & it : permutation) {
+                    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 (int & it : permutation) {
+                        // COMMENTED TO SUPPRESS WARNING UNUSED AUTHOR TAKE IT UNCOMMENTED
+                        //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 (auto & connection : connections) {
+            if (connection->Distance() > (*longestConnect)->Distance()) {
+                *longestConnect = connection;
+            }
+        }
+        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 (auto & connection : connections) {
+        for (auto pnt : connection->points) {
+            assert(pnt->connection == connection);
+            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 (auto & group : *groups) {
+        group->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 = nullptr;
+
+    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 (auto & it : infoex) {
+        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 (auto & it : infoex) {
+        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 (auto & it : infoex) {
+        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 (auto & group : groups) {
+        for (unsigned int iItem = 0; iItem < group->items.size(); iItem++) {
+            unsigned int iItemRev = group->revItemList ? group->items.size() - 1 - iItem : iItem;
+            OrderingInfoEx *item = group->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) == group->revItems;
+            if (!reverse) {
+                for (int & origIndice : item->origIndices) {
+                    result.push_back(infos[origIndice]);
+                    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