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 */
36 #ifndef _2GEOM_SVG_ELLIPTICAL_ARC_H_
37 #define _2GEOM_SVG_ELLIPTICAL_ARC_H_
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>
50 #include <algorithm>
54 namespace Geom
55 {
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 }
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 }
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 }
119 Curve* duplicate() const
120 {
121 return new SVGEllipticalArc(*this);
122 }
124 double center(unsigned int i) const
125 {
126 return m_center[i];
127 }
129 Point center() const
130 {
131 return m_center;
132 }
134 Point initialPoint() const
135 {
136 return m_initial_point;
137 }
139 Point finalPoint() const
140 {
141 return m_final_point;
142 }
144 double start_angle() const
145 {
146 return m_start_angle;
147 }
149 double end_angle() const
150 {
151 return m_end_angle;
152 }
154 double ray(unsigned int i) const
155 {
156 return (i == 0) ? m_rx : m_ry;
157 }
159 bool large_arc_flag() const
160 {
161 return m_large_arc;
162 }
164 bool sweep_flag() const
165 {
166 return m_sweep;
167 }
169 double rotation_angle() const
170 {
171 return m_rot_angle;
172 }
174 void setInitial( const Point _point)
175 {
176 m_initial_point = _point;
177 calculate_center_and_extreme_angles();
178 }
180 void setFinal( const Point _point)
181 {
182 m_final_point = _point;
183 calculate_center_and_extreme_angles();
184 }
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 }
193 bool isDegenerate() const
194 {
195 return ( are_near(ray(X), 0) || are_near(ray(Y), 0) );
196 }
198 bool is_svg_compliant() const
199 {
200 return m_svg_compliant;
201 }
203 virtual OptRect boundsFast() const
204 {
205 return boundsExact();
206 }
208 virtual OptRect boundsExact() const;
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 }
219 std::vector<double> roots(double v, Dim2 d) const;
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;
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 }
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 }
252 int degreesOfFreedom() const { return 5;}
254 Curve *derivative() const;
256 Curve *transformed(Matrix const &m) const;
258 std::vector<Point> pointAndDerivatives(Coord t, unsigned int n) const;
260 D2<SBasis> toSBasis() const;
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;
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;
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 }
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);
298 Coord tt = map_to_02PI(t);
299 return valueAtAngle(tt, d);
300 }
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);
311 Coord tt = map_to_02PI(t);
312 return pointAtAngle(tt);
313 }
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 }
327 Curve* portion(double f, double t) const;
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 }
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 }
351 LineSegment chord() const
352 {
353 return LineSegment(initialPoint(), finalPoint());
354 }
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();
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;
369 }; // end class SVGEllipticalArc
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 << " }";
387 return os;
388 }
393 // forward declation
394 namespace detail
395 {
396 struct ellipse_equation;
397 }
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;
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 );
436 private:
437 bool bound_exceeded( unsigned int k, detail::ellipse_equation const & ee,
438 double e1x, double e1y, double e2 );
440 bool check_bound(double A, double B, double C, double D, double E, double F);
442 void fit();
444 bool make_elliptiarc();
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 }
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 }
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 }
483 void svg_compliant_flag(bool _svg_compliant)
484 {
485 svg_compliant = _svg_compliant;
486 }
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 };
512 } // end namespace Geom
517 #endif /* _2GEOM_SVG_ELLIPTICAL_ARC_H_ */
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 :