5c42e6e1d1e57fecb3e88590b77a7850e20378b6
1 /*
2 * Elliptical Arc - implementation of the svg elliptical arc path element
3 *
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 * Marco Cecchetti <mrcekets at gmail.com>
7 *
8 * Copyright 2007-2008 authors
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it either under the terms of the GNU Lesser General Public
12 * License version 2.1 as published by the Free Software Foundation
13 * (the "LGPL") or, at your option, under the terms of the Mozilla
14 * Public License Version 1.1 (the "MPL"). If you do not alter this
15 * notice, a recipient may use your version of this file under either
16 * the MPL or the LGPL.
17 *
18 * You should have received a copy of the LGPL along with this library
19 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 * You should have received a copy of the MPL along with this library
22 * in the file COPYING-MPL-1.1
23 *
24 * The contents of this file are subject to the Mozilla Public License
25 * Version 1.1 (the "License"); you may not use this file except in
26 * compliance with the License. You may obtain a copy of the License at
27 * http://www.mozilla.org/MPL/
28 *
29 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
31 * the specific language governing rights and limitations.
32 */
35 #ifndef _2GEOM_SVG_ELLIPTICAL_ARC_H_
36 #define _2GEOM_SVG_ELLIPTICAL_ARC_H_
39 #include <2geom/curve.h>
40 #include <2geom/angle.h>
41 #include <2geom/utils.h>
42 #include <2geom/bezier-curve.h>
43 #include <2geom/sbasis-curve.h> // for non-native methods
44 #include <2geom/numeric/vector.h>
45 #include <2geom/numeric/fitting-tool.h>
46 #include <2geom/numeric/fitting-model.h>
49 #include <algorithm>
53 namespace Geom
54 {
56 class SVGEllipticalArc : public Curve
57 {
58 public:
59 SVGEllipticalArc(bool _svg_compliant = true)
60 : m_initial_point(Point(0,0)), m_final_point(Point(0,0)),
61 m_rx(0), m_ry(0), m_rot_angle(0),
62 m_large_arc(true), m_sweep(true),
63 m_svg_compliant(_svg_compliant),
64 m_start_angle(0), m_end_angle(0),
65 m_center(Point(0,0))
66 {
67 }
69 /*
70 * constructor
71 *
72 * input parameters:
73 * _initial_point: initial arc end point;
74 * _rx: ellipse x-axis ray length
75 * _ry: ellipse y-axis ray length
76 * _rot_angle: ellipse x-axis rotation angle;
77 * _large_arc: if true the largest arc is chosen,
78 * if false the smallest arc is chosen;
79 * _sweep : if true the clockwise arc is chosen,
80 * if false the counter-clockwise arc is chosen;
81 * _final_point: final arc end point;
82 * _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 Rect boundsFast() const
204 {
205 return boundsExact();
206 }
208 Rect boundsExact() const;
210 // TODO: native implementation of the following methods
211 Rect boundsLocal(Interval 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 Curve *derivative() const;
254 Curve *transformed(Matrix const &m) const;
256 std::vector<Point> pointAndDerivatives(Coord t, unsigned int n) const;
258 D2<SBasis> toSBasis() const;
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;
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;
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 }
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);
296 Coord tt = map_to_02PI(t);
297 return valueAtAngle(tt, d);
298 }
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);
309 Coord tt = map_to_02PI(t);
310 return pointAtAngle(tt);
311 }
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 }
325 Curve* portion(double f, double t) const;
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 }
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 }
349 LineSegment chord() const
350 {
351 return LineSegment(initialPoint(), finalPoint());
352 }
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();
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;
367 }; // end class SVGEllipticalArc
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 << " }";
385 return os;
386 }
391 // forward declation
392 namespace detail
393 {
394 struct ellipse_equation;
395 }
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;
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 );
434 private:
435 bool bound_exceeded( unsigned int k, detail::ellipse_equation const & ee,
436 double e1x, double e1y, double e2 );
438 bool check_bound(double A, double B, double C, double D, double E, double F);
440 void fit();
442 bool make_elliptiarc();
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 }
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 }
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 }
481 void svg_compliant_flag(bool _svg_compliant)
482 {
483 svg_compliant = _svg_compliant;
484 }
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 };
510 } // end namespace Geom
515 #endif /* _2GEOM_SVG_ELLIPTICAL_ARC_H_ */
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 :