![[tokkee]](http://tokkee.org/images/avatar.png){kind=avatar}
diff --git a/src/2geom/path.h b/src/2geom/path.h
index f314e6efaba722ea8f06b50bf28d736c42cb08e0..9dfc929754b5dfa3789f723a3701b289d92c0700 100644 (file)
--- a/src/2geom/path.h
+++ b/src/2geom/path.h
/*
* Path - Series of continuous curves
*
- * Copyright 2007 MenTaLguY <mental@rydia.net>
+ * Authors:
+ * MenTaLguY <mental@rydia.net>
+ * Marco Cecchetti <mrcekets at gmail.com>
+ *
+ * Copyright 2007-2008 authors
*
* This library is free software; you can redistribute it and/or
* modify it either under the terms of the GNU Lesser General Public
* the specific language governing rights and limitations.
*/
-#ifndef SEEN_GEOM_PATH_H
-#define SEEN_GEOM_PATH_H
-
-#include "point.h"
-#include <iterator>
-#include <algorithm>
-#include "exception.h"
-#include "d2.h"
-#include "matrix.h"
-#include "bezier.h"
-#include "crossing.h"
-#include "utils.h"
-
-namespace Geom {
-
-class Curve;
-
-struct CurveHelpers {
-protected:
- static int root_winding(Curve const &c, Point p);
-};
-
-class Curve : private CurveHelpers {
-public:
- virtual ~Curve() {}
-
- virtual Point initialPoint() const = 0;
- virtual Point finalPoint() const = 0;
-
- virtual bool isDegenerate() const = 0;
-
- virtual Curve *duplicate() const = 0;
- virtual Rect boundsFast() const = 0;
- virtual Rect boundsExact() const = 0;
- virtual Rect boundsLocal(Interval i, unsigned deg) const = 0;
- Rect boundsLocal(Interval i) const { return boundsLocal(i, 0); }
- virtual std::vector<double> roots(double v, Dim2 d) const = 0;
- virtual int winding(Point p) const { return root_winding(*this, p); }
-
- //mental: review these
- virtual Curve *portion(double f, double t) const = 0;
- virtual Curve *reverse() const { return portion(1, 0); }
- virtual Curve *derivative() const = 0;
-
- virtual void setInitial(Point v) = 0;
- virtual void setFinal(Point v) = 0;
-
- virtual Curve *transformed(Matrix const &m) const = 0;
-
- virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); }
- virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; }
- virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0;
- virtual D2<SBasis> toSBasis() const = 0;
-};
-
-class SBasisCurve : public Curve {
-private:
- SBasisCurve();
- D2<SBasis> inner;
-public:
- explicit SBasisCurve(D2<SBasis> const &sb) : inner(sb) {}
- explicit SBasisCurve(Curve const &other) : inner(other.toSBasis()) {}
- Curve *duplicate() const { return new SBasisCurve(*this); }
+#ifndef SEEN_GEOM_PATH_H
+#define SEEN_GEOM_PATH_H
- Point initialPoint() const { return inner.at0(); }
- Point finalPoint() const { return inner.at1(); }
- bool isDegenerate() const { return inner.isConstant(); }
- Point pointAt(Coord t) const { return inner.valueAt(t); }
- std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const {
- return inner.valueAndDerivatives(t, n);
- }
- double valueAt(Coord t, Dim2 d) const { return inner[d].valueAt(t); }
- void setInitial(Point v) { for(unsigned d = 0; d < 2; d++) { inner[d][0][0] = v[d]; } }
- void setFinal(Point v) { for(unsigned d = 0; d < 2; d++) { inner[d][0][1] = v[d]; } }
+#include <boost/shared_ptr.hpp>
+#include <2geom/curve.h>
+#include <2geom/bezier-curve.h>
- Rect boundsFast() const { return bounds_fast(inner); }
- Rect boundsExact() const { return bounds_exact(inner); }
- Rect boundsLocal(Interval i, unsigned deg) const { return bounds_local(inner, i, deg); }
+#include <iterator>
+#include <algorithm>
- std::vector<double> roots(double v, Dim2 d) const { return Geom::roots(inner[d] - v); }
- Curve *portion(double f, double t) const {
- return new SBasisCurve(Geom::portion(inner, f, t));
- }
+namespace Geom
+{
- Curve *transformed(Matrix const &m) const {
- return new SBasisCurve(inner * m);
- }
+class Path;
- Curve *derivative() const {
- return new SBasisCurve(Geom::derivative(inner));
- }
+namespace PathInternal {
- D2<SBasis> toSBasis() const { return inner; }
+typedef std::vector<boost::shared_ptr<Curve const> > Sequence;
-};
+template <typename C, typename P>
+class BaseIterator {
+protected:
+ BaseIterator() : path(NULL), index(0) {}
+ BaseIterator(P *p, unsigned i) : path(p), index(i) {}
+ // default copy, default assign
-template <unsigned order>
-class BezierCurve : public Curve {
-private:
- D2<Bezier > inner;
public:
- template <unsigned required_degree>
- static void assert_degree(BezierCurve<required_degree> const *) {}
-
- BezierCurve() : inner(Bezier::Order(order), Bezier::Order(order)) {
- }
-
- explicit BezierCurve(D2<Bezier > const &x) : inner(x) {}
-
- BezierCurve(Bezier x, Bezier y) : inner(x, y) {}
-
- // default copy
- // default assign
-
- BezierCurve(Point c0, Point c1) {
- assert_degree<1>(this);
- for(unsigned d = 0; d < 2; d++)
- inner[d] = Bezier(c0[d], c1[d]);
- }
-
- BezierCurve(Point c0, Point c1, Point c2) {
- assert_degree<2>(this);
- for(unsigned d = 0; d < 2; d++)
- inner[d] = Bezier(c0[d], c1[d], c2[d]);
- }
-
- BezierCurve(Point c0, Point c1, Point c2, Point c3) {
- assert_degree<3>(this);
- for(unsigned d = 0; d < 2; d++)
- inner[d] = Bezier(c0[d], c1[d], c2[d], c3[d]);
- }
-
- unsigned degree() const { return order; }
-
- Curve *duplicate() const { return new BezierCurve(*this); }
-
- Point initialPoint() const { return inner.at0(); }
- Point finalPoint() const { return inner.at1(); }
-
- bool isDegenerate() const { return inner.isConstant(); }
-
- void setInitial(Point v) { setPoint(0, v); }
- void setFinal(Point v) { setPoint(1, v); }
-
- void setPoint(unsigned ix, Point v) { inner[X].setPoint(ix, v[X]); inner[Y].setPoint(ix, v[Y]); }
- Point const operator[](unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); }
-
- Rect boundsFast() const { return bounds_fast(inner); }
- Rect boundsExact() const { return bounds_exact(inner); }
- Rect boundsLocal(Interval i, unsigned deg) const {
- if(i.min() == 0 && i.max() == 1) return boundsFast();
- if(deg == 0) return bounds_local(inner, i);
- // TODO: UUUUUUGGGLLY
- if(deg == 1 && order > 1) return Rect(bounds_local(Geom::derivative(inner[X]), i),
- bounds_local(Geom::derivative(inner[Y]), i));
- return Rect(Interval(0,0), Interval(0,0));
- }
-//TODO: local
-
-//TODO: implement next 3 natively
- int winding(Point p) const {
- return SBasisCurve(toSBasis()).winding(p);
- }
-
- std::vector<double>
- roots(double v, Dim2 d) const {
- return (inner[d] - v).roots();
+ bool operator==(BaseIterator const &other) {
+ return path == other.path && index == other.index;
}
-
- void setPoints(std::vector<Point> ps) {
- for(unsigned i = 0; i <= order; i++) {
- setPoint(i, ps[i]);
- }
+ bool operator!=(BaseIterator const &other) {
+ return path != other.path || index != other.index;
}
- std::vector<Point> points() const { return bezier_points(inner); }
- std::pair<BezierCurve<order>, BezierCurve<order> > subdivide(Coord t) const {
- std::pair<Bezier, Bezier > sx = inner[X].subdivide(t), sy = inner[Y].subdivide(t);
- return std::pair<BezierCurve<order>, BezierCurve<order> >(
- BezierCurve<order>(sx.first, sy.first),
- BezierCurve<order>(sx.second, sy.second));
+ Curve const &operator*() const { return (*path)[index]; }
+ Curve const *operator->() const { return &(*path)[index]; }
+ boost::shared_ptr<Curve const> get_ref() const {
+ return path->get_ref_at_index(index);
}
- Curve *portion(double f, double t) const {
- return new BezierCurve(Geom::portion(inner, f, t));
+ C &operator++() {
+ ++index;
+ return static_cast<C &>(*this);
}
-
- Curve *reverse() const {
- return new BezierCurve(Geom::reverse(inner));
+ C operator++(int) {
+ C old(static_cast<C &>(*this));
+ ++(*this);
+ return old;
}
- Curve *transformed(Matrix const &m) const {
- BezierCurve *ret = new BezierCurve();
- std::vector<Point> ps = points();
- for(unsigned i = 0; i <= order; i++) ps[i] = ps[i] * m;
- ret->setPoints(ps);
- return ret;
+ C &operator--() {
+ --index;
+ return static_cast<C &>(*this);
}
-
- Curve *derivative() const {
- if(order > 1)
- return new BezierCurve<order-1>(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
- else if (order == 1) {
- double dx = inner[X][1] - inner[X][0], dy = inner[Y][1] - inner[Y][0];
- return new BezierCurve<1>(Point(dx,dy),Point(dx,dy));
- }
+ C operator--(int) {
+ C old(static_cast<C &>(*this));
+ --(*this);
+ return old;
}
- Point pointAt(double t) const { return inner.valueAt(t); }
- std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const { return inner.valueAndDerivatives(t, n); }
-
- double valueAt(double t, Dim2 d) const { return inner[d].valueAt(t); }
-
- D2<SBasis> toSBasis() const {return inner.toSBasis(); }
+private:
+ P *path;
+ unsigned index;
-protected:
- BezierCurve(Point c[]) {
- Coord x[order+1], y[order+1];
- for(unsigned i = 0; i <= order; i++) {
- x[i] = c[i][X]; y[i] = c[i][Y];
- }
- inner = Bezier(x, y);
- }
+ friend class ::Geom::Path;
};
-// BezierCurve<0> is meaningless; specialize it out
-template<> class BezierCurve<0> : public BezierCurve<1> { public: BezierCurve(); BezierCurve(Bezier x, Bezier y); };
-
-typedef BezierCurve<1> LineSegment;
-typedef BezierCurve<2> QuadraticBezier;
-typedef BezierCurve<3> CubicBezier;
-
-class SVGEllipticalArc : public Curve {
+class ConstIterator : public BaseIterator<ConstIterator, Path const> {
public:
- SVGEllipticalArc() {}
-
- SVGEllipticalArc(Point initial, double rx, double ry,
- double x_axis_rotation, bool large_arc,
- bool sweep, Point final)
- : initial_(initial), rx_(rx), ry_(ry), x_axis_rotation_(x_axis_rotation),
- large_arc_(large_arc), sweep_(sweep), final_(final)
- {}
-
- Curve *duplicate() const { return new SVGEllipticalArc(*this); }
-
- Point initialPoint() const { return initial_; }
- Point finalPoint() const { return final_; }
-
- void setInitial(Point v) { initial_ = v; }
- void setFinal(Point v) { final_ = v; }
+ typedef BaseIterator<ConstIterator, Path const> Base;
- //TODO: implement funcs
-
- bool isDegenerate() const { return toSBasis().isConstant(); }
- Rect boundsFast() const;
- Rect boundsExact() const;
- Rect boundsLocal(Interval i, unsigned deg) const;
-
- int winding(Point p) const {
- return SBasisCurve(toSBasis()).winding(p);
- }
-
- std::vector<double> roots(double v, Dim2 d) const;
-
- inline std::pair<SVGEllipticalArc, SVGEllipticalArc>
- subdivide(Coord t) {
- SVGEllipticalArc a(*this), b(*this);
- a.final_ = b.initial_ = pointAt(t);
- return std::pair<SVGEllipticalArc, SVGEllipticalArc>(a, b);
- }
-
-// TODO: how are the flags affected by reducing an arc from more than 180deg to less than 180deg?
- Curve *portion(double f, double t) const {
- SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
- ret->initial_ = pointAt(f);
- ret->final_ = pointAt(t);
- return ret;
- }
-
-// TODO: incomplete/buggy
- Curve *reverse(double /*f*/, double /*t*/) const {
- SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
- ret->initial_ = final_;
- ret->final_ = initial_;
- return ret;
- }
-
- //TODO: this next def isn't right
- Curve *transformed(Matrix const & m) const {
- SVGEllipticalArc *ret = new SVGEllipticalArc (*this);
- ret->initial_ = initial_ * m;
- ret->final_ = final_ * m;
- return ret;
- }
-
- Curve *derivative() const { throwNotImplemented(); }
-
- std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const;
-
- D2<SBasis> toSBasis() const;
+ ConstIterator() : Base() {}
+ // default copy, default assign
private:
- Point initial_;
- double rx_;
- double ry_;
- double x_axis_rotation_;
- bool large_arc_;
- bool sweep_;
- Point final_;
+ ConstIterator(Path const &p, unsigned i) : Base(&p, i) {}
+ friend class ::Geom::Path;
};
-template <typename IteratorImpl>
-class BaseIterator
-: public std::iterator<std::forward_iterator_tag, Curve const>
-{
+class Iterator : public BaseIterator<Iterator, Path> {
public:
- BaseIterator() {}
+ typedef BaseIterator<Iterator, Path> Base;
- // default construct
- // default copy
+ Iterator() : Base() {}
+ // default copy, default assign
- bool operator==(BaseIterator const &other) {
- return other.impl_ == impl_;
- }
- bool operator!=(BaseIterator const &other) {
- return other.impl_ != impl_;
- }
-
- Curve const &operator*() const { return **impl_; }
- Curve const *operator->() const { return *impl_; }
-
- BaseIterator &operator++() {
- ++impl_;
- return *this;
- }
-
- BaseIterator operator++(int) {
- BaseIterator old=*this;
- ++(*this);
- return old;
+ operator ConstIterator const &() const {
+ return reinterpret_cast<ConstIterator const &>(*this);
}
private:
- BaseIterator(IteratorImpl const &pos) : impl_(pos) {}
-
- IteratorImpl impl_;
- friend class Path;
+ Iterator(Path &p, unsigned i) : Base(&p, i) {}
+ friend class ::Geom::Path;
};
-template <typename Iterator>
-class DuplicatingIterator
-: public std::iterator<std::input_iterator_tag, Curve *>
-{
-public:
- DuplicatingIterator() {}
- DuplicatingIterator(Iterator const &iter) : impl_(iter) {}
-
- bool operator==(DuplicatingIterator const &other) {
- return other.impl_ == impl_;
- }
- bool operator!=(DuplicatingIterator const &other) {
- return other.impl_ != impl_;
- }
-
- Curve *operator*() const { return (*impl_)->duplicate(); }
-
- DuplicatingIterator &operator++() {
- ++impl_;
- return *this;
- }
- DuplicatingIterator operator++(int) {
- DuplicatingIterator old=*this;
- ++(*this);
- return old;
- }
-
-private:
- Iterator impl_;
-};
+}
+/*
+ * Open and closed paths: all paths, whether open or closed, store a final
+ * segment which connects the initial and final endpoints of the "real"
+ * path data. While similar to the "z" in an SVG path, it exists for
+ * both open and closed paths, and is not considered part of the "normal"
+ * path data, which is always covered by the range [begin(), end_open()).
+ * Conversely, the range [begin(), end_closed()) always contains the "extra"
+ * closing segment.
+ *
+ * The only difference between a closed and an open path is whether
+ * end_default() returns end_closed() or end_open(). The idea behind this
+ * is to let any path be stroked using [begin(), end_default()), and filled
+ * using [begin(), end_closed()), without requiring a separate "filled" version
+ * of the path to use for filling.
+ *
+ * \invariant : curves_ always contains at least one segment. The last segment
+ * is always of type ClosingSegment. All constructors take care of this.
+ (curves_.size() > 0) && dynamic_cast<ClosingSegment>(curves_.back())
+ */
class Path {
-private:
- typedef std::vector<Curve *> Sequence;
-
public:
- typedef BaseIterator<Sequence::iterator> iterator;
- typedef BaseIterator<Sequence::const_iterator> const_iterator;
+ typedef PathInternal::Sequence Sequence;
+ typedef PathInternal::Iterator iterator;
+ typedef PathInternal::ConstIterator const_iterator;
typedef Sequence::size_type size_type;
typedef Sequence::difference_type difference_type;
- Path()
- : final_(new LineSegment()), closed_(false)
+ class ClosingSegment : public LineSegment {
+ public:
+ ClosingSegment() : LineSegment() {}
+ ClosingSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
+ virtual Curve *duplicate() const { return new ClosingSegment(*this); }
+ virtual Curve *reverse() const { return new ClosingSegment((*this)[1], (*this)[0]); }
+ };
+
+ enum Stitching {
+ NO_STITCHING=0,
+ STITCH_DISCONTINUOUS
+ };
+
+ class StitchSegment : public LineSegment {
+ public:
+ StitchSegment() : LineSegment() {}
+ StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
+ virtual Curve *duplicate() const { return new StitchSegment(*this); }
+ virtual Curve *reverse() const { return new StitchSegment((*this)[1], (*this)[0]); }
+ };
+
+ // Path(Path const &other) - use default copy constructor
+
+ explicit Path(Point p=Point())
+ : curves_(boost::shared_ptr<Sequence>(new Sequence(1, boost::shared_ptr<Curve>()))),
+ final_(new ClosingSegment(p, p)),
+ closed_(false)
{
- curves_.push_back(final_);
+ get_curves().back() = boost::shared_ptr<Curve>(final_);
}
- Path(Path const &other)
- : final_(new LineSegment()), closed_(other.closed_)
+ Path(const_iterator const &first,
+ const_iterator const &last,
+ bool closed=false)
+ : curves_(boost::shared_ptr<Sequence>(new Sequence(seq_iter(first),
+ seq_iter(last)))),
+ closed_(closed)
{
- curves_.push_back(final_);
- insert(begin(), other.begin(), other.end());
+ if (!get_curves().empty()) {
+ final_ = new ClosingSegment(get_curves().back()->finalPoint(),
+ get_curves().front()->initialPoint());
+ } else {
+ final_ = new ClosingSegment();
+ }
+ get_curves().push_back(boost::shared_ptr<Curve>(final_));
}
- explicit Path(Point p)
- : final_(new LineSegment(p, p)), closed_(false)
- {
- curves_.push_back(final_);
- }
+ virtual ~Path() {}
+
+ // Path &operator=(Path const &other) - use default assignment operator
- template <typename Impl>
- Path(BaseIterator<Impl> first, BaseIterator<Impl> last, bool closed=false)
- : closed_(closed), final_(new LineSegment())
- {
- curves_.push_back(final_);
- insert(begin(), first, last);
+ void swap(Path &other) {
+ std::swap(other.curves_, curves_);
+ std::swap(other.final_, final_);
+ std::swap(other.closed_, closed_);
}
- virtual ~Path() {
- delete_range(curves_.begin(), curves_.end()-1);
- delete final_;
+ Curve const &operator[](unsigned i) const { return *get_curves()[i]; }
+ Curve const &at_index(unsigned i) const { return *get_curves()[i]; }
+ boost::shared_ptr<Curve const> get_ref_at_index(unsigned i) {
+ return get_curves()[i];
}
- Path &operator=(Path const &other) {
- clear();
- insert(begin(), other.begin(), other.end());
- close(other.closed_);
- return *this;
+ Curve const &front() const { return *get_curves()[0]; }
+ Curve const &back() const { return back_open(); }
+ Curve const &back_open() const {
+ if (empty()) { THROW_RANGEERROR("Path contains not enough segments"); }
+ return *get_curves()[get_curves().size()-2];
+ }
+ Curve const &back_closed() const { return *get_curves()[get_curves().size()-1]; }
+ Curve const &back_default() const {
+ return ( closed_ ? back_closed() : back_open() );
}
- void swap(Path &other);
-
- Curve const &operator[](unsigned i) const { return *curves_[i]; }
-
- iterator begin() { return curves_.begin(); }
- iterator end() { return curves_.end()-1; }
-
- Curve const &front() const { return *curves_[0]; }
- Curve const &back() const { return *curves_[curves_.size()-2]; }
-
- const_iterator begin() const { return curves_.begin(); }
- const_iterator end() const { return curves_.end()-1; }
+ const_iterator begin() const { return const_iterator(*this, 0); }
+ const_iterator end() const { return const_iterator(*this, size()); }
+ iterator begin() { return iterator(*this, 0); }
+ iterator end() { return iterator(*this, size()); }
- const_iterator end_open() const { return curves_.end()-1; }
- const_iterator end_closed() const { return curves_.end(); }
+ const_iterator end_open() const { return const_iterator(*this, size()); }
+ const_iterator end_closed() const { return const_iterator(*this, size()+1); }
const_iterator end_default() const {
return ( closed_ ? end_closed() : end_open() );
}
- size_type size() const { return curves_.size()-1; }
- size_type max_size() const { return curves_.max_size()-1; }
+ size_type size_open() const { return get_curves().size()-1; }
+ size_type size_closed() const { return get_curves().size(); }
+ size_type size_default() const {
+ return ( closed_ ? size_closed() : size_open() );
+ }
+ size_type size() const { return size_open(); }
+
+ size_type max_size() const { return get_curves().max_size()-1; }
- bool empty() const { return curves_.size() == 1; }
+ bool empty() const { return get_curves().size() == 1; }
bool closed() const { return closed_; }
void close(bool closed=true) { closed_ = closed; }
Piecewise<D2<SBasis> > ret;
ret.push_cut(0);
unsigned i = 1;
- // ignore that path is closed or open. pw<d2<>> is always open.
- for(const_iterator it = begin(); it != end(); ++it) {
+ bool degenerate = true;
+ // pw<d2<>> is always open. so if path is closed, add closing segment as well to pwd2.
+ for(const_iterator it = begin(); it != end_default(); ++it) {
if (!it->isDegenerate()) {
ret.push(it->toSBasis(), i++);
+ degenerate = false;
}
}
- return ret;
- }
-
- Path operator*(Matrix const &m) const {
- Path ret;
- for(const_iterator it = begin(); it != end(); ++it) {
- Curve *temp = it->transformed(m);
- //Possible point of discontinuity?
- ret.append(*temp);
- delete temp;
+ if (degenerate) {
+ // if path only contains degenerate curves, no second cut is added
+ // so we need to create at least one segment manually
+ ret = Piecewise<D2<SBasis> >(initialPoint());
}
return ret;
}
- Point pointAt(double t) const {
- if(empty()) return Point(0,0);
- double i, f = modf(t, &i);
- if(i == size() && f == 0) { i--; }
- assert(i >= 0 && i <= size());
- return (*this)[unsigned(i)].pointAt(f);
+ bool operator==(Path const &other) const {
+ if (this == &other) return true;
+ if (closed_ != other.closed_) return false;
+ return get_curves() == other.get_curves();
+ }
+ bool operator!=(Path const &other) const {
+ return !( *this == other );
}
- double valueAt(double t, Dim2 d) const {
- if(empty()) return 0;
- double i, f = modf(t, &i);
- if(i == size() && f == 0) { i--; }
- assert(i >= 0 && i <= size());
- return (*this)[unsigned(i)].valueAt(f, d);
+ Path operator*(Matrix const &m) const {
+ Path ret(*this);
+ ret *= m;
+ return ret;
}
+ Path &operator*=(Matrix const &m);
+
+ Point pointAt(double t) const
+ {
+ unsigned int sz = size();
+ if ( closed() ) ++sz;
+ if ( t < 0 || t > sz )
+ {
+ THROW_RANGEERROR("parameter t out of bounds");
+ }
+ if ( empty() ) return Point(0,0);
+ double k, lt = modf(t, &k);
+ unsigned int i = static_cast<unsigned int>(k);
+ if ( i == sz )
+ {
+ --i;
+ lt = 1;
+ }
+ return (*this)[i].pointAt(lt);
+ }
+
+ double valueAt(double t, Dim2 d) const
+ {
+ unsigned int sz = size();
+ if ( closed() ) ++sz;
+ if ( t < 0 || t > sz )
+ {
+ THROW_RANGEERROR("parameter t out of bounds");
+ }
+ if ( empty() ) return 0;
+ double k, lt = modf(t, &k);
+ unsigned int i = static_cast<unsigned int>(k);
+ if ( i == sz )
+ {
+ --i;
+ lt = 1;
+ }
+ return (*this)[i].valueAt(lt, d);
+ }
+
+
+ Point operator() (double t) const
+ {
+ return pointAt(t);
+ }
+
std::vector<double> roots(double v, Dim2 d) const {
std::vector<double> res;
for(unsigned i = 0; i <= size(); i++) {
}
return res;
}
-
+
+ std::vector<double>
+ allNearestPoints(Point const& _point, double from, double to) const;
+
+ std::vector<double>
+ allNearestPoints(Point const& _point) const
+ {
+ unsigned int sz = size();
+ if ( closed() ) ++sz;
+ return allNearestPoints(_point, 0, sz);
+ }
+
+ std::vector<double>
+ nearestPointPerCurve(Point const& _point) const;
+
+ double nearestPoint(Point const& _point, double from, double to, double *distance_squared = NULL) const;
+
+ double nearestPoint(Point const& _point, double *distance_squared = NULL) const
+ {
+ unsigned int sz = size();
+ if ( closed() ) ++sz;
+ return nearestPoint(_point, 0, sz, distance_squared);
+ }
+
void appendPortionTo(Path &p, double f, double t) const;
Path portion(double f, double t) const {
Path portion(Interval i) const { return portion(i.min(), i.max()); }
Path reverse() const {
- Path ret;
- ret.close(closed_);
- for(int i = size() - (closed_ ? 0 : 1); i >= 0; i--) {
- //TODO: do we really delete?
- Curve *temp = (*this)[i].reverse();
- ret.append(*temp);
- delete temp;
+ Path ret(*this);
+ ret.unshare();
+ for ( Sequence::iterator iter = ret.get_curves().begin() ;
+ iter != ret.get_curves().end()-1 ; ++iter )
+ {
+ *iter = boost::shared_ptr<Curve>((*iter)->reverse());
}
+ std::reverse(ret.get_curves().begin(), ret.get_curves().end()-1);
+ ret.final_ = static_cast<ClosingSegment *>(ret.final_->reverse());
+ ret.get_curves().back() = boost::shared_ptr<Curve>(ret.final_);
return ret;
}
- void insert(iterator pos, Curve const &curve) {
- Sequence source(1, curve.duplicate());
- try {
- do_update(pos.impl_, pos.impl_, source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
- }
+ void insert(iterator const &pos,
+ Curve const &curve, Stitching stitching=NO_STITCHING)
+ {
+ unshare();
+ Sequence::iterator seq_pos(seq_iter(pos));
+ Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
+ if (stitching) stitch(seq_pos, seq_pos, source);
+ do_update(seq_pos, seq_pos, source.begin(), source.end());
}
- template <typename Impl>
- void insert(iterator pos, BaseIterator<Impl> first, BaseIterator<Impl> last)
+ void insert(iterator const &pos,
+ const_iterator const &first,
+ const_iterator const &last,
+ Stitching stitching=NO_STITCHING)
{
- Sequence source(DuplicatingIterator<Impl>(first.impl_),
- DuplicatingIterator<Impl>(last.impl_));
- try {
- do_update(pos.impl_, pos.impl_, source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
- }
+ unshare();
+ Sequence::iterator seq_pos(seq_iter(pos));
+ Sequence source(seq_iter(first), seq_iter(last));
+ if (stitching) stitch(seq_pos, seq_pos, source);
+ do_update(seq_pos, seq_pos, source.begin(), source.end());
}
void clear() {
- do_update(curves_.begin(), curves_.end()-1,
- curves_.begin(), curves_.begin());
- }
-
- void erase(iterator pos) {
- do_update(pos.impl_, pos.impl_+1, curves_.begin(), curves_.begin());
- }
-
- void erase(iterator first, iterator last) {
- do_update(first.impl_, last.impl_, curves_.begin(), curves_.begin());
- }
-
- void replace(iterator replaced, Curve const &curve) {
- Sequence source(1, curve.duplicate());
- try {
- do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
+ unshare();
+ do_update(get_curves().begin(), get_curves().end()-1,
+ get_curves().begin(), get_curves().begin());
+ }
+
+ void erase(iterator const &pos, Stitching stitching=NO_STITCHING) {
+ unshare();
+ Sequence::iterator seq_pos(seq_iter(pos));
+ if (stitching) {
+ Sequence stitched;
+ stitch(seq_pos, seq_pos+1, stitched);
+ do_update(seq_pos, seq_pos+1, stitched.begin(), stitched.end());
+ } else {
+ do_update(seq_pos, seq_pos+1, get_curves().begin(), get_curves().begin());
}
}
- void replace(iterator first_replaced, iterator last_replaced,
- Curve const &curve)
+ void erase(iterator const &first,
+ iterator const &last,
+ Stitching stitching=NO_STITCHING)
{
- Sequence source(1, curve.duplicate());
- try {
- do_update(first_replaced.impl_, last_replaced.impl_,
- source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
+ unshare();
+ Sequence::iterator seq_first=seq_iter(first);
+ Sequence::iterator seq_last=seq_iter(last);
+ if (stitching) {
+ Sequence stitched;
+ stitch(seq_first, seq_last, stitched);
+ do_update(seq_first, seq_last, stitched.begin(), stitched.end());
+ } else {
+ do_update(seq_first, seq_last,
+ get_curves().begin(), get_curves().begin());
}
}
- template <typename Impl>
- void replace(iterator replaced,
- BaseIterator<Impl> first, BaseIterator<Impl> last)
+ // erase last segment of path
+ void erase_last() {
+ erase(iterator(*this, size()-1));
+ }
+
+ void replace(iterator const &replaced,
+ Curve const &curve,
+ Stitching stitching=NO_STITCHING)
{
- Sequence source(DuplicatingIterator<Impl>(first.impl_),
- DuplicatingIterator<Impl>(last.impl_));
- try {
- do_update(replaced.impl_, replaced.impl_+1, source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
- }
+ unshare();
+ Sequence::iterator seq_replaced(seq_iter(replaced));
+ Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
+ if (stitching) stitch(seq_replaced, seq_replaced+1, source);
+ do_update(seq_replaced, seq_replaced+1, source.begin(), source.end());
}
- template <typename Impl>
- void replace(iterator first_replaced, iterator last_replaced,
- BaseIterator<Impl> first, BaseIterator<Impl> last)
+ void replace(iterator const &first_replaced,
+ iterator const &last_replaced,
+ Curve const &curve, Stitching stitching=NO_STITCHING)
{
- Sequence source(first.impl_, last.impl_);
- try {
- do_update(first_replaced.impl_, last_replaced.impl_,
- source.begin(), source.end());
- } catch (...) {
- delete_range(source.begin(), source.end());
- throw;
- }
+ unshare();
+ Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
+ Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
+ Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
+ if (stitching) stitch(seq_first_replaced, seq_last_replaced, source);
+ do_update(seq_first_replaced, seq_last_replaced,
+ source.begin(), source.end());
+ }
+
+ void replace(iterator const &replaced,
+ const_iterator const &first,
+ const_iterator const &last,
+ Stitching stitching=NO_STITCHING)
+ {
+ unshare();
+ Sequence::iterator seq_replaced(seq_iter(replaced));
+ Sequence source(seq_iter(first), seq_iter(last));
+ if (stitching) stitch(seq_replaced, seq_replaced+1, source);
+ do_update(seq_replaced, seq_replaced+1, source.begin(), source.end());
+ }
+
+ void replace(iterator const &first_replaced,
+ iterator const &last_replaced,
+ const_iterator const &first,
+ const_iterator const &last,
+ Stitching stitching=NO_STITCHING)
+ {
+ unshare();
+ Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
+ Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
+ Sequence source(seq_iter(first), seq_iter(last));
+ if (stitching) stitch(seq_first_replaced, seq_last_replaced, source);
+ do_update(seq_first_replaced, seq_last_replaced,
+ source.begin(), source.end());
}
void start(Point p) {
Point initialPoint() const { return (*final_)[1]; }
Point finalPoint() const { return (*final_)[0]; }
- void append(Curve const &curve);
- void append(D2<SBasis> const &curve);
+ void setInitial(Point const& p)
+ {
+ if ( empty() ) return;
+ unshare();
+ boost::shared_ptr<Curve> head(front().duplicate());
+ head->setInitial(p);
+ Sequence::iterator replaced = get_curves().begin();
+ Sequence source(1, head);
+ do_update(replaced, replaced + 1, source.begin(), source.end());
+ }
+
+ void setFinal(Point const& p)
+ {
+ if ( empty() ) return;
+ unshare();
+ boost::shared_ptr<Curve> tail(back().duplicate());
+ tail->setFinal(p);
+ Sequence::iterator replaced = get_curves().end() - 2;
+ Sequence source(1, tail);
+ do_update(replaced, replaced + 1, source.begin(), source.end());
+ }
+
+ void append(Curve const &curve, Stitching stitching=NO_STITCHING) {
+ unshare();
+ if (stitching) stitchTo(curve.initialPoint());
+ do_append(curve.duplicate());
+ }
+ void append(D2<SBasis> const &curve, Stitching stitching=NO_STITCHING) {
+ unshare();
+ if (stitching) stitchTo(Point(curve[X][0][0], curve[Y][0][0]));
+ do_append(new SBasisCurve(curve));
+ }
+ void append(Path const &other, Stitching stitching=NO_STITCHING) {
+ insert(end(), other.begin(), other.end(), stitching);
+ }
+
+ void stitchTo(Point const &p) {
+ if (!empty() && finalPoint() != p) {
+ unshare();
+ do_append(new StitchSegment(finalPoint(), p));
+ }
+ }
template <typename CurveType, typename A>
void appendNew(A a) {
- do_append(new CurveType((*final_)[0], a));
+ unshare();
+ do_append(new CurveType(finalPoint(), a));
}
template <typename CurveType, typename A, typename B>
void appendNew(A a, B b) {
- do_append(new CurveType((*final_)[0], a, b));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b));
}
template <typename CurveType, typename A, typename B, typename C>
void appendNew(A a, B b, C c) {
- do_append(new CurveType((*final_)[0], a, b, c));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c));
}
template <typename CurveType, typename A, typename B, typename C,
typename D>
void appendNew(A a, B b, C c, D d) {
- do_append(new CurveType((*final_)[0], a, b, c, d));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d));
}
template <typename CurveType, typename A, typename B, typename C,
typename D, typename E>
void appendNew(A a, B b, C c, D d, E e) {
- do_append(new CurveType((*final_)[0], a, b, c, d, e));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d, e));
}
template <typename CurveType, typename A, typename B, typename C,
typename D, typename E, typename F>
void appendNew(A a, B b, C c, D d, E e, F f) {
- do_append(new CurveType((*final_)[0], a, b, c, d, e, f));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d, e, f));
}
template <typename CurveType, typename A, typename B, typename C,
typename D, typename E, typename F,
typename G>
void appendNew(A a, B b, C c, D d, E e, F f, G g) {
- do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g));
}
template <typename CurveType, typename A, typename B, typename C,
typename D, typename E, typename F,
typename G, typename H>
void appendNew(A a, B b, C c, D d, E e, F f, G g, H h) {
- do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h));
}
template <typename CurveType, typename A, typename B, typename C,
typename D, typename E, typename F,
typename G, typename H, typename I>
void appendNew(A a, B b, C c, D d, E e, F f, G g, H h, I i) {
- do_append(new CurveType((*final_)[0], a, b, c, d, e, f, g, h, i));
+ unshare();
+ do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h, i));
}
private:
+ static Sequence::iterator seq_iter(iterator const &iter) {
+ return iter.path->get_curves().begin() + iter.index;
+ }
+ static Sequence::const_iterator seq_iter(const_iterator const &iter) {
+ return iter.path->get_curves().begin() + iter.index;
+ }
+
+ Sequence &get_curves() { return *curves_; }
+ Sequence const &get_curves() const { return *curves_; }
+
+ void unshare() {
+ if (!curves_.unique()) {
+ curves_ = boost::shared_ptr<Sequence>(new Sequence(*curves_));
+ }
+ if (!get_curves().back().unique()) {
+ final_ = static_cast<ClosingSegment *>(final_->duplicate());
+ get_curves().back() = boost::shared_ptr<Curve>(final_);
+ }
+ }
+
+ void stitch(Sequence::iterator first_replaced,
+ Sequence::iterator last_replaced,
+ Sequence &sequence);
+
void do_update(Sequence::iterator first_replaced,
Sequence::iterator last_replaced,
Sequence::iterator first,
Sequence::iterator last);
+ // n.b. takes ownership of curve object
void do_append(Curve *curve);
- void delete_range(Sequence::iterator first, Sequence::iterator last);
-
void check_continuity(Sequence::iterator first_replaced,
Sequence::iterator last_replaced,
Sequence::iterator first,
Sequence::iterator last);
- Sequence curves_;
- LineSegment *final_;
+ boost::shared_ptr<Sequence> curves_;
+ ClosingSegment *final_;
bool closed_;
-};
+}; // end class Path
inline static Piecewise<D2<SBasis> > paths_to_pw(std::vector<Path> paths) {
Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
return ret;
}
-/*
-class PathPortion : public Curve {
- Path *source;
- double f, t;
- boost::optional<Path> result;
-
- public:
- double from() const { return f; }
- double to() const { return t; }
-
- explicit PathPortion(Path *s, double fp, double tp) : source(s), f(fp), t(tp) {}
- Curve *duplicate() const { return new PathPortion(*this); }
-
- Point initialPoint() const { return source->pointAt(f); }
- Point finalPoint() const { return source->pointAt(t); }
-
- Path actualPath() {
- if(!result) *result = source->portion(f, t);
- return *result;
- }
-
- Rect boundsFast() const { return actualPath().boundsFast; }
- Rect boundsExact() const { return actualPath().boundsFast; }
- Rect boundsLocal(Interval i) const { throwNotImplemented(); }
-
- std::vector<double> roots(double v, Dim2 d) const = 0;
-
- virtual int winding(Point p) const { return root_winding(*this, p); }
-
- virtual Curve *portion(double f, double t) const = 0;
- virtual Curve *reverse() const { return portion(1, 0); }
-
- virtual Crossings crossingsWith(Curve const & other) const;
-
- virtual void setInitial(Point v) = 0;
- virtual void setFinal(Point v) = 0;
-
- virtual Curve *transformed(Matrix const &m) const = 0;
-
- virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); }
- virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; }
- virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0;
- virtual D2<SBasis> toSBasis() const = 0;
-
-};
-*/
-
+inline
+Coord nearest_point(Point const& p, Path const& c)
+{
+ return c.nearestPoint(p);
}
+} // end namespace Geom
+
namespace std {
template <>
a.swap(b);
}
-}
+} // end namespace std
#endif // SEEN_GEOM_PATH_H
+
+
+
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
- c-file-offsets:((innamespace . 0)(substatement-open . 0))
+ c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
- c-brace-offset:0
fill-column:99
End:
*/
-// vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :