diff options
Diffstat (limited to '')
| -rw-r--r-- | include/2geom/curve.h | 375 |
1 files changed, 375 insertions, 0 deletions
diff --git a/include/2geom/curve.h b/include/2geom/curve.h new file mode 100644 index 0000000..9519144 --- /dev/null +++ b/include/2geom/curve.h @@ -0,0 +1,375 @@ +/** + * \file + * \brief Abstract curve type + * + *//* + * Authors: + * MenTaLguY <mental@rydia.net> + * Marco Cecchetti <mrcekets at gmail.com> + * Krzysztof Kosiński <tweenk.pl@gmail.com> + * + * Copyright 2007-2009 Authors + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + */ + + +#ifndef LIB2GEOM_SEEN_CURVE_H +#define LIB2GEOM_SEEN_CURVE_H + +#include <vector> +#include <boost/operators.hpp> +#include <2geom/coord.h> +#include <2geom/point.h> +#include <2geom/interval.h> +#include <2geom/sbasis.h> +#include <2geom/d2.h> +#include <2geom/affine.h> +#include <2geom/intersection.h> + +namespace Geom { + +class PathSink; +typedef Intersection<> CurveIntersection; + +/** + * @brief Abstract continuous curve on a plane defined on [0,1]. + * + * Formally, a curve in 2Geom is defined as a function + * \f$\mathbf{C}: [0, 1] \to \mathbb{R}^2\f$ + * (a function that maps the unit interval to points on a 2D plane). Its image (the set of points + * the curve passes through) will be denoted \f$\mathcal{C} = \mathbf{C}[ [0, 1] ]\f$. + * All curve types available in 2Geom are continuous and differentiable on their + * interior, e.g. \f$(0, 1)\f$. Sometimes the curve's image (value set) is referred to as the curve + * itself for simplicity, but keep in mind that it's not strictly correct. + * + * It is common to think of the parameter as time. The curve can then be interpreted as + * describing the position of some moving object from time \f$t=0\f$ to \f$t=1\f$. + * Because of this, the parameter is frequently called the time value. + * + * Some methods return pointers to newly allocated curves. They are expected to be freed + * by the caller when no longer used. Default implementations are provided for some methods. + * + * @ingroup Curves + */ +class Curve + : boost::equality_comparable<Curve> +{ +public: + virtual ~Curve() {} + + /// @name Evaluate the curve + /// @{ + /** @brief Retrieve the start of the curve. + * @return The point corresponding to \f$\mathbf{C}(0)\f$. */ + virtual Point initialPoint() const = 0; + + /** Retrieve the end of the curve. + * @return The point corresponding to \f$\mathbf{C}(1)\f$. */ + virtual Point finalPoint() const = 0; + + /** @brief Check whether the curve has exactly zero length. + * @return True if the curve's initial point is exactly the same as its final point, and it contains + * no other points (its value set contains only one element). */ + virtual bool isDegenerate() const = 0; + + /// Check whether the curve is a line segment. + virtual bool isLineSegment() const { return false; } + + /** @brief Get the interval of allowed time values. + * @return \f$[0, 1]\f$ */ + virtual Interval timeRange() const { + Interval tr(0, 1); + return tr; + } + + /** @brief Evaluate the curve at a specified time value. + * @param t Time value + * @return \f$\mathbf{C}(t)\f$ */ + virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 0).front(); } + + /** @brief Evaluate one of the coordinates at the specified time value. + * @param t Time value + * @param d The dimension to evaluate + * @return The specified coordinate of \f$\mathbf{C}(t)\f$ */ + virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; } + + /** @brief Evaluate the function at the specified time value. Allows curves to be used + * as functors. */ + virtual Point operator() (Coord t) const { return pointAt(t); } + + /** @brief Evaluate the curve and its derivatives. + * This will return a vector that contains the value of the curve and the specified number + * of derivatives. However, the returned vector might contain less elements than specified + * if some derivatives do not exist. + * @param t Time value + * @param n The number of derivatives to compute + * @return Vector of at most \f$n+1\f$ elements of the form \f$[\mathbf{C}(t), + \mathbf{C}'(t), \mathbf{C}''(t), \ldots]\f$ */ + virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0; + /// @} + + /// @name Change the curve's endpoints + /// @{ + /** @brief Change the starting point of the curve. + * After calling this method, it is guaranteed that \f$\mathbf{C}(0) = \mathbf{p}\f$, + * and the curve is still continuous. The precise new shape of the curve varies with curve + * type. + * @param p New starting point of the curve */ + virtual void setInitial(Point const &v) = 0; + + /** @brief Change the ending point of the curve. + * After calling this method, it is guaranteed that \f$\mathbf{C}(0) = \mathbf{p}\f$, + * and the curve is still continuous. The precise new shape of the curve varies + * with curve type. + * @param p New ending point of the curve */ + virtual void setFinal(Point const &v) = 0; + /// @} + + /// @name Compute the bounding box + /// @{ + /** @brief Quickly compute the curve's approximate bounding box. + * The resulting rectangle is guaranteed to contain all points belonging to the curve, + * but it might not be the smallest such rectangle. This method is usually fast. + * @return A rectangle that contains all points belonging to the curve. */ + virtual Rect boundsFast() const = 0; + + /** @brief Compute the curve's exact bounding box. + * This method can be dramatically slower than boundsFast() depending on the curve type. + * @return The smallest possible rectangle containing all of the curve's points. */ + virtual Rect boundsExact() const = 0; + + /** @brief Expand the given rectangle to include the transformed curve, + * assuming it already contains its initial point. + * @param bbox[in,out] bbox The rectangle to expand; it is assumed to already contain (initialPoint() * transform). + * @param transform The transform to apply to the curve before taking its bounding box. */ + virtual void expandToTransformed(Rect &bbox, Affine const &transform) const = 0; + + // I have no idea what the 'deg' parameter is for, so this is undocumented for now. + virtual OptRect boundsLocal(OptInterval const &i, unsigned deg) const = 0; + + /** @brief Compute the bounding box of a part of the curve. + * Since this method returns the smallest possible bounding rectangle of the specified portion, + * it can also be rather slow. + * @param a An interval specifying a part of the curve, or nothing. + * If \f$[0, 1] \subseteq a\f$, then the bounding box for the entire curve + * is calculated. + * @return The smallest possible rectangle containing all points in \f$\mathbf{C}[a]\f$, + * or nothing if the supplied interval is empty. */ + OptRect boundsLocal(OptInterval const &a) const { return boundsLocal(a, 0); } + /// @} + + /// @name Create new curves based on this one + /// @{ + /** @brief Create an exact copy of this curve. + * @return Pointer to a newly allocated curve, identical to the original */ + virtual Curve *duplicate() const = 0; + + /** @brief Transform this curve by an affine transformation. + * Because of this method, all curve types must be closed under affine + * transformations. + * @param m Affine describing the affine transformation */ + void transform(Affine const &m) { + *this *= m; + } + + virtual void operator*=(Translate const &tr) { *this *= Affine(tr); } + virtual void operator*=(Scale const &s) { *this *= Affine(s); } + virtual void operator*=(Rotate const &r) { *this *= Affine(r); } + virtual void operator*=(HShear const &hs) { *this *= Affine(hs); } + virtual void operator*=(VShear const &vs) { *this *= Affine(vs); } + virtual void operator*=(Zoom const &z) { *this *= Affine(z); } + virtual void operator*=(Affine const &m) = 0; + + /** @brief Create a curve transformed by an affine transformation. + * This method returns a new curve instead modifying the existing one. + * @param m Affine describing the affine transformation + * @return Pointer to a new, transformed curve */ + virtual Curve *transformed(Affine const &m) const { + Curve *ret = duplicate(); + ret->transform(m); + return ret; + } + + /** @brief Create a curve that corresponds to a part of this curve. + * For \f$a > b\f$, the returned portion will be reversed with respect to the original. + * The returned curve will always be of the same type. + * @param a Beginning of the interval specifying the portion of the curve + * @param b End of the interval + * @return New curve \f$\mathbf{D}\f$ such that: + * - \f$\mathbf{D}(0) = \mathbf{C}(a)\f$ + * - \f$\mathbf{D}(1) = \mathbf{C}(b)\f$ + * - \f$\mathbf{D}[ [0, 1] ] = \mathbf{C}[ [a?b] ]\f$, + * where \f$[a?b] = [\min(a, b), \max(a, b)]\f$ */ + virtual Curve *portion(Coord a, Coord b) const = 0; + + /** @brief A version of that accepts an Interval. */ + Curve *portion(Interval const &i) const { return portion(i.min(), i.max()); } + + /** @brief Create a reversed version of this curve. + * The result corresponds to <code>portion(1, 0)</code>, but this method might be faster. + * @return Pointer to a new curve \f$\mathbf{D}\f$ such that + * \f$\forall_{x \in [0, 1]} \mathbf{D}(x) = \mathbf{C}(1-x)\f$ */ + virtual Curve *reverse() const { return portion(1, 0); } + + /** @brief Create a derivative of this curve. + * It's best to think of the derivative in physical terms: if the curve describes + * the position of some object on the plane from time \f$t=0\f$ to \f$t=1\f$ as said in the + * introduction, then the curve's derivative describes that object's speed at the same times. + * The second derivative refers to its acceleration, the third to jerk, etc. + * @return New curve \f$\mathbf{D} = \mathbf{C}'\f$. */ + virtual Curve *derivative() const = 0; + /// @} + + /// @name Advanced operations + /// @{ + /** @brief Compute a time value at which the curve comes closest to a specified point. + * The first value with the smallest distance is returned if there are multiple such points. + * @param p Query point + * @param a Minimum time value to consider + * @param b Maximum time value to consider; \f$a < b\f$ + * @return \f$q \in [a, b]: ||\mathbf{C}(q) - \mathbf{p}|| = + \inf(\{r \in \mathbb{R} : ||\mathbf{C}(r) - \mathbf{p}||\})\f$ */ + virtual Coord nearestTime( Point const& p, Coord a = 0, Coord b = 1 ) const; + + /** @brief A version that takes an Interval. */ + Coord nearestTime(Point const &p, Interval const &i) const { + return nearestTime(p, i.min(), i.max()); + } + + /** @brief Compute time values at which the curve comes closest to a specified point. + * @param p Query point + * @param a Minimum time value to consider + * @param b Maximum time value to consider; \f$a < b\f$ + * @return Vector of points closest and equally far away from the query point */ + virtual std::vector<Coord> allNearestTimes( Point const& p, Coord from = 0, + Coord to = 1 ) const; + + /** @brief A version that takes an Interval. */ + std::vector<Coord> allNearestTimes(Point const &p, Interval const &i) { + return allNearestTimes(p, i.min(), i.max()); + } + + /** @brief Compute the arc length of this curve. + * For a curve \f$\mathbf{C}(t) = (C_x(t), C_y(t))\f$, arc length is defined for 2D curves as + * \f[ \ell = \int_{0}^{1} \sqrt { [C_x'(t)]^2 + [C_y'(t)]^2 }\, \text{d}t \f] + * In other words, we divide the curve into infinitely small linear segments + * and add together their lengths. Of course we can't subdivide the curve into + * infinitely many segments on a computer, so this method returns an approximation. + * Not that there is usually no closed form solution to such integrals, so this + * method might be slow. + * @param tolerance Maximum allowed error + * @return Total distance the curve's value travels on the plane when going from 0 to 1 */ + virtual Coord length(Coord tolerance=0.01) const; + + /** @brief Computes time values at which the curve intersects an axis-aligned line. + * @param v The coordinate of the line + * @param d Which axis the coordinate is on. X means a vertical line, Y a horizontal line. */ + virtual std::vector<Coord> roots(Coord v, Dim2 d) const = 0; + + /** @brief Compute the partial winding number of this curve. + * The partial winding number is equal to the difference between the number + * of roots at which the curve goes in the +Y direction and the number of roots + * at which the curve goes in the -Y direction. This method is mainly useful + * for implementing path winding calculation. It will ignore roots which + * are local maxima on the Y axis. + * @param p Point where the winding number should be determined + * @return Winding number contribution at p */ + virtual int winding(Point const &p) const; + + /// Compute intersections with another curve. + virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const; + + /// Compute intersections of this curve with itself. + virtual std::vector<CurveIntersection> intersectSelf(Coord eps = EPSILON) const; + + /** @brief Compute a vector tangent to the curve. + * This will return an unit vector (a Point with length() equal to 1) that denotes a vector + * tangent to the curve. This vector is defined as + * \f$ \mathbf{v}(t) = \frac{\mathbf{C}'(t)}{||\mathbf{C}'(t)||} \f$. It is pointed + * in the direction of increasing \f$t\f$, at the specified time value. The method uses + * l'Hopital's rule when the derivative is zero. A zero vector is returned if no non-zero + * derivative could be found. + * @param t Time value + * @param n The maximum order of derivative to consider + * @return Unit tangent vector \f$\mathbf{v}(t)\f$ */ + virtual Point unitTangentAt(Coord t, unsigned n = 3) const; + + /** @brief Convert the curve to a symmetric power basis polynomial. + * Symmetric power basis polynomials (S-basis for short) are numerical representations + * of curves with excellent numerical properties. Most high level operations provided by 2Geom + * are implemented in terms of S-basis operations, so every curve has to provide a method + * to convert it to an S-basis polynomial on two variables. See SBasis class reference + * for more information. */ + virtual D2<SBasis> toSBasis() const = 0; + /// @} + + /// @name Miscellaneous + /// @{ + /** Return the number of independent parameters required to represent all variations + * of this curve. For example, for Bezier curves it returns the curve's order + * multiplied by 2. */ + virtual int degreesOfFreedom() const { return 0;} + + /** @brief Test equality of two curves. + * Equality means that for any time value, the evaluation of either curve will yield + * the same value. This means non-degenerate curves are not equal to their reverses. + * Note that this tests for exact equality. + * @return True if the curves are identical, false otherwise */ + virtual bool operator==(Curve const &c) const = 0; + + /** @brief Test whether two curves are approximately the same. */ + virtual bool isNear(Curve const &c, Coord precision) const = 0; + + /** @brief Feed the curve to a PathSink */ + virtual void feed(PathSink &sink, bool moveto_initial) const; + /// @} +}; + +inline +Coord nearest_time(Point const& p, Curve const& c) { + return c.nearestTime(p); +} + +// for make benefit glorious library of Boost Pointer Container +inline +Curve *new_clone(Curve const &c) { + return c.duplicate(); +} + +} // end namespace Geom + + +#endif // _2GEOM_CURVE_H_ + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |