src/2geom/svg-elliptical-arc.h

   1 /**
   2  * \file
   3  * \brief  Elliptical Arc - implementation of the SVGEllipticalArc path element
   4  *
   5  * Authors:
   6  *      MenTaLguY <mental@rydia.net>
   7  *      Marco Cecchetti <mrcekets at gmail.com>
   8  *
   9  * Copyright 2007-2008  authors
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it either under the terms of the GNU Lesser General Public
  13  * License version 2.1 as published by the Free Software Foundation
  14  * (the "LGPL") or, at your option, under the terms of the Mozilla
  15  * Public License Version 1.1 (the "MPL"). If you do not alter this
  16  * notice, a recipient may use your version of this file under either
  17  * the MPL or the LGPL.
  18  *
  19  * You should have received a copy of the LGPL along with this library
  20  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  22  * You should have received a copy of the MPL along with this library
  23  * in the file COPYING-MPL-1.1
  24  *
  25  * The contents of this file are subject to the Mozilla Public License
  26  * Version 1.1 (the "License"); you may not use this file except in
  27  * compliance with the License. You may obtain a copy of the License at
  28  * http://www.mozilla.org/MPL/
  29  *
  30  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  31  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  32  * the specific language governing rights and limitations.
  33  */
  34
  35
  36 #ifndef _2GEOM_SVG_ELLIPTICAL_ARC_H_
  37 #define _2GEOM_SVG_ELLIPTICAL_ARC_H_
  38
  39
  40 #include <2geom/curve.h>
  41 #include <2geom/angle.h>
  42 #include <2geom/utils.h>
  43 #include <2geom/bezier-curve.h>
  44 #include <2geom/sbasis-curve.h>  // for non-native methods
  45 #include <2geom/numeric/vector.h>
  46 #include <2geom/numeric/fitting-tool.h>
  47 #include <2geom/numeric/fitting-model.h>
  48
  49
  50 #include <algorithm>
  51
  52
  53
  54 namespace Geom
  55 {
  56
  57 class SVGEllipticalArc : public Curve
  58 {
  59   public:
  60     SVGEllipticalArc(bool _svg_compliant = true)
  61         : m_initial_point(Point(0,0)), m_final_point(Point(0,0)),
  62           m_rx(0), m_ry(0), m_rot_angle(0),
  63           m_large_arc(true), m_sweep(true),
  64           m_svg_compliant(_svg_compliant),
  65           m_start_angle(0), m_end_angle(0),
  66           m_center(Point(0,0))
  67     {
  68     }
  69
  70     /**
  71      * \brief constructor
  72      *
  73      * \param _initial_point:     initial arc end point;
  74      * \param _rx:                ellipse x-axis ray length
  75      * \param _ry:                ellipse y-axis ray length
  76      * \param _rot_angle:         ellipse x-axis rotation angle in radians;
  77      * \param _large_arc:         if true the largest arc is chosen,
  78      *                     if false the smallest arc is chosen;
  79      * \param _sweep :            if true the clockwise arc is chosen,
  80      *                     if false the counter-clockwise arc is chosen;
  81      * \param _final_point:       final arc end point;
  82      * \param _svg_compliant:     if true the class behaviour follows the Standard
  83      *                     SVG 1.1 implementation guidelines (see Appendix F.6)
  84      *                     if false the class behavoiur is more strict
  85      *                     on input parameter
  86      *
  87      * in case the initial and the final arc end-points overlaps
  88      * a degenerate arc of zero length is generated
  89      *
  90      */
  91     SVGEllipticalArc( Point _initial_point, double _rx, double _ry,
  92                       double _rot_angle, bool _large_arc, bool _sweep,
  93                       Point _final_point,
  94                       bool _svg_compliant = true
  95                     )
  96         : m_initial_point(_initial_point), m_final_point(_final_point),
  97           m_rx(_rx), m_ry(_ry), m_rot_angle(_rot_angle),
  98           m_large_arc(_large_arc), m_sweep(_sweep),
  99           m_svg_compliant(_svg_compliant)
 100     {
 101             calculate_center_and_extreme_angles();
 102     }
 103
 104     void set( Point _initial_point, double _rx, double _ry,
 105               double _rot_angle, bool _large_arc, bool _sweep,
 106               Point _final_point
 107              )
 108     {
 109         m_initial_point = _initial_point;
 110         m_final_point = _final_point;
 111         m_rx = _rx;
 112         m_ry = _ry;
 113         m_rot_angle = _rot_angle;
 114         m_large_arc = _large_arc;
 115         m_sweep = _sweep;
 116         calculate_center_and_extreme_angles();
 117     }
 118
 119     Curve* duplicate() const
 120     {
 121         return new SVGEllipticalArc(*this);
 122     }
 123
 124     double center(unsigned int i) const
 125     {
 126         return m_center[i];
 127     }
 128
 129     Point center() const
 130     {
 131         return m_center;
 132     }
 133
 134     Point initialPoint() const
 135     {
 136         return m_initial_point;
 137     }
 138
 139     Point finalPoint() const
 140     {
 141         return m_final_point;
 142     }
 143
 144     double start_angle() const
 145     {
 146         return m_start_angle;
 147     }
 148
 149     double end_angle() const
 150     {
 151         return m_end_angle;
 152     }
 153
 154     double ray(unsigned int i) const
 155     {
 156         return (i == 0) ? m_rx : m_ry;
 157     }
 158
 159     bool large_arc_flag() const
 160     {
 161         return m_large_arc;
 162     }
 163
 164     bool sweep_flag() const
 165     {
 166         return m_sweep;
 167     }
 168
 169     double rotation_angle() const
 170     {
 171         return m_rot_angle;
 172     }
 173
 174     void setInitial( const Point _point)
 175     {
 176         m_initial_point = _point;
 177         calculate_center_and_extreme_angles();
 178     }
 179
 180     void setFinal( const Point _point)
 181     {
 182         m_final_point = _point;
 183         calculate_center_and_extreme_angles();
 184     }
 185
 186     void setExtremes( const Point& _initial_point, const Point& _final_point )
 187     {
 188         m_initial_point = _initial_point;
 189         m_final_point = _final_point;
 190         calculate_center_and_extreme_angles();
 191     }
 192
 193     bool isDegenerate() const
 194     {
 195         return ( are_near(ray(X), 0) || are_near(ray(Y), 0) );
 196     }
 197
 198     bool is_svg_compliant() const
 199     {
 200         return m_svg_compliant;
 201     }
 202
 203     virtual OptRect boundsFast() const
 204     {
 205         return boundsExact();
 206     }
 207
 208     virtual OptRect boundsExact() const;
 209
 210     // TODO: native implementation of the following methods
 211     virtual OptRect boundsLocal(OptInterval i, unsigned int deg) const
 212     {
 213         if (isDegenerate() && is_svg_compliant())
 214             return chord().boundsLocal(i, deg);
 215         else
 216             return SBasisCurve(toSBasis()).boundsLocal(i, deg);
 217     }
 218
 219     std::vector<double> roots(double v, Dim2 d) const;
 220
 221     /*
 222      * find all the points on the curve portion between "from" and "to"
 223      * at the same smallest distance from the point "p" the points are returned
 224      * as their parameter t value;
 225      */
 226     std::vector<double>
 227     allNearestPoints( Point const& p, double from = 0, double to = 1 ) const;
 228
 229     /*
 230      * find a point on the curve portion between "from" and "to"
 231      * at the same smallest distance from the point "p";
 232      * the point is returned as its parameter t value;
 233      */
 234     double nearestPoint( Point const& p, double from = 0, double to = 1 ) const
 235     {
 236         if ( are_near(ray(X), ray(Y)) && are_near(center(), p) )
 237         {
 238             return from;
 239         }
 240         return allNearestPoints(p, from, to).front();
 241     }
 242
 243     // TODO: native implementation of the following methods
 244     int winding(Point p) const
 245     {
 246         if (isDegenerate() && is_svg_compliant())
 247             return chord().winding(p);
 248         else
 249             return SBasisCurve(toSBasis()).winding(p);
 250     }
 251
 252     int degreesOfFreedom() const { return 5;}
 253
 254     Curve *derivative() const;
 255
 256     Curve *transformed(Matrix const &m) const;
 257
 258     std::vector<Point> pointAndDerivatives(Coord t, unsigned int n) const;
 259
 260     D2<SBasis> toSBasis() const;
 261
 262     /*
 263      * return true if the angle argument (in radiants) is contained
 264      * in the range [start_angle(), end_angle() ]
 265      */
 266     bool containsAngle(Coord angle) const;
 267
 268     /*
 269      * return the value of the d-dimensional coordinate related to "t"
 270      * here t belongs to the [0,2PI] domain
 271      */
 272     double valueAtAngle(Coord t, Dim2 d) const;
 273
 274     /*
 275      * return the point related to the parameter value "t"
 276      * here t belongs to the [0,2PI] domain
 277      */
 278     Point pointAtAngle(Coord t) const
 279     {
 280         double sin_rot_angle = std::sin(rotation_angle());
 281         double cos_rot_angle = std::cos(rotation_angle());
 282         Matrix m( ray(X) * cos_rot_angle, ray(X) * sin_rot_angle,
 283                  -ray(Y) * sin_rot_angle, ray(Y) * cos_rot_angle,
 284                   center(X),              center(Y) );
 285         Point p( std::cos(t), std::sin(t) );
 286         return p * m;
 287     }
 288
 289     /*
 290      * return the value of the d-dimensional coordinate related to "t"
 291      * here t belongs to the [0,1] domain
 292      */
 293     double valueAt(Coord t, Dim2 d) const
 294     {
 295         if (isDegenerate() && is_svg_compliant())
 296             return chord().valueAt(t, d);
 297
 298         Coord tt = map_to_02PI(t);
 299         return valueAtAngle(tt, d);
 300     }
 301
 302     /*
 303      * return the point related to the parameter value "t"
 304      * here t belongs to the [0,1] domain
 305      */
 306     Point pointAt(Coord t) const
 307     {
 308         if (isDegenerate() && is_svg_compliant())
 309             return chord().pointAt(t);
 310
 311         Coord tt = map_to_02PI(t);
 312         return pointAtAngle(tt);
 313     }
 314
 315     std::pair<SVGEllipticalArc, SVGEllipticalArc>
 316     subdivide(Coord t) const
 317     {
 318         SVGEllipticalArc* arc1 = static_cast<SVGEllipticalArc*>(portion(0, t));
 319         SVGEllipticalArc* arc2 = static_cast<SVGEllipticalArc*>(portion(t, 1));
 320         assert( arc1 != NULL && arc2 != NULL);
 321         std::pair<SVGEllipticalArc, SVGEllipticalArc> arc_pair(*arc1, *arc2);
 322         delete arc1;
 323         delete arc2;
 324         return arc_pair;
 325     }
 326
 327     Curve* portion(double f, double t) const;
 328
 329     // the arc is the same but traversed in the opposite direction
 330     Curve* reverse() const
 331     {
 332         SVGEllipticalArc* rarc = new SVGEllipticalArc( *this );
 333         rarc->m_sweep = !m_sweep;
 334         rarc->m_initial_point = m_final_point;
 335         rarc->m_final_point = m_initial_point;
 336         rarc->m_start_angle = m_end_angle;
 337         rarc->m_end_angle = m_start_angle;
 338         return rarc;
 339     }
 340
 341
 342     double sweep_angle() const
 343     {
 344         Coord d = end_angle() - start_angle();
 345         if ( !sweep_flag() ) d = -d;
 346         if ( d < 0 )
 347             d += 2*M_PI;
 348         return d;
 349     }
 350
 351     LineSegment chord() const
 352     {
 353         return LineSegment(initialPoint(), finalPoint());
 354     }
 355
 356   private:
 357     Coord map_to_02PI(Coord t) const;
 358     Coord map_to_01(Coord angle) const;
 359     void calculate_center_and_extreme_angles();
 360
 361   private:
 362     Point m_initial_point, m_final_point;
 363     double m_rx, m_ry, m_rot_angle;
 364     bool m_large_arc, m_sweep;
 365     bool m_svg_compliant;
 366     double m_start_angle, m_end_angle;
 367     Point m_center;
 368
 369 }; // end class SVGEllipticalArc
 370
 371
 372 /*
 373  * useful for testing and debugging
 374  */
 375 template< class charT >
 376 inline
 377 std::basic_ostream<charT> &
 378 operator<< (std::basic_ostream<charT> & os, const SVGEllipticalArc & ea)
 379 {
 380     os << "{ cx: " << ea.center(X) << ", cy: " <<  ea.center(Y)
 381        << ", rx: " << ea.ray(X) << ", ry: " << ea.ray(Y)
 382        << ", rot angle: " << decimal_round(rad_to_deg(ea.rotation_angle()),2)
 383        << ", start angle: " << decimal_round(rad_to_deg(ea.start_angle()),2)
 384        << ", end angle: " << decimal_round(rad_to_deg(ea.end_angle()),2)
 385        << " }";
 386
 387     return os;
 388 }
 389
 390
 391
 392
 393 // forward declation
 394 namespace detail
 395 {
 396     struct ellipse_equation;
 397 }
 398
 399 /*
 400  * make_elliptical_arc
 401  *
 402  * convert a parametric polynomial curve given in symmetric power basis form
 403  * into an SVGEllipticalArc type; in order to be successfull the input curve
 404  * has to look like an actual elliptical arc even if a certain tolerance
 405  * is allowed through an ad-hoc parameter.
 406  * The conversion is performed through an interpolation on a certain amount of
 407  * sample points computed on the input curve;
 408  * the interpolation computes the coefficients of the general implicit equation
 409  * of an ellipse (A*X^2 + B*XY + C*Y^2 + D*X + E*Y + F = 0), then from the
 410  * implicit equation we compute the parametric form.
 411  *
 412  */
 413 class make_elliptical_arc
 414 {
 415   public:
 416     typedef D2<SBasis> curve_type;
 417
 418     /*
 419      * constructor
 420      *
 421      * it doesn't execute the conversion but set the input and output parameters
 422      *
 423      * _ea:         the output SVGEllipticalArc that will be generated;
 424      * _curve:      the input curve to be converted;
 425      * _total_samples: the amount of sample points to be taken
 426      *                 on the input curve for performing the conversion
 427      * _tolerance:     how much likelihood is required between the input curve
 428      *                 and the generated elliptical arc; the smaller it is the
 429      *                 the tolerance the higher it is the likelihood.
 430      */
 431     make_elliptical_arc( SVGEllipticalArc& _ea,
 432                          curve_type const& _curve,
 433                          unsigned int _total_samples,
 434                          double _tolerance );
 435
 436   private:
 437     bool bound_exceeded( unsigned int k, detail::ellipse_equation const & ee,
 438                          double e1x, double e1y, double e2 );
 439
 440     bool check_bound(double A, double B, double C, double D, double E, double F);
 441
 442     void fit();
 443
 444     bool make_elliptiarc();
 445
 446     void print_bound_error(unsigned int k)
 447     {
 448         std::cerr
 449             << "tolerance error" << std::endl
 450             << "at point: " << k << std::endl
 451             << "error value: "<< dist_err << std::endl
 452             << "bound: " << dist_bound << std::endl
 453             << "angle error: " << angle_err
 454             << " (" << angle_tol << ")" << std::endl;
 455     }
 456
 457   public:
 458     /*
 459      * perform the actual conversion
 460      * return true if the conversion is successfull, false on the contrary
 461      */
 462     bool operator()()
 463     {
 464         // initialize the reference
 465         const NL::Vector & coeff = fitter.result();
 466         fit();
 467         if ( !check_bound(1, coeff[0], coeff[1], coeff[2], coeff[3], coeff[4]) )
 468             return false;
 469         if ( !(make_elliptiarc()) ) return false;
 470         return true;
 471     }
 472
 473     /*
 474      * you can set a boolean parameter to tell the conversion routine
 475      * if the output elliptical arc has to be svg compliant or not;
 476      * the default value is true
 477      */
 478     bool svg_compliant_flag() const
 479     {
 480         return svg_compliant;
 481     }
 482
 483     void svg_compliant_flag(bool _svg_compliant)
 484     {
 485         svg_compliant = _svg_compliant;
 486     }
 487
 488   private:
 489       SVGEllipticalArc& ea;                 // output elliptical arc
 490       const curve_type & curve;             // input curve
 491       Piecewise<D2<SBasis> > dcurve;        // derivative of the input curve
 492       NL::LFMEllipse model;                 // model used for fitting
 493       // perform the actual fitting task
 494       NL::least_squeares_fitter<NL::LFMEllipse> fitter;
 495       // tolerance: the user-defined tolerance parameter;
 496       // tol_at_extr: the tolerance at end-points automatically computed
 497       // on the value of "tolerance", and usually more strict;
 498       // tol_at_center: tolerance at the center of the ellipse
 499       // angle_tol: tolerance for the angle btw the input curve tangent
 500       // versor and the ellipse normal versor at the sample points
 501       double tolerance, tol_at_extr, tol_at_center, angle_tol;
 502       Point initial_point, final_point;     // initial and final end-points
 503       unsigned int N;                       // total samples
 504       unsigned int last; // N-1
 505       double partitions; // N-1
 506       std::vector<Point> p;                 // sample points
 507       double dist_err, dist_bound, angle_err;
 508       bool svg_compliant;
 509 };
 510
 511
 512 } // end namespace Geom
 513
 514
 515
 516
 517 #endif /* _2GEOM_SVG_ELLIPTICAL_ARC_H_ */
 518
 519 /*
 520   Local Variables:
 521   mode:c++
 522   c-file-style:"stroustrup"
 523   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 524   indent-tabs-mode:nil
 525   fill-column:99
 526   End:
 527 */
 528 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
 529