Upgrade to 2Geom r2413

(bzr r14059.2.18)

1 files changed, 99 insertions, 38 deletions

diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp
index ff96c28a8..e18561f67 100644
--- a/src/2geom/intersection-graph.cpp
+++ b/src/2geom/intersection-graph.cpp
@@ -39,7 +39,7 @@
 
 namespace Geom {
 
-struct IntersectionVertexLess {
+struct PathIntersectionGraph::IntersectionVertexLess {
     bool operator()(IntersectionVertex const &a, IntersectionVertex const &b) const {
         return a.pos < b.pos;
     }
@@ -49,7 +49,8 @@ struct IntersectionVertexLess {
  * @brief Intermediate data for computing Boolean operations on paths.
  *
  * This class implements the Greiner-Hormann clipping algorithm,
- * with improvements by Foster and Overfelt.
+ * with improvements inspired by Foster and Overfelt as well as some
+ * original contributions.
  *
  * @ingroup Paths
  */
@@ -69,15 +70,16 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con
     }
 
     std::vector<PVIntersection> pxs = _a.intersect(_b, precision);
+    // NOTE: this early return means that the path data structures will not be created
+    // if there are no intersections at all!
     if (pxs.empty()) return;
-    if (pxs.size() % 2) return;
 
     // prepare intersection lists for each path component
     for (std::size_t i = 0; i < _a.size(); ++i) {
-        _xalists.push_back(new IntersectionList());
+        _apaths.push_back(new PathData());
     }
     for (std::size_t i = 0; i < _b.size(); ++i) {
-        _xblists.push_back(new IntersectionList());
+        _bpaths.push_back(new PathData());
     }
 
     for (std::size_t i = 0; i < pxs.size(); ++i) {
@@ -92,30 +94,32 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con
         xb->neighbor = xa;
         _xs.push_back(xa);
         _xs.push_back(xb);
-        _xalists[xa->pos.path_index].push_back(*xa);
-        _xblists[xb->pos.path_index].push_back(*xb);
+        _apaths[xa->pos.path_index].xlist.push_back(*xa);
+        _bpaths[xb->pos.path_index].xlist.push_back(*xb);
     }
 
-    for (std::size_t i = 0; i < _xalists.size(); ++i) {
-        _xalists[i].sort(IntersectionVertexLess());
+    for (std::size_t i = 0; i < _apaths.size(); ++i) {
+        _apaths[i].xlist.sort(IntersectionVertexLess());
     }
-    for (std::size_t i = 0; i < _xblists.size(); ++i) {
-        _xblists[i].sort(IntersectionVertexLess());
+    for (std::size_t i = 0; i < _bpaths.size(); ++i) {
+        _bpaths[i].xlist.sort(IntersectionVertexLess());
     }
 
     typedef IntersectionList::iterator Iter;
 
     // determine in/out/on flags using winding
     for (unsigned npv = 0; npv < 2; ++npv) {
-        boost::ptr_vector<IntersectionList> &ls = npv ? _xblists : _xalists;
+        boost::ptr_vector<PathData> &ls = npv ? _bpaths : _apaths;
+        boost::ptr_vector<PathData> &ols = npv ? _apaths : _bpaths;
         PathVector const &pv = npv ? b : a;
         PathVector const &other = npv ? a : b;
 
         for (unsigned li = 0; li < ls.size(); ++li) {
-            for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) {
+            IntersectionList &xl = ls[li].xlist;
+            for (Iter i = xl.begin(); i != xl.end(); ++i) {
                 Iter n = boost::next(i);
-                if (n == ls[li].end()) {
-                    n = ls[li].begin();
+                if (n == xl.end()) {
+                    n = xl.begin();
                 }
                 std::size_t pi = i->pos.path_index;
 
@@ -123,7 +127,6 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con
                 PathTime mid = ival.inside(precision);
 
                 // TODO check for degenerate cases
-                // requires changes in the winding routine
                 int w = other.winding(pv[pi].pointAt(mid));
                 if (w % 2) {
                     i->next = POINT_INSIDE;
@@ -134,9 +137,22 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con
                 }
             }
 
-            // assign exit / entry flags
-            for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) {
-                i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_OUTSIDE));
+            // remove intersections that don't change between in/out
+            // and assign exit / entry flags
+            for (Iter i = xl.begin(); i != xl.end();) {
+                if (i->previous == i->next) {
+                    IntersectionList &oxl = ols[i->neighbor->pos.path_index].xlist;
+                    oxl.erase(oxl.iterator_to(*i->neighbor));
+                    xl.erase(i++);
+                    if (i->next == POINT_INSIDE) {
+                        ++ls[li].removed_in;
+                    } else {
+                        ++ls[li].removed_out;
+                    }
+                } else {
+                    i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_OUTSIDE));
+                    ++i;
+                }
             }
         }
     }
@@ -162,6 +178,7 @@ PathVector PathIntersectionGraph::getAminusB()
 {
     PathVector result = _getResult(false, true);
     _handleNonintersectingPaths(result, 0, false);
+    _handleNonintersectingPaths(result, 1, true);
     return result;
 }
 
@@ -169,6 +186,7 @@ PathVector PathIntersectionGraph::getBminusA()
 {
     PathVector result = _getResult(true, false);
     _handleNonintersectingPaths(result, 1, false);
+    _handleNonintersectingPaths(result, 0, true);
     return result;
 }
 
@@ -180,13 +198,22 @@ PathVector PathIntersectionGraph::getXOR()
     return r1;
 }
 
+std::size_t PathIntersectionGraph::size() const
+{
+    std::size_t result = 0;
+    for (std::size_t i = 0; i < _apaths.size(); ++i) {
+        result += _apaths[i].xlist.size();
+    }
+    return result;
+}
+
 std::vector<Point> PathIntersectionGraph::intersectionPoints() const
 {
     std::vector<Point> result;
 
     typedef IntersectionList::const_iterator Iter;
-    for (std::size_t i = 0; i < _xalists.size(); ++i) {
-        for (Iter j = _xalists[i].begin(); j != _xalists[i].end(); ++j) {
+    for (std::size_t i = 0; i < _apaths.size(); ++i) {
+        for (Iter j = _apaths[i].xlist.begin(); j != _apaths[i].xlist.end(); ++j) {
             result.push_back(j->p);
         }
     }
@@ -201,9 +228,9 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
 
     // reset processed status
     for (unsigned npv = 0; npv < 2; ++npv) {
-        boost::ptr_vector<IntersectionList> &ls = npv ? _xblists : _xalists;
+        boost::ptr_vector<PathData> &ls = npv ? _bpaths : _apaths;
         for (std::size_t li = 0; li < ls.size(); ++li) {
-            for (Iter k = ls[li].begin(); k != ls[li].end(); ++k) {
+            for (Iter k = ls[li].xlist.begin(); k != ls[li].xlist.end(); ++k) {
                 k->processed = false;
             }
         }
@@ -213,7 +240,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
 
     while (true) {
         PathVector const *cur = &_a, *other = &_b;
-        boost::ptr_vector<IntersectionList> *lscur = &_xalists, *lsother = &_xblists;
+        boost::ptr_vector<PathData> *lscur = &_apaths, *lsother = &_bpaths;
 
         // find unprocessed intersection
         Iter i;
@@ -239,14 +266,14 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
 
             // get next intersection
             if (reverse) {
-                if (i == (*lscur)[pi].begin()) {
-                    i = (*lscur)[pi].end();
+                if (i == (*lscur)[pi].xlist.begin()) {
+                    i = (*lscur)[pi].xlist.end();
                 }
                 --i;
             } else {
                 ++i;
-                if (i == (*lscur)[pi].end()) {
-                    i = (*lscur)[pi].begin();
+                if (i == (*lscur)[pi].xlist.end()) {
+                    i = (*lscur)[pi].xlist.begin();
                 }
             }
 
@@ -263,7 +290,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
             n_processed += 2;
 
             // switch to the other path
-            i = (*lsother)[i->neighbor->pos.path_index].iterator_to(*i->neighbor);
+            i = (*lsother)[i->neighbor->pos.path_index].xlist.iterator_to(*i->neighbor);
             std::swap(lscur, lsother);
             std::swap(cur, other);
         }
@@ -272,7 +299,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
         assert(!result.back().empty());
     }
 
-    assert(n_processed == _xs.size());
+    assert(n_processed == size() * 2);
 
     return result;
 }
@@ -285,15 +312,29 @@ void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, int
      * evaluating the winding rule at the initial point. If inside is true and
      * the path is inside, we add it to the result.
      */
-    boost::ptr_vector<IntersectionList> const &ls = which ? _xblists : _xalists;
+    boost::ptr_vector<PathData> const &ls = which ? _bpaths : _apaths;
     PathVector const &cur = which ? _b : _a;
     PathVector const &other = which ? _a : _b;
 
     for (std::size_t i = 0; i < cur.size(); ++i) {
-        if (!ls.empty() && !ls[i].empty()) continue;
+        // the path data vector might have been left empty if there were no intersections at all
+        bool has_path_data = !ls.empty();
+        // Skip if the path has intersections
+        if (has_path_data && !ls[i].xlist.empty()) continue;
+        bool path_inside = false;
+
+        // If the path had any intersections removed, use the result of that,
+        // since one of those might have been at the initial point.
+        // Also, it saves time.
+        if (has_path_data && ls[i].removed_in != 0) {
+            path_inside = true;
+        } else if (has_path_data && ls[i].removed_out != 0) {
+            path_inside = false;
+        } else {
+            int w = other.winding(cur[i].initialPoint());
+            path_inside = w % 2 != 0;
+        }
 
-        int w = other.winding(cur[i].initialPoint());
-        bool path_inside = w % 2 != 0;
         if (path_inside == inside) {
             result.push_back(cur[i]);
         }
@@ -304,11 +345,16 @@ bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result)
 {
     typedef IntersectionList::iterator Iter;
 
-    Iter it;
+    Iter it, last;
 
-    for (std::size_t k = 0; k < _xalists.size(); ++k) {
-        it = _xalists[k].begin();
-        for (; it != _xalists[k].end(); ++it) {
+    for (std::size_t k = 0; k < _apaths.size(); ++k) {
+        it = _apaths[k].xlist.begin();
+        last = _apaths[k].xlist.end();
+        for (; it != last; ++it) {
+            if (!it->_hook.is_linked()) {
+                // this intersection was removed since it did not change inside/outside status
+                continue;
+            }
             if (!it->processed) {
                 result = it;
                 return true;
@@ -319,6 +365,21 @@ bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result)
     return false;
 }
 
+
+std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig)
+{
+    os << "Intersection graph:\n"
+       << pig._xs.size()/2 << " total intersections\n"
+       << pig.size() << " considered intersections\n";
+    for (std::size_t i = 0; i < pig._apaths.size(); ++i) {
+        typedef PathIntersectionGraph::IntersectionList::const_iterator Iter;
+        for (Iter j = pig._apaths[i].xlist.begin(); j != pig._apaths[i].xlist.end(); ++j) {
+            os << j->pos << " - " << j->neighbor->pos << " @ " << j->p << "\n";
+        }
+    }
+    return os;
+}
+
 } // namespace Geom
 
 /*