src/2geom/path.h

   1 /*
   2  * Path - Series of continuous curves
   3  *
   4  * Authors:
   5  *              MenTaLguY <mental@rydia.net>
   6  *              Marco Cecchetti <mrcekets at gmail.com>
   7  *
   8  * Copyright 2007-2008  authors
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it either under the terms of the GNU Lesser General Public
  12  * License version 2.1 as published by the Free Software Foundation
  13  * (the "LGPL") or, at your option, under the terms of the Mozilla
  14  * Public License Version 1.1 (the "MPL"). If you do not alter this
  15  * notice, a recipient may use your version of this file under either
  16  * the MPL or the LGPL.
  17  *
  18  * You should have received a copy of the LGPL along with this library
  19  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  21  * You should have received a copy of the MPL along with this library
  22  * in the file COPYING-MPL-1.1
  23  *
  24  * The contents of this file are subject to the Mozilla Public License
  25  * Version 1.1 (the "License"); you may not use this file except in
  26  * compliance with the License. You may obtain a copy of the License at
  27  * http://www.mozilla.org/MPL/
  28  *
  29  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  30  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  31  * the specific language governing rights and limitations.
  32  */
  33
  34 #ifndef SEEN_GEOM_PATH_H
  35 #define SEEN_GEOM_PATH_H
  36
  37 #include "point.h"
  38 #include "angle.h"
  39 #include <iterator>
  40 #include <algorithm>
  41 #include "exception.h"
  42 #include "d2.h"
  43 #include "matrix.h"
  44 #include "bezier.h"
  45 #include "crossing.h"
  46 #include "utils.h"
  47
  48 namespace Geom {
  49
  50 class Curve;
  51
  52 struct CurveHelpers {
  53 protected:
  54   static int root_winding(Curve const &c, Point p);
  55 };
  56
  57 class Curve : private CurveHelpers {
  58 public:
  59   virtual ~Curve() {}
  60
  61   virtual Point initialPoint() const = 0;
  62   virtual Point finalPoint() const = 0;
  63
  64   virtual bool isDegenerate() const = 0;
  65
  66   virtual Curve *duplicate() const = 0;
  67
  68   virtual Rect boundsFast() const = 0;
  69   virtual Rect boundsExact() const = 0;
  70   virtual Rect boundsLocal(Interval i, unsigned deg) const = 0;
  71   Rect boundsLocal(Interval i) const { return boundsLocal(i, 0); }
  72
  73   virtual std::vector<double> roots(double v, Dim2 d) const = 0;
  74
  75   virtual int winding(Point p) const { return root_winding(*this, p); }
  76
  77   //mental: review these
  78   virtual Curve *portion(double f, double t) const = 0;
  79   virtual Curve *reverse() const { return portion(1, 0); }
  80   virtual Curve *derivative() const = 0;
  81
  82   virtual void setInitial(Point v) = 0;
  83   virtual void setFinal(Point v) = 0;
  84
  85   virtual Curve *transformed(Matrix const &m) const = 0;
  86
  87   virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); }
  88   virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; }
  89   virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0;
  90   virtual D2<SBasis> toSBasis() const = 0;
  91 };
  92
  93 class SBasisCurve : public Curve {
  94 private:
  95   SBasisCurve();
  96   D2<SBasis> inner;
  97 public:
  98   explicit SBasisCurve(D2<SBasis> const &sb) : inner(sb) {}
  99   explicit SBasisCurve(Curve const &other) : inner(other.toSBasis()) {}
 100   Curve *duplicate() const { return new SBasisCurve(*this); }
 101
 102   Point initialPoint() const    { return inner.at0(); }
 103   Point finalPoint() const      { return inner.at1(); }
 104   bool isDegenerate() const     { return inner.isConstant(); }
 105   Point pointAt(Coord t) const  { return inner.valueAt(t); }
 106   std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const {
 107       return inner.valueAndDerivatives(t, n);
 108   }
 109   double valueAt(Coord t, Dim2 d) const { return inner[d].valueAt(t); }
 110
 111   void setInitial(Point v) { for(unsigned d = 0; d < 2; d++) { inner[d][0][0] = v[d]; } }
 112   void setFinal(Point v)   { for(unsigned d = 0; d < 2; d++) { inner[d][0][1] = v[d]; } }
 113
 114   Rect boundsFast() const  { return bounds_fast(inner); }
 115   Rect boundsExact() const { return bounds_exact(inner); }
 116   Rect boundsLocal(Interval i, unsigned deg) const { return bounds_local(inner, i, deg); }
 117
 118   std::vector<double> roots(double v, Dim2 d) const { return Geom::roots(inner[d] - v); }
 119
 120   Curve *portion(double f, double t) const {
 121     return new SBasisCurve(Geom::portion(inner, f, t));
 122   }
 123
 124   Curve *transformed(Matrix const &m) const {
 125     return new SBasisCurve(inner * m);
 126   }
 127
 128   Curve *derivative() const {
 129     return new SBasisCurve(Geom::derivative(inner));
 130   }
 131
 132   D2<SBasis> toSBasis() const { return inner; }
 133
 134 };
 135
 136 template <unsigned order>
 137 class BezierCurve : public Curve {
 138 private:
 139   D2<Bezier > inner;
 140 public:
 141   template <unsigned required_degree>
 142   static void assert_degree(BezierCurve<required_degree> const *) {}
 143
 144   BezierCurve() : inner(Bezier::Order(order), Bezier::Order(order)) {
 145   }
 146
 147   explicit BezierCurve(D2<Bezier > const &x) : inner(x) {}
 148
 149   BezierCurve(Bezier x, Bezier y) : inner(x, y) {}
 150
 151   // default copy
 152   // default assign
 153
 154   BezierCurve(Point c0, Point c1) {
 155     assert_degree<1>(this);
 156     for(unsigned d = 0; d < 2; d++)
 157         inner[d] = Bezier(c0[d], c1[d]);
 158   }
 159
 160   BezierCurve(Point c0, Point c1, Point c2) {
 161     assert_degree<2>(this);
 162     for(unsigned d = 0; d < 2; d++)
 163         inner[d] = Bezier(c0[d], c1[d], c2[d]);
 164   }
 165
 166   BezierCurve(Point c0, Point c1, Point c2, Point c3) {
 167     assert_degree<3>(this);
 168     for(unsigned d = 0; d < 2; d++)
 169         inner[d] = Bezier(c0[d], c1[d], c2[d], c3[d]);
 170   }
 171
 172   unsigned degree() const { return order; }
 173
 174   Curve *duplicate() const { return new BezierCurve(*this); }
 175
 176   Point initialPoint() const { return inner.at0(); }
 177   Point finalPoint() const { return inner.at1(); }
 178
 179   bool isDegenerate() const { return inner.isConstant(); }
 180
 181   void setInitial(Point v) { setPoint(0, v); }
 182   void setFinal(Point v)   { setPoint(1, v); }
 183
 184   void setPoint(unsigned ix, Point v) { inner[X].setPoint(ix, v[X]); inner[Y].setPoint(ix, v[Y]); }
 185   Point const operator[](unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); }
 186
 187   Rect boundsFast() const { return bounds_fast(inner); }
 188   Rect boundsExact() const { return bounds_exact(inner); }
 189   Rect boundsLocal(Interval i, unsigned deg) const {
 190       if(i.min() == 0 && i.max() == 1) return boundsFast();
 191       if(deg == 0) return bounds_local(inner, i);
 192       // TODO: UUUUUUGGGLLY
 193       if(deg == 1 && order > 1) return Rect(bounds_local(Geom::derivative(inner[X]), i),
 194                                             bounds_local(Geom::derivative(inner[Y]), i));
 195       return Rect(Interval(0,0), Interval(0,0));
 196   }
 197 //TODO: local
 198
 199 //TODO: implement next 3 natively
 200   int winding(Point p) const {
 201     return SBasisCurve(toSBasis()).winding(p);
 202   }
 203
 204   std::vector<double>
 205   roots(double v, Dim2 d) const {
 206       return (inner[d] - v).roots();
 207   }
 208
 209   void setPoints(std::vector<Point> ps) {
 210     for(unsigned i = 0; i <= order; i++) {
 211       setPoint(i, ps[i]);
 212     }
 213   }
 214   std::vector<Point> points() const { return bezier_points(inner); }
 215
 216   std::pair<BezierCurve<order>, BezierCurve<order> > subdivide(Coord t) const {
 217     std::pair<Bezier, Bezier > sx = inner[X].subdivide(t), sy = inner[Y].subdivide(t);
 218     return std::pair<BezierCurve<order>, BezierCurve<order> >(
 219                BezierCurve<order>(sx.first, sy.first),
 220                BezierCurve<order>(sx.second, sy.second));
 221   }
 222
 223   Curve *portion(double f, double t) const {
 224     return new BezierCurve(Geom::portion(inner, f, t));
 225   }
 226
 227   Curve *reverse() const {
 228     return new BezierCurve(Geom::reverse(inner));
 229   }
 230
 231   Curve *transformed(Matrix const &m) const {
 232     BezierCurve *ret = new BezierCurve();
 233     std::vector<Point> ps = points();
 234     for(unsigned i = 0;  i <= order; i++) ps[i] = ps[i] * m;
 235     ret->setPoints(ps);
 236     return ret;
 237   }
 238
 239   Curve *derivative() const {
 240      if(order > 1)
 241         return new BezierCurve<order-1>(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
 242      else if (order == 1) {
 243         double dx = inner[X][1] - inner[X][0], dy = inner[Y][1] - inner[Y][0];
 244         return new BezierCurve<1>(Point(dx,dy),Point(dx,dy));
 245      }
 246   }
 247
 248   Point pointAt(double t) const { return inner.valueAt(t); }
 249   std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const { return inner.valueAndDerivatives(t, n); }
 250
 251   double valueAt(double t, Dim2 d) const { return inner[d].valueAt(t); }
 252
 253   D2<SBasis> toSBasis() const {return inner.toSBasis(); }
 254
 255 protected:
 256   BezierCurve(Point c[]) {
 257     Coord x[order+1], y[order+1];
 258     for(unsigned i = 0; i <= order; i++) {
 259         x[i] = c[i][X]; y[i] = c[i][Y];
 260     }
 261     inner = Bezier(x, y);
 262   }
 263 };
 264
 265 // BezierCurve<0> is meaningless; specialize it out
 266 template<> class BezierCurve<0> : public BezierCurve<1> { public: BezierCurve(); BezierCurve(Bezier x, Bezier y); };
 267
 268 typedef BezierCurve<1> LineSegment;
 269 typedef BezierCurve<2> QuadraticBezier;
 270 typedef BezierCurve<3> CubicBezier;
 271
 272
 273
 274
 275 class SVGEllipticalArc : public Curve
 276 {
 277   public:
 278         SVGEllipticalArc()
 279         {}
 280
 281     SVGEllipticalArc( Point _initial_point, double _rx, double _ry,
 282                       double _rot_angle, bool _large_arc, bool _sweep,
 283                       Point _final_point
 284                     )
 285         : m_initial_point(_initial_point), m_final_point(_final_point),
 286           m_rx(_rx), m_ry(_ry), m_rot_angle(_rot_angle),
 287           m_large_arc(_large_arc), m_sweep(_sweep)
 288     {
 289         //assert( (ray(X) >= 0) && (ray(Y) >= 0) );
 290         if ( are_near(initialPoint(), finalPoint()) )
 291         {
 292             m_start_angle = m_end_angle = 0;
 293             m_center = initialPoint();
 294         }
 295         else
 296         {
 297             calculate_center_and_extreme_angles();
 298         }
 299     }
 300
 301         Curve* duplicate() const
 302         {
 303                 return new SVGEllipticalArc(*this);
 304         }
 305
 306     double center(Dim2 i) const
 307     {
 308         return m_center[i];
 309     }
 310
 311     Point center() const
 312     {
 313         return m_center;
 314     }
 315
 316     Point initialPoint() const
 317     {
 318         return m_initial_point;
 319     }
 320
 321     Point finalPoint() const
 322     {
 323         return m_final_point;
 324     }
 325
 326     double start_angle() const
 327     {
 328         return m_start_angle;
 329     }
 330
 331     double end_angle() const
 332     {
 333         return m_end_angle;
 334     }
 335
 336     double ray(Dim2 i) const
 337     {
 338         return (i == 0) ? m_rx : m_ry;
 339     }
 340
 341     bool large_arc_flag() const
 342     {
 343         return m_large_arc;
 344     }
 345
 346     bool sweep_flag() const
 347     {
 348         return m_sweep;
 349     }
 350
 351     double rotation_angle() const
 352     {
 353         return m_rot_angle;
 354     }
 355
 356     void setInitial( const Point _point)
 357     {
 358         m_initial_point = _point;
 359         calculate_center_and_extreme_angles();
 360     }
 361
 362     void setFinal( const Point _point)
 363     {
 364         m_final_point = _point;
 365         calculate_center_and_extreme_angles();
 366     }
 367
 368     void setExtremes( const Point& _initial_point, const Point& _final_point )
 369     {
 370         m_initial_point = _initial_point;
 371         m_final_point = _final_point;
 372         calculate_center_and_extreme_angles();
 373     }
 374
 375     bool isDegenerate() const
 376     {
 377         return are_near(initialPoint(), finalPoint());
 378     }
 379
 380     // TODO: native implementation of the following methods
 381     Rect boundsFast() const
 382     {
 383         return SBasisCurve(toSBasis()).boundsFast();
 384     }
 385
 386     Rect boundsExact() const
 387     {
 388         return SBasisCurve(toSBasis()).boundsExact();
 389     }
 390
 391     Rect boundsLocal(Interval i, unsigned int deg) const
 392     {
 393         return SBasisCurve(toSBasis()).boundsLocal(i, deg);
 394     }
 395
 396     std::vector<double> roots(double v, Dim2 d) const
 397     {
 398         return SBasisCurve(toSBasis()).roots(v, d);
 399     }
 400
 401     int winding(Point p) const
 402     {
 403         return SBasisCurve(toSBasis()).winding(p);
 404     }
 405
 406     Curve *derivative() const
 407     {
 408         return SBasisCurve(toSBasis()).derivative();
 409     }
 410
 411     Curve *transformed(Matrix const &m) const
 412     {
 413         return SBasisCurve(toSBasis()).transformed(m);
 414     }
 415
 416     std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const
 417     {
 418         return SBasisCurve(toSBasis()).pointAndDerivatives(t, n);
 419     }
 420
 421     D2<SBasis> toSBasis() const;
 422
 423     double valueAt(Coord t, Dim2 d) const;
 424
 425     Point pointAt(Coord t) const
 426     {
 427         Coord tt = from_01_to_02PI(t);
 428         double sin_rot_angle = std::sin(rotation_angle());
 429         double cos_rot_angle = std::cos(rotation_angle());
 430         Matrix m( ray(X) * cos_rot_angle, ray(X) * sin_rot_angle,
 431                  -ray(Y) * sin_rot_angle, ray(Y) * cos_rot_angle,
 432                   center(X),              center(Y) );
 433         Point p( std::cos(tt), std::sin(tt) );
 434         return p * m;
 435     }
 436
 437     std::pair<SVGEllipticalArc, SVGEllipticalArc>
 438     subdivide(Coord t) const
 439     {
 440         SVGEllipticalArc* arc1 = static_cast<SVGEllipticalArc*>(portion(0, t));
 441         SVGEllipticalArc* arc2 = static_cast<SVGEllipticalArc*>(portion(t, 1));
 442         assert( arc1 != NULL && arc2 != NULL);
 443         std::pair<SVGEllipticalArc, SVGEllipticalArc> arc_pair(*arc1, *arc2);
 444         delete arc1;
 445         delete arc2;
 446         return arc_pair;
 447     }
 448
 449     Curve* portion(double f, double t) const;
 450
 451     // the arc is the same but traversed in the opposite direction
 452     Curve* reverse() const
 453     {
 454         SVGEllipticalArc* rarc = new SVGEllipticalArc( *this );
 455         rarc->m_sweep = !m_sweep;
 456         rarc->m_initial_point = m_final_point;
 457         rarc->m_final_point = m_initial_point;
 458         rarc->m_start_angle = m_end_angle;
 459         rarc->m_end_angle = m_start_angle;
 460         return rarc;
 461     }
 462
 463   private:
 464     double sweep_angle() const
 465     {
 466         Coord d = end_angle() - start_angle();
 467         if ( !sweep_flag() ) d = -d;
 468         if ( d < 0 )
 469             d += 2*M_PI;
 470         return d;
 471     }
 472
 473     Coord from_01_to_02PI(Coord t) const;
 474
 475     void calculate_center_and_extreme_angles() throw(RangeError);
 476
 477   private:
 478     Point m_initial_point, m_final_point;
 479     double m_rx, m_ry, m_rot_angle;
 480     bool m_large_arc, m_sweep;
 481     double m_start_angle, m_end_angle;
 482     Point m_center;
 483
 484 }; // end class SVGEllipticalArc
 485
 486
 487
 488
 489 template <typename IteratorImpl>
 490 class BaseIterator
 491 : public std::iterator<std::forward_iterator_tag, Curve const>
 492 {
 493 public:
 494   BaseIterator() {}
 495
 496   // default construct
 497   // default copy
 498
 499   bool operator==(BaseIterator const &other) {
 500     return other.impl_ == impl_;
 501   }
 502   bool operator!=(BaseIterator const &other) {
 503     return other.impl_ != impl_;
 504   }
 505
 506   Curve const &operator*() const { return **impl_; }
 507   Curve const *operator->() const { return *impl_; }
 508
 509   BaseIterator &operator++() {
 510     ++impl_;
 511     return *this;
 512   }
 513
 514   BaseIterator operator++(int) {
 515     BaseIterator old=*this;
 516     ++(*this);
 517     return old;
 518   }
 519
 520 private:
 521   BaseIterator(IteratorImpl const &pos) : impl_(pos) {}
 522
 523   IteratorImpl impl_;
 524   friend class Path;
 525 };
 526
 527 template <typename Iterator>
 528 class DuplicatingIterator
 529 : public std::iterator<std::input_iterator_tag, Curve *>
 530 {
 531 public:
 532   DuplicatingIterator() {}
 533   DuplicatingIterator(Iterator const &iter) : impl_(iter) {}
 534
 535   bool operator==(DuplicatingIterator const &other) {
 536     return other.impl_ == impl_;
 537   }
 538   bool operator!=(DuplicatingIterator const &other) {
 539     return other.impl_ != impl_;
 540   }
 541
 542   Curve *operator*() const { return (*impl_)->duplicate(); }
 543
 544   DuplicatingIterator &operator++() {
 545     ++impl_;
 546     return *this;
 547   }
 548   DuplicatingIterator operator++(int) {
 549     DuplicatingIterator old=*this;
 550     ++(*this);
 551     return old;
 552   }
 553
 554 private:
 555   Iterator impl_;
 556 };
 557
 558 class Path {
 559 private:
 560   typedef std::vector<Curve *> Sequence;
 561
 562 public:
 563   typedef BaseIterator<Sequence::iterator> iterator;
 564   typedef BaseIterator<Sequence::const_iterator> const_iterator;
 565   typedef Sequence::size_type size_type;
 566   typedef Sequence::difference_type difference_type;
 567
 568   Path()
 569   : final_(new LineSegment()), closed_(false)
 570   {
 571     curves_.push_back(final_);
 572   }
 573
 574   Path(Path const &other)
 575   : final_(new LineSegment()), closed_(other.closed_)
 576   {
 577     curves_.push_back(final_);
 578     insert(begin(), other.begin(), other.end());
 579   }
 580
 581   explicit Path(Point p)
 582   : final_(new LineSegment(p, p)), closed_(false)
 583   {
 584     curves_.push_back(final_);
 585   }
 586
 587   template <typename Impl>
 588   Path(BaseIterator<Impl> first, BaseIterator<Impl> last, bool closed=false)
 589   : closed_(closed), final_(new LineSegment())
 590   {
 591     curves_.push_back(final_);
 592     insert(begin(), first, last);
 593   }
 594
 595   virtual ~Path() {
 596       delete_range(curves_.begin(), curves_.end()-1);
 597       delete final_;
 598   }
 599
 600   Path &operator=(Path const &other) {
 601     clear();
 602     insert(begin(), other.begin(), other.end());
 603     close(other.closed_);
 604     return *this;
 605   }
 606
 607   void swap(Path &other);
 608
 609   Curve const &operator[](unsigned i) const { return *curves_[i]; }
 610
 611   iterator begin() { return curves_.begin(); }
 612   iterator end() { return curves_.end()-1; }
 613
 614   Curve const &front() const { return *curves_[0]; }
 615   Curve const &back() const { return *curves_[curves_.size()-2]; }
 616
 617   const_iterator begin() const { return curves_.begin(); }
 618   const_iterator end() const { return curves_.end()-1; }
 619
 620   const_iterator end_open() const { return curves_.end()-1; }
 621   const_iterator end_closed() const { return curves_.end(); }
 622   const_iterator end_default() const {
 623     return ( closed_ ? end_closed() : end_open() );
 624   }
 625
 626   size_type size() const { return curves_.size()-1; }
 627   size_type max_size() const { return curves_.max_size()-1; }
 628
 629   bool empty() const { return curves_.size() == 1; }
 630   bool closed() const { return closed_; }
 631   void close(bool closed=true) { closed_ = closed; }
 632
 633   Rect boundsFast() const;
 634   Rect boundsExact() const;
 635
 636   Piecewise<D2<SBasis> > toPwSb() const {
 637     Piecewise<D2<SBasis> > ret;
 638     ret.push_cut(0);
 639     unsigned i = 1;
 640     // pw<d2<>> is always open. so if path is closed, add closing segment as well to pwd2.
 641     for(const_iterator it = begin(); it != end_default(); ++it) {
 642       if (!it->isDegenerate()) {
 643         ret.push(it->toSBasis(), i++);
 644       }
 645     }
 646     return ret;
 647   }
 648
 649   Path operator*(Matrix const &m) const {
 650     Path ret;
 651     for(const_iterator it = begin(); it != end(); ++it) {
 652       Curve *temp = it->transformed(m);
 653       //Possible point of discontinuity?
 654       ret.append(*temp);
 655       delete temp;
 656     }
 657     return ret;
 658   }
 659
 660   Point pointAt(double t) const {
 661     if(empty()) return Point(0,0);
 662     double i, f = modf(t, &i);
 663     if(i == size() && f == 0) { i--; }
 664     assert(i >= 0 && i <= size());
 665     return (*this)[unsigned(i)].pointAt(f);
 666   }
 667
 668   double valueAt(double t, Dim2 d) const {
 669     if(empty()) return 0;
 670     double i, f = modf(t, &i);
 671     if(i == size() && f == 0) { i--; }
 672     assert(i >= 0 && i <= size());
 673     return (*this)[unsigned(i)].valueAt(f, d);
 674   }
 675
 676   std::vector<double> roots(double v, Dim2 d) const {
 677     std::vector<double> res;
 678     for(unsigned i = 0; i <= size(); i++) {
 679       std::vector<double> temp = (*this)[i].roots(v, d);
 680       for(unsigned j = 0; j < temp.size(); j++)
 681         res.push_back(temp[j] + i);
 682     }
 683     return res;
 684   }
 685
 686   void appendPortionTo(Path &p, double f, double t) const;
 687
 688   Path portion(double f, double t) const {
 689     Path ret;
 690     ret.close(false);
 691     appendPortionTo(ret, f, t);
 692     return ret;
 693   }
 694   Path portion(Interval i) const { return portion(i.min(), i.max()); }
 695
 696   Path reverse() const {
 697     Path ret;
 698     ret.close(closed_);
 699     for(int i = size() - (closed_ ? 0 : 1); i >= 0; i--) {
 700       //TODO: do we really delete?
 701       Curve *temp = (*this)[i].reverse();
 702       ret.append(*temp);
 703       delete temp;
 704     }
 705     return ret;
 706   }
 707
 708   void insert(iterator pos, Curve const &curve) {
 709     Sequence source(1, curve.duplicate());
 710     try {
 711       do_update(pos.impl_, pos.impl_, source.begin(), source.end());
 712     } catch (...) {
 713       delete_range(source.begin(), source.end());
 714       throw;
 715     }
 716   }
 717
 718   template <typename Impl>
 719   void insert(iterator pos, BaseIterator<Impl> first, BaseIterator<Impl> last)
 720   {
 721     Sequence source(DuplicatingIterator<Impl>(first.impl_),
 722                     DuplicatingIterator<Impl>(last.impl_));
 723     try {
 724       do_update(pos.impl_, pos.impl_, source.begin(), source.end());
 725     } catch (...) {
 726       delete_range(source.begin(), source.end());
 727       throw;
 728     }
 729   }
 730
 731   void clear() {
 732     do_update(curves_.begin(), curves_.end()-1,
 733               curves_.begin(), curves_.begin());
 734   }
 735
 736   void erase(iterator pos) {
 737     do_update(pos.impl_, pos.impl_+1, curves_.begin(), curves_.begin());
 738   }
 739
 740   void erase(iterator first, iterator last) {
 741     do_update(first.impl_, last.impl_, curves_.begin(), curves_.begin());
 742   }
 743
 744   void replace(iterator replaced, Curve const &curve) {
 745     Sequence source(1, curve.duplicate());
 746     try {
 747       do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
 748     } catch (...) {
 749       delete_range(source.begin(), source.end());
 750       throw;
 751     }
 752   }
 753
 754   void replace(iterator first_replaced, iterator last_replaced,
 755                Curve const &curve)
 756   {
 757     Sequence source(1, curve.duplicate());
 758     try {
 759       do_update(first_replaced.impl_, last_replaced.impl_,
 760                 source.begin(), source.end());
 761     } catch (...) {
 762       delete_range(source.begin(), source.end());
 763       throw;
 764     }
 765   }
 766
 767   template <typename Impl>
 768   void replace(iterator replaced,
 769                BaseIterator<Impl> first, BaseIterator<Impl> last)
 770   {
 771     Sequence source(DuplicatingIterator<Impl>(first.impl_),
 772                     DuplicatingIterator<Impl>(last.impl_));
 773     try {
 774       do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
 775     } catch (...) {
 776       delete_range(source.begin(), source.end());
 777       throw;
 778     }
 779   }
 780
 781   template <typename Impl>
 782   void replace(iterator first_replaced, iterator last_replaced,
 783                BaseIterator<Impl> first, BaseIterator<Impl> last)
 784   {
 785     Sequence source(first.impl_, last.impl_);
 786     try {
 787       do_update(first_replaced.impl_, last_replaced.impl_,
 788                 source.begin(), source.end());
 789     } catch (...) {
 790       delete_range(source.begin(), source.end());
 791       throw;
 792     }
 793   }
 794
 795   void start(Point p) {
 796     clear();
 797     final_->setPoint(0, p);
 798     final_->setPoint(1, p);
 799   }
 800
 801   Point initialPoint() const { return (*final_)[1]; }
 802   Point finalPoint() const { return (*final_)[0]; }
 803
 804   void append(Curve const &curve);
 805   void append(D2<SBasis> const &curve);
 806
 807   template <typename CurveType, typename A>
 808   void appendNew(A a) {
 809     do_append(new CurveType((*final_)[0], a));
 810   }
 811
 812   template <typename CurveType, typename A, typename B>
 813   void appendNew(A a, B b) {
 814     do_append(new CurveType((*final_)[0], a, b));
 815   }
 816
 817   template <typename CurveType, typename A, typename B, typename C>
 818   void appendNew(A a, B b, C c) {
 819     do_append(new CurveType((*final_)[0], a, b, c));
 820   }
 821
 822   template <typename CurveType, typename A, typename B, typename C,
 823                                 typename D>
 824   void appendNew(A a, B b, C c, D d) {
 825     do_append(new CurveType((*final_)[0], a, b, c, d));
 826   }
 827
 828   template <typename CurveType, typename A, typename B, typename C,
 829                                 typename D, typename E>
 830   void appendNew(A a, B b, C c, D d, E e) {
 831     do_append(new CurveType((*final_)[0], a, b, c, d, e));
 832   }
 833
 834   template <typename CurveType, typename A, typename B, typename C,
 835                                 typename D, typename E, typename F>
 836   void appendNew(A a, B b, C c, D d, E e, F f) {
 837     do_append(new CurveType((*final_)[0], a, b, c, d, e, f));
 838   }
 839
 840   template <typename CurveType, typename A, typename B, typename C,
 841                                 typename D, typename E, typename F,
 842                                 typename G>
 843   void appendNew(A a, B b, C c, D d, E e, F f, G g) {
 844     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g));
 845   }
 846
 847   template <typename CurveType, typename A, typename B, typename C,
 848                                 typename D, typename E, typename F,
 849                                 typename G, typename H>
 850   void appendNew(A a, B b, C c, D d, E e, F f, G g, H h) {
 851     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h));
 852   }
 853
 854   template <typename CurveType, typename A, typename B, typename C,
 855                                 typename D, typename E, typename F,
 856                                 typename G, typename H, typename I>
 857   void appendNew(A a, B b, C c, D d, E e, F f, G g, H h, I i) {
 858     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h, i));
 859   }
 860
 861 private:
 862   void do_update(Sequence::iterator first_replaced,
 863                  Sequence::iterator last_replaced,
 864                  Sequence::iterator first,
 865                  Sequence::iterator last);
 866
 867   void do_append(Curve *curve);
 868
 869   void delete_range(Sequence::iterator first, Sequence::iterator last);
 870
 871   void check_continuity(Sequence::iterator first_replaced,
 872                         Sequence::iterator last_replaced,
 873                         Sequence::iterator first,
 874                         Sequence::iterator last);
 875
 876   Sequence curves_;
 877   LineSegment *final_;
 878   bool closed_;
 879 };
 880
 881 inline static Piecewise<D2<SBasis> > paths_to_pw(std::vector<Path> paths) {
 882     Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
 883     for(unsigned i = 1; i < paths.size(); i++) {
 884         ret.concat(paths[i].toPwSb());
 885     }
 886     return ret;
 887 }
 888
 889 /*
 890 class PathPortion : public Curve {
 891   Path *source;
 892   double f, t;
 893   boost::optional<Path> result;
 894
 895   public:
 896   double from() const { return f; }
 897   double to() const { return t; }
 898
 899   explicit PathPortion(Path *s, double fp, double tp) : source(s), f(fp), t(tp) {}
 900   Curve *duplicate() const { return new PathPortion(*this); }
 901
 902   Point initialPoint() const { return source->pointAt(f); }
 903   Point finalPoint() const { return source->pointAt(t); }
 904
 905   Path actualPath() {
 906     if(!result) *result = source->portion(f, t);
 907     return *result;
 908   }
 909
 910   Rect boundsFast() const { return actualPath().boundsFast; }
 911   Rect boundsExact() const { return actualPath().boundsFast; }
 912   Rect boundsLocal(Interval i) const { throwNotImplemented(); }
 913
 914   std::vector<double> roots(double v, Dim2 d) const = 0;
 915
 916   virtual int winding(Point p) const { return root_winding(*this, p); }
 917
 918   virtual Curve *portion(double f, double t) const = 0;
 919   virtual Curve *reverse() const { return portion(1, 0); }
 920
 921   virtual Crossings crossingsWith(Curve const & other) const;
 922
 923   virtual void setInitial(Point v) = 0;
 924   virtual void setFinal(Point v) = 0;
 925
 926   virtual Curve *transformed(Matrix const &m) const = 0;
 927
 928   virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); }
 929   virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; }
 930   virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0;
 931   virtual D2<SBasis> toSBasis() const = 0;
 932
 933 };
 934 */
 935
 936 }
 937
 938 namespace std {
 939
 940 template <>
 941 inline void swap<Geom::Path>(Geom::Path &a, Geom::Path &b)
 942 {
 943   a.swap(b);
 944 }
 945
 946 }
 947
 948 #endif // SEEN_GEOM_PATH_H
 949
 950 /*
 951   Local Variables:
 952   mode:c++
 953   c-file-style:"stroustrup"
 954   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 955   indent-tabs-mode:nil
 956   fill-column:99
 957   End:
 958 */
 959 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :