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         if(dx == 0) return new BezierCurve<1>(Point(0,0), Point(0,0));
 240         double slope = dy / dx;
 241         Geom::Point pnt;
 242         if(slope == 0) pnt = Geom::Point(0, 0); else pnt = Geom::Point(slope, 1./slope);
 243         return new BezierCurve<1>(pnt, pnt);
 244      }
 245   }
 246
 247   Point pointAt(double t) const { return inner.valueAt(t); }
 248   std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const { return inner.valueAndDerivatives(t, n); }
 249
 250   double valueAt(double t, Dim2 d) const { return inner[d].valueAt(t); }
 251
 252   D2<SBasis> toSBasis() const {return inner.toSBasis(); }
 253
 254 protected:
 255   BezierCurve(Point c[]) {
 256     Coord x[order+1], y[order+1];
 257     for(unsigned i = 0; i <= order; i++) {
 258         x[i] = c[i][X]; y[i] = c[i][Y];
 259     }
 260     inner = Bezier(x, y);
 261   }
 262 };
 263
 264 // BezierCurve<0> is meaningless; specialize it out
 265 template<> class BezierCurve<0> : public BezierCurve<1> { public: BezierCurve(); BezierCurve(Bezier x, Bezier y); };
 266
 267 typedef BezierCurve<1> LineSegment;
 268 typedef BezierCurve<2> QuadraticBezier;
 269 typedef BezierCurve<3> CubicBezier;
 270
 271 class SVGEllipticalArc : public Curve {
 272 public:
 273   SVGEllipticalArc() {}
 274
 275   SVGEllipticalArc(Point initial, double rx, double ry,
 276                    double x_axis_rotation, bool large_arc,
 277                    bool sweep, Point final)
 278   : initial_(initial), rx_(rx), ry_(ry), x_axis_rotation_(x_axis_rotation),
 279     large_arc_(large_arc), sweep_(sweep), final_(final)
 280   {}
 281
 282   Curve *duplicate() const { return new SVGEllipticalArc(*this); }
 283
 284   Point initialPoint() const { return initial_; }
 285   Point finalPoint() const { return final_; }
 286
 287   void setInitial(Point v) { initial_ = v; }
 288   void setFinal(Point v) { final_ = v; }
 289
 290   //TODO: implement funcs
 291
 292   bool isDegenerate() const { return toSBasis().isConstant(); }
 293   Rect boundsFast() const;
 294   Rect boundsExact() const;
 295   Rect boundsLocal(Interval i, unsigned deg) const;
 296
 297   int winding(Point p) const {
 298     return SBasisCurve(toSBasis()).winding(p);
 299   }
 300
 301   std::vector<double> roots(double v, Dim2 d) const;
 302
 303   inline std::pair<SVGEllipticalArc, SVGEllipticalArc>
 304   subdivide(Coord t) {
 305     SVGEllipticalArc a(*this), b(*this);
 306     a.final_ = b.initial_ = pointAt(t);
 307     return std::pair<SVGEllipticalArc, SVGEllipticalArc>(a, b);
 308   }
 309
 310 // TODO: how are the flags affected by reducing an arc from more than 180deg to less than 180deg?
 311   Curve *portion(double f, double t) const {
 312     SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
 313     ret->initial_ = pointAt(f);
 314     ret->final_ = pointAt(t);
 315     return ret;
 316   }
 317
 318 // TODO: incomplete/buggy
 319   Curve *reverse(double /*f*/, double /*t*/) const {
 320     SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
 321     ret->initial_ = final_;
 322     ret->final_ = initial_;
 323     return ret;
 324   }
 325
 326   //TODO: this next def isn't right
 327   Curve *transformed(Matrix const & m) const {
 328     SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
 329     ret->initial_ = initial_ * m;
 330     ret->final_ = final_ * m;
 331     return ret;
 332   }
 333
 334   Curve *derivative() const { throwNotImplemented(); }
 335
 336   std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const;
 337
 338   D2<SBasis> toSBasis() const;
 339
 340 private:
 341   Point initial_;
 342   double rx_;
 343   double ry_;
 344   double x_axis_rotation_;
 345   bool large_arc_;
 346   bool sweep_;
 347   Point final_;
 348 };
 349
 350 template <typename IteratorImpl>
 351 class BaseIterator
 352 : public std::iterator<std::forward_iterator_tag, Curve const>
 353 {
 354 public:
 355   BaseIterator() {}
 356
 357   // default construct
 358   // default copy
 359
 360   bool operator==(BaseIterator const &other) {
 361     return other.impl_ == impl_;
 362   }
 363   bool operator!=(BaseIterator const &other) {
 364     return other.impl_ != impl_;
 365   }
 366
 367   Curve const &operator*() const { return **impl_; }
 368   Curve const *operator->() const { return *impl_; }
 369
 370   BaseIterator &operator++() {
 371     ++impl_;
 372     return *this;
 373   }
 374
 375   BaseIterator operator++(int) {
 376     BaseIterator old=*this;
 377     ++(*this);
 378     return old;
 379   }
 380
 381 private:
 382   BaseIterator(IteratorImpl const &pos) : impl_(pos) {}
 383
 384   IteratorImpl impl_;
 385   friend class Path;
 386 };
 387
 388 template <typename Iterator>
 389 class DuplicatingIterator
 390 : public std::iterator<std::input_iterator_tag, Curve *>
 391 {
 392 public:
 393   DuplicatingIterator() {}
 394   DuplicatingIterator(Iterator const &iter) : impl_(iter) {}
 395
 396   bool operator==(DuplicatingIterator const &other) {
 397     return other.impl_ == impl_;
 398   }
 399   bool operator!=(DuplicatingIterator const &other) {
 400     return other.impl_ != impl_;
 401   }
 402
 403   Curve *operator*() const { return (*impl_)->duplicate(); }
 404
 405   DuplicatingIterator &operator++() {
 406     ++impl_;
 407     return *this;
 408   }
 409   DuplicatingIterator operator++(int) {
 410     DuplicatingIterator old=*this;
 411     ++(*this);
 412     return old;
 413   }
 414
 415 private:
 416   Iterator impl_;
 417 };
 418
 419 class Path {
 420 private:
 421   typedef std::vector<Curve *> Sequence;
 422
 423 public:
 424   typedef BaseIterator<Sequence::iterator> iterator;
 425   typedef BaseIterator<Sequence::const_iterator> const_iterator;
 426   typedef Sequence::size_type size_type;
 427   typedef Sequence::difference_type difference_type;
 428
 429   Path()
 430   : final_(new LineSegment()), closed_(false)
 431   {
 432     curves_.push_back(final_);
 433   }
 434
 435   Path(Path const &other)
 436   : final_(new LineSegment()), closed_(other.closed_)
 437   {
 438     curves_.push_back(final_);
 439     insert(begin(), other.begin(), other.end());
 440   }
 441
 442   explicit Path(Point p)
 443   : final_(new LineSegment(p, p)), closed_(false)
 444   {
 445     curves_.push_back(final_);
 446   }
 447
 448   template <typename Impl>
 449   Path(BaseIterator<Impl> first, BaseIterator<Impl> last, bool closed=false)
 450   : closed_(closed), final_(new LineSegment())
 451   {
 452     curves_.push_back(final_);
 453     insert(begin(), first, last);
 454   }
 455
 456   virtual ~Path() {
 457       delete_range(curves_.begin(), curves_.end()-1);
 458       delete final_;
 459   }
 460
 461   Path &operator=(Path const &other) {
 462     clear();
 463     insert(begin(), other.begin(), other.end());
 464     close(other.closed_);
 465     return *this;
 466   }
 467
 468   void swap(Path &other);
 469
 470   Curve const &operator[](unsigned i) const { return *curves_[i]; }
 471
 472   iterator begin() { return curves_.begin(); }
 473   iterator end() { return curves_.end()-1; }
 474
 475   Curve const &front() const { return *curves_[0]; }
 476   Curve const &back() const { return *curves_[curves_.size()-2]; }
 477
 478   const_iterator begin() const { return curves_.begin(); }
 479   const_iterator end() const { return curves_.end()-1; }
 480
 481   const_iterator end_open() const { return curves_.end()-1; }
 482   const_iterator end_closed() const { return curves_.end(); }
 483   const_iterator end_default() const {
 484     return ( closed_ ? end_closed() : end_open() );
 485   }
 486
 487   size_type size() const { return curves_.size()-1; }
 488   size_type max_size() const { return curves_.max_size()-1; }
 489
 490   bool empty() const { return curves_.size() == 1; }
 491   bool closed() const { return closed_; }
 492   void close(bool closed=true) { closed_ = closed; }
 493
 494   Rect boundsFast() const;
 495   Rect boundsExact() const;
 496
 497   Piecewise<D2<SBasis> > toPwSb() const {
 498     Piecewise<D2<SBasis> > ret;
 499     ret.push_cut(0);
 500     unsigned i = 1;
 501     // ignore that path is closed or open. pw<d2<>> is always open.
 502     for(const_iterator it = begin(); it != end(); ++it) {
 503       if (!it->isDegenerate()) {
 504         ret.push(it->toSBasis(), i++);
 505       }
 506     }
 507     return ret;
 508   }
 509
 510   Path operator*(Matrix const &m) const {
 511     Path ret;
 512     for(const_iterator it = begin(); it != end(); ++it) {
 513       Curve *temp = it->transformed(m);
 514       //Possible point of discontinuity?
 515       ret.append(*temp);
 516       delete temp;
 517     }
 518     return ret;
 519   }
 520
 521   Point pointAt(double t) const {
 522     if(empty()) return Point(0,0);
 523     double i, f = modf(t, &i);
 524     if(i == size() && f == 0) { i--; }
 525     assert(i >= 0 && i <= size());
 526     return (*this)[unsigned(i)].pointAt(f);
 527   }
 528
 529   double valueAt(double t, Dim2 d) const {
 530     if(empty()) return 0;
 531     double i, f = modf(t, &i);
 532     if(i == size() && f == 0) { i--; }
 533     assert(i >= 0 && i <= size());
 534     return (*this)[unsigned(i)].valueAt(f, d);
 535   }
 536
 537   std::vector<double> roots(double v, Dim2 d) const {
 538     std::vector<double> res;
 539     for(unsigned i = 0; i <= size(); i++) {
 540       std::vector<double> temp = (*this)[i].roots(v, d);
 541       for(unsigned j = 0; j < temp.size(); j++)
 542         res.push_back(temp[j] + i);
 543     }
 544     return res;
 545   }
 546
 547   void appendPortionTo(Path &p, double f, double t) const;
 548
 549   Path portion(double f, double t) const {
 550     Path ret;
 551     ret.close(false);
 552     appendPortionTo(ret, f, t);
 553     return ret;
 554   }
 555   Path portion(Interval i) const { return portion(i.min(), i.max()); }
 556
 557   Path reverse() const {
 558     Path ret;
 559     ret.close(closed_);
 560     for(int i = size() - (closed_ ? 0 : 1); i >= 0; i--) {
 561       //TODO: do we really delete?
 562       Curve *temp = (*this)[i].reverse();
 563       ret.append(*temp);
 564       delete temp;
 565     }
 566     return ret;
 567   }
 568
 569   void insert(iterator pos, Curve const &curve) {
 570     Sequence source(1, curve.duplicate());
 571     try {
 572       do_update(pos.impl_, pos.impl_, source.begin(), source.end());
 573     } catch (...) {
 574       delete_range(source.begin(), source.end());
 575       throw;
 576     }
 577   }
 578
 579   template <typename Impl>
 580   void insert(iterator pos, BaseIterator<Impl> first, BaseIterator<Impl> last)
 581   {
 582     Sequence source(DuplicatingIterator<Impl>(first.impl_),
 583                     DuplicatingIterator<Impl>(last.impl_));
 584     try {
 585       do_update(pos.impl_, pos.impl_, source.begin(), source.end());
 586     } catch (...) {
 587       delete_range(source.begin(), source.end());
 588       throw;
 589     }
 590   }
 591
 592   void clear() {
 593     do_update(curves_.begin(), curves_.end()-1,
 594               curves_.begin(), curves_.begin());
 595   }
 596
 597   void erase(iterator pos) {
 598     do_update(pos.impl_, pos.impl_+1, curves_.begin(), curves_.begin());
 599   }
 600
 601   void erase(iterator first, iterator last) {
 602     do_update(first.impl_, last.impl_, curves_.begin(), curves_.begin());
 603   }
 604
 605   void replace(iterator replaced, Curve const &curve) {
 606     Sequence source(1, curve.duplicate());
 607     try {
 608       do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
 609     } catch (...) {
 610       delete_range(source.begin(), source.end());
 611       throw;
 612     }
 613   }
 614
 615   void replace(iterator first_replaced, iterator last_replaced,
 616                Curve const &curve)
 617   {
 618     Sequence source(1, curve.duplicate());
 619     try {
 620       do_update(first_replaced.impl_, last_replaced.impl_,
 621                 source.begin(), source.end());
 622     } catch (...) {
 623       delete_range(source.begin(), source.end());
 624       throw;
 625     }
 626   }
 627
 628   template <typename Impl>
 629   void replace(iterator replaced,
 630                BaseIterator<Impl> first, BaseIterator<Impl> last)
 631   {
 632     Sequence source(DuplicatingIterator<Impl>(first.impl_),
 633                     DuplicatingIterator<Impl>(last.impl_));
 634     try {
 635       do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
 636     } catch (...) {
 637       delete_range(source.begin(), source.end());
 638       throw;
 639     }
 640   }
 641
 642   template <typename Impl>
 643   void replace(iterator first_replaced, iterator last_replaced,
 644                BaseIterator<Impl> first, BaseIterator<Impl> last)
 645   {
 646     Sequence source(first.impl_, last.impl_);
 647     try {
 648       do_update(first_replaced.impl_, last_replaced.impl_,
 649                 source.begin(), source.end());
 650     } catch (...) {
 651       delete_range(source.begin(), source.end());
 652       throw;
 653     }
 654   }
 655
 656   void start(Point p) {
 657     clear();
 658     final_->setPoint(0, p);
 659     final_->setPoint(1, p);
 660   }
 661
 662   Point initialPoint() const { return (*final_)[1]; }
 663   Point finalPoint() const { return (*final_)[0]; }
 664
 665   void append(Curve const &curve);
 666   void append(D2<SBasis> const &curve);
 667
 668   template <typename CurveType, typename A>
 669   void appendNew(A a) {
 670     do_append(new CurveType((*final_)[0], a));
 671   }
 672
 673   template <typename CurveType, typename A, typename B>
 674   void appendNew(A a, B b) {
 675     do_append(new CurveType((*final_)[0], a, b));
 676   }
 677
 678   template <typename CurveType, typename A, typename B, typename C>
 679   void appendNew(A a, B b, C c) {
 680     do_append(new CurveType((*final_)[0], a, b, c));
 681   }
 682
 683   template <typename CurveType, typename A, typename B, typename C,
 684                                 typename D>
 685   void appendNew(A a, B b, C c, D d) {
 686     do_append(new CurveType((*final_)[0], a, b, c, d));
 687   }
 688
 689   template <typename CurveType, typename A, typename B, typename C,
 690                                 typename D, typename E>
 691   void appendNew(A a, B b, C c, D d, E e) {
 692     do_append(new CurveType((*final_)[0], a, b, c, d, e));
 693   }
 694
 695   template <typename CurveType, typename A, typename B, typename C,
 696                                 typename D, typename E, typename F>
 697   void appendNew(A a, B b, C c, D d, E e, F f) {
 698     do_append(new CurveType((*final_)[0], a, b, c, d, e, f));
 699   }
 700
 701   template <typename CurveType, typename A, typename B, typename C,
 702                                 typename D, typename E, typename F,
 703                                 typename G>
 704   void appendNew(A a, B b, C c, D d, E e, F f, G g) {
 705     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g));
 706   }
 707
 708   template <typename CurveType, typename A, typename B, typename C,
 709                                 typename D, typename E, typename F,
 710                                 typename G, typename H>
 711   void appendNew(A a, B b, C c, D d, E e, F f, G g, H h) {
 712     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h));
 713   }
 714
 715   template <typename CurveType, typename A, typename B, typename C,
 716                                 typename D, typename E, typename F,
 717                                 typename G, typename H, typename I>
 718   void appendNew(A a, B b, C c, D d, E e, F f, G g, H h, I i) {
 719     do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h, i));
 720   }
 721
 722 private:
 723   void do_update(Sequence::iterator first_replaced,
 724                  Sequence::iterator last_replaced,
 725                  Sequence::iterator first,
 726                  Sequence::iterator last);
 727
 728   void do_append(Curve *curve);
 729
 730   void delete_range(Sequence::iterator first, Sequence::iterator last);
 731
 732   void check_continuity(Sequence::iterator first_replaced,
 733                         Sequence::iterator last_replaced,
 734                         Sequence::iterator first,
 735                         Sequence::iterator last);
 736
 737   Sequence curves_;
 738   LineSegment *final_;
 739   bool closed_;
 740 };
 741
 742 inline static Piecewise<D2<SBasis> > paths_to_pw(std::vector<Path> paths) {
 743     Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
 744     for(unsigned i = 1; i < paths.size(); i++) {
 745         ret.concat(paths[i].toPwSb());
 746     }
 747     return ret;
 748 }
 749
 750 /*
 751 class PathPortion : public Curve {
 752   Path *source;
 753   double f, t;
 754   boost::optional<Path> result;
 755
 756   public:
 757   double from() const { return f; }
 758   double to() const { return t; }
 759
 760   explicit PathPortion(Path *s, double fp, double tp) : source(s), f(fp), t(tp) {}
 761   Curve *duplicate() const { return new PathPortion(*this); }
 762
 763   Point initialPoint() const { return source->pointAt(f); }
 764   Point finalPoint() const { return source->pointAt(t); }
 765
 766   Path actualPath() {
 767     if(!result) *result = source->portion(f, t);
 768     return *result;
 769   }
 770
 771   Rect boundsFast() const { return actualPath().boundsFast; }
 772   Rect boundsExact() const { return actualPath().boundsFast; }
 773   Rect boundsLocal(Interval i) const { throwNotImplemented(); }
 774
 775   std::vector<double> roots(double v, Dim2 d) const = 0;
 776
 777   virtual int winding(Point p) const { return root_winding(*this, p); }
 778
 779   virtual Curve *portion(double f, double t) const = 0;
 780   virtual Curve *reverse() const { return portion(1, 0); }
 781
 782   virtual Crossings crossingsWith(Curve const & other) const;
 783
 784   virtual void setInitial(Point v) = 0;
 785   virtual void setFinal(Point v) = 0;
 786
 787   virtual Curve *transformed(Matrix const &m) const = 0;
 788
 789   virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); }
 790   virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; }
 791   virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0;
 792   virtual D2<SBasis> toSBasis() const = 0;
 793
 794 };
 795 */
 796
 797 }
 798
 799 namespace std {
 800
 801 template <>
 802 inline void swap<Geom::Path>(Geom::Path &a, Geom::Path &b)
 803 {
 804   a.swap(b);
 805 }
 806
 807 }
 808
 809 #endif // SEEN_GEOM_PATH_H
 810
 811 /*
 812   Local Variables:
 813   mode:c++
 814   c-file-style:"stroustrup"
 815   c-file-offsets:((innamespace . 0)(substatement-open . 0))
 816   indent-tabs-mode:nil
 817   c-brace-offset:0
 818   fill-column:99
 819   End:
 820 */
 821 // vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :