| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Abstract curve type | ||
| 4 | * | ||
| 5 | *//* | ||
| 6 | * Authors: | ||
| 7 | * MenTaLguY <mental@rydia.net> | ||
| 8 | * Marco Cecchetti <mrcekets at gmail.com> | ||
| 9 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 10 | * | ||
| 11 | * Copyright 2007-2009 Authors | ||
| 12 | * | ||
| 13 | * This library is free software; you can redistribute it and/or | ||
| 14 | * modify it either under the terms of the GNU Lesser General Public | ||
| 15 | * License version 2.1 as published by the Free Software Foundation | ||
| 16 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 17 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 18 | * notice, a recipient may use your version of this file under either | ||
| 19 | * the MPL or the LGPL. | ||
| 20 | * | ||
| 21 | * You should have received a copy of the LGPL along with this library | ||
| 22 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 23 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 24 | * You should have received a copy of the MPL along with this library | ||
| 25 | * in the file COPYING-MPL-1.1 | ||
| 26 | * | ||
| 27 | * The contents of this file are subject to the Mozilla Public License | ||
| 28 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 29 | * compliance with the License. You may obtain a copy of the License at | ||
| 30 | * http://www.mozilla.org/MPL/ | ||
| 31 | * | ||
| 32 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 33 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 34 | * the specific language governing rights and limitations. | ||
| 35 | */ | ||
| 36 | |||
| 37 | |||
| 38 | #ifndef LIB2GEOM_SEEN_CURVE_H | ||
| 39 | #define LIB2GEOM_SEEN_CURVE_H | ||
| 40 | |||
| 41 | #include <vector> | ||
| 42 | #include <boost/operators.hpp> | ||
| 43 | #include <2geom/coord.h> | ||
| 44 | #include <2geom/point.h> | ||
| 45 | #include <2geom/interval.h> | ||
| 46 | #include <2geom/sbasis.h> | ||
| 47 | #include <2geom/d2.h> | ||
| 48 | #include <2geom/affine.h> | ||
| 49 | #include <2geom/intersection.h> | ||
| 50 | |||
| 51 | namespace Geom { | ||
| 52 | |||
| 53 | class PathSink; | ||
| 54 | typedef Intersection<> CurveIntersection; | ||
| 55 | |||
| 56 | /** | ||
| 57 | * @brief Abstract continuous curve on a plane defined on [0,1]. | ||
| 58 | * | ||
| 59 | * Formally, a curve in 2Geom is defined as a function | ||
| 60 | * \f$\mathbf{C}: [0, 1] \to \mathbb{R}^2\f$ | ||
| 61 | * (a function that maps the unit interval to points on a 2D plane). Its image (the set of points | ||
| 62 | * the curve passes through) will be denoted \f$\mathcal{C} = \mathbf{C}[ [0, 1] ]\f$. | ||
| 63 | * All curve types available in 2Geom are continuous and differentiable on their | ||
| 64 | * interior, e.g. \f$(0, 1)\f$. Sometimes the curve's image (value set) is referred to as the curve | ||
| 65 | * itself for simplicity, but keep in mind that it's not strictly correct. | ||
| 66 | * | ||
| 67 | * It is common to think of the parameter as time. The curve can then be interpreted as | ||
| 68 | * describing the position of some moving object from time \f$t=0\f$ to \f$t=1\f$. | ||
| 69 | * Because of this, the parameter is frequently called the time value. | ||
| 70 | * | ||
| 71 | * Some methods return pointers to newly allocated curves. They are expected to be freed | ||
| 72 | * by the caller when no longer used. Default implementations are provided for some methods. | ||
| 73 | * | ||
| 74 | * @ingroup Curves | ||
| 75 | */ | ||
| 76 | class Curve | ||
| 77 | : boost::equality_comparable<Curve> | ||
| 78 | { | ||
| 79 | public: | ||
| 80 | 2307610 | virtual ~Curve() {} | |
| 81 | |||
| 82 | /// @name Evaluate the curve | ||
| 83 | /// @{ | ||
| 84 | /** @brief Retrieve the start of the curve. | ||
| 85 | * @return The point corresponding to \f$\mathbf{C}(0)\f$. */ | ||
| 86 | virtual Point initialPoint() const = 0; | ||
| 87 | |||
| 88 | /** Retrieve the end of the curve. | ||
| 89 | * @return The point corresponding to \f$\mathbf{C}(1)\f$. */ | ||
| 90 | virtual Point finalPoint() const = 0; | ||
| 91 | |||
| 92 | /** @brief Check whether the curve has exactly zero length. | ||
| 93 | * @return True if the curve's initial point is exactly the same as its final point, and it contains | ||
| 94 | * no other points (its value set contains only one element). */ | ||
| 95 | virtual bool isDegenerate() const = 0; | ||
| 96 | |||
| 97 | /// Check whether the curve is a line segment. | ||
| 98 | ✗ | virtual bool isLineSegment() const { return false; } | |
| 99 | |||
| 100 | /** @brief Get the interval of allowed time values. | ||
| 101 | * @return \f$[0, 1]\f$ */ | ||
| 102 | ✗ | virtual Interval timeRange() const { | |
| 103 | ✗ | Interval tr(0, 1); | |
| 104 | ✗ | return tr; | |
| 105 | } | ||
| 106 | |||
| 107 | /** @brief Evaluate the curve at a specified time value. | ||
| 108 | * @param t Time value | ||
| 109 | * @return \f$\mathbf{C}(t)\f$ */ | ||
| 110 | ✗ | virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 0).front(); } | |
| 111 | |||
| 112 | /** @brief Evaluate one of the coordinates at the specified time value. | ||
| 113 | * @param t Time value | ||
| 114 | * @param d The dimension to evaluate | ||
| 115 | * @return The specified coordinate of \f$\mathbf{C}(t)\f$ */ | ||
| 116 | ✗ | virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; } | |
| 117 | |||
| 118 | /** @brief Evaluate the function at the specified time value. Allows curves to be used | ||
| 119 | * as functors. */ | ||
| 120 | ✗ | virtual Point operator() (Coord t) const { return pointAt(t); } | |
| 121 | |||
| 122 | /** @brief Evaluate the curve and its derivatives. | ||
| 123 | * This will return a vector that contains the value of the curve and the specified number | ||
| 124 | * of derivatives. However, the returned vector might contain less elements than specified | ||
| 125 | * if some derivatives do not exist. | ||
| 126 | * @param t Time value | ||
| 127 | * @param n The number of derivatives to compute | ||
| 128 | * @return Vector of at most \f$n+1\f$ elements of the form \f$[\mathbf{C}(t), | ||
| 129 | \mathbf{C}'(t), \mathbf{C}''(t), \ldots]\f$ */ | ||
| 130 | virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const = 0; | ||
| 131 | /// @} | ||
| 132 | |||
| 133 | /// @name Change the curve's endpoints | ||
| 134 | /// @{ | ||
| 135 | /** @brief Change the starting point of the curve. | ||
| 136 | * After calling this method, it is guaranteed that \f$\mathbf{C}(0) = \mathbf{p}\f$, | ||
| 137 | * and the curve is still continuous. The precise new shape of the curve varies with curve | ||
| 138 | * type. | ||
| 139 | * @param p New starting point of the curve */ | ||
| 140 | virtual void setInitial(Point const &v) = 0; | ||
| 141 | |||
| 142 | /** @brief Change the ending point of the curve. | ||
| 143 | * After calling this method, it is guaranteed that \f$\mathbf{C}(0) = \mathbf{p}\f$, | ||
| 144 | * and the curve is still continuous. The precise new shape of the curve varies | ||
| 145 | * with curve type. | ||
| 146 | * @param p New ending point of the curve */ | ||
| 147 | virtual void setFinal(Point const &v) = 0; | ||
| 148 | /// @} | ||
| 149 | |||
| 150 | /// @name Compute the bounding box | ||
| 151 | /// @{ | ||
| 152 | /** @brief Quickly compute the curve's approximate bounding box. | ||
| 153 | * The resulting rectangle is guaranteed to contain all points belonging to the curve, | ||
| 154 | * but it might not be the smallest such rectangle. This method is usually fast. | ||
| 155 | * @return A rectangle that contains all points belonging to the curve. */ | ||
| 156 | virtual Rect boundsFast() const = 0; | ||
| 157 | |||
| 158 | /** @brief Compute the curve's exact bounding box. | ||
| 159 | * This method can be dramatically slower than boundsFast() depending on the curve type. | ||
| 160 | * @return The smallest possible rectangle containing all of the curve's points. */ | ||
| 161 | virtual Rect boundsExact() const = 0; | ||
| 162 | |||
| 163 | /** @brief Expand the given rectangle to include the transformed curve, | ||
| 164 | * assuming it already contains its initial point. | ||
| 165 | * @param bbox[in,out] bbox The rectangle to expand; it is assumed to already contain (initialPoint() * transform). | ||
| 166 | * @param transform The transform to apply to the curve before taking its bounding box. */ | ||
| 167 | virtual void expandToTransformed(Rect &bbox, Affine const &transform) const = 0; | ||
| 168 | |||
| 169 | // I have no idea what the 'deg' parameter is for, so this is undocumented for now. | ||
| 170 | virtual OptRect boundsLocal(OptInterval const &i, unsigned deg) const = 0; | ||
| 171 | |||
| 172 | /** @brief Compute the bounding box of a part of the curve. | ||
| 173 | * Since this method returns the smallest possible bounding rectangle of the specified portion, | ||
| 174 | * it can also be rather slow. | ||
| 175 | * @param a An interval specifying a part of the curve, or nothing. | ||
| 176 | * If \f$[0, 1] \subseteq a\f$, then the bounding box for the entire curve | ||
| 177 | * is calculated. | ||
| 178 | * @return The smallest possible rectangle containing all points in \f$\mathbf{C}[a]\f$, | ||
| 179 | * or nothing if the supplied interval is empty. */ | ||
| 180 | ✗ | OptRect boundsLocal(OptInterval const &a) const { return boundsLocal(a, 0); } | |
| 181 | /// @} | ||
| 182 | |||
| 183 | /// @name Create new curves based on this one | ||
| 184 | /// @{ | ||
| 185 | /** @brief Create an exact copy of this curve. | ||
| 186 | * @return Pointer to a newly allocated curve, identical to the original */ | ||
| 187 | virtual Curve *duplicate() const = 0; | ||
| 188 | |||
| 189 | /** @brief Transform this curve by an affine transformation. | ||
| 190 | * Because of this method, all curve types must be closed under affine | ||
| 191 | * transformations. | ||
| 192 | * @param m Affine describing the affine transformation */ | ||
| 193 | 40000 | void transform(Affine const &m) { | |
| 194 | 40000 | *this *= m; | |
| 195 | 40000 | } | |
| 196 | |||
| 197 | ✗ | virtual void operator*=(Translate const &tr) { *this *= Affine(tr); } | |
| 198 | ✗ | virtual void operator*=(Scale const &s) { *this *= Affine(s); } | |
| 199 | ✗ | virtual void operator*=(Rotate const &r) { *this *= Affine(r); } | |
| 200 | ✗ | virtual void operator*=(HShear const &hs) { *this *= Affine(hs); } | |
| 201 | ✗ | virtual void operator*=(VShear const &vs) { *this *= Affine(vs); } | |
| 202 | ✗ | virtual void operator*=(Zoom const &z) { *this *= Affine(z); } | |
| 203 | virtual void operator*=(Affine const &m) = 0; | ||
| 204 | |||
| 205 | /** @brief Create a curve transformed by an affine transformation. | ||
| 206 | * This method returns a new curve instead modifying the existing one. | ||
| 207 | * @param m Affine describing the affine transformation | ||
| 208 | * @return Pointer to a new, transformed curve */ | ||
| 209 | ✗ | virtual Curve *transformed(Affine const &m) const { | |
| 210 | ✗ | Curve *ret = duplicate(); | |
| 211 | ✗ | ret->transform(m); | |
| 212 | ✗ | return ret; | |
| 213 | } | ||
| 214 | |||
| 215 | /** @brief Create a curve that corresponds to a part of this curve. | ||
| 216 | * For \f$a > b\f$, the returned portion will be reversed with respect to the original. | ||
| 217 | * The returned curve will always be of the same type. | ||
| 218 | * @param a Beginning of the interval specifying the portion of the curve | ||
| 219 | * @param b End of the interval | ||
| 220 | * @return New curve \f$\mathbf{D}\f$ such that: | ||
| 221 | * - \f$\mathbf{D}(0) = \mathbf{C}(a)\f$ | ||
| 222 | * - \f$\mathbf{D}(1) = \mathbf{C}(b)\f$ | ||
| 223 | * - \f$\mathbf{D}[ [0, 1] ] = \mathbf{C}[ [a?b] ]\f$, | ||
| 224 | * where \f$[a?b] = [\min(a, b), \max(a, b)]\f$ */ | ||
| 225 | virtual Curve *portion(Coord a, Coord b) const = 0; | ||
| 226 | |||
| 227 | /** @brief A version of that accepts an Interval. */ | ||
| 228 | Curve *portion(Interval const &i) const { return portion(i.min(), i.max()); } | ||
| 229 | |||
| 230 | /** @brief Create a reversed version of this curve. | ||
| 231 | * The result corresponds to <code>portion(1, 0)</code>, but this method might be faster. | ||
| 232 | * @return Pointer to a new curve \f$\mathbf{D}\f$ such that | ||
| 233 | * \f$\forall_{x \in [0, 1]} \mathbf{D}(x) = \mathbf{C}(1-x)\f$ */ | ||
| 234 | ✗ | virtual Curve *reverse() const { return portion(1, 0); } | |
| 235 | |||
| 236 | /** @brief Create a derivative of this curve. | ||
| 237 | * It's best to think of the derivative in physical terms: if the curve describes | ||
| 238 | * the position of some object on the plane from time \f$t=0\f$ to \f$t=1\f$ as said in the | ||
| 239 | * introduction, then the curve's derivative describes that object's speed at the same times. | ||
| 240 | * The second derivative refers to its acceleration, the third to jerk, etc. | ||
| 241 | * @return New curve \f$\mathbf{D} = \mathbf{C}'\f$. */ | ||
| 242 | virtual Curve *derivative() const = 0; | ||
| 243 | /// @} | ||
| 244 | |||
| 245 | /// @name Advanced operations | ||
| 246 | /// @{ | ||
| 247 | /** @brief Compute a time value at which the curve comes closest to a specified point. | ||
| 248 | * The first value with the smallest distance is returned if there are multiple such points. | ||
| 249 | * @param p Query point | ||
| 250 | * @param a Minimum time value to consider | ||
| 251 | * @param b Maximum time value to consider; \f$a < b\f$ | ||
| 252 | * @return \f$q \in [a, b]: ||\mathbf{C}(q) - \mathbf{p}|| = | ||
| 253 | \inf(\{r \in \mathbb{R} : ||\mathbf{C}(r) - \mathbf{p}||\})\f$ */ | ||
| 254 | virtual Coord nearestTime( Point const& p, Coord a = 0, Coord b = 1 ) const; | ||
| 255 | |||
| 256 | /** @brief A version that takes an Interval. */ | ||
| 257 | Coord nearestTime(Point const &p, Interval const &i) const { | ||
| 258 | return nearestTime(p, i.min(), i.max()); | ||
| 259 | } | ||
| 260 | |||
| 261 | /** @brief Compute time values at which the curve comes closest to a specified point. | ||
| 262 | * @param p Query point | ||
| 263 | * @param a Minimum time value to consider | ||
| 264 | * @param b Maximum time value to consider; \f$a < b\f$ | ||
| 265 | * @return Vector of points closest and equally far away from the query point */ | ||
| 266 | virtual std::vector<Coord> allNearestTimes( Point const& p, Coord from = 0, | ||
| 267 | Coord to = 1 ) const; | ||
| 268 | |||
| 269 | /** @brief A version that takes an Interval. */ | ||
| 270 | std::vector<Coord> allNearestTimes(Point const &p, Interval const &i) { | ||
| 271 | return allNearestTimes(p, i.min(), i.max()); | ||
| 272 | } | ||
| 273 | |||
| 274 | /** @brief Compute the arc length of this curve. | ||
| 275 | * For a curve \f$\mathbf{C}(t) = (C_x(t), C_y(t))\f$, arc length is defined for 2D curves as | ||
| 276 | * \f[ \ell = \int_{0}^{1} \sqrt { [C_x'(t)]^2 + [C_y'(t)]^2 }\, \text{d}t \f] | ||
| 277 | * In other words, we divide the curve into infinitely small linear segments | ||
| 278 | * and add together their lengths. Of course we can't subdivide the curve into | ||
| 279 | * infinitely many segments on a computer, so this method returns an approximation. | ||
| 280 | * Not that there is usually no closed form solution to such integrals, so this | ||
| 281 | * method might be slow. | ||
| 282 | * @param tolerance Maximum allowed error | ||
| 283 | * @return Total distance the curve's value travels on the plane when going from 0 to 1 */ | ||
| 284 | virtual Coord length(Coord tolerance=0.01) const; | ||
| 285 | |||
| 286 | /** @brief Computes time values at which the curve intersects an axis-aligned line. | ||
| 287 | * @param v The coordinate of the line | ||
| 288 | * @param d Which axis the coordinate is on. X means a vertical line, Y a horizontal line. */ | ||
| 289 | virtual std::vector<Coord> roots(Coord v, Dim2 d) const = 0; | ||
| 290 | |||
| 291 | /** @brief Compute the partial winding number of this curve. | ||
| 292 | * The partial winding number is equal to the difference between the number | ||
| 293 | * of roots at which the curve goes in the +Y direction and the number of roots | ||
| 294 | * at which the curve goes in the -Y direction. This method is mainly useful | ||
| 295 | * for implementing path winding calculation. It will ignore roots which | ||
| 296 | * are local maxima on the Y axis. | ||
| 297 | * @param p Point where the winding number should be determined | ||
| 298 | * @return Winding number contribution at p */ | ||
| 299 | virtual int winding(Point const &p) const; | ||
| 300 | |||
| 301 | /// Compute intersections with another curve. | ||
| 302 | virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const; | ||
| 303 | |||
| 304 | /// Compute intersections of this curve with itself. | ||
| 305 | virtual std::vector<CurveIntersection> intersectSelf(Coord eps = EPSILON) const; | ||
| 306 | |||
| 307 | /** @brief Compute a vector tangent to the curve. | ||
| 308 | * This will return an unit vector (a Point with length() equal to 1) that denotes a vector | ||
| 309 | * tangent to the curve. This vector is defined as | ||
| 310 | * \f$ \mathbf{v}(t) = \frac{\mathbf{C}'(t)}{||\mathbf{C}'(t)||} \f$. It is pointed | ||
| 311 | * in the direction of increasing \f$t\f$, at the specified time value. The method uses | ||
| 312 | * l'Hopital's rule when the derivative is zero. A zero vector is returned if no non-zero | ||
| 313 | * derivative could be found. | ||
| 314 | * @param t Time value | ||
| 315 | * @param n The maximum order of derivative to consider | ||
| 316 | * @return Unit tangent vector \f$\mathbf{v}(t)\f$ */ | ||
| 317 | virtual Point unitTangentAt(Coord t, unsigned n = 3) const; | ||
| 318 | |||
| 319 | /** @brief Convert the curve to a symmetric power basis polynomial. | ||
| 320 | * Symmetric power basis polynomials (S-basis for short) are numerical representations | ||
| 321 | * of curves with excellent numerical properties. Most high level operations provided by 2Geom | ||
| 322 | * are implemented in terms of S-basis operations, so every curve has to provide a method | ||
| 323 | * to convert it to an S-basis polynomial on two variables. See SBasis class reference | ||
| 324 | * for more information. */ | ||
| 325 | virtual D2<SBasis> toSBasis() const = 0; | ||
| 326 | /// @} | ||
| 327 | |||
| 328 | /// @name Miscellaneous | ||
| 329 | /// @{ | ||
| 330 | /** Return the number of independent parameters required to represent all variations | ||
| 331 | * of this curve. For example, for Bezier curves it returns the curve's order | ||
| 332 | * multiplied by 2. */ | ||
| 333 | ✗ | virtual int degreesOfFreedom() const { return 0;} | |
| 334 | |||
| 335 | /** @brief Test equality of two curves. | ||
| 336 | * Equality means that for any time value, the evaluation of either curve will yield | ||
| 337 | * the same value. This means non-degenerate curves are not equal to their reverses. | ||
| 338 | * Note that this tests for exact equality. | ||
| 339 | * @return True if the curves are identical, false otherwise */ | ||
| 340 | 313 | bool operator==(Curve const &c) const { return _equalTo(c); } | |
| 341 | |||
| 342 | /** @brief Test whether two curves are approximately the same. */ | ||
| 343 | virtual bool isNear(Curve const &c, Coord precision) const = 0; | ||
| 344 | |||
| 345 | /** @brief Feed the curve to a PathSink */ | ||
| 346 | virtual void feed(PathSink &sink, bool moveto_initial) const; | ||
| 347 | /// @} | ||
| 348 | |||
| 349 | protected: | ||
| 350 | virtual bool _equalTo(Curve const &c) const = 0; | ||
| 351 | }; | ||
| 352 | |||
| 353 | inline | ||
| 354 | Coord nearest_time(Point const& p, Curve const& c) { | ||
| 355 | return c.nearestTime(p); | ||
| 356 | } | ||
| 357 | |||
| 358 | // for make benefit glorious library of Boost Pointer Container | ||
| 359 | inline | ||
| 360 | 24135 | Curve *new_clone(Curve const &c) { | |
| 361 | 24135 | return c.duplicate(); | |
| 362 | } | ||
| 363 | |||
| 364 | } // end namespace Geom | ||
| 365 | |||
| 366 | |||
| 367 | #endif // _2GEOM_CURVE_H_ | ||
| 368 | |||
| 369 | /* | ||
| 370 | Local Variables: | ||
| 371 | mode:c++ | ||
| 372 | c-file-style:"stroustrup" | ||
| 373 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 374 | indent-tabs-mode:nil | ||
| 375 | fill-column:99 | ||
| 376 | End: | ||
| 377 | */ | ||
| 378 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 379 |