Update to 2Geom revision 2396

(bzr r14059.2.16)

1 files changed, 133 insertions, 13 deletions

diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp
index 8cba316f5..5fbc65b3e 100644
--- a/src/2geom/path.cpp
+++ b/src/2geom/path.cpp
@@ -35,8 +35,11 @@
 #include <2geom/path.h>
 #include <2geom/pathvector.h>
 #include <2geom/transforms.h>
+#include <2geom/circle.h>
+#include <2geom/ellipse.h>
 #include <2geom/convex-hull.h>
 #include <2geom/svg-path-writer.h>
+#include <2geom/sweeper.h>
 #include <algorithm>
 #include <limits>
 
@@ -231,7 +234,7 @@ Path::Path(Rect const &r)
 Path::Path(ConvexHull const &ch)
     : _curves(new Sequence())
     , _closing_seg(new ClosingSegment(Point(), Point()))
-    , _closed(false)
+    , _closed(true)
     , _exception_on_stitch(true)
 {
     if (ch.empty()) {
@@ -253,6 +256,49 @@ Path::Path(ConvexHull const &ch)
     _closed = true;
 }
 
+Path::Path(Circle const &c)
+    : _curves(new Sequence())
+    , _closing_seg(NULL)
+    , _closed(true)
+    , _exception_on_stitch(true)
+{
+    Point p1 = c.pointAt(0);
+    Point p2 = c.pointAt(M_PI);
+    _curves->push_back(new EllipticalArc(p1, c.radius(), c.radius(), 0, false, true, p2));
+    _curves->push_back(new EllipticalArc(p2, c.radius(), c.radius(), 0, false, true, p1));
+    _closing_seg = new ClosingSegment(p1, p1);
+    _curves->push_back(_closing_seg);
+}
+
+Path::Path(Ellipse const &e)
+    : _curves(new Sequence())
+    , _closing_seg(NULL)
+    , _closed(true)
+    , _exception_on_stitch(true)
+{
+    Point p1 = e.pointAt(0);
+    Point p2 = e.pointAt(M_PI);
+    _curves->push_back(new EllipticalArc(p1, e.rays(), e.rotationAngle(), false, true, p2));
+    _curves->push_back(new EllipticalArc(p2, e.rays(), e.rotationAngle(), false, true, p1));
+    _closing_seg = new ClosingSegment(p1, p1);
+    _curves->push_back(_closing_seg);
+}
+
+void Path::close(bool c)
+{
+    if (c == _closed) return;
+    if (c && _curves->size() >= 2) {
+        // when closing, if last segment is linear and ends at initial point,
+        // replace it with the closing segment
+        Sequence::iterator last = _curves->end() - 2;
+        if (last->isLineSegment() && last->finalPoint() == initialPoint()) {
+            _closing_seg->setInitial(last->initialPoint());
+            _curves->erase(last);
+        }
+    }
+    _closed = c;
+}
+
 void Path::clear()
 {
     _unshare();
@@ -405,23 +451,91 @@ std::vector<PathTime> Path::roots(Coord v, Dim2 d) const
     return res;
 }
 
-std::vector<PathIntersection> Path::intersect(Path const &other, Coord precision) const
+
+// The class below implements sweepline optimization for curve intersection in paths.
+// Instead of O(N^2), this takes O(N + X), where X is the number of overlaps
+// between the bounding boxes of curves.
+namespace {
+
+struct CurveSweepTraits {
+    struct Bound {
+        Rect r;
+        std::size_t index;
+        int which;
+    };
+    typedef std::less<Coord> Compare;
+    inline static Coord entry_value(Bound const &b) { return b.r[X].min(); }
+    inline static Coord exit_value(Bound const &b) { return b.r[X].max(); }
+};
+
+class CurveSweeper
+    : public Sweeper<Curve const *, CurveSweepTraits>
 {
-    std::vector<PathIntersection> result;
+public:
+    CurveSweeper(Path const &a, Path const &b, std::vector<PathIntersection> &result, Coord prec)
+        : _result(result)
+        , _precision(prec)
+    {
+        for (std::size_t i = 0; i < a.size(); ++i) {
+            Bound bound;
+            bound.r = a[i].boundsFast();
+            bound.index = i;
+            bound.which = 0;
+            insert(bound, &a[i]);
+        }
+        for (std::size_t i = 0; i < b.size(); ++i) {
+            Bound bound;
+            bound.r = b[i].boundsFast();
+            bound.index = i;
+            bound.which = 1;
+            insert(bound, &b[i]);
+        }
+    }
+
+protected:
+    void _enter(Record const &record) {
+        int which = record.bound.which;
+
+        for (RecordList::iterator i = _active_items.begin(); i != _active_items.end(); ++i) {
+            // do not intersect in the same path
+            if (i->bound.which == which) continue;
+            // do not intersect if boxes do not overlap in Y
+            if (!record.bound.r[Y].intersects(i->bound.r[Y])) continue;
+
+            std::vector<CurveIntersection> cx;
+            int ia = record.bound.index;
+            int ib = i->bound.index;
+
+            if (which == 0) {
+                cx = record.item->intersect(*i->item);
+            } else {
+                cx = i->item->intersect(*record.item, _precision);
+                std::swap(ia, ib);
+            }
 
-    // TODO: sweepline optimization
-    // TODO: remove multiple intersections within precision of each other?
-    for (size_type i = 0; i < size(); ++i) {
-        for (size_type j = 0; j < other.size(); ++j) {
-            std::vector<CurveIntersection> cx = (*this)[i].intersect(other[j], precision);
             for (std::size_t ci = 0; ci < cx.size(); ++ci) {
-                PathTime a(i, cx[ci].first), b(j, cx[ci].second);
+                PathTime a(ia, cx[ci].first), b(ib, cx[ci].second);
                 PathIntersection px(a, b, cx[ci].point());
-                result.push_back(px);
+                _result.push_back(px);
             }
         }
     }
 
+private:
+    std::vector<PathIntersection> &_result;
+    Coord _precision;
+};
+
+} // end anonymous namespace
+
+std::vector<PathIntersection> Path::intersect(Path const &other, Coord precision) const
+{
+    std::vector<PathIntersection> result;
+
+    CurveSweeper sweeper(*this, other, result, precision);
+    sweeper.process();
+
+    // TODO: remove multiple intersections within precision of each other?
     return result;
 }
 
@@ -700,11 +814,10 @@ Path Path::reversed() const
 
     if (_closed) {
         // when the path is closed, there are two cases:
-        BezierCurve const *iseg = dynamic_cast<BezierCurve const *>(&front());
-        if (iseg && iseg->size() == 2) {
+        if (front().isLineSegment()) {
             // 1. initial segment is linear: it becomes the new closing segment.
             rend = RIter(_curves->begin() + 1);
-            ret._closing_seg = new ClosingSegment(iseg->finalPoint(), iseg->initialPoint());
+            ret._closing_seg = new ClosingSegment(front().finalPoint(), front().initialPoint());
         } else {
             // 2. initial segment is not linear: the closing segment becomes degenerate.
             // However, skip it if it's already degenerate.
@@ -883,6 +996,13 @@ void Path::do_append(Curve *c)
         if (c->initialPoint() != _closing_seg->initialPoint()) {
             THROW_CONTINUITYERROR();
         }
+        if (_closed && c->isLineSegment() &&
+            c->finalPoint() == _closing_seg->finalPoint())
+        {
+            // appending a curve that matches the closing segment has no effect
+            delete c;
+            return;
+        }
     }
     _curves->insert(_curves->end() - 1, c);
     _closing_seg->setInitial(c->finalPoint());