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