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.
65 #include "cpml-internal.h"
66 #include "cpml-extents.h"
67 #include "cpml-segment.h"
68 #include "cpml-primitive.h"
69 #include "cpml-primitive-private.h"
75 /* Hardcoded max angle of the arc to be approximated by a Bézier curve:
76 * this influence the arc quality (the default value is got from cairo) */
77 #define ARC_MAX_ANGLE M_PI_2
80 static double get_length (const CpmlPrimitive
*arc
);
81 static cairo_bool_t
get_center (const CpmlPair
*p
,
83 static void get_angles (const CpmlPair
*p
,
84 const CpmlPair
*center
,
87 static void arc_to_curve (CpmlPrimitive
*curve
,
88 const CpmlPair
*center
,
94 const _CpmlPrimitiveClass
*
95 _cpml_arc_get_class(void)
97 static _CpmlPrimitiveClass
*p_class
= NULL
;
99 if (p_class
== NULL
) {
100 static _CpmlPrimitiveClass class_data
= {
111 p_class
= &class_data
;
120 * @arc: the #CpmlPrimitive arc data
121 * @center: where to store the center coordinates (can be %NULL)
122 * @r: where to store the radius (can be %NULL)
123 * @start: where to store the starting angle (can be %NULL)
124 * @end: where to store the ending angle (can be %NULL)
126 * Given an @arc, this function calculates and returns its basic data.
127 * Any pointer can be %NULL, in which case the requested info is not
128 * returned. This function can fail (when the three points lay on a
129 * straight line, for example) in which case 0 is returned and no
130 * data can be considered valid.
132 * The radius @r can be 0 when the three points are coincidents: a
133 * circle with radius 0 is considered a valid path.
135 * When the start and end angle are returned, together with their
136 * values these angles implicitely gives another important information:
139 * If @start < @end the arc must be rendered with increasing angle
140 * value (clockwise direction using the ordinary cairo coordinate
141 * system) while if @start > @end the arc must be rendered in reverse
142 * order (that is counterclockwise in the cairo world). This is the
143 * reason the angle values are returned in the range
144 * { -M_PI < value < 3*M_PI } inclusive instead of the usual
145 * { -M_PI < value < M_PI } range.
147 * Returns: 1 if the function worked succesfully, 0 on errors
150 cpml_arc_info(const CpmlPrimitive
*arc
, CpmlPair
*center
,
151 double *r
, double *start
, double *end
)
153 CpmlPair p
[3], l_center
;
155 cpml_pair_from_cairo(&p
[0], arc
->org
);
156 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
157 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
159 if (!get_center(p
, &l_center
))
166 *r
= cpml_pair_distance(&p
[0], &l_center
);
168 if (start
!= NULL
|| end
!= NULL
) {
169 double l_start
, l_end
;
171 get_angles(p
, &l_center
, &l_start
, &l_end
);
182 /* Hardcoded macro to save a lot of typing and make the
183 * cpml_arc_put_extents() code clearer */
184 #define ANGLE_INCLUDED(d) \
185 ((start < (d) && end > (d)) || (start > (d) && end < (d)))
188 * cpml_arc_put_extents:
189 * @arc: the #CpmlPrimitive arc data
190 * @extents: where to store the extents
192 * Given an @arc primitive, returns its boundary box in @extents.
195 cpml_arc_put_extents(const CpmlPrimitive
*arc
, CpmlExtents
*extents
)
197 double r
, start
, end
;
198 CpmlPair center
, pair
;
200 extents
->is_defined
= 0;
202 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
205 /* Add the right quadrant point if needed */
206 if (ANGLE_INCLUDED(0) || ANGLE_INCLUDED(M_PI
* 2)) {
207 pair
.x
= center
.x
+ r
;
209 cpml_extents_pair_add(extents
, &pair
);
212 /* Add the bottom quadrant point if needed */
213 if (ANGLE_INCLUDED(M_PI_2
) || ANGLE_INCLUDED(M_PI_2
* 5)) {
215 pair
.y
= center
.y
+ r
;
216 cpml_extents_pair_add(extents
, &pair
);
219 /* Add the left quadrant point if needed */
220 if (ANGLE_INCLUDED(M_PI
)) {
221 pair
.x
= center
.x
- r
;
223 cpml_extents_pair_add(extents
, &pair
);
226 /* Add the top quadrant point if needed */
227 if (ANGLE_INCLUDED(M_PI_2
* 3) || ANGLE_INCLUDED(-M_PI_2
)) {
229 pair
.y
= center
.y
- r
;
230 cpml_extents_pair_add(extents
, &pair
);
233 /* Add the start point */
234 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, 0));
235 cpml_extents_pair_add(extents
, &pair
);
237 /* Add the end point */
238 cpml_pair_from_cairo(&pair
, cpml_primitive_get_point(arc
, -1));
239 cpml_extents_pair_add(extents
, &pair
);
243 * cpml_arc_put_pair_at:
244 * @arc: the #CpmlPrimitive arc data
245 * @pos: the position value
246 * @pair: the destination #CpmlPair
248 * Given an @arc, finds the coordinates at position @pos (where 0 is
249 * the start and 1 is the end) and stores the result in @pair.
251 * @pos can also be outside the 0..1 limit, as interpolating on an
252 * arc is quite trivial.
255 cpml_arc_put_pair_at(const CpmlPrimitive
*arc
, double pos
, CpmlPair
*pair
)
258 cpml_pair_from_cairo(pair
, arc
->org
);
259 } else if (pos
== 1.) {
260 cpml_pair_from_cairo(pair
, &arc
->data
[2]);
263 double r
, start
, end
, angle
;
265 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
268 angle
= (end
-start
)*pos
+ start
;
269 cpml_vector_from_angle(pair
, angle
);
270 cpml_vector_set_length(pair
, r
);
271 cpml_pair_add(pair
, ¢er
);
276 * cpml_arc_put_vector_at:
277 * @arc: the #CpmlPrimitive arc data
278 * @pos: the position value
279 * @vector: the destination vector
281 * Given an @arc, finds the slope at position @pos (where 0 is
282 * the start and 1 is the end) and stores the result in @vector.
284 * @pos can also be outside the 0..1 limit, as interpolating on an
285 * arc is quite trivial.
288 cpml_arc_put_vector_at(const CpmlPrimitive
*arc
, double pos
,
291 double start
, end
, angle
;
293 if (!cpml_arc_info(arc
, NULL
, NULL
, &start
, &end
))
296 angle
= (end
-start
)*pos
+ start
;
297 cpml_vector_from_angle(vector
, angle
);
298 cpml_vector_normal(vector
);
301 cpml_pair_negate(vector
);
305 * cpml_arc_get_closest_pos:
306 * @arc: the #CpmlPrimitive arc data
307 * @pair: the coordinates of the subject point
309 * Returns the pos value of the point on @arc nearest to @pair.
310 * The returned value is always between 0 and 1.
313 * <title>TODO</title>
315 * <listitem>To be implemented...</listitem>
319 * Returns: the pos value, always between 0 and 1
322 cpml_arc_get_closest_pos(const CpmlPrimitive
*arc
, const CpmlPair
*pair
)
330 * cpml_arc_put_intersections:
331 * @arc: the first arc
332 * @arc2: the second arc
333 * @max: maximum number of intersections to return
334 * (that is, the size of @dest)
335 * @dest: a vector of #CpmlPair
337 * Given two arcs (@arc and @arc2), gets their intersection points
338 * and store the result in @dest. Keep in mind two arcs can have
339 * up to 2 intersections.
341 * If @max is 0, the function returns 0 immediately without any
342 * further processing. If @arc and @arc2 are cohincident (same
343 * center and same radius), their intersections are not considered.
346 * <title>TODO</title>
348 * <listitem>To be implemented...</listitem>
352 * Returns: the number of intersections found (max 2)
353 * or 0 if the primitives do not intersect
356 cpml_arc_put_intersections(const CpmlPrimitive
*arc
, const CpmlPrimitive
*arc2
,
357 int max
, CpmlPair
*dest
)
363 * cpml_arc_put_intersections_with_line:
366 * @max: maximum number of intersections to return
367 * (that is, the size of @dest)
368 * @dest: a vector of #CpmlPair
370 * Given an @arc and a @line, gets their intersection points
371 * and store the result in @dest. Keep in mind an arc and a
372 * line can have up to 2 intersections.
374 * If @max is 0, the function returns 0 immediately without any
375 * further processing.
378 * <title>TODO</title>
380 * <listitem>To be implemented...</listitem>
384 * Returns: the number of intersections found (max 2)
385 * or 0 if the primitives do not intersect
388 cpml_arc_put_intersections_with_line(const CpmlPrimitive
*arc
,
389 const CpmlPrimitive
*line
,
390 int max
, CpmlPair
*dest
)
397 * @arc: the #CpmlPrimitive arc data
398 * @offset: distance for the computed parallel arc
400 * Given an @arc, this function computes the parallel arc at
401 * distance @offset. The three points needed to build the
402 * new arc are returned in the @arc data (substituting the
406 cpml_arc_offset(CpmlPrimitive
*arc
, double offset
)
408 CpmlPair p
[3], center
;
411 cpml_pair_from_cairo(&p
[0], arc
->org
);
412 cpml_pair_from_cairo(&p
[1], &arc
->data
[1]);
413 cpml_pair_from_cairo(&p
[2], &arc
->data
[2]);
415 if (!get_center(p
, ¢er
))
418 r
= cpml_pair_distance(&p
[0], ¢er
) + offset
;
420 /* Offset the three points by calculating their vector from the center,
421 * setting the new radius as length and readding the center */
422 cpml_pair_sub(&p
[0], ¢er
);
423 cpml_pair_sub(&p
[1], ¢er
);
424 cpml_pair_sub(&p
[2], ¢er
);
426 cpml_vector_set_length(&p
[0], r
);
427 cpml_vector_set_length(&p
[1], r
);
428 cpml_vector_set_length(&p
[2], r
);
430 cpml_pair_add(&p
[0], ¢er
);
431 cpml_pair_add(&p
[1], ¢er
);
432 cpml_pair_add(&p
[2], ¢er
);
434 cpml_pair_to_cairo(&p
[0], arc
->org
);
435 cpml_pair_to_cairo(&p
[1], &arc
->data
[1]);
436 cpml_pair_to_cairo(&p
[2], &arc
->data
[2]);
441 * @arc: the #CpmlPrimitive arc data
442 * @cr: the destination cairo context
444 * Renders @arc to the @cr cairo context. As cairo does not support
445 * arcs natively, it is approximated using one or more Bézier curves.
447 * The number of curves used is dependent from the angle of the arc.
448 * Anyway, this function uses internally the hardcoded %M_PI_2 value
449 * as threshold value. This means the maximum arc approximated by a
450 * single curve will be a quarter of a circle and, consequently, a
451 * whole circle will be approximated by 4 Bézier curves.
454 cpml_arc_to_cairo(const CpmlPrimitive
*arc
, cairo_t
*cr
)
457 double r
, start
, end
;
461 cairo_path_data_t data
[4];
463 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
466 n_curves
= ceil(fabs(end
-start
) / ARC_MAX_ANGLE
);
467 step
= (end
-start
) / (double) n_curves
;
470 for (angle
= start
; n_curves
--; angle
+= step
) {
471 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
473 curve
.data
[1].point
.x
, curve
.data
[1].point
.y
,
474 curve
.data
[2].point
.x
, curve
.data
[2].point
.y
,
475 curve
.data
[3].point
.x
, curve
.data
[3].point
.y
);
480 * cpml_arc_to_curves:
481 * @arc: the #CpmlPrimitive arc data
482 * @segment: the destination #CpmlSegment
483 * @n_curves: number of Bézier to use
485 * Converts @arc to a serie of @n_curves Bézier curves and puts them
486 * inside @segment. Obviously, @segment must have enough space to
487 * contain at least @n_curves curves.
489 * This function works in a similar way as cpml_arc_to_cairo() but
490 * has two important differences: it does not need a cairo context
491 * and the number of curves to be generated is explicitely defined.
492 * The latter difference allows a more specific error control from
493 * the application: in the file src/cairo-arc.c, found in the cairo
494 * tarball (at least in cairo-1.9.1), there is a table showing the
495 * magnitude of error of this curve approximation algorithm.
498 cpml_arc_to_curves(const CpmlPrimitive
*arc
, CpmlSegment
*segment
,
502 double r
, start
, end
;
506 if (!cpml_arc_info(arc
, ¢er
, &r
, &start
, &end
))
509 step
= (end
-start
) / (double) n_curves
;
510 segment
->num_data
= n_curves
*4;
511 curve
.segment
= segment
;
512 curve
.data
= segment
->data
;
514 for (angle
= start
; n_curves
--; angle
+= step
) {
515 arc_to_curve(&curve
, ¢er
, r
, angle
, angle
+step
);
522 get_length(const CpmlPrimitive
*arc
)
524 double r
, start
, end
, delta
;
526 if (!cpml_arc_info(arc
, NULL
, &r
, &start
, &end
) || start
== end
)
537 get_center(const CpmlPair
*p
, CpmlPair
*dest
)
542 /* When p[0] == p[2], p[0]..p[1] is considered the diameter of a circle */
543 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
544 dest
->x
= (p
[0].x
+ p
[1].x
) / 2;
545 dest
->y
= (p
[0].y
+ p
[1].y
) / 2;
549 /* Translate the 3 points of -p0, to simplify the formula */
550 cpml_pair_copy(&b
, &p
[1]);
551 cpml_pair_sub(&b
, &p
[0]);
552 cpml_pair_copy(&c
, &p
[2]);
553 cpml_pair_sub(&c
, &p
[0]);
555 /* Check for division by 0, that is the case where the 3 given points
556 * are laying on a straight line and there is no fitting circle */
557 d
= (b
.x
*c
.y
- b
.y
*c
.x
) * 2;
561 b2
= b
.x
*b
.x
+ b
.y
*b
.y
;
562 c2
= c
.x
*c
.x
+ c
.y
*c
.y
;
564 dest
->x
= (c
.y
*b2
- b
.y
*c2
) / d
+ p
[0].x
;
565 dest
->y
= (b
.x
*c2
- c
.x
*b2
) / d
+ p
[0].y
;
571 get_angles(const CpmlPair
*p
, const CpmlPair
*center
,
572 double *start
, double *end
)
577 /* Calculate the starting angle */
578 cpml_pair_copy(&vector
, &p
[0]);
579 cpml_pair_sub(&vector
, center
);
580 *start
= cpml_vector_angle(&vector
);
582 if (p
[0].x
== p
[2].x
&& p
[0].y
== p
[2].y
) {
583 /* When p[0] and p[2] are cohincidents, p[0]..p[1] is the diameter
584 * of a circle: return by convention start=start end=start+2PI */
585 *end
= *start
+ M_PI
*2;
587 /* Calculate the mid and end angle: cpml_vector_angle()
588 * returns an angle between -M_PI and M_PI */
589 cpml_pair_copy(&vector
, &p
[1]);
590 cpml_pair_sub(&vector
, center
);
591 mid
= cpml_vector_angle(&vector
);
592 cpml_pair_copy(&vector
, &p
[2]);
593 cpml_pair_sub(&vector
, center
);
594 *end
= cpml_vector_angle(&vector
);
597 /* If the middle angle is outside the start..end range,
598 * the arc should be reversed (that is, start must
599 * be greather than end) */
600 if (mid
< *start
|| mid
> *end
)
603 /* Here the arc is reversed: if the middle angle is
604 * outside the end..start range, the arc should be
605 * re-reversed to get a straight arc (that is, end
606 * must be greather than start) */
607 if (mid
< *end
|| mid
> *start
)
614 arc_to_curve(CpmlPrimitive
*curve
, const CpmlPair
*center
,
615 double r
, double start
, double end
)
617 double r_sin1
, r_cos1
;
618 double r_sin2
, r_cos2
;
621 r_sin1
= r
*sin(start
);
622 r_cos1
= r
*cos(start
);
626 h
= 4./3. * tan((end
-start
) / 4.);
628 curve
->data
[0].header
.type
= CAIRO_PATH_CURVE_TO
;
629 curve
->data
[0].header
.length
= 4;
630 curve
->data
[1].point
.x
= center
->x
+ r_cos1
- h
*r_sin1
;
631 curve
->data
[1].point
.y
= center
->y
+ r_sin1
+ h
*r_cos1
;
632 curve
->data
[2].point
.x
= center
->x
+ r_cos2
+ h
*r_sin2
;
633 curve
->data
[2].point
.y
= center
->y
+ r_sin2
- h
*r_cos2
;
634 curve
->data
[3].point
.x
= center
->x
+ r_cos2
;
635 curve
->data
[3].point
.y
= center
->y
+ r_sin2
;