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
)
192 * @arc: the #CpmlPrimitive arc data
193 * @extents: where to store the extents
195 * Given an @arc primitive, returns its boundary box in @extents.
198 cpml_arc_extents(const CpmlPrimitive
*arc
, CpmlExtents
*extents
)
200 double r
, start
, end
;
201 CpmlPair center
, pair
;
203 extents
->is_defined
= 0;
205 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
208 /* Add the right quadrant point if needed */
209 if ((start
< 0 && end
> 0) ||
210 (end
< M_PI
* 2 && start
> M_PI
* 2)) {
211 pair
.x
= center
.x
+ r
;
213 cpml_extents_pair_add(extents
, &pair
);
216 /* Add the bottom quadrant point if needed */
217 if ((start
< M_PI_2
&& end
> M_PI_2
) ||
218 (end
< M_PI_2
* 5 && start
> M_PI_2
* 5)) {
220 pair
.y
= center
.y
+ r
;
221 cpml_extents_pair_add(extents
, &pair
);
224 /* Add the left quadrant point if needed */
225 if (start
< M_PI
&& end
> M_PI
) {
226 pair
.x
= center
.x
- r
;
228 cpml_extents_pair_add(extents
, &pair
);
231 /* Add the top quadrant point if needed */
232 if (start
< M_PI_2
* 3 && end
> M_PI
) {
234 pair
.y
= center
.y
- r
;
235 cpml_extents_pair_add(extents
, &pair
);
238 /* Add the start point */
239 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, 0));
240 cpml_extents_pair_add(extents
, &pair
);
242 /* Add the end point */
243 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, -1));
244 cpml_extents_pair_add(extents
, &pair
);
249 * @arc: the #CpmlPrimitive arc data
250 * @pair: the destination #CpmlPair
251 * @pos: the position value
253 * Given an @arc, finds the coordinates at position @pos (where 0 is
254 * the start and 1 is the end) and stores the result in @pair.
256 * @pos can also be outside the 0..1 limit, as interpolating on an
257 * arc is quite trivial.
260 cpml_arc_pair_at(const CpmlPrimitive
*arc
, CpmlPair
*pair
, double pos
)
263 cpml_pair_from_cairo(pair
, arc
->org
);
264 } else if (pos
== 1.) {
265 cpml_pair_from_cairo(pair
, &arc
->data
[2]);
268 double r
, start
, end
, angle
;
270 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
273 angle
= (end
-start
)*pos
+ start
;
274 cpml_vector_from_angle(pair
, angle
);
275 cpml_vector_set_length(pair
, r
);
276 cpml_pair_add(pair
, ¢er
);
281 * cpml_arc_vector_at:
282 * @arc: the #CpmlPrimitive arc data
283 * @vector: the destination vector
284 * @pos: the position value
286 * Given an @arc, finds the slope at position @pos (where 0 is
287 * the start and 1 is the end) and stores the result in @vector.
289 * @pos can also be outside the 0..1 limit, as interpolating on an
290 * arc is quite trivial.
293 cpml_arc_vector_at(const CpmlPrimitive
*arc
, CpmlVector
*vector
, double pos
)
295 double start
, end
, angle
;
297 if (!cpml_arc_info(arc
, NULL
, NULL
, &start
, &end
))
300 angle
= (end
-start
)*pos
+ start
;
301 cpml_vector_from_angle(vector
, angle
);
302 cpml_vector_normal(vector
);
305 cpml_pair_negate(vector
);
310 * @arc: the #CpmlPrimitive arc data
311 * @pair: the coordinates of the subject point
313 * Returns the pos value of the point on @arc nearest to @pair.
314 * The returned value is always between 0 and 1.
317 * <title>TODO</title>
319 * <listitem>To be implemented...</listitem>
323 * Return value: the pos value, always between 0 and 1
326 cpml_arc_near_pos(const CpmlPrimitive
*arc
, const CpmlPair
*pair
)
334 * cpml_arc_intersection:
335 * @arc: the first arc
336 * @arc2: the second arc
337 * @dest: a vector of #CpmlPair
338 * @max: maximum number of intersections to return
339 * (that is, the size of @dest)
341 * Given two arcs (@arc and @arc2), gets their intersection points
342 * and store the result in @dest. Keep in mind two arcs can have
343 * up to 2 intersections.
345 * If @max is 0, the function returns 0 immediately without any
346 * further processing. If @arc and @arc2 are cohincident (same
347 * center and same radius), their intersections are not considered.
350 * <title>TODO</title>
352 * <listitem>To be implemented...</listitem>
356 * Return value: the number of intersections found (max 2)
357 * or 0 if the primitives do not intersect
360 cpml_arc_intersection(const CpmlPrimitive
*arc
, const CpmlPrimitive
*arc2
,
361 CpmlPair
*dest
, int max
)
367 * cpml_arc_intersection_with_line:
370 * @dest: a vector of #CpmlPair
371 * @max: maximum number of intersections to return
372 * (that is, the size of @dest)
374 * Given an @arc and a @line, gets their intersection points
375 * and store the result in @dest. Keep in mind an arc and a
376 * line can have up to 2 intersections.
378 * If @max is 0, the function returns 0 immediately without any
379 * further processing.
382 * <title>TODO</title>
384 * <listitem>To be implemented...</listitem>
388 * Return value: the number of intersections found (max 2)
389 * or 0 if the primitives do not intersect
392 cpml_arc_intersection_with_line(const CpmlPrimitive
*arc
,
393 const CpmlPrimitive
*line
,
394 CpmlPair
*dest
, int max
)
401 * @arc: the #CpmlPrimitive arc data
402 * @offset: distance for the computed parallel arc
404 * Given an @arc, this function computes the parallel arc at
405 * distance @offset. The three points needed to build the
406 * new arc are returned in the @arc data (substituting the
410 cpml_arc_offset(CpmlPrimitive
*arc
, double offset
)
412 CpmlPair p
[3], center
;
415 cpml_pair_from_cairo(&p
[0], arc
->org
);
416 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
417 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
419 if (!get_center(p
, ¢er
))
422 r
= cpml_pair_distance(&p
[0], ¢er
) + offset
;
424 /* Offset the three points by calculating their vector from the center,
425 * setting the new radius as length and readding the center */
426 cpml_pair_sub(&p
[0], ¢er
);
427 cpml_pair_sub(&p
[1], ¢er
);
428 cpml_pair_sub(&p
[2], ¢er
);
430 cpml_vector_set_length(&p
[0], r
);
431 cpml_vector_set_length(&p
[1], r
);
432 cpml_vector_set_length(&p
[2], r
);
434 cpml_pair_add(&p
[0], ¢er
);
435 cpml_pair_add(&p
[1], ¢er
);
436 cpml_pair_add(&p
[2], ¢er
);
438 cpml_pair_to_cairo(&p
[0], arc
->org
);
439 cpml_pair_to_cairo(&p
[1], &arc
->data
[1]);
440 cpml_pair_to_cairo(&p
[2], &arc
->data
[2]);
445 * @arc: the #CpmlPrimitive arc data
446 * @cr: the destination cairo context
448 * Renders @arc to the @cr cairo context. As cairo does not support
449 * arcs natively, it is approximated using one or more Bézier curves.
451 * The number of curves used is dependent from the angle of the arc.
452 * Anyway, this function uses internally the hardcoded %M_PI_2 value
453 * as threshold value. This means the maximum arc approximated by a
454 * single curve will be a quarter of a circle and, consequently, a
455 * whole circle will be approximated by 4 Bézier curves.
458 cpml_arc_to_cairo(const CpmlPrimitive
*arc
, cairo_t
*cr
)
461 double r
, start
, end
;
465 cairo_path_data_t data
[4];
467 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
470 n_curves
= ceil(fabs(end
-start
) / ARC_MAX_ANGLE
);
471 step
= (end
-start
) / (double) n_curves
;
474 for (angle
= start
; n_curves
--; angle
+= step
) {
475 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
477 curve
.data
[1].point
.x
, curve
.data
[1].point
.y
,
478 curve
.data
[2].point
.x
, curve
.data
[2].point
.y
,
479 curve
.data
[3].point
.x
, curve
.data
[3].point
.y
);
484 * cpml_arc_to_curves:
485 * @arc: the #CpmlPrimitive arc data
486 * @segment: the destination #CpmlSegment
487 * @n_curves: number of Bézier to use
489 * Converts @arc to a serie of @n_curves Bézier curves and puts them
490 * inside @segment. Obviously, @segment must have enough space to
491 * contain at least @n_curves curves.
493 * This function works in a similar way as cpml_arc_to_cairo() but
494 * has two important differences: it does not need a cairo context
495 * and the number of curves to be generated is explicitely defined.
496 * The latter difference allows a more specific error control from
497 * the application: in the file src/cairo-arc.c, found in the cairo
498 * tarball (at least in cairo-1.9.1), there is a table showing the
499 * magnitude of error of this curve approximation algorithm.
502 cpml_arc_to_curves(const CpmlPrimitive
*arc
, CpmlSegment
*segment
,
506 double r
, start
, end
;
510 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
513 step
= (end
-start
) / (double) n_curves
;
514 segment
->num_data
= n_curves
*4;
515 curve
.segment
= segment
;
516 curve
.data
= segment
->data
;
518 for (angle
= start
; n_curves
--; angle
+= step
) {
519 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
526 get_center(const CpmlPair
*p
, CpmlPair
*dest
)
531 /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
532 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
533 dest
->x
= (p
[0].x
+ p
[1].x
) / 2;
534 dest
->y
= (p
[0].y
+ p
[1].y
) / 2;
538 /* Translate the 3 points of -p0, to simplify the formula */
539 cpml_pair_sub(cpml_pair_copy(&b
, &p
[1]), &p
[0]);
540 cpml_pair_sub(cpml_pair_copy(&c
, &p
[2]), &p
[0]);
542 /* Check for division by 0, that is the case where the 3 given points
543 * are laying on a straight line and there is no fitting circle */
544 d
= (b
.x
*c
.y
- b
.y
*c
.x
) * 2;
548 b2
= b
.x
*b
.x
+ b
.y
*b
.y
;
549 c2
= c
.x
*c
.x
+ c
.y
*c
.y
;
551 dest
->x
= (c
.y
*b2
- b
.y
*c2
) / d
+ p
[0].x
;
552 dest
->y
= (b
.x
*c2
- c
.x
*b2
) / d
+ p
[0].y
;
558 get_angles(const CpmlPair
*p
, const CpmlPair
*center
,
559 double *start
, double *end
)
564 /* Calculate the starting angle */
565 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[0]), center
);
566 *start
= cpml_vector_angle(&vector
);
568 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
569 /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
570 * of a circle: return by convention start=start end=start+2PI */
571 *end
= *start
+ M_PI
*2;
573 /* Calculate the mid and end angle */
574 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[1]), center
);
575 mid
= cpml_vector_angle(&vector
);
576 cpml_pair_sub(cpml_pair_copy(&vector
, &p
[2]), center
);
577 *end
= cpml_vector_angle(&vector
);
580 if (mid
> *end
|| mid
< *start
)
583 if (mid
< *end
|| mid
> *start
)
590 arc_to_curve(CpmlPrimitive
*curve
, const CpmlPair
*center
,
591 double r
, double start
, double end
)
593 double r_sin1
, r_cos1
;
594 double r_sin2
, r_cos2
;
597 r_sin1
= r
*sin(start
);
598 r_cos1
= r
*cos(start
);
602 h
= 4./3. * tan((end
-start
) / 4.);
604 curve
->data
[0].header
.type
= CAIRO_PATH_CURVE_TO
;
605 curve
->data
[0].header
.length
= 4;
606 curve
->data
[1].point
.x
= center
->x
+ r_cos1
- h
*r_sin1
;
607 curve
->data
[1].point
.y
= center
->y
+ r_sin1
+ h
*r_cos1
;
608 curve
->data
[2].point
.x
= center
->x
+ r_cos2
+ h
*r_sin2
;
609 curve
->data
[2].point
.y
= center
->y
+ r_sin2
- h
*r_cos2
;
610 curve
->data
[3].point
.x
= center
->x
+ r_cos2
;
611 curve
->data
[3].point
.y
= center
->y
+ r_sin2
;