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     Curve *derivative() const;
 253
 254     Curve *transformed(Matrix const &m) const;
 255
 256     std::vector<Point> pointAndDerivatives(Coord t, unsigned int n) const;
 257
 258     D2<SBasis> toSBasis() const;
 259
 260     /*
 261      * return true if the angle argument (in radiants) is contained
 262      * in the range [start_angle(), end_angle() ]
 263      */
 264     bool containsAngle(Coord angle) const;
 265
 266     /*
 267      * return the value of the d-dimensional coordinate related to "t"
 268      * here t belongs to the [0,2PI] domain
 269      */
 270     double valueAtAngle(Coord t, Dim2 d) const;
 271
 272     /*
 273      * return the point related to the parameter value "t"
 274      * here t belongs to the [0,2PI] domain
 275      */
 276     Point pointAtAngle(Coord t) const
 277     {
 278         double sin_rot_angle = std::sin(rotation_angle());
 279         double cos_rot_angle = std::cos(rotation_angle());
 280         Matrix m( ray(X) * cos_rot_angle, ray(X) * sin_rot_angle,
 281                  -ray(Y) * sin_rot_angle, ray(Y) * cos_rot_angle,
 282                   center(X),              center(Y) );
 283         Point p( std::cos(t), std::sin(t) );
 284         return p * m;
 285     }
 286
 287     /*
 288      * return the value of the d-dimensional coordinate related to "t"
 289      * here t belongs to the [0,1] domain
 290      */
 291     double valueAt(Coord t, Dim2 d) const
 292     {
 293         if (isDegenerate() && is_svg_compliant())
 294             return chord().valueAt(t, d);
 295
 296         Coord tt = map_to_02PI(t);
 297         return valueAtAngle(tt, d);
 298     }
 299
 300     /*
 301      * return the point related to the parameter value "t"
 302      * here t belongs to the [0,1] domain
 303      */
 304     Point pointAt(Coord t) const
 305     {
 306         if (isDegenerate() && is_svg_compliant())
 307             return chord().pointAt(t);
 308
 309         Coord tt = map_to_02PI(t);
 310         return pointAtAngle(tt);
 311     }
 312
 313     std::pair<SVGEllipticalArc, SVGEllipticalArc>
 314     subdivide(Coord t) const
 315     {
 316         SVGEllipticalArc* arc1 = static_cast<SVGEllipticalArc*>(portion(0, t));
 317         SVGEllipticalArc* arc2 = static_cast<SVGEllipticalArc*>(portion(t, 1));
 318         assert( arc1 != NULL && arc2 != NULL);
 319         std::pair<SVGEllipticalArc, SVGEllipticalArc> arc_pair(*arc1, *arc2);
 320         delete arc1;
 321         delete arc2;
 322         return arc_pair;
 323     }
 324
 325     Curve* portion(double f, double t) const;
 326
 327     // the arc is the same but traversed in the opposite direction
 328     Curve* reverse() const
 329     {
 330         SVGEllipticalArc* rarc = new SVGEllipticalArc( *this );
 331         rarc->m_sweep = !m_sweep;
 332         rarc->m_initial_point = m_final_point;
 333         rarc->m_final_point = m_initial_point;
 334         rarc->m_start_angle = m_end_angle;
 335         rarc->m_end_angle = m_start_angle;
 336         return rarc;
 337     }
 338
 339
 340     double sweep_angle() const
 341     {
 342         Coord d = end_angle() - start_angle();
 343         if ( !sweep_flag() ) d = -d;
 344         if ( d < 0 )
 345             d += 2*M_PI;
 346         return d;
 347     }
 348
 349     LineSegment chord() const
 350     {
 351         return LineSegment(initialPoint(), finalPoint());
 352     }
 353
 354   private:
 355     Coord map_to_02PI(Coord t) const;
 356     Coord map_to_01(Coord angle) const;
 357     void calculate_center_and_extreme_angles();
 358
 359   private:
 360     Point m_initial_point, m_final_point;
 361     double m_rx, m_ry, m_rot_angle;
 362     bool m_large_arc, m_sweep;
 363     bool m_svg_compliant;
 364     double m_start_angle, m_end_angle;
 365     Point m_center;
 366
 367 }; // end class SVGEllipticalArc
 368
 369
 370 /*
 371  * useful for testing and debugging
 372  */
 373 template< class charT >
 374 inline
 375 std::basic_ostream<charT> &
 376 operator<< (std::basic_ostream<charT> & os, const SVGEllipticalArc & ea)
 377 {
 378     os << "{ cx: " << ea.center(X) << ", cy: " <<  ea.center(Y)
 379        << ", rx: " << ea.ray(X) << ", ry: " << ea.ray(Y)
 380        << ", rot angle: " << decimal_round(rad_to_deg(ea.rotation_angle()),2)
 381        << ", start angle: " << decimal_round(rad_to_deg(ea.start_angle()),2)
 382        << ", end angle: " << decimal_round(rad_to_deg(ea.end_angle()),2)
 383        << " }";
 384
 385     return os;
 386 }
 387
 388
 389
 390
 391 // forward declation
 392 namespace detail
 393 {
 394     struct ellipse_equation;
 395 }
 396
 397 /*
 398  * make_elliptical_arc
 399  *
 400  * convert a parametric polynomial curve given in symmetric power basis form
 401  * into an SVGEllipticalArc type; in order to be successfull the input curve
 402  * has to look like an actual elliptical arc even if a certain tolerance
 403  * is allowed through an ad-hoc parameter.
 404  * The conversion is performed through an interpolation on a certain amount of
 405  * sample points computed on the input curve;
 406  * the interpolation computes the coefficients of the general implicit equation
 407  * of an ellipse (A*X^2 + B*XY + C*Y^2 + D*X + E*Y + F = 0), then from the
 408  * implicit equation we compute the parametric form.
 409  *
 410  */
 411 class make_elliptical_arc
 412 {
 413   public:
 414     typedef D2<SBasis> curve_type;
 415
 416     /*
 417      * constructor
 418      *
 419      * it doesn't execute the conversion but set the input and output parameters
 420      *
 421      * _ea:         the output SVGEllipticalArc that will be generated;
 422      * _curve:      the input curve to be converted;
 423      * _total_samples: the amount of sample points to be taken
 424      *                 on the input curve for performing the conversion
 425      * _tolerance:     how much likelihood is required between the input curve
 426      *                 and the generated elliptical arc; the smaller it is the
 427      *                 the tolerance the higher it is the likelihood.
 428      */
 429     make_elliptical_arc( SVGEllipticalArc& _ea,
 430                          curve_type const& _curve,
 431                          unsigned int _total_samples,
 432                          double _tolerance );
 433
 434   private:
 435     bool bound_exceeded( unsigned int k, detail::ellipse_equation const & ee,
 436                          double e1x, double e1y, double e2 );
 437
 438     bool check_bound(double A, double B, double C, double D, double E, double F);
 439
 440     void fit();
 441
 442     bool make_elliptiarc();
 443
 444     void print_bound_error(unsigned int k)
 445     {
 446         std::cerr
 447             << "tolerance error" << std::endl
 448             << "at point: " << k << std::endl
 449             << "error value: "<< dist_err << std::endl
 450             << "bound: " << dist_bound << std::endl
 451             << "angle error: " << angle_err
 452             << " (" << angle_tol << ")" << std::endl;
 453     }
 454
 455   public:
 456     /*
 457      * perform the actual conversion
 458      * return true if the conversion is successfull, false on the contrary
 459      */
 460     bool operator()()
 461     {
 462         // initialize the reference
 463         const NL::Vector & coeff = fitter.result();
 464         fit();
 465         if ( !check_bound(1, coeff[0], coeff[1], coeff[2], coeff[3], coeff[4]) )
 466             return false;
 467         if ( !(make_elliptiarc()) ) return false;
 468         return true;
 469     }
 470
 471     /*
 472      * you can set a boolean parameter to tell the conversion routine
 473      * if the output elliptical arc has to be svg compliant or not;
 474      * the default value is true
 475      */
 476     bool svg_compliant_flag() const
 477     {
 478         return svg_compliant;
 479     }
 480
 481     void svg_compliant_flag(bool _svg_compliant)
 482     {
 483         svg_compliant = _svg_compliant;
 484     }
 485
 486   private:
 487       SVGEllipticalArc& ea;                 // output elliptical arc
 488       const curve_type & curve;             // input curve
 489       Piecewise<D2<SBasis> > dcurve;        // derivative of the input curve
 490       NL::LFMEllipse model;                 // model used for fitting
 491       // perform the actual fitting task
 492       NL::least_squeares_fitter<NL::LFMEllipse> fitter;
 493       // tolerance: the user-defined tolerance parameter;
 494       // tol_at_extr: the tolerance at end-points automatically computed
 495       // on the value of "tolerance", and usually more strict;
 496       // tol_at_center: tolerance at the center of the ellipse
 497       // angle_tol: tolerance for the angle btw the input curve tangent
 498       // versor and the ellipse normal versor at the sample points
 499       double tolerance, tol_at_extr, tol_at_center, angle_tol;
 500       Point initial_point, final_point;     // initial and final end-points
 501       unsigned int N;                       // total samples
 502       unsigned int last; // N-1
 503       double partitions; // N-1
 504       std::vector<Point> p;                 // sample points
 505       double dist_err, dist_bound, angle_err;
 506       bool svg_compliant;
 507 };
 508
 509
 510 } // end namespace Geom
 511
 512
 513
 514
 515 #endif /* _2GEOM_SVG_ELLIPTICAL_ARC_H_ */
 516
 517 /*
 518   Local Variables:
 519   mode:c++
 520   c-file-style:"stroustrup"
 521   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 522   indent-tabs-mode:nil
 523   fill-column:99
 524   End:
 525 */
 526 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
 527