Adding upstream version 1.2.2.upstream/1.2.2upstream

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

1 files changed, 956 insertions, 0 deletions

diff --git a/src/path/path-boolop.cpp b/src/path/path-boolop.cpp
new file mode 100644
index 0000000..78f7281
--- /dev/null
+++ b/src/path/path-boolop.cpp
@@ -0,0 +1,956 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/** @file
+ * Boolean operations.
+ *//*
+ * Authors:
+ * see git history
+ *  Created by fred on Fri Dec 05 2003.
+ *  tweaked endlessly by bulia byak <buliabyak@users.sf.net>
+ *
+ * Copyright (C) 2018 Authors
+ * Released under GNU GPL v2+, read the file 'COPYING' for more information.
+ */
+
+#include <vector>
+
+#include <glibmm/i18n.h>
+#include <2geom/intersection-graph.h>
+#include <2geom/svg-path-parser.h> // to get from SVG on boolean to Geom::Path
+#include <2geom/utils.h>
+
+#include "path-boolop.h"
+#include "path-util.h"
+
+#include "message-stack.h"
+#include "path-chemistry.h"     // copy_object_properties()
+
+#include "helper/geom.h"        // pathv_to_linear_and_cubic_beziers()
+
+#include "livarot/Path.h"
+#include "livarot/Shape.h"
+
+#include "object/sp-flowtext.h"
+#include "object/sp-shape.h"
+#include "object/sp-text.h"
+
+#include "display/curve.h"
+
+#include "ui/icon-names.h"
+#include "ui/widget/canvas.h"  // Disable drawing during op
+
+#include "svg/svg.h"
+
+#include "xml/repr-sorting.h"
+
+using Inkscape::DocumentUndo;
+
+// fonctions utilitaires
+bool
+Ancetre(Inkscape::XML::Node *a, Inkscape::XML::Node *who)
+{
+    if (who == nullptr || a == nullptr)
+        return false;
+    if (who == a)
+        return true;
+    return Ancetre(a->parent(), who);
+}
+
+
+bool Inkscape::ObjectSet::pathUnion(const bool skip_undo, bool silent) {
+    BoolOpErrors result = pathBoolOp(bool_op_union, skip_undo, false, INKSCAPE_ICON("path-union"),
+                                     _("Union"), silent);
+    return DONE == result;
+}
+
+bool
+Inkscape::ObjectSet::pathIntersect(const bool skip_undo, bool silent)
+{
+    BoolOpErrors result = pathBoolOp(bool_op_inters, skip_undo, false, INKSCAPE_ICON("path-intersection"),
+                                     _("Intersection"), silent);
+    return DONE == result;
+}
+
+bool
+Inkscape::ObjectSet::pathDiff(const bool skip_undo, bool silent)
+{
+    BoolOpErrors result = pathBoolOp(bool_op_diff, skip_undo, false, INKSCAPE_ICON("path-difference"),
+                                     _("Difference"), silent);
+    return DONE == result;
+}
+
+bool
+Inkscape::ObjectSet::pathSymDiff(const bool skip_undo, bool silent)
+{
+    BoolOpErrors result = pathBoolOp(bool_op_symdiff, skip_undo, false, INKSCAPE_ICON("path-exclusion"),
+                                     _("Exclusion"), silent);
+    return DONE == result;
+}
+
+bool
+Inkscape::ObjectSet::pathCut(const bool skip_undo, bool silent)
+{
+    BoolOpErrors result = pathBoolOp(bool_op_cut, skip_undo, false, INKSCAPE_ICON("path-division"),
+                                     _("Division"), silent);
+    return DONE == result;
+}
+
+bool
+Inkscape::ObjectSet::pathSlice(const bool skip_undo, bool silent)
+{
+    BoolOpErrors result = pathBoolOp(bool_op_slice, skip_undo, false, INKSCAPE_ICON("path-cut"),
+                                     _("Cut path"), silent);
+    return DONE == result;
+}
+
+// helper for printing error messages, regardless of whether we have a GUI or not
+// If desktop == NULL, errors will be shown on stderr
+static void
+boolop_display_error_message(SPDesktop *desktop, Glib::ustring const &msg)
+{
+    if (desktop) {
+        desktop->messageStack()->flash(Inkscape::ERROR_MESSAGE, msg);
+    } else {
+        g_printerr("%s\n", msg.c_str());
+    }
+}
+
+/**
+ * Calculate the threshold for the given PathVector based
+ * on it's bounding box.
+ *
+ * @param path - The PathVector to calculate the threshold for.
+ * @param threshold - The starting threshold, usually 0.1
+ */
+double get_threshold(Geom::PathVector const &path, double threshold)
+{
+    auto maybe_box = path.boundsFast();
+    if (!maybe_box)
+        return threshold;
+    Geom::Rect box = *maybe_box;
+    double diagonal = Geom::distance(
+        Geom::Point(box[Geom::X].min(), box[Geom::Y].min()),
+        Geom::Point(box[Geom::X].max(), box[Geom::Y].max())
+    );
+    return threshold * (diagonal / 100);
+}
+
+/**
+ * Calculate the threshold for the given SPItem/SPShape based
+ * on it's bounding box (see PathVector get_threshold above)
+ *
+ * @param item - The SPItem to calculate the threshold for.
+ * @param threshold - The starting threshold, usually 0.1
+ */
+double get_threshold(SPItem const *item, double threshold)
+{
+    auto shape = dynamic_cast<SPShape const *>(item);
+    if (shape && shape->curve()) {
+        return get_threshold(shape->curve()->get_pathvector(), threshold);
+    }
+    return threshold;
+}
+
+void
+sp_flatten(Geom::PathVector &pathvector, FillRule fillkind)
+{
+    Path *orig = new Path;
+    orig->LoadPathVector(pathvector);
+    Shape *theShape = new Shape;
+    Shape *theRes = new Shape;
+    orig->ConvertWithBackData(1.0);
+    orig->Fill(theShape, 0);
+    theRes->ConvertToShape(theShape, fillkind);
+    Path *originaux[1];
+    originaux[0] = orig;
+    Path *res = new Path;
+    theRes->ConvertToForme(res, 1, originaux, true);
+
+    delete theShape;
+    delete theRes;
+    char *res_d = res->svg_dump_path();
+    delete res;
+    delete orig;
+    pathvector = sp_svg_read_pathv(res_d);
+}
+
+// boolean operations PathVectors A,B -> PathVector result.
+// This is derived from sp_selected_path_boolop
+// take the source paths from the file, do the operation, delete the originals and add the results
+// fra,fra are fill_rules for PathVectors a,b
+Geom::PathVector 
+sp_pathvector_boolop(Geom::PathVector const &pathva, Geom::PathVector const &pathvb, bool_op bop, 
+                     fill_typ fra, fill_typ frb, bool livarotonly, bool flattenbefore)
+{  
+    int error = 0;
+    return sp_pathvector_boolop(pathva, pathvb, bop, fra, frb, livarotonly, flattenbefore, error);
+}
+
+Geom::PathVector 
+sp_pathvector_boolop(Geom::PathVector const &pathva, Geom::PathVector const &pathvb, bool_op bop,
+                     fill_typ fra, fill_typ frb, bool livarotonly, bool flattenbefore, int &error)
+{       
+    if (!livarotonly) {
+        try {
+            Geom::PathVector a = pathv_to_linear_and_cubic_beziers(pathva);
+            Geom::PathVector b = pathv_to_linear_and_cubic_beziers(pathvb);
+            if (flattenbefore) {
+                sp_flatten(a, fra);
+                sp_flatten(b, frb);
+            }
+            Geom::PathVector out;
+            // dont change tolerande give errors on boolops
+            auto pig = Geom::PathIntersectionGraph(a, b, Geom::EPSILON);
+            if (bop == bool_op_inters) {
+                out = pig.getIntersection();
+            } else if (bop == bool_op_union) {
+                out = pig.getUnion();
+            
+            } else if (bop == bool_op_symdiff) {
+                out = pig.getXOR();
+            } else if (bop == bool_op_diff) {
+                out = pig.getBminusA(); //livarot order...
+            } else if (bop == bool_op_cut) {
+                out = pig.getBminusA();
+                auto tmp = pig.getIntersection();
+                out.insert(out.end(), tmp.begin(), tmp.end()); 
+            } else if (bop == bool_op_slice) {
+                // go to livarot
+                livarotonly = true;
+            }
+            if (!livarotonly) {
+                return out;
+            }
+        } catch (...) {
+            g_debug("Path Intersection Graph failed boolops, fallback to livarot");
+        }
+    }
+    error = 1;
+    // extract the livarot Paths from the source objects
+    // also get the winding rule specified in the style
+    int nbOriginaux = 2;
+    std::vector<Path *> originaux(nbOriginaux);
+    std::vector<FillRule> origWind(nbOriginaux);
+    origWind[0]=fra;
+    origWind[1]=frb;
+    Geom::PathVector patht;
+    // Livarot's outline of arcs is broken. So convert the path to linear and cubics only, for which the outline is created correctly. 
+    originaux[0] = Path_for_pathvector(pathv_to_linear_and_cubic_beziers( pathva));
+    originaux[1] = Path_for_pathvector(pathv_to_linear_and_cubic_beziers( pathvb));
+
+    // some temporary instances, first
+    Shape *theShapeA = new Shape;
+    Shape *theShapeB = new Shape;
+    Shape *theShape = new Shape;
+    Path *res = new Path;
+    res->SetBackData(false);
+
+    Path::cut_position *toCut=nullptr;
+    int nbToCut = 0;
+
+    if ( bop == bool_op_inters || bop == bool_op_union || bop == bool_op_diff || bop == bool_op_symdiff ) {
+        // true boolean op
+        // get the polygons of each path, with the winding rule specified, and apply the operation iteratively
+        originaux[0]->ConvertWithBackData(get_threshold(pathva, 0.1));
+
+        originaux[0]->Fill(theShape, 0);
+
+        theShapeA->ConvertToShape(theShape, origWind[0]);
+
+        originaux[1]->ConvertWithBackData(get_threshold(pathvb, 0.1));
+
+        originaux[1]->Fill(theShape, 1);
+
+        theShapeB->ConvertToShape(theShape, origWind[1]);
+        
+        theShape->Booleen(theShapeB, theShapeA, bop);
+
+    } else if ( bop == bool_op_cut ) {
+        // cuts= sort of a bastard boolean operation, thus not the axact same modus operandi
+        // technically, the cut path is not necessarily a polygon (thus has no winding rule)
+        // it is just uncrossed, and cleaned from duplicate edges and points
+        // then it's fed to Booleen() which will uncross it against the other path
+        // then comes the trick: each edge of the cut path is duplicated (one in each direction),
+        // thus making a polygon. the weight of the edges of the cut are all 0, but
+        // the Booleen need to invert the ones inside the source polygon (for the subsequent
+        // ConvertToForme)
+
+        // the cut path needs to have the highest pathID in the back data
+        // that's how the Booleen() function knows it's an edge of the cut
+        {
+            Path* swap=originaux[0];originaux[0]=originaux[1];originaux[1]=swap;
+            int   swai=origWind[0];origWind[0]=origWind[1];origWind[1]=(fill_typ)swai;
+        }
+        originaux[0]->ConvertWithBackData(get_threshold(pathva, 0.1));
+
+        originaux[0]->Fill(theShape, 0);
+
+        theShapeA->ConvertToShape(theShape, origWind[0]);
+
+        originaux[1]->ConvertWithBackData(get_threshold(pathvb, 0.1));
+
+        originaux[1]->Fill(theShape, 1,false,false,false); //do not closeIfNeeded
+
+        theShapeB->ConvertToShape(theShape, fill_justDont); // fill_justDont doesn't computes winding numbers
+
+        // les elements arrivent en ordre inverse dans la liste
+        theShape->Booleen(theShapeB, theShapeA, bool_op_cut, 1);
+
+    } else if ( bop == bool_op_slice ) {
+        // slice is not really a boolean operation
+        // you just put the 2 shapes in a single polygon, uncross it
+        // the points where the degree is > 2 are intersections
+        // just check it's an intersection on the path you want to cut, and keep it
+        // the intersections you have found are then fed to ConvertPositionsToMoveTo() which will
+        // make new subpath at each one of these positions
+        // inversion pour l'opération
+        {
+            Path* swap=originaux[0];originaux[0]=originaux[1];originaux[1]=swap;
+            int   swai=origWind[0];origWind[0]=origWind[1];origWind[1]=(fill_typ)swai;
+        }
+        originaux[0]->ConvertWithBackData(get_threshold(pathva, 0.1));
+
+        originaux[0]->Fill(theShapeA, 0,false,false,false); // don't closeIfNeeded
+
+        originaux[1]->ConvertWithBackData(get_threshold(pathvb, 0.1));
+
+        originaux[1]->Fill(theShapeA, 1,true,false,false);// don't closeIfNeeded and just dump in the shape, don't reset it
+
+        theShape->ConvertToShape(theShapeA, fill_justDont);
+
+        if ( theShape->hasBackData() ) {
+            // should always be the case, but ya never know
+            {
+                for (int i = 0; i < theShape->numberOfPoints(); i++) {
+                    if ( theShape->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 = theShape->getPoint(i).incidentEdge[FIRST];
+                        int   nbOrig=0;
+                        int   nbOther=0;
+                        int   piece=-1;
+                        float t=0.0;
+                        while ( cb >= 0 && cb < theShape->numberOfEdges() ) {
+                            if ( theShape->ebData[cb].pathID == 0 ) {
+                                // the source has an edge incident to the point, get its position on the path
+                                piece=theShape->ebData[cb].pieceID;
+                                if ( theShape->getEdge(cb).st == i ) {
+                                    t=theShape->ebData[cb].tSt;
+                                } else {
+                                    t=theShape->ebData[cb].tEn;
+                                }
+                                nbOrig++;
+                            }
+                            if ( theShape->ebData[cb].pathID == 1 ) nbOther++; // the cut is incident to this point
+                            cb=theShape->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
+                            toCut=(Path::cut_position*)realloc(toCut, (nbToCut+1)*sizeof(Path::cut_position));
+                            toCut[nbToCut].piece=piece;
+                            toCut[nbToCut].t=t;
+                            nbToCut++;
+                        }
+                    }
+                }
+            }
+            {
+                // i think it's useless now
+                int i = theShape->numberOfEdges() - 1;
+                for (;i>=0;i--) {
+                    if ( theShape->ebData[i].pathID == 1 ) {
+                        theShape->SubEdge(i);
+                    }
+                }
+            }
+
+        }
+    }
+
+    int*    nesting=nullptr;
+    int*    conts=nullptr;
+    int     nbNest=0;
+    // pour compenser le swap juste avant
+    if ( bop == bool_op_slice ) {
+//    theShape->ConvertToForme(res, nbOriginaux, originaux, true);
+//    res->ConvertForcedToMoveTo();
+        res->Copy(originaux[0]);
+        res->ConvertPositionsToMoveTo(nbToCut, toCut); // cut where you found intersections
+        free(toCut);
+    } else if ( bop == bool_op_cut ) {
+        // il faut appeler pour desallouer PointData (pas vital, mais bon)
+        // the Booleen() function did not deallocate the point_data array in theShape, because this
+        // function needs it.
+        // this function uses the point_data to get the winding number of each path (ie: is a hole or not)
+        // for later reconstruction in objects, you also need to extract which path is parent of holes (nesting info)
+        theShape->ConvertToFormeNested(res, nbOriginaux, &originaux[0], 1, nbNest, nesting, conts);
+    } else {
+        theShape->ConvertToForme(res, nbOriginaux, &originaux[0]);
+    }
+
+    delete theShape;
+    delete theShapeA;
+    delete theShapeB;
+    delete originaux[0];
+    delete originaux[1];
+
+    gchar *result_str = res->svg_dump_path();
+    Geom::PathVector outres =  Geom::parse_svg_path(result_str);
+    g_free(result_str);
+
+    delete res;
+    return outres;
+}
+
+/**
+ * Workaround for buggy Path::Transform() which incorrectly transforms arc commands.
+ *
+ * TODO: Fix PathDescrArcTo::transform() and then remove this workaround.
+ */
+static void transformLivarotPath(Path *res, Geom::Affine const &affine)
+{
+    res->LoadPathVector(res->MakePathVector() * affine);
+}
+
+// boolean operations on the desktop
+// take the source paths from the file, do the operation, delete the originals and add the results
+BoolOpErrors Inkscape::ObjectSet::pathBoolOp(bool_op bop, const bool skip_undo, const bool checked,
+                                             const Glib::ustring icon_name, const Glib::ustring description,
+                                             bool const silent)
+{
+    if (nullptr != desktop() && !checked) {
+        SPDocument *doc = desktop()->getDocument();
+        // don't redraw the canvas during the operation as that can remarkably slow down the progress
+        desktop()->getCanvas()->set_drawing_disabled(true);
+        BoolOpErrors returnCode = ObjectSet::pathBoolOp(bop, true, true,icon_name);
+        desktop()->getCanvas()->set_drawing_disabled(false);
+
+        switch(returnCode) {
+        case ERR_TOO_LESS_PATHS_1:
+            if (!silent) {
+                boolop_display_error_message(desktop(),
+                                             _("Select <b>at least 1 path</b> to perform a boolean union."));
+            }
+            break;
+        case ERR_TOO_LESS_PATHS_2:
+            if (!silent) {
+                boolop_display_error_message(desktop(),
+                                             _("Select <b>at least 2 paths</b> to perform a boolean operation."));
+            }
+            break;
+        case ERR_NO_PATHS:
+            if (!silent) {
+                boolop_display_error_message(desktop(),
+                                             _("One of the objects is <b>not a path</b>, cannot perform boolean operation."));
+            }
+            break;
+        case ERR_Z_ORDER:
+            if (!silent) {
+                boolop_display_error_message(desktop(),
+                                             _("Unable to determine the <b>z-order</b> of the objects selected for difference, XOR, division, or path cut."));
+            }
+            break;
+        case DONE_NO_PATH:
+            if (!skip_undo) { 
+                DocumentUndo::done(doc, description, "");
+            }
+            break;
+        case DONE:
+            if (!skip_undo) { 
+                DocumentUndo::done(doc, description, icon_name);
+            }
+            break;
+        case DONE_NO_ACTION:
+            // Do nothing (?)
+            break;
+        }
+        return returnCode;
+    }
+
+    SPDocument *doc = document();
+    std::vector<SPItem*> il(items().begin(), items().end());
+
+    // allow union on a single object for the purpose of removing self overlapse (svn log, revision 13334)
+    if (il.size() < 2 && bop != bool_op_union) {
+        return ERR_TOO_LESS_PATHS_2;
+    }
+    else if (il.size() < 1) {
+        return ERR_TOO_LESS_PATHS_1;
+    }
+
+    g_assert(!il.empty());
+
+    // reverseOrderForOp marks whether the order of the list is the top->down order
+    // it's only used when there are 2 objects, and for operations who need to know the
+    // topmost object (differences, cuts)
+    bool reverseOrderForOp = false;
+
+    if (bop == bool_op_diff || bop == bool_op_cut || bop == bool_op_slice) {
+        // check in the tree to find which element of the selection list is topmost (for 2-operand commands only)
+        Inkscape::XML::Node *a = il.front()->getRepr();
+        Inkscape::XML::Node *b = il.back()->getRepr();
+
+        if (a == nullptr || b == nullptr) {
+            return ERR_Z_ORDER;
+        }
+
+        if (Ancetre(a, b)) {
+            // a is the parent of b, already in the proper order
+        } else if (Ancetre(b, a)) {
+            // reverse order
+            reverseOrderForOp = true;
+        } else {
+
+            // objects are not in parent/child relationship;
+            // find their lowest common ancestor
+            Inkscape::XML::Node *parent = LCA(a, b);
+            if (parent == nullptr) {
+                return ERR_Z_ORDER;
+            }
+
+            // find the children of the LCA that lead from it to the a and b
+            Inkscape::XML::Node *as = AncetreFils(a, parent);
+            Inkscape::XML::Node *bs = AncetreFils(b, parent);
+
+            // find out which comes first
+            for (Inkscape::XML::Node *child = parent->firstChild(); child; child = child->next()) {
+                if (child == as) {
+                    /* a first, so reverse. */
+                    reverseOrderForOp = true;
+                    break;
+                }
+                if (child == bs)
+                    break;
+            }
+        }
+    }
+
+    g_assert(!il.empty());
+
+    // first check if all the input objects have shapes
+    // otherwise bail out
+    for (auto item : il)
+    {
+        if (!SP_IS_SHAPE(item) && !SP_IS_TEXT(item) && !SP_IS_FLOWTEXT(item))
+        {
+            return ERR_NO_PATHS;
+        }
+    }
+
+    // extract the livarot Paths from the source objects
+    // also get the winding rule specified in the style
+    int nbOriginaux = il.size();
+    std::vector<Path *> originaux(nbOriginaux);
+    std::vector<FillRule> origWind(nbOriginaux);
+    int curOrig;
+    {
+        curOrig = 0;
+        for (auto item : il)
+        {
+            // apply live path effects prior to performing boolean operation
+            char const *id = item->getAttribute("id");
+            SPLPEItem *lpeitem = dynamic_cast<SPLPEItem *>(item);
+            if (lpeitem) {
+                SPDocument * document = item->document;
+                lpeitem->removeAllPathEffects(true);
+                SPObject *elemref = document->getObjectById(id);
+                if (elemref && elemref != item) {
+                    // If the LPE item is a shape, it is converted to a path 
+                    // so we need to reupdate the item
+                    item = dynamic_cast<SPItem *>(elemref);
+                }
+            }
+            SPCSSAttr *css = sp_repr_css_attr(reinterpret_cast<SPObject *>(il[0])->getRepr(), "style");
+            gchar const *val = sp_repr_css_property(css, "fill-rule", nullptr);
+            if (val && strcmp(val, "nonzero") == 0) {
+                origWind[curOrig]= fill_nonZero;
+            } else if (val && strcmp(val, "evenodd") == 0) {
+                origWind[curOrig]= fill_oddEven;
+            } else {
+                origWind[curOrig]= fill_nonZero;
+            }
+
+            originaux[curOrig] = Path_for_item(item, true, true);
+            if (originaux[curOrig] == nullptr || originaux[curOrig]->descr_cmd.size() <= 1)
+            {
+                for (int i = curOrig; i >= 0; i--) delete originaux[i];
+                return DONE_NO_ACTION;
+            }
+            curOrig++;
+        }
+    }
+    // reverse if needed
+    // note that the selection list keeps its order
+    if ( reverseOrderForOp ) {
+        std::swap(originaux[0], originaux[1]);
+        std::swap(origWind[0], origWind[1]);
+    }
+
+    // and work
+    // some temporary instances, first
+    Shape *theShapeA = new Shape;
+    Shape *theShapeB = new Shape;
+    Shape *theShape = new Shape;
+    Path *res = new Path;
+    res->SetBackData(false);
+    Path::cut_position  *toCut=nullptr;
+    int                  nbToCut=0;
+
+    if ( bop == bool_op_inters || bop == bool_op_union || bop == bool_op_diff || bop == bool_op_symdiff ) {
+        // true boolean op
+        // get the polygons of each path, with the winding rule specified, and apply the operation iteratively
+        originaux[0]->ConvertWithBackData(get_threshold(il[0], 0.1));
+
+        originaux[0]->Fill(theShape, 0);
+
+        theShapeA->ConvertToShape(theShape, origWind[0]);
+
+        curOrig = 1;
+        for (auto item : il){
+            if(item==il[0])continue;
+            originaux[curOrig]->ConvertWithBackData(get_threshold(item, 0.1));
+
+            originaux[curOrig]->Fill(theShape, curOrig);
+
+            theShapeB->ConvertToShape(theShape, origWind[curOrig]);
+
+            /* Due to quantization of the input shape coordinates, we may end up with A or B being empty.
+             * If this is a union or symdiff operation, we just use the non-empty shape as the result:
+             *   A=0  =>  (0 or B) == B
+             *   B=0  =>  (A or 0) == A
+             *   A=0  =>  (0 xor B) == B
+             *   B=0  =>  (A xor 0) == A
+             * If this is an intersection operation, we just use the empty shape as the result:
+             *   A=0  =>  (0 and B) == 0 == A
+             *   B=0  =>  (A and 0) == 0 == B
+             * If this a difference operation, and the upper shape (A) is empty, we keep B.
+             * If the lower shape (B) is empty, we still keep B, as it's empty:
+             *   A=0  =>  (B - 0) == B
+             *   B=0  =>  (0 - A) == 0 == B
+             *
+             * In any case, the output from this operation is stored in shape A, so we may apply
+             * the above rules simply by judicious use of swapping A and B where necessary.
+             */
+            bool zeroA = theShapeA->numberOfEdges() == 0;
+            bool zeroB = theShapeB->numberOfEdges() == 0;
+            if (zeroA || zeroB) {
+                // We might need to do a swap. Apply the above rules depending on operation type.
+                bool resultIsB =   ((bop == bool_op_union || bop == bool_op_symdiff) && zeroA)
+                                   || ((bop == bool_op_inters) && zeroB)
+                                   ||  (bop == bool_op_diff);
+                if (resultIsB) {
+                    // Swap A and B to use B as the result
+                    Shape *swap = theShapeB;
+                    theShapeB = theShapeA;
+                    theShapeA = swap;
+                }
+            } else {
+                // Just do the Boolean operation as usual
+                // les elements arrivent en ordre inverse dans la liste
+                theShape->Booleen(theShapeB, theShapeA, bop);
+                Shape *swap = theShape;
+                theShape = theShapeA;
+                theShapeA = swap;
+            }
+            curOrig++;
+        }
+
+        {
+            Shape *swap = theShape;
+            theShape = theShapeA;
+            theShapeA = swap;
+        }
+
+    } else if ( bop == bool_op_cut ) {
+        // cuts= sort of a bastard boolean operation, thus not the axact same modus operandi
+        // technically, the cut path is not necessarily a polygon (thus has no winding rule)
+        // it is just uncrossed, and cleaned from duplicate edges and points
+        // then it's fed to Booleen() which will uncross it against the other path
+        // then comes the trick: each edge of the cut path is duplicated (one in each direction),
+        // thus making a polygon. the weight of the edges of the cut are all 0, but
+        // the Booleen need to invert the ones inside the source polygon (for the subsequent
+        // ConvertToForme)
+
+        // the cut path needs to have the highest pathID in the back data
+        // that's how the Booleen() function knows it's an edge of the cut
+        {
+            Path* swap=originaux[0];originaux[0]=originaux[1];originaux[1]=swap;
+            int   swai=origWind[0];origWind[0]=origWind[1];origWind[1]=(fill_typ)swai;
+        }
+        originaux[0]->ConvertWithBackData(get_threshold(il[0], 0.1));
+
+        originaux[0]->Fill(theShape, 0);
+
+        theShapeA->ConvertToShape(theShape, origWind[0]);
+
+        originaux[1]->ConvertWithBackData(get_threshold(il[1], 0.1));
+
+        if ((originaux[1]->pts.size() == 2) && originaux[1]->pts[0].isMoveTo && !originaux[1]->pts[1].isMoveTo)
+            originaux[1]->Fill(theShape, 1,false,true,false); // see LP Bug 177956
+        else
+            originaux[1]->Fill(theShape, 1,false,false,false); //do not closeIfNeeded
+
+        theShapeB->ConvertToShape(theShape, fill_justDont); // fill_justDont doesn't computes winding numbers
+
+        // les elements arrivent en ordre inverse dans la liste
+        theShape->Booleen(theShapeB, theShapeA, bool_op_cut, 1);
+
+    } else if ( bop == bool_op_slice ) {
+        // slice is not really a boolean operation
+        // you just put the 2 shapes in a single polygon, uncross it
+        // the points where the degree is > 2 are intersections
+        // just check it's an intersection on the path you want to cut, and keep it
+        // the intersections you have found are then fed to ConvertPositionsToMoveTo() which will
+        // make new subpath at each one of these positions
+        // inversion pour l'opération
+        {
+            Path* swap=originaux[0];originaux[0]=originaux[1];originaux[1]=swap;
+            int   swai=origWind[0];origWind[0]=origWind[1];origWind[1]=(fill_typ)swai;
+        }
+        originaux[0]->ConvertWithBackData(get_threshold(il[0], 0.1));
+
+        originaux[0]->Fill(theShapeA, 0,false,false,false); // don't closeIfNeeded
+
+        originaux[1]->ConvertWithBackData(get_threshold(il[1], 0.1));
+
+        originaux[1]->Fill(theShapeA, 1,true,false,false);// don't closeIfNeeded and just dump in the shape, don't reset it
+
+        theShape->ConvertToShape(theShapeA, fill_justDont);
+
+        if ( theShape->hasBackData() ) {
+            // should always be the case, but ya never know
+            {
+                for (int i = 0; i < theShape->numberOfPoints(); i++) {
+                    if ( theShape->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 = theShape->getPoint(i).incidentEdge[FIRST];
+                        int   nbOrig=0;
+                        int   nbOther=0;
+                        int   piece=-1;
+                        float t=0.0;
+                        while ( cb >= 0 && cb < theShape->numberOfEdges() ) {
+                            if ( theShape->ebData[cb].pathID == 0 ) {
+                                // the source has an edge incident to the point, get its position on the path
+                                piece=theShape->ebData[cb].pieceID;
+                                if ( theShape->getEdge(cb).st == i ) {
+                                    t=theShape->ebData[cb].tSt;
+                                } else {
+                                    t=theShape->ebData[cb].tEn;
+                                }
+                                nbOrig++;
+                            }
+                            if ( theShape->ebData[cb].pathID == 1 ) nbOther++; // the cut is incident to this point
+                            cb=theShape->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
+                            toCut=(Path::cut_position*)realloc(toCut, (nbToCut+1)*sizeof(Path::cut_position));
+                            toCut[nbToCut].piece=piece;
+                            toCut[nbToCut].t=t;
+                            nbToCut++;
+                        }
+                    }
+                }
+            }
+            {
+                // i think it's useless now
+                int i = theShape->numberOfEdges() - 1;
+                for (;i>=0;i--) {
+                    if ( theShape->ebData[i].pathID == 1 ) {
+                        theShape->SubEdge(i);
+                    }
+                }
+            }
+
+        }
+    }
+
+    int*    nesting=nullptr;
+    int*    conts=nullptr;
+    int     nbNest=0;
+    // pour compenser le swap juste avant
+    if ( bop == bool_op_slice ) {
+//    theShape->ConvertToForme(res, nbOriginaux, originaux, true);
+//    res->ConvertForcedToMoveTo();
+        res->Copy(originaux[0]);
+        res->ConvertPositionsToMoveTo(nbToCut, toCut); // cut where you found intersections
+        free(toCut);
+    } else if ( bop == bool_op_cut ) {
+        // il faut appeler pour desallouer PointData (pas vital, mais bon)
+        // the Booleen() function did not deallocate the point_data array in theShape, because this
+        // function needs it.
+        // this function uses the point_data to get the winding number of each path (ie: is a hole or not)
+        // for later reconstruction in objects, you also need to extract which path is parent of holes (nesting info)
+        theShape->ConvertToFormeNested(res, nbOriginaux, &originaux[0], 1, nbNest, nesting, conts);
+    } else {
+        theShape->ConvertToForme(res, nbOriginaux, &originaux[0]);
+    }
+
+    delete theShape;
+    delete theShapeA;
+    delete theShapeB;
+    for (int i = 0; i < nbOriginaux; i++)  delete originaux[i];
+
+    if (res->descr_cmd.size() <= 1)
+    {
+        // only one command, presumably a moveto: it isn't a path
+        for (auto l : il){
+            l->deleteObject();
+        }
+        clear();
+
+        delete res;
+        return DONE_NO_PATH;
+    }
+
+    // get the source path object
+    SPObject *source;
+    if ( bop == bool_op_diff || bop == bool_op_cut || bop == bool_op_slice ) {
+        if (reverseOrderForOp) {
+            source = il[0];
+        } else {
+            source = il.back();
+        }
+    } else {
+        // find out the bottom object
+        std::vector<Inkscape::XML::Node*> sorted(xmlNodes().begin(), xmlNodes().end());
+
+        sort(sorted.begin(),sorted.end(),sp_repr_compare_position_bool);
+
+        source = doc->getObjectByRepr(sorted.front());
+    }
+
+    // adjust style properties that depend on a possible transform in the source object in order
+    // to get a correct style attribute for the new path
+    SPItem* item_source = SP_ITEM(source);
+    Geom::Affine i2doc(item_source->i2doc_affine());
+
+    Inkscape::XML::Node *repr_source = source->getRepr();
+
+    // remember important aspects of the source path, to be restored
+    gint pos = repr_source->position();
+    Inkscape::XML::Node *parent = repr_source->parent();
+    // remove source paths
+    clear();
+    for (auto l : il){
+        if (l != item_source) {
+            // delete the object for real, so that its clones can take appropriate action
+            l->deleteObject();
+        }
+    }
+
+    auto const source2doc_inverse = i2doc.inverse();
+    char const *const old_transform_attibute = repr_source->attribute("transform");
+
+    // now that we have the result, add it on the canvas
+    if ( bop == bool_op_cut || bop == bool_op_slice ) {
+        int    nbRP=0;
+        Path** resPath;
+        if ( bop == bool_op_slice ) {
+            // there are moveto's at each intersection, but it's still one unique path
+            // so break it down and add each subpath independently
+            // we could call break_apart to do this, but while we have the description...
+            resPath=res->SubPaths(nbRP, false);
+        } else {
+            // cut operation is a bit wicked: you need to keep holes
+            // that's why you needed the nesting
+            // ConvertToFormeNested() dumped all the subpath in a single Path "res", so we need
+            // to get the path for each part of the polygon. that's why you need the nesting info:
+            // to know in which subpath to add a subpath
+            resPath=res->SubPathsWithNesting(nbRP, true, nbNest, nesting, conts);
+
+            // cleaning
+            if ( conts ) free(conts);
+            if ( nesting ) free(nesting);
+        }
+
+        // add all the pieces resulting from cut or slice
+        std::vector <Inkscape::XML::Node*> selection;
+        for (int i=0;i<nbRP;i++) {
+            transformLivarotPath(resPath[i], source2doc_inverse);
+            gchar *d = resPath[i]->svg_dump_path();
+
+            Inkscape::XML::Document *xml_doc = doc->getReprDoc();
+            Inkscape::XML::Node *repr = xml_doc->createElement("svg:path");
+
+            Inkscape::copy_object_properties(repr, repr_source);
+
+            // Delete source on last iteration (after we don't need repr_source anymore). As a consequence, the last
+            // item will inherit the original's id.
+            if (i + 1 == nbRP) {
+                item_source->deleteObject(false);
+            }
+
+            repr->setAttribute("d", d);
+            g_free(d);
+
+            // for slice, remove fill
+            if (bop == bool_op_slice) {
+                SPCSSAttr *css;
+
+                css = sp_repr_css_attr_new();
+                sp_repr_css_set_property(css, "fill", "none");
+
+                sp_repr_css_change(repr, css, "style");
+
+                sp_repr_css_attr_unref(css);
+            }
+
+            repr->setAttributeOrRemoveIfEmpty("transform", old_transform_attibute);
+
+            // add the new repr to the parent
+            // move to the saved position
+            parent->addChildAtPos(repr, pos);
+
+            selection.push_back(repr);
+            Inkscape::GC::release(repr);
+
+            delete resPath[i];
+        }
+        setReprList(selection);
+        if ( resPath ) free(resPath);
+
+    } else {
+        transformLivarotPath(res, source2doc_inverse);
+        gchar *d = res->svg_dump_path();
+
+        Inkscape::XML::Document *xml_doc = doc->getReprDoc();
+        Inkscape::XML::Node *repr = xml_doc->createElement("svg:path");
+
+        Inkscape::copy_object_properties(repr, repr_source);
+
+        // delete it so that its clones don't get alerted; this object will be restored shortly, with the same id
+        item_source->deleteObject(false);
+
+        repr->setAttribute("d", d);
+        g_free(d);
+
+        repr->setAttributeOrRemoveIfEmpty("transform", old_transform_attibute);
+
+        parent->addChildAtPos(repr, pos);
+
+        set(repr);
+        Inkscape::GC::release(repr);
+    }
+
+    delete res;
+
+    return DONE;
+}
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :