1 /* CPML - Cairo Path Manipulation Library
2 * Copyright (C) 2008,2009,2010 Nicola Fontana <ntd at entidi.it>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
25 * @short_description: Manipulation of circular arcs
27 * The following functions manipulate %CPML_ARC #CpmlPrimitive.
28 * No validation is made on the input so use the following methods
29 * only when you are sure the <varname>primitive</varname> argument
30 * is effectively an arc-to.
32 * The arc primitive is defined by 3 points: the first one is the usual
33 * implicit point got from the previous primitive, the second point is
34 * an arbitrary intermediate point laying on the arc and the third point
35 * is the end of the arc. These points identify univocally an arc:
36 * furthermore, the intermediate point also gives the side of
39 * As a special case, when the first point is coincident with the end
40 * point the primitive is considered a circle with diameter defined by
41 * the segment between the first and the intermediate point.
45 * An arc is not a native cairo primitive and should be treated specially.
49 * Using these CPML APIs you are free to use %CPML_ARC whenever
50 * you want but, if you are directly accessing the struct fields, you
51 * are responsible of converting arcs to curves before passing them
52 * to cairo. In other words, do not directly feed #CpmlPath struct to
53 * cairo (throught cairo_append_path() for example) or at least do not
54 * expect it will work.
56 * The conversion is provided by two APIs: cpml_arc_to_cairo() and
57 * cpml_arc_to_curves(). The former directly renders to a cairo context
58 * and is internally used by all the ..._to_cairo() functions when an
59 * arc is met. The latter provided a more powerful (and more complex)
60 * approach as it allows to specify the number of curves to use and do
61 * not need a cairo context.
66 * <listitem>the get_closest_pos() method must be implemented;</listitem>
67 * <listitem>the put_intersections() method must be implemented;</listitem>
73 #include "cpml-internal.h"
74 #include "cpml-extents.h"
75 #include "cpml-segment.h"
76 #include "cpml-primitive.h"
77 #include "cpml-primitive-private.h"
79 #include "cpml-curve.h"
83 /* Hardcoded max angle of the arc to be approximated by a Bézier curve:
84 * this influence the arc quality (the default value is got from cairo) */
85 #define ARC_MAX_ANGLE M_PI_2
87 /* Macro to save typing and make put_extents() code cleaner */
88 #define ANGLE_INCLUDED(d) \
89 ((start < (d) && end > (d)) || (start > (d) && end < (d)))
92 static double get_length (const CpmlPrimitive
*arc
);
93 static void put_extents (const CpmlPrimitive
*arc
,
94 CpmlExtents
*extents
);
95 static void put_pair_at (const CpmlPrimitive
*arc
,
98 static void put_vector_at (const CpmlPrimitive
*arc
,
101 static void offset (CpmlPrimitive
*arc
,
103 static cairo_bool_t
get_center (const CpmlPair
*p
,
105 static void get_angles (const CpmlPair
*p
,
106 const CpmlPair
*center
,
109 static void arc_to_curve (CpmlPrimitive
*curve
,
110 const CpmlPair
*center
,
116 const _CpmlPrimitiveClass
*
117 _cpml_arc_get_class(void)
119 static _CpmlPrimitiveClass
*p_class
= NULL
;
121 if (p_class
== NULL
) {
122 static _CpmlPrimitiveClass class_data
= {
133 p_class
= &class_data
;
142 * @arc: the #CpmlPrimitive arc data
143 * @center: where to store the center coordinates (can be %NULL)
144 * @r: where to store the radius (can be %NULL)
145 * @start: where to store the starting angle (can be %NULL)
146 * @end: where to store the ending angle (can be %NULL)
148 * Given an @arc, this function calculates and returns its basic data.
149 * Any pointer can be %NULL, in which case the requested info is not
150 * returned. This function can fail (when the three points lay on a
151 * straight line, for example) in which case 0 is returned and no
152 * data can be considered valid.
154 * The radius @r can be 0 when the three points are coincidents: a
155 * circle with radius 0 is considered a valid path.
157 * When the start and end angle are returned, together with their
158 * values these angles implicitely gives another important information:
161 * If @start < @end the arc must be rendered with increasing angle
162 * value (clockwise direction using the ordinary cairo coordinate
163 * system) while if @start > @end the arc must be rendered in reverse
164 * order (that is counterclockwise in the cairo world). This is the
165 * reason the angle values are returned in the range
166 * { -M_PI < value < 3*M_PI } inclusive instead of the usual
167 * { -M_PI < value < M_PI } range.
169 * Returns: 1 if the function worked succesfully, 0 on errors
172 cpml_arc_info(const CpmlPrimitive
*arc
, CpmlPair
*center
,
173 double *r
, double *start
, double *end
)
175 CpmlPair p
[3], l_center
;
177 cpml_pair_from_cairo(&p
[0], arc
->org
);
178 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
179 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
181 if (!get_center(p
, &l_center
))
188 *r
= cpml_pair_distance(&p
[0], &l_center
);
190 if (start
!= NULL
|| end
!= NULL
) {
191 double l_start
, l_end
;
193 get_angles(p
, &l_center
, &l_start
, &l_end
);
206 * @arc: the #CpmlPrimitive arc data
207 * @cr: the destination cairo context
209 * Renders @arc to the @cr cairo context. As cairo does not support
210 * arcs natively, it is approximated using one or more Bézier curves.
212 * The number of curves used is dependent from the angle of the arc.
213 * Anyway, this function uses internally the hardcoded %M_PI_2 value
214 * as threshold value. This means the maximum arc approximated by a
215 * single curve will be a quarter of a circle and, consequently, a
216 * whole circle will be approximated by 4 Bézier curves.
219 cpml_arc_to_cairo(const CpmlPrimitive
*arc
, cairo_t
*cr
)
222 double r
, start
, end
;
226 cairo_path_data_t data
[4];
228 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
231 n_curves
= ceil(fabs(end
-start
) / ARC_MAX_ANGLE
);
232 step
= (end
-start
) / (double) n_curves
;
235 for (angle
= start
; n_curves
--; angle
+= step
) {
236 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
238 curve
.data
[1].point
.x
, curve
.data
[1].point
.y
,
239 curve
.data
[2].point
.x
, curve
.data
[2].point
.y
,
240 curve
.data
[3].point
.x
, curve
.data
[3].point
.y
);
245 * cpml_arc_to_curves:
246 * @arc: the #CpmlPrimitive arc data
247 * @segment: the destination #CpmlSegment
248 * @n_curves: number of Bézier to use
250 * Converts @arc to a serie of @n_curves Bézier curves and puts them
251 * inside @segment. Obviously, @segment must have enough space to
252 * contain at least @n_curves curves.
254 * This function works in a similar way as cpml_arc_to_cairo() but
255 * has two important differences: it does not need a cairo context
256 * and the number of curves to be generated is explicitely defined.
257 * The latter difference allows a more specific error control from
258 * the application: in the file src/cairo-arc.c, found in the cairo
259 * tarball (at least in cairo-1.9.1), there is a table showing the
260 * magnitude of error of this curve approximation algorithm.
263 cpml_arc_to_curves(const CpmlPrimitive
*arc
, CpmlSegment
*segment
,
267 double r
, start
, end
;
271 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
274 step
= (end
-start
) / (double) n_curves
;
275 segment
->num_data
= n_curves
*4;
276 curve
.segment
= segment
;
277 curve
.data
= segment
->data
;
279 for (angle
= start
; n_curves
--; angle
+= step
) {
280 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
287 get_length(const CpmlPrimitive
*arc
)
289 double r
, start
, end
, delta
;
291 if (!cpml_arc_info(arc
, NULL
, &r
, &start
, &end
) || start
== end
)
302 put_extents(const CpmlPrimitive
*arc
, CpmlExtents
*extents
)
304 double r
, start
, end
;
305 CpmlPair center
, pair
;
307 extents
->is_defined
= 0;
309 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
312 /* Add the right quadrant point if needed */
313 if (ANGLE_INCLUDED(0) || ANGLE_INCLUDED(M_PI
* 2)) {
314 pair
.x
= center
.x
+ r
;
316 cpml_extents_pair_add(extents
, &pair
);
319 /* Add the bottom quadrant point if needed */
320 if (ANGLE_INCLUDED(M_PI_2
) || ANGLE_INCLUDED(M_PI_2
* 5)) {
322 pair
.y
= center
.y
+ r
;
323 cpml_extents_pair_add(extents
, &pair
);
326 /* Add the left quadrant point if needed */
327 if (ANGLE_INCLUDED(M_PI
)) {
328 pair
.x
= center
.x
- r
;
330 cpml_extents_pair_add(extents
, &pair
);
333 /* Add the top quadrant point if needed */
334 if (ANGLE_INCLUDED(M_PI_2
* 3) || ANGLE_INCLUDED(-M_PI_2
)) {
336 pair
.y
= center
.y
- r
;
337 cpml_extents_pair_add(extents
, &pair
);
340 /* Add the start point */
341 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, 0));
342 cpml_extents_pair_add(extents
, &pair
);
344 /* Add the end point */
345 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, -1));
346 cpml_extents_pair_add(extents
, &pair
);
350 put_pair_at(const CpmlPrimitive
*arc
, double pos
, CpmlPair
*pair
)
353 cpml_pair_from_cairo(pair
, arc
->org
);
354 } else if (pos
== 1.) {
355 cpml_pair_from_cairo(pair
, &arc
->data
[2]);
358 double r
, start
, end
, angle
;
360 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
363 angle
= (end
-start
)*pos
+ start
;
364 cpml_vector_from_angle(pair
, angle
);
365 cpml_vector_set_length(pair
, r
);
373 put_vector_at(const CpmlPrimitive
*arc
, double pos
, CpmlVector
*vector
)
375 double start
, end
, angle
;
377 if (!cpml_arc_info(arc
, NULL
, NULL
, &start
, &end
))
380 angle
= (end
-start
)*pos
+ start
;
381 cpml_vector_from_angle(vector
, angle
);
382 cpml_vector_normal(vector
);
385 vector
->x
= -vector
->x
;
386 vector
->y
= -vector
->y
;
391 offset(CpmlPrimitive
*arc
, double offset
)
393 CpmlPair p
[3], center
;
396 cpml_pair_from_cairo(&p
[0], arc
->org
);
397 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
398 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
400 if (!get_center(p
, ¢er
))
403 r
= cpml_pair_distance(&p
[0], ¢er
) + offset
;
405 /* Offset the three points by calculating their vector from the center,
406 * setting the new radius as length and readding the center */
414 cpml_vector_set_length(&p
[0], r
);
415 cpml_vector_set_length(&p
[1], r
);
416 cpml_vector_set_length(&p
[2], r
);
425 cpml_pair_to_cairo(&p
[0], arc
->org
);
426 cpml_pair_to_cairo(&p
[1], &arc
->data
[1]);
427 cpml_pair_to_cairo(&p
[2], &arc
->data
[2]);
431 get_center(const CpmlPair
*p
, CpmlPair
*dest
)
436 /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
437 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
438 dest
->x
= (p
[0].x
+ p
[1].x
) / 2;
439 dest
->y
= (p
[0].y
+ p
[1].y
) / 2;
443 /* Translate the 3 points of -p0, to simplify the formula */
444 b
.x
= p
[1].x
- p
[0].x
;
445 b
.y
= p
[1].y
- p
[0].y
;
446 c
.x
= p
[2].x
- p
[0].x
;
447 c
.y
= p
[2].y
- p
[0].y
;
449 /* Check for division by 0, that is the case where the 3 given points
450 * are laying on a straight line and there is no fitting circle */
451 d
= (b
.x
*c
.y
- b
.y
*c
.x
) * 2;
455 b2
= b
.x
*b
.x
+ b
.y
*b
.y
;
456 c2
= c
.x
*c
.x
+ c
.y
*c
.y
;
458 dest
->x
= (c
.y
*b2
- b
.y
*c2
) / d
+ p
[0].x
;
459 dest
->y
= (b
.x
*c2
- c
.x
*b2
) / d
+ p
[0].y
;
465 get_angles(const CpmlPair
*p
, const CpmlPair
*center
,
466 double *start
, double *end
)
471 /* Calculate the starting angle */
472 vector
.x
= p
[0].x
- center
->x
;
473 vector
.y
= p
[0].y
- center
->y
;
474 *start
= cpml_vector_angle(&vector
);
476 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
477 /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
478 * of a circle: return by convention start=start end=start+2PI */
479 *end
= *start
+ M_PI
*2;
481 /* Calculate the mid and end angle: cpml_vector_angle()
482 * returns an angle between -M_PI and M_PI */
483 vector
.x
= p
[1].x
- center
->x
;
484 vector
.y
= p
[1].y
- center
->y
;
485 mid
= cpml_vector_angle(&vector
);
486 vector
.x
= p
[2].x
- center
->x
;
487 vector
.y
= p
[2].y
- center
->y
;
488 *end
= cpml_vector_angle(&vector
);
491 /* If the middle angle is outside the start..end range,
492 * the arc should be reversed (that is, start must
493 * be greather than end) */
494 if (mid
< *start
|| mid
> *end
)
497 /* Here the arc is reversed: if the middle angle is
498 * outside the end..start range, the arc should be
499 * re-reversed to get a straight arc (that is, end
500 * must be greather than start) */
501 if (mid
< *end
|| mid
> *start
)
508 arc_to_curve(CpmlPrimitive
*curve
, const CpmlPair
*center
,
509 double r
, double start
, double end
)
511 double r_sin1
, r_cos1
;
512 double r_sin2
, r_cos2
;
515 r_sin1
= r
*sin(start
);
516 r_cos1
= r
*cos(start
);
520 h
= 4./3. * tan((end
-start
) / 4.);
522 curve
->data
[0].header
.type
= CPML_CURVE
;
523 curve
->data
[0].header
.length
= 4;
524 curve
->data
[1].point
.x
= center
->x
+ r_cos1
- h
*r_sin1
;
525 curve
->data
[1].point
.y
= center
->y
+ r_sin1
+ h
*r_cos1
;
526 curve
->data
[2].point
.x
= center
->x
+ r_cos2
+ h
*r_sin2
;
527 curve
->data
[2].point
.y
= center
->y
+ r_sin2
- h
*r_cos2
;
528 curve
->data
[3].point
.x
= center
->x
+ r_cos2
;
529 curve
->data
[3].point
.y
= center
->y
+ r_sin2
;