src/2geom/path.h

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