1 /* CPML - Cairo Path Manipulation Library
2 * Copyright (C) 2008, 2009 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 #CAIRO_PATH_ARC_TO #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 #CAIRO_PATH_ARC_TO 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 #include "cpml-pair.h"
72 /* Hardcoded max angle of the arc to be approximated by a Bézier curve:
73 * this influence the arc quality (the default value is got from cairo) */
74 #define ARC_MAX_ANGLE M_PI_2
77 static cairo_bool_t
get_center (const CpmlPair
*p
,
79 static void get_angles (const CpmlPair
*p
,
80 const CpmlPair
*center
,
83 static void arc_to_curve (CpmlPrimitive
*curve
,
84 const CpmlPair
*center
,
91 * cpml_arc_type_get_npoints:
93 * Returns the number of point needed to properly specify an arc primitive.
98 cpml_arc_type_get_npoints(void)
105 * @arc: the #CpmlPrimitive arc data
106 * @center: where to store the center coordinates (can be %NULL)
107 * @r: where to store the radius (can be %NULL)
108 * @start: where to store the starting angle (can be %NULL)
109 * @end: where to store the ending angle (can be %NULL)
111 * Given an @arc, this function calculates and returns its basic data.
112 * Any pointer can be %NULL, in which case the requested info is not
113 * returned. This function can fail (when the three points lay on a
114 * straight line, for example) in which case 0 is returned and no
115 * data can be considered valid.
117 * The radius @r can be 0 when the three points are coincidents: a
118 * circle with radius 0 is considered a valid path.
120 * When the start and end angle are returned, together with their
121 * values these angles implicitely gives another important information:
124 * If @start < @end the arc must be rendered with increasing angle
125 * value (clockwise direction using the ordinary cairo coordinate
126 * system) while if @start > @end the arc must be rendered in reverse
127 * order (that is counterclockwise in the cairo world). This is the
128 * reason the angle values are returned in the range
129 * { -M_PI < value < 3*M_PI } inclusive instead of the usual
130 * { -M_PI < value < M_PI } range.
132 * Return value: 1 if the function worked succesfully, 0 on errors
135 cpml_arc_info(const CpmlPrimitive
*arc
, CpmlPair
*center
,
136 double *r
, double *start
, double *end
)
138 CpmlPair p
[3], l_center
;
140 cpml_pair_from_cairo(&p
[0], arc
->org
);
141 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
142 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
144 if (!get_center(p
, &l_center
))
151 *r
= cpml_pair_distance(&p
[0], &l_center
);
153 if (start
!= NULL
|| end
!= NULL
) {
154 double l_start
, l_end
;
156 get_angles(p
, &l_center
, &l_start
, &l_end
);
169 * @arc: the #CpmlPrimitive arc data
171 * Given the @arc primitive, returns its length.
173 * Return value: the requested length or 0 on errors
176 cpml_arc_length(const CpmlPrimitive
*arc
)
178 double r
, start
, end
, delta
;
180 if (!cpml_arc_info(arc
, NULL
, &r
, &start
, &end
) || start
== end
)
190 /* Hardcoded macro to save a lot of typing and make the
191 * cpml_arc_extents() code clearer */
192 #define ANGLE_INCLUDED(d) \
193 ((start < (d) && end > (d)) || (start > (d) && end < (d)))
197 * @arc: the #CpmlPrimitive arc data
198 * @extents: where to store the extents
200 * Given an @arc primitive, returns its boundary box in @extents.
203 cpml_arc_extents(const CpmlPrimitive
*arc
, CpmlExtents
*extents
)
205 double r
, start
, end
;
206 CpmlPair center
, pair
;
208 extents
->is_defined
= 0;
210 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
213 /* Add the right quadrant point if needed */
214 if (ANGLE_INCLUDED(0) || ANGLE_INCLUDED(M_PI
* 2)) {
215 pair
.x
= center
.x
+ r
;
217 cpml_extents_pair_add(extents
, &pair
);
220 /* Add the bottom quadrant point if needed */
221 if (ANGLE_INCLUDED(M_PI_2
) || ANGLE_INCLUDED(M_PI_2
* 5)) {
223 pair
.y
= center
.y
+ r
;
224 cpml_extents_pair_add(extents
, &pair
);
227 /* Add the left quadrant point if needed */
228 if (ANGLE_INCLUDED(M_PI
)) {
229 pair
.x
= center
.x
- r
;
231 cpml_extents_pair_add(extents
, &pair
);
234 /* Add the top quadrant point if needed */
235 if (ANGLE_INCLUDED(M_PI_2
* 3) || ANGLE_INCLUDED(-M_PI_2
)) {
237 pair
.y
= center
.y
- r
;
238 cpml_extents_pair_add(extents
, &pair
);
241 /* Add the start point */
242 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, 0));
243 cpml_extents_pair_add(extents
, &pair
);
245 /* Add the end point */
246 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, -1));
247 cpml_extents_pair_add(extents
, &pair
);
252 * @arc: the #CpmlPrimitive arc data
253 * @pair: the destination #CpmlPair
254 * @pos: the position value
256 * Given an @arc, finds the coordinates at position @pos (where 0 is
257 * the start and 1 is the end) and stores the result in @pair.
259 * @pos can also be outside the 0..1 limit, as interpolating on an
260 * arc is quite trivial.
263 cpml_arc_pair_at(const CpmlPrimitive
*arc
, CpmlPair
*pair
, double pos
)
266 cpml_pair_from_cairo(pair
, arc
->org
);
267 } else if (pos
== 1.) {
268 cpml_pair_from_cairo(pair
, &arc
->data
[2]);
271 double r
, start
, end
, angle
;
273 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
276 angle
= (end
-start
)*pos
+ start
;
277 cpml_vector_from_angle(pair
, angle
);
278 cpml_vector_set_length(pair
, r
);
279 cpml_pair_add(pair
, ¢er
);
284 * cpml_arc_vector_at:
285 * @arc: the #CpmlPrimitive arc data
286 * @vector: the destination vector
287 * @pos: the position value
289 * Given an @arc, finds the slope at position @pos (where 0 is
290 * the start and 1 is the end) and stores the result in @vector.
292 * @pos can also be outside the 0..1 limit, as interpolating on an
293 * arc is quite trivial.
296 cpml_arc_vector_at(const CpmlPrimitive
*arc
, CpmlVector
*vector
, double pos
)
298 double start
, end
, angle
;
300 if (!cpml_arc_info(arc
, NULL
, NULL
, &start
, &end
))
303 angle
= (end
-start
)*pos
+ start
;
304 cpml_vector_from_angle(vector
, angle
);
305 cpml_vector_normal(vector
);
308 cpml_pair_negate(vector
);
313 * @arc: the #CpmlPrimitive arc data
314 * @pair: the coordinates of the subject point
316 * Returns the pos value of the point on @arc nearest to @pair.
317 * The returned value is always between 0 and 1.
320 * <title>TODO</title>
322 * <listitem>To be implemented...</listitem>
326 * Return value: the pos value, always between 0 and 1
329 cpml_arc_near_pos(const CpmlPrimitive
*arc
, const CpmlPair
*pair
)
337 * cpml_arc_intersection:
338 * @arc: the first arc
339 * @arc2: the second arc
340 * @dest: a vector of #CpmlPair
341 * @max: maximum number of intersections to return
342 * (that is, the size of @dest)
344 * Given two arcs (@arc and @arc2), gets their intersection points
345 * and store the result in @dest. Keep in mind two arcs can have
346 * up to 2 intersections.
348 * If @max is 0, the function returns 0 immediately without any
349 * further processing. If @arc and @arc2 are cohincident (same
350 * center and same radius), their intersections are not considered.
353 * <title>TODO</title>
355 * <listitem>To be implemented...</listitem>
359 * Return value: the number of intersections found (max 2)
360 * or 0 if the primitives do not intersect
363 cpml_arc_intersection(const CpmlPrimitive
*arc
, const CpmlPrimitive
*arc2
,
364 CpmlPair
*dest
, int max
)
370 * cpml_arc_intersection_with_line:
373 * @dest: a vector of #CpmlPair
374 * @max: maximum number of intersections to return
375 * (that is, the size of @dest)
377 * Given an @arc and a @line, gets their intersection points
378 * and store the result in @dest. Keep in mind an arc and a
379 * line can have up to 2 intersections.
381 * If @max is 0, the function returns 0 immediately without any
382 * further processing.
385 * <title>TODO</title>
387 * <listitem>To be implemented...</listitem>
391 * Return value: the number of intersections found (max 2)
392 * or 0 if the primitives do not intersect
395 cpml_arc_intersection_with_line(const CpmlPrimitive
*arc
,
396 const CpmlPrimitive
*line
,
397 CpmlPair
*dest
, int max
)
404 * @arc: the #CpmlPrimitive arc data
405 * @offset: distance for the computed parallel arc
407 * Given an @arc, this function computes the parallel arc at
408 * distance @offset. The three points needed to build the
409 * new arc are returned in the @arc data (substituting the
413 cpml_arc_offset(CpmlPrimitive
*arc
, double offset
)
415 CpmlPair p
[3], center
;
418 cpml_pair_from_cairo(&p
[0], arc
->org
);
419 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
420 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
422 if (!get_center(p
, ¢er
))
425 r
= cpml_pair_distance(&p
[0], ¢er
) + offset
;
427 /* Offset the three points by calculating their vector from the center,
428 * setting the new radius as length and readding the center */
429 cpml_pair_sub(&p
[0], ¢er
);
430 cpml_pair_sub(&p
[1], ¢er
);
431 cpml_pair_sub(&p
[2], ¢er
);
433 cpml_vector_set_length(&p
[0], r
);
434 cpml_vector_set_length(&p
[1], r
);
435 cpml_vector_set_length(&p
[2], r
);
437 cpml_pair_add(&p
[0], ¢er
);
438 cpml_pair_add(&p
[1], ¢er
);
439 cpml_pair_add(&p
[2], ¢er
);
441 cpml_pair_to_cairo(&p
[0], arc
->org
);
442 cpml_pair_to_cairo(&p
[1], &arc
->data
[1]);
443 cpml_pair_to_cairo(&p
[2], &arc
->data
[2]);
448 * @arc: the #CpmlPrimitive arc data
449 * @cr: the destination cairo context
451 * Renders @arc to the @cr cairo context. As cairo does not support
452 * arcs natively, it is approximated using one or more Bézier curves.
454 * The number of curves used is dependent from the angle of the arc.
455 * Anyway, this function uses internally the hardcoded %M_PI_2 value
456 * as threshold value. This means the maximum arc approximated by a
457 * single curve will be a quarter of a circle and, consequently, a
458 * whole circle will be approximated by 4 Bézier curves.
461 cpml_arc_to_cairo(const CpmlPrimitive
*arc
, cairo_t
*cr
)
464 double r
, start
, end
;
468 cairo_path_data_t data
[4];
470 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
473 n_curves
= ceil(fabs(end
-start
) / ARC_MAX_ANGLE
);
474 step
= (end
-start
) / (double) n_curves
;
477 for (angle
= start
; n_curves
--; angle
+= step
) {
478 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
480 curve
.data
[1].point
.x
, curve
.data
[1].point
.y
,
481 curve
.data
[2].point
.x
, curve
.data
[2].point
.y
,
482 curve
.data
[3].point
.x
, curve
.data
[3].point
.y
);
487 * cpml_arc_to_curves:
488 * @arc: the #CpmlPrimitive arc data
489 * @segment: the destination #CpmlSegment
490 * @n_curves: number of Bézier to use
492 * Converts @arc to a serie of @n_curves Bézier curves and puts them
493 * inside @segment. Obviously, @segment must have enough space to
494 * contain at least @n_curves curves.
496 * This function works in a similar way as cpml_arc_to_cairo() but
497 * has two important differences: it does not need a cairo context
498 * and the number of curves to be generated is explicitely defined.
499 * The latter difference allows a more specific error control from
500 * the application: in the file src/cairo-arc.c, found in the cairo
501 * tarball (at least in cairo-1.9.1), there is a table showing the
502 * magnitude of error of this curve approximation algorithm.
505 cpml_arc_to_curves(const CpmlPrimitive
*arc
, CpmlSegment
*segment
,
509 double r
, start
, end
;
513 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
516 step
= (end
-start
) / (double) n_curves
;
517 segment
->num_data
= n_curves
*4;
518 curve
.segment
= segment
;
519 curve
.data
= segment
->data
;
521 for (angle
= start
; n_curves
--; angle
+= step
) {
522 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
529 get_center(const CpmlPair
*p
, CpmlPair
*dest
)
534 /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
535 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
536 dest
->x
= (p
[0].x
+ p
[1].x
) / 2;
537 dest
->y
= (p
[0].y
+ p
[1].y
) / 2;
541 /* Translate the 3 points of -p0, to simplify the formula */
542 cpml_pair_sub(cpml_pair_copy(&b
, &p
[1]), &p
[0]);
543 cpml_pair_sub(cpml_pair_copy(&c
, &p
[2]), &p
[0]);
545 /* Check for division by 0, that is the case where the 3 given points
546 * are laying on a straight line and there is no fitting circle */
547 d
= (b
.x
*c
.y
- b
.y
*c
.x
) * 2;
551 b2
= b
.x
*b
.x
+ b
.y
*b
.y
;
552 c2
= c
.x
*c
.x
+ c
.y
*c
.y
;
554 dest
->x
= (c
.y
*b2
- b
.y
*c2
) / d
+ p
[0].x
;
555 dest
->y
= (b
.x
*c2
- c
.x
*b2
) / d
+ p
[0].y
;
561 get_angles(const CpmlPair
*p
, const CpmlPair
*center
,
562 double *start
, double *end
)
567 /* Calculate the starting angle */
568 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[0]), center
);
569 *start
= cpml_vector_angle(&vector
);
571 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
572 /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
573 * of a circle: return by convention start=start end=start+2PI */
574 *end
= *start
+ M_PI
*2;
576 /* Calculate the mid and end angle: cpml_vector_angle()
577 * returns an angle between -M_PI and M_PI */
578 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[1]), center
);
579 mid
= cpml_vector_angle(&vector
);
580 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[2]), center
);
581 *end
= cpml_vector_angle(&vector
);
584 /* If the middle angle is outside the start..end range,
585 * the arc should be reversed (that is, start must
586 * be greather than end) */
587 if (mid
< *start
|| mid
> *end
)
590 /* Here the arc is reversed: if the middle angle is
591 * outside the end..start range, the arc should be
592 * re-reversed to get a straight arc (that is, end
593 * must be greather than start) */
594 if (mid
< *end
|| mid
> *start
)
601 arc_to_curve(CpmlPrimitive
*curve
, const CpmlPair
*center
,
602 double r
, double start
, double end
)
604 double r_sin1
, r_cos1
;
605 double r_sin2
, r_cos2
;
608 r_sin1
= r
*sin(start
);
609 r_cos1
= r
*cos(start
);
613 h
= 4./3. * tan((end
-start
) / 4.);
615 curve
->data
[0].header
.type
= CAIRO_PATH_CURVE_TO
;
616 curve
->data
[0].header
.length
= 4;
617 curve
->data
[1].point
.x
= center
->x
+ r_cos1
- h
*r_sin1
;
618 curve
->data
[1].point
.y
= center
->y
+ r_sin1
+ h
*r_cos1
;
619 curve
->data
[2].point
.x
= center
->x
+ r_cos2
+ h
*r_sin2
;
620 curve
->data
[2].point
.y
= center
->y
+ r_sin2
- h
*r_cos2
;
621 curve
->data
[3].point
.x
= center
->x
+ r_cos2
;
622 curve
->data
[3].point
.y
= center
->y
+ r_sin2
;