Update to 2Geom rev. 1113

(bzr r3622)

1 files changed, 258 insertions, 367 deletions

diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp
index 91868eb7e..f05d3b0cf 100644
--- a/src/2geom/path.cpp
+++ b/src/2geom/path.cpp
@@ -1,367 +1,258 @@
-/*

- * Path - Series of continuous curves

- *   

- * Copyright 2007  MenTaLguY <mental@rydia.net>

- *     

- * This library is free software; you can redistribute it and/or 

- * modify it either under the terms of the GNU Lesser General Public

- * License version 2.1 as published by the Free Software Foundation

- * (the "LGPL") or, at your option, under the terms of the Mozilla

- * Public License Version 1.1 (the "MPL"). If you do not alter this 

- * notice, a recipient may use your version of this file under either

- * the MPL or the LGPL.

- *            

- * You should have received a copy of the LGPL along with this library

- * in the file COPYING-LGPL-2.1; if not, write to the Free Software 

- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

- * You should have received a copy of the MPL along with this library 

- * in the file COPYING-MPL-1.1

- *                

- * The contents of this file are subject to the Mozilla Public License

- * Version 1.1 (the "License"); you may not use this file except in

- * compliance with the License. You may obtain a copy of the License at

- * http://www.mozilla.org/MPL/

- *                   

- * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY

- * OF ANY KIND, either express or implied. See the LGPL or the MPL for

- * the specific language governing rights and limitations.

- */

-

-#include "path.h"

-

-namespace Geom {

-

-namespace {

-

-enum Cmp {

-  LESS_THAN=-1,

-  GREATER_THAN=1,

-  EQUAL_TO=0

-};

-

-template <typename T1, typename T2>

-inline Cmp cmp(T1 const &a, T2 const &b) {

-  if ( a < b ) {

-    return LESS_THAN;

-  } else if ( b < a ) {

-    return GREATER_THAN;

-  } else {

-    return EQUAL_TO;

-  }

-}

-

-}

-

-boost::optional<int> CurveHelpers::sbasis_winding(D2<SBasis> const &sb, Point p) {

-  Interval ix = bounds_fast(sb[X]);

-

-  if ( p[X] > ix.max() ) { /* ray does not intersect bbox */

-    return 0;

-  }

-

-  SBasis fy = sb[Y];

-  fy -= p[Y];

-

-  if (fy.empty()) { /* coincident horizontal segment */

-    return boost::optional<int>();

-  }

-

-  if ( p[X] < ix.min() ) { /* ray does not originate in bbox */

-    double y = p[Y];

-    /* winding determined by position of endpoints */

-    Cmp initial_to_ray = cmp(fy[0][0], y);

-    Cmp final_to_ray = cmp(fy[0][1], y);

-    switch (cmp(final_to_ray, initial_to_ray)) {

-    case GREATER_THAN:

-      /* exclude final endpoint */

-      return ( final_to_ray != EQUAL_TO );

-    case LESS_THAN:

-      /* exclude final endpoint */

-      return -( final_to_ray != EQUAL_TO );

-    default:

-      /* any intersections cancel out */

-      return 0;

-    }

-  } else { /* ray originates in bbox */

-    std::vector<double> ts = roots(fy);

-

-    static const unsigned MAX_DERIVATIVES=8;

-    boost::optional<SBasis> ds[MAX_DERIVATIVES];

-    ds[0] = derivative(fy);

-

-    /* winding determined by summing signs of derivatives at intersections */

-    int winding=0;

-    for ( std::vector<double>::iterator ti = ts.begin()

-        ; ti != ts.end()

-        ; ++ti )

-    { 

-      double t = *ti;

-      if ( sb[X](t) >= p[X] ) { /* root is ray intersection */

-        for ( boost::optional<SBasis> *di = ds

-            ; di != ( ds + MAX_DERIVATIVES )

-            ; ++di )

-        {

-          if (!*di) {

-            *di = derivative(**(di-1));

-          }

-          switch (cmp((**di)(t), 0)) {

-          case GREATER_THAN:

-            if ( t < 1 ) { /* exclude final endpoint */

-              winding += 1;

-            }

-            goto next_root;

-          case LESS_THAN:

-            if ( t < 1 ) { /* exclude final endpoint */

-              winding -= 1;

-            }

-            goto next_root;

-          default: (void)0;

-            /* give up */

-          };

-        }

-      } 

-next_root: (void)0;

-    }

-    

-    return winding;

-  }

-}

-

-Rect BezierHelpers::bounds(unsigned degree, Point const *points) {

-  Point min=points[0];

-  Point max=points[0];

-  for ( unsigned i = 1 ; i <= degree ; ++i ) {

-    for ( unsigned axis = 0 ; axis < 2 ; ++axis ) {

-      min[axis] = std::min(min[axis], points[i][axis]);

-      max[axis] = std::max(max[axis], points[i][axis]);

-    }

-  }

-  return Rect(min, max);

-}

-

-Point BezierHelpers::point_and_derivatives_at(Coord t,

-                                              unsigned degree,

-                                              Point const *points,

-                                              unsigned n_derivs,

-                                              Point *derivs)

-{

-  return Point(0,0); // TODO

-}

-

-Geom::Point

-BezierHelpers::subdivideArr(Coord t,              // Parameter value

-                            unsigned degree,      // Degree of bezier curve

-                            Geom::Point const *V, // Control pts

-                            Geom::Point *Left,    // RETURN left half ctl pts

-                            Geom::Point *Right)   // RETURN right half ctl pts

-{

-    Geom::Point Vtemp[degree+1][degree+1];

-

-    /* Copy control points	*/

-    std::copy(V, V+degree+1, Vtemp[0]);

-

-    /* Triangle computation	*/

-    for (unsigned i = 1; i <= degree; i++) {	

-        for (unsigned j = 0; j <= degree - i; j++) {

-            Vtemp[i][j] = lerp(t, Vtemp[i-1][j], Vtemp[i-1][j+1]);

-        }

-    }

-    

-    for (unsigned j = 0; j <= degree; j++)

-        Left[j]  = Vtemp[j][0];

-    for (unsigned j = 0; j <= degree; j++)

-        Right[j] = Vtemp[degree-j][j];

-

-    return (Vtemp[degree][0]);

-}

-

-void Path::swap(Path &other) {

-  std::swap(curves_, other.curves_);

-  std::swap(closed_, other.closed_);

-  std::swap(*final_, *other.final_);

-  curves_[curves_.size()-1] = final_;

-  other.curves_[other.curves_.size()-1] = other.final_;

-}

-

-Rect Path::bounds_fast() const {

-  Rect bounds=front().bounds_fast();

-  for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {

-    bounds.unionWith(iter->bounds_fast());

-  }

-  return bounds;

-}

-

-Rect Path::bounds_exact() const {

-  Rect bounds=front().bounds_exact();

-  for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {

-    bounds.unionWith(iter->bounds_exact());

-  }

-  return bounds;

-}

-

-int Path::winding(Point p) const {

-  int winding = 0;

-  boost::optional<Cmp> ignore = boost::optional<Cmp>();

-  for ( const_iterator iter = begin()

-      ; iter != end_closed()

-      ; ++iter )

-  {

-    boost::optional<int> w = iter->winding(p);

-    if (w) {

-      winding += *w;

-      ignore = boost::optional<Cmp>();

-    } else {

-      Point initial = iter->initialPoint();

-      Point final = iter->finalPoint();

-      switch (cmp(initial[X], final[X])) {

-      case GREATER_THAN:

-        if ( !ignore || *ignore != GREATER_THAN ) { /* ignore repeated */

-          winding += 1;

-          ignore = GREATER_THAN;

-        }

-        break;

-      case LESS_THAN:

-        if ( !ignore || *ignore != LESS_THAN ) { /* ignore repeated */

-          if ( p[X] < final[X] ) { /* ignore final point */

-            winding -= 1;

-            ignore = LESS_THAN;

-          }

-        }

-        break;

-      case EQUAL_TO:

-        /* always ignore null segments */

-        break;

-      }

-    }

-  }

-  return winding;

-}

-

-void Path::append(Curve const &curve) {

-  if ( curves_.front() != final_ && curve.initialPoint() != (*final_)[0] ) {

-    throw ContinuityError();

-  }

-  do_append(curve.duplicate());

-}

-

-void Path::append(D2<SBasis> const &curve) {

-  if ( curves_.front() != final_ ) {

-    for ( int i = 0 ; i < 2 ; ++i ) {

-      if ( curve[i][0][0] != (*final_)[0][i] ) {

-        throw ContinuityError();

-      }

-    }

-  }

-  do_append(new SBasisCurve(curve));

-}

-

-void Path::do_update(Sequence::iterator first_replaced,

-                     Sequence::iterator last_replaced,

-                     Sequence::iterator first,

-                    Sequence::iterator last)

-{

-  // note: modifies the contents of [first,last)

-

-  check_continuity(first_replaced, last_replaced, first, last);

-  delete_range(first_replaced, last_replaced);

-  if ( ( last - first ) == ( last_replaced - first_replaced ) ) {

-    std::copy(first, last, first_replaced);

-  } else {

-    // this approach depends on std::vector's behavior WRT iterator stability

-    curves_.erase(first_replaced, last_replaced);

-    curves_.insert(first_replaced, first, last);

-  }

-

-  if ( curves_.front() != final_ ) {

-    (*final_)[0] = back().finalPoint();

-    (*final_)[1] = front().initialPoint();

-  }

-}

-

-void Path::do_append(Curve *curve) {

-  if ( curves_.front() == final_ ) {

-    (*final_)[1] = curve->initialPoint();

-  }

-  curves_.insert(curves_.end()-1, curve);

-  (*final_)[0] = curve->finalPoint();

-}

-

-void Path::delete_range(Sequence::iterator first, Sequence::iterator last) {

-  for ( Sequence::iterator iter=first ; iter != last ; ++iter ) {

-    delete *iter;

-  }

-}

-

-void Path::check_continuity(Sequence::iterator first_replaced,

-                            Sequence::iterator last_replaced,

-                            Sequence::iterator first,

-                            Sequence::iterator last)

-{

-  if ( first != last ) {

-    if ( first_replaced != curves_.begin() ) {

-      if ( (*first_replaced)->initialPoint() != (*first)->initialPoint() ) {

-        throw ContinuityError();

-      }

-    }

-    if ( last_replaced != (curves_.end()-1) ) {

-      if ( (*(last_replaced-1))->finalPoint() != (*(last-1))->finalPoint() ) {

-        throw ContinuityError();

-      }

-    }

-  } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) {

-    if ( (*first_replaced)->initialPoint() !=

-         (*(last_replaced-1))->finalPoint() )

-    {

-      throw ContinuityError();

-    }

-  }

-}

-

-Rect SBasisCurve::bounds_fast() const {

-  throw NotImplemented();

-  return Rect(Point(0,0), Point(0,0));

-}

-

-Rect SBasisCurve::bounds_exact() const {

-  throw NotImplemented();

-  return Rect(Point(0,0), Point(0,0));

-}

-

-Point SBasisCurve::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const {

-  throw NotImplemented();

-  return Point(0,0);

-}

-

-Path const &SBasisCurve::subdivide(Coord t, Path &out) const {

-  throw NotImplemented();

-}

-

-Rect SVGEllipticalArc::bounds_fast() const {

-    throw NotImplemented();

-}

-Rect SVGEllipticalArc::bounds_exact() const {

-    throw NotImplemented();

-}

-

-Point SVGEllipticalArc::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const {

-    throw NotImplemented();

-}

-

-D2<SBasis> SVGEllipticalArc::sbasis() const {

-    throw NotImplemented();

-}

-

-}

-

-/*

-  Local Variables:

-  mode:c++

-  c-file-style:"stroustrup"

-  c-file-offsets:((innamespace . 0)(substatement-open . 0))

-  indent-tabs-mode:nil

-  c-brace-offset:0

-  fill-column:99

-  End:

-  vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :

-*/

-

+/*
+ * Path - Series of continuous curves
+ *   
+ * Copyright 2007  MenTaLguY <mental@rydia.net>
+ *     
+ * This library is free software; you can redistribute it and/or 
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this 
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *            
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software 
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library 
+ * in the file COPYING-MPL-1.1
+ *                
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *                   
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+#include "path.h"
+
+#include "ord.h"
+
+namespace Geom {
+
+int CurveHelpers::root_winding(Curve const &c, Point p) {
+    std::vector<double> ts = c.roots(p[Y], Y);
+
+    if(ts.empty()) return 0;
+
+    double const fudge = 0.01; //fudge factor used on first and last
+
+    std::sort(ts.begin(), ts.end());
+
+    // winding determined by crossings at roots
+    int wind=0;
+    // previous time
+    double pt = ts.front() - fudge;
+    for ( std::vector<double>::iterator ti = ts.begin()
+        ; ti != ts.end()
+        ; ++ti )
+    {
+        double t = *ti;
+        if ( t <= 0. || t >= 1. ) continue; //skip endpoint roots 
+        if ( c.valueAt(t, X) > p[X] ) { // root is ray intersection
+            // Get t of next:
+            std::vector<double>::iterator next = ti;
+            next++;
+            double nt;
+            if(next == ts.end()) nt = t + fudge; else nt = *next;
+            
+            // Check before in time and after in time for positions
+            // Currently we're using the average times between next and previous segs
+            Cmp after_to_ray =  cmp(c.valueAt((t + nt) / 2, Y), p[Y]);
+            Cmp before_to_ray = cmp(c.valueAt((t + pt) / 2, Y), p[Y]);
+            // if y is included, these will have opposite values, giving order.
+            Cmp dt = cmp(after_to_ray, before_to_ray);
+            if(dt != EQUAL_TO) //Should always be true, but yah never know..
+                wind += dt;
+            pt = t;
+        }
+    }
+    
+    return wind;
+}
+
+void Path::swap(Path &other) {
+  std::swap(curves_, other.curves_);
+  std::swap(closed_, other.closed_);
+  std::swap(*final_, *other.final_);
+  curves_[curves_.size()-1] = final_;
+  other.curves_[other.curves_.size()-1] = other.final_;
+}
+
+Rect Path::boundsFast() const {
+  Rect bounds=front().boundsFast();
+  for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
+    bounds.unionWith(iter->boundsFast());
+  }
+  return bounds;
+}
+
+Rect Path::boundsExact() const {
+  Rect bounds=front().boundsExact();
+  for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
+    bounds.unionWith(iter->boundsExact());
+  }
+  return bounds;
+}
+
+template<typename iter>
+iter inc(iter const &x, unsigned n) {
+  iter ret = x;
+  for(unsigned i = 0; i < n; i++)
+    ret++;
+  return ret;
+}
+
+//This assumes that you can't be perfect in your t-vals, and as such, tweaks the start
+void Path::appendPortionTo(Path &ret, double from, double to) const {
+  assert(from >= 0 && to >= 0);
+  if(to == 0) to = size()+0.999999;
+  if(from == to) { return; }
+  double fi, ti;
+  double ff = modf(from, &fi), tf = modf(to, &ti);
+  if(tf == 0) { ti--; tf = 1; }
+  const_iterator fromi = inc(begin(), (unsigned)fi);
+  if(fi == ti && from < to) {
+    Curve *v = fromi->portion(ff, tf);
+    ret.append(*v);
+    delete v;
+    return;
+  }
+  const_iterator toi   = inc(begin(), (unsigned)ti);
+  if(ff != 1.) {
+    Curve *fromv = fromi->portion(ff, 1.);
+    //fromv->setInitial(ret.finalPoint());
+    ret.append(*fromv);
+    delete fromv;
+  }
+  if(from > to) {
+    const_iterator ender = end();
+    if(ender->initialPoint() == ender->finalPoint()) ender++;
+    ret.insert(ret.end(), ++fromi, ender);
+    ret.insert(ret.end(), begin(), toi);
+  } else {
+    ret.insert(ret.end(), ++fromi, toi);
+  }
+  Curve *tov = toi->portion(0., tf);
+  ret.append(*tov);
+  delete tov;
+}
+
+const double eps = .1;
+
+void Path::append(Curve const &curve) {
+  if ( curves_.front() != final_ && !near(curve.initialPoint(), (*final_)[0], eps) ) {
+    throw ContinuityError();
+  }
+  do_append(curve.duplicate());
+}
+
+void Path::append(D2<SBasis> const &curve) {
+  if ( curves_.front() != final_ ) {
+    for ( int i = 0 ; i < 2 ; ++i ) {
+      if ( !near(curve[i][0][0], (*final_)[0][i], eps) ) {
+        throw ContinuityError();
+      }
+    }
+  }
+  do_append(new SBasisCurve(curve));
+}
+
+void Path::do_update(Sequence::iterator first_replaced,
+                     Sequence::iterator last_replaced,
+                     Sequence::iterator first,
+                    Sequence::iterator last)
+{
+  // note: modifies the contents of [first,last)
+
+  check_continuity(first_replaced, last_replaced, first, last);
+  delete_range(first_replaced, last_replaced);
+  if ( ( last - first ) == ( last_replaced - first_replaced ) ) {
+    std::copy(first, last, first_replaced);
+  } else {
+    // this approach depends on std::vector's behavior WRT iterator stability
+    curves_.erase(first_replaced, last_replaced);
+    curves_.insert(first_replaced, first, last);
+  }
+
+  if ( curves_.front() != final_ ) {
+    final_->setPoint(0, back().finalPoint());
+    final_->setPoint(1, front().initialPoint());
+  }
+}
+
+void Path::do_append(Curve *curve) {
+  if ( curves_.front() == final_ ) {
+    final_->setPoint(1, curve->initialPoint());
+  }
+  curves_.insert(curves_.end()-1, curve);
+  final_->setPoint(0, curve->finalPoint());
+}
+
+void Path::delete_range(Sequence::iterator first, Sequence::iterator last) {
+  for ( Sequence::iterator iter=first ; iter != last ; ++iter ) {
+    delete *iter;
+  }
+}
+
+void Path::check_continuity(Sequence::iterator first_replaced,
+                            Sequence::iterator last_replaced,
+                            Sequence::iterator first,
+                            Sequence::iterator last)
+{
+  if ( first != last ) {
+    if ( first_replaced != curves_.begin() ) {
+      if ( !near( (*first_replaced)->initialPoint(), (*first)->initialPoint(), eps ) ) {
+        throw ContinuityError();
+      }
+    }
+    if ( last_replaced != (curves_.end()-1) ) {
+      if ( !near( (*(last_replaced-1))->finalPoint(), (*(last-1))->finalPoint(), eps ) ) {
+        throw ContinuityError();
+      }
+    }
+  } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) {
+    if ( !near((*first_replaced)->initialPoint(), (*(last_replaced-1))->finalPoint(), eps ) ) {
+      throw ContinuityError();
+    }
+  }
+}
+
+Rect SVGEllipticalArc::boundsFast() const {
+    throw NotImplemented();
+}
+Rect SVGEllipticalArc::boundsExact() const {
+    throw NotImplemented();
+}
+Rect SVGEllipticalArc::boundsLocal(Interval i, unsigned deg) const {
+    //throw NotImplemented();
+}
+
+std::vector<Point> SVGEllipticalArc::pointAndDerivatives(Coord t, unsigned n) const {
+    throw NotImplemented();
+}
+
+std::vector<double> SVGEllipticalArc::roots(double v, Dim2 d) const {
+    //throw NotImplemented();
+}
+
+D2<SBasis> SVGEllipticalArc::toSBasis() const {
+    return D2<SBasis>(Linear(initial_[X], final_[X]), Linear(initial_[Y], final_[Y]));
+}
+
+}
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(substatement-open . 0))
+  indent-tabs-mode:nil
+  c-brace-offset:0
+  fill-column:99
+  End:
+  vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :
+*/