1//! Elliptic arc related maths and tools.
2
3use core::mem::swap;
4use core::ops::Range;
5
6use num_traits::NumCast;
7
8use crate::scalar::{cast, Float, Scalar};
9use crate::segment::{BoundingBox, Segment};
10use crate::{point, vector, Angle, Box2D, Point, Rotation, Transform, Vector};
11use crate::{CubicBezierSegment, Line, LineSegment, QuadraticBezierSegment};
12
13/// An elliptic arc curve segment.
14#[derive(Copy, Clone, Debug, PartialEq)]
15#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
16pub struct Arc<S> {
17 pub center: Point<S>,
18 pub radii: Vector<S>,
19 pub start_angle: Angle<S>,
20 pub sweep_angle: Angle<S>,
21 pub x_rotation: Angle<S>,
22}
23
24/// An elliptic arc curve segment using the SVG's end-point notation.
25#[derive(Copy, Clone, Debug, PartialEq)]
26#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
27pub struct SvgArc<S> {
28 pub from: Point<S>,
29 pub to: Point<S>,
30 pub radii: Vector<S>,
31 pub x_rotation: Angle<S>,
32 pub flags: ArcFlags,
33}
34
35impl<S: Scalar> Arc<S> {
36 pub fn cast<NewS: NumCast>(self) -> Arc<NewS> {
37 Arc {
38 center: self.center.cast(),
39 radii: self.radii.cast(),
40 start_angle: self.start_angle.cast(),
41 sweep_angle: self.sweep_angle.cast(),
42 x_rotation: self.x_rotation.cast(),
43 }
44 }
45
46 /// Create simple circle.
47 pub fn circle(center: Point<S>, radius: S) -> Self {
48 Arc {
49 center,
50 radii: vector(radius, radius),
51 start_angle: Angle::zero(),
52 sweep_angle: Angle::two_pi(),
53 x_rotation: Angle::zero(),
54 }
55 }
56
57 /// Convert from the SVG arc notation.
58 pub fn from_svg_arc(arc: &SvgArc<S>) -> Arc<S> {
59 debug_assert!(!arc.from.x.is_nan());
60 debug_assert!(!arc.from.y.is_nan());
61 debug_assert!(!arc.to.x.is_nan());
62 debug_assert!(!arc.to.y.is_nan());
63 debug_assert!(!arc.radii.x.is_nan());
64 debug_assert!(!arc.radii.y.is_nan());
65 debug_assert!(!arc.x_rotation.get().is_nan());
66 // The SVG spec specifies what we should do if one of the two
67 // radii is zero and not the other, but it's better to handle
68 // this out of arc code and generate a line_to instead of an arc.
69 assert!(!arc.is_straight_line());
70
71 let mut rx = S::abs(arc.radii.x);
72 let mut ry = S::abs(arc.radii.y);
73
74 let xr = arc.x_rotation.get() % (S::TWO * S::PI());
75 let cos_phi = Float::cos(xr);
76 let sin_phi = Float::sin(xr);
77 let hd_x = (arc.from.x - arc.to.x) / S::TWO;
78 let hd_y = (arc.from.y - arc.to.y) / S::TWO;
79 let hs_x = (arc.from.x + arc.to.x) / S::TWO;
80 let hs_y = (arc.from.y + arc.to.y) / S::TWO;
81
82 // F6.5.1
83 let p = Point::new(
84 cos_phi * hd_x + sin_phi * hd_y,
85 -sin_phi * hd_x + cos_phi * hd_y,
86 );
87
88 // Sanitize the radii.
89 // If rf > 1 it means the radii are too small for the arc to
90 // possibly connect the end points. In this situation we scale
91 // them up according to the formula provided by the SVG spec.
92
93 // F6.6.2
94 let rf = p.x * p.x / (rx * rx) + p.y * p.y / (ry * ry);
95 if rf > S::ONE {
96 let scale = S::sqrt(rf);
97 rx *= scale;
98 ry *= scale;
99 }
100
101 let rxry = rx * ry;
102 let rxpy = rx * p.y;
103 let rypx = ry * p.x;
104 let sum_of_sq = rxpy * rxpy + rypx * rypx;
105
106 debug_assert_ne!(sum_of_sq, S::ZERO);
107
108 // F6.5.2
109 let sign_coe = if arc.flags.large_arc == arc.flags.sweep {
110 -S::ONE
111 } else {
112 S::ONE
113 };
114 let coe = sign_coe * S::sqrt(S::abs((rxry * rxry - sum_of_sq) / sum_of_sq));
115 let transformed_cx = coe * rxpy / ry;
116 let transformed_cy = -coe * rypx / rx;
117
118 // F6.5.3
119 let center = point(
120 cos_phi * transformed_cx - sin_phi * transformed_cy + hs_x,
121 sin_phi * transformed_cx + cos_phi * transformed_cy + hs_y,
122 );
123
124 let start_v: Vector<S> = vector((p.x - transformed_cx) / rx, (p.y - transformed_cy) / ry);
125 let end_v: Vector<S> = vector((-p.x - transformed_cx) / rx, (-p.y - transformed_cy) / ry);
126
127 let two_pi = S::TWO * S::PI();
128
129 let start_angle = start_v.angle_from_x_axis();
130
131 let mut sweep_angle = (end_v.angle_from_x_axis() - start_angle).radians % two_pi;
132
133 if arc.flags.sweep && sweep_angle < S::ZERO {
134 sweep_angle += two_pi;
135 } else if !arc.flags.sweep && sweep_angle > S::ZERO {
136 sweep_angle -= two_pi;
137 }
138
139 Arc {
140 center,
141 radii: vector(rx, ry),
142 start_angle,
143 sweep_angle: Angle::radians(sweep_angle),
144 x_rotation: arc.x_rotation,
145 }
146 }
147
148 /// Convert to the SVG arc notation.
149 pub fn to_svg_arc(&self) -> SvgArc<S> {
150 let from = self.sample(S::ZERO);
151 let to = self.sample(S::ONE);
152 let flags = ArcFlags {
153 sweep: self.sweep_angle.get() >= S::ZERO,
154 large_arc: S::abs(self.sweep_angle.get()) >= S::PI(),
155 };
156 SvgArc {
157 from,
158 to,
159 radii: self.radii,
160 x_rotation: self.x_rotation,
161 flags,
162 }
163 }
164
165 /// Approximate the arc with a sequence of quadratic bézier curves.
166 #[inline]
167 pub fn for_each_quadratic_bezier<F>(&self, cb: &mut F)
168 where
169 F: FnMut(&QuadraticBezierSegment<S>),
170 {
171 arc_to_quadratic_beziers_with_t(self, &mut |curve, _| cb(curve));
172 }
173
174 /// Approximate the arc with a sequence of quadratic bézier curves.
175 #[inline]
176 pub fn for_each_quadratic_bezier_with_t<F>(&self, cb: &mut F)
177 where
178 F: FnMut(&QuadraticBezierSegment<S>, Range<S>),
179 {
180 arc_to_quadratic_beziers_with_t(self, cb);
181 }
182
183 /// Approximate the arc with a sequence of cubic bézier curves.
184 #[inline]
185 pub fn for_each_cubic_bezier<F>(&self, cb: &mut F)
186 where
187 F: FnMut(&CubicBezierSegment<S>),
188 {
189 arc_to_cubic_beziers(self, cb);
190 }
191
192 /// Sample the curve at t (expecting t between 0 and 1).
193 #[inline]
194 pub fn sample(&self, t: S) -> Point<S> {
195 let angle = self.get_angle(t);
196 self.center + sample_ellipse(self.radii, self.x_rotation, angle).to_vector()
197 }
198
199 #[inline]
200 pub fn x(&self, t: S) -> S {
201 self.sample(t).x
202 }
203
204 #[inline]
205 pub fn y(&self, t: S) -> S {
206 self.sample(t).y
207 }
208
209 /// Sample the curve's tangent at t (expecting t between 0 and 1).
210 #[inline]
211 pub fn sample_tangent(&self, t: S) -> Vector<S> {
212 self.tangent_at_angle(self.get_angle(t))
213 }
214
215 /// Sample the curve's angle at t (expecting t between 0 and 1).
216 #[inline]
217 pub fn get_angle(&self, t: S) -> Angle<S> {
218 self.start_angle + Angle::radians(self.sweep_angle.get() * t)
219 }
220
221 #[inline]
222 pub fn end_angle(&self) -> Angle<S> {
223 self.start_angle + self.sweep_angle
224 }
225
226 #[inline]
227 pub fn from(&self) -> Point<S> {
228 self.sample(S::ZERO)
229 }
230
231 #[inline]
232 pub fn to(&self) -> Point<S> {
233 self.sample(S::ONE)
234 }
235
236 /// Return the sub-curve inside a given range of t.
237 ///
238 /// This is equivalent splitting at the range's end points.
239 pub fn split_range(&self, t_range: Range<S>) -> Self {
240 let angle_1 = Angle::radians(self.sweep_angle.get() * t_range.start);
241 let angle_2 = Angle::radians(self.sweep_angle.get() * t_range.end);
242
243 Arc {
244 center: self.center,
245 radii: self.radii,
246 start_angle: self.start_angle + angle_1,
247 sweep_angle: angle_2 - angle_1,
248 x_rotation: self.x_rotation,
249 }
250 }
251
252 /// Split this curve into two sub-curves.
253 pub fn split(&self, t: S) -> (Arc<S>, Arc<S>) {
254 let split_angle = Angle::radians(self.sweep_angle.get() * t);
255 (
256 Arc {
257 center: self.center,
258 radii: self.radii,
259 start_angle: self.start_angle,
260 sweep_angle: split_angle,
261 x_rotation: self.x_rotation,
262 },
263 Arc {
264 center: self.center,
265 radii: self.radii,
266 start_angle: self.start_angle + split_angle,
267 sweep_angle: self.sweep_angle - split_angle,
268 x_rotation: self.x_rotation,
269 },
270 )
271 }
272
273 /// Return the curve before the split point.
274 pub fn before_split(&self, t: S) -> Arc<S> {
275 let split_angle = Angle::radians(self.sweep_angle.get() * t);
276 Arc {
277 center: self.center,
278 radii: self.radii,
279 start_angle: self.start_angle,
280 sweep_angle: split_angle,
281 x_rotation: self.x_rotation,
282 }
283 }
284
285 /// Return the curve after the split point.
286 pub fn after_split(&self, t: S) -> Arc<S> {
287 let split_angle = Angle::radians(self.sweep_angle.get() * t);
288 Arc {
289 center: self.center,
290 radii: self.radii,
291 start_angle: self.start_angle + split_angle,
292 sweep_angle: self.sweep_angle - split_angle,
293 x_rotation: self.x_rotation,
294 }
295 }
296
297 /// Swap the direction of the segment.
298 pub fn flip(&self) -> Self {
299 let mut arc = *self;
300 arc.start_angle += self.sweep_angle;
301 arc.sweep_angle = -self.sweep_angle;
302
303 arc
304 }
305
306 /// Approximates the curve with sequence of line segments.
307 ///
308 /// The `tolerance` parameter defines the maximum distance between the curve and
309 /// its approximation.
310 pub fn for_each_flattened<F>(&self, tolerance: S, callback: &mut F)
311 where
312 F: FnMut(&LineSegment<S>),
313 {
314 let mut from = self.from();
315 let mut iter = *self;
316 loop {
317 let t = iter.flattening_step(tolerance);
318 if t >= S::ONE {
319 break;
320 }
321 iter = iter.after_split(t);
322 let to = iter.from();
323 callback(&LineSegment { from, to });
324 from = to;
325 }
326
327 callback(&LineSegment {
328 from,
329 to: self.to(),
330 });
331 }
332
333 /// Approximates the curve with sequence of line segments.
334 ///
335 /// The `tolerance` parameter defines the maximum distance between the curve and
336 /// its approximation.
337 ///
338 /// The end of the t parameter range at the final segment is guaranteed to be equal to `1.0`.
339 pub fn for_each_flattened_with_t<F>(&self, tolerance: S, callback: &mut F)
340 where
341 F: FnMut(&LineSegment<S>, Range<S>),
342 {
343 let mut iter = *self;
344 let mut t0 = S::ZERO;
345 let mut from = self.from();
346 loop {
347 let step = iter.flattening_step(tolerance);
348
349 if step >= S::ONE {
350 break;
351 }
352
353 iter = iter.after_split(step);
354 let t1 = t0 + step * (S::ONE - t0);
355 let to = iter.from();
356 callback(&LineSegment { from, to }, t0..t1);
357 from = to;
358 t0 = t1;
359 }
360
361 callback(
362 &LineSegment {
363 from,
364 to: self.to(),
365 },
366 t0..S::ONE,
367 );
368 }
369
370 /// Finds the interval of the beginning of the curve that can be approximated with a
371 /// line segment.
372 fn flattening_step(&self, tolerance: S) -> S {
373 // cos(theta) = (r - tolerance) / r
374 // angle = 2 * theta
375 // s = angle / sweep
376
377 // Here we make the approximation that for small tolerance values we consider
378 // the radius to be constant over each approximated segment.
379 let r = (self.from() - self.center).length();
380 let a = S::TWO * S::acos((r - tolerance) / r);
381 let result = S::min(a / self.sweep_angle.radians.abs(), S::ONE);
382
383 if result < S::EPSILON {
384 return S::ONE;
385 }
386
387 result
388 }
389
390 /// Returns the flattened representation of the curve as an iterator, starting *after* the
391 /// current point.
392 pub fn flattened(&self, tolerance: S) -> Flattened<S> {
393 Flattened::new(*self, tolerance)
394 }
395
396 /// Returns a conservative rectangle that contains the curve.
397 pub fn fast_bounding_box(&self) -> Box2D<S> {
398 Transform::rotation(self.x_rotation).outer_transformed_box(&Box2D {
399 min: self.center - self.radii,
400 max: self.center + self.radii,
401 })
402 }
403
404 /// Returns a conservative rectangle that contains the curve.
405 pub fn bounding_box(&self) -> Box2D<S> {
406 let from = self.from();
407 let to = self.to();
408 let mut min = Point::min(from, to);
409 let mut max = Point::max(from, to);
410 self.for_each_local_x_extremum_t(&mut |t| {
411 let p = self.sample(t);
412 min.x = S::min(min.x, p.x);
413 max.x = S::max(max.x, p.x);
414 });
415 self.for_each_local_y_extremum_t(&mut |t| {
416 let p = self.sample(t);
417 min.y = S::min(min.y, p.y);
418 max.y = S::max(max.y, p.y);
419 });
420
421 Box2D { min, max }
422 }
423
424 pub fn for_each_local_x_extremum_t<F>(&self, cb: &mut F)
425 where
426 F: FnMut(S),
427 {
428 let rx = self.radii.x;
429 let ry = self.radii.y;
430 let a1 = Angle::radians(-S::atan(ry * Float::tan(self.x_rotation.radians) / rx));
431 let a2 = Angle::pi() + a1;
432
433 self.for_each_extremum_inner(a1, a2, cb);
434 }
435
436 pub fn for_each_local_y_extremum_t<F>(&self, cb: &mut F)
437 where
438 F: FnMut(S),
439 {
440 let rx = self.radii.x;
441 let ry = self.radii.y;
442 let a1 = Angle::radians(S::atan(ry / (Float::tan(self.x_rotation.radians) * rx)));
443 let a2 = Angle::pi() + a1;
444
445 self.for_each_extremum_inner(a1, a2, cb);
446 }
447
448 fn for_each_extremum_inner<F>(&self, a1: Angle<S>, a2: Angle<S>, cb: &mut F)
449 where
450 F: FnMut(S),
451 {
452 let sweep = self.sweep_angle.radians;
453 let abs_sweep = S::abs(sweep);
454 let sign = S::signum(sweep);
455
456 let mut a1 = (a1 - self.start_angle).positive().radians;
457 let mut a2 = (a2 - self.start_angle).positive().radians;
458 if a1 * sign > a2 * sign {
459 swap(&mut a1, &mut a2);
460 }
461
462 let two_pi = S::TWO * S::PI();
463 if sweep >= S::ZERO {
464 if a1 < abs_sweep {
465 cb(a1 / abs_sweep);
466 }
467 if a2 < abs_sweep {
468 cb(a2 / abs_sweep);
469 }
470 } else {
471 if a1 > two_pi - abs_sweep {
472 cb(a1 / abs_sweep);
473 }
474 if a2 > two_pi - abs_sweep {
475 cb(a2 / abs_sweep);
476 }
477 }
478 }
479
480 pub fn bounding_range_x(&self) -> (S, S) {
481 let r = self.bounding_box();
482 (r.min.x, r.max.x)
483 }
484
485 pub fn bounding_range_y(&self) -> (S, S) {
486 let r = self.bounding_box();
487 (r.min.y, r.max.y)
488 }
489
490 pub fn fast_bounding_range_x(&self) -> (S, S) {
491 let r = self.fast_bounding_box();
492 (r.min.x, r.max.x)
493 }
494
495 pub fn fast_bounding_range_y(&self) -> (S, S) {
496 let r = self.fast_bounding_box();
497 (r.min.y, r.max.y)
498 }
499
500 pub fn approximate_length(&self, tolerance: S) -> S {
501 let mut len = S::ZERO;
502 self.for_each_flattened(tolerance, &mut |segment| {
503 len += segment.length();
504 });
505
506 len
507 }
508
509 #[inline]
510 fn tangent_at_angle(&self, angle: Angle<S>) -> Vector<S> {
511 let a = angle.get();
512 Rotation::new(self.x_rotation).transform_vector(vector(
513 -self.radii.x * Float::sin(a),
514 self.radii.y * Float::cos(a),
515 ))
516 }
517}
518
519impl<S: Scalar> From<SvgArc<S>> for Arc<S> {
520 fn from(svg: SvgArc<S>) -> Self {
521 svg.to_arc()
522 }
523}
524
525impl<S: Scalar> SvgArc<S> {
526 /// Converts this arc from endpoints to center notation.
527 pub fn to_arc(&self) -> Arc<S> {
528 Arc::from_svg_arc(self)
529 }
530
531 /// Per SVG spec, this arc should be rendered as a line_to segment.
532 ///
533 /// Do not convert an `SvgArc` into an `arc` if this returns true.
534 pub fn is_straight_line(&self) -> bool {
535 S::abs(self.radii.x) <= S::EPSILON
536 || S::abs(self.radii.y) <= S::EPSILON
537 || self.from == self.to
538 }
539
540 /// Approximates the arc with a sequence of quadratic bézier segments.
541 pub fn for_each_quadratic_bezier<F>(&self, cb: &mut F)
542 where
543 F: FnMut(&QuadraticBezierSegment<S>),
544 {
545 if self.is_straight_line() {
546 cb(&QuadraticBezierSegment {
547 from: self.from,
548 ctrl: self.from,
549 to: self.to,
550 });
551 return;
552 }
553
554 Arc::from_svg_arc(self).for_each_quadratic_bezier(cb);
555 }
556
557 /// Approximates the arc with a sequence of quadratic bézier segments.
558 pub fn for_each_quadratic_bezier_with_t<F>(&self, cb: &mut F)
559 where
560 F: FnMut(&QuadraticBezierSegment<S>, Range<S>),
561 {
562 if self.is_straight_line() {
563 cb(
564 &QuadraticBezierSegment {
565 from: self.from,
566 ctrl: self.from,
567 to: self.to,
568 },
569 S::ZERO..S::ONE,
570 );
571 return;
572 }
573
574 Arc::from_svg_arc(self).for_each_quadratic_bezier_with_t(cb);
575 }
576
577 /// Approximates the arc with a sequence of cubic bézier segments.
578 pub fn for_each_cubic_bezier<F>(&self, cb: &mut F)
579 where
580 F: FnMut(&CubicBezierSegment<S>),
581 {
582 if self.is_straight_line() {
583 cb(&CubicBezierSegment {
584 from: self.from,
585 ctrl1: self.from,
586 ctrl2: self.to,
587 to: self.to,
588 });
589 return;
590 }
591
592 Arc::from_svg_arc(self).for_each_cubic_bezier(cb);
593 }
594
595 /// Approximates the curve with sequence of line segments.
596 ///
597 /// The `tolerance` parameter defines the maximum distance between the curve and
598 /// its approximation.
599 pub fn for_each_flattened<F: FnMut(&LineSegment<S>)>(&self, tolerance: S, cb: &mut F) {
600 if self.is_straight_line() {
601 cb(&LineSegment {
602 from: self.from,
603 to: self.to,
604 });
605 return;
606 }
607
608 Arc::from_svg_arc(self).for_each_flattened(tolerance, cb);
609 }
610
611 /// Approximates the curve with sequence of line segments.
612 ///
613 /// The `tolerance` parameter defines the maximum distance between the curve and
614 /// its approximation.
615 ///
616 /// The end of the t parameter range at the final segment is guaranteed to be equal to `1.0`.
617 pub fn for_each_flattened_with_t<F: FnMut(&LineSegment<S>, Range<S>)>(
618 &self,
619 tolerance: S,
620 cb: &mut F,
621 ) {
622 if self.is_straight_line() {
623 cb(
624 &LineSegment {
625 from: self.from,
626 to: self.to,
627 },
628 S::ZERO..S::ONE,
629 );
630 return;
631 }
632
633 Arc::from_svg_arc(self).for_each_flattened_with_t(tolerance, cb);
634 }
635}
636
637/// Flag parameters for arcs as described by the SVG specification.
638///
639/// For most situations using the SVG arc notation, there are four different arcs
640/// (two different ellipses, each with two different arc sweeps) that satisfy the
641/// arc parameters. The `large_arc` and `sweep` flags indicate which one of the
642/// four arcs are drawn, as follows:
643///
644/// See more examples in the [SVG specification](https://svgwg.org/specs/paths/)
645#[derive(Copy, Clone, Debug, PartialEq, Default)]
646#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
647pub struct ArcFlags {
648 /// Of the four candidate arc sweeps, two will represent an arc sweep of greater
649 /// than or equal to 180 degrees (the "large-arc"), and two will represent an arc
650 /// sweep of less than or equal to 180 degrees (the "small arc"). If `large_arc`
651 /// is `true`, then one of the two larger arc sweeps will be chosen; otherwise, if
652 /// `large_arc` is `false`, one of the smaller arc sweeps will be chosen.
653 pub large_arc: bool,
654 /// If `sweep` is `true`, then the arc will be drawn in a "positive-angle" direction
655 /// (the ellipse formula `x=cx+rx*cos(theta)` and `y=cy+ry*sin(theta)` is evaluated
656 /// such that theta starts at an angle corresponding to the current point and increases
657 /// positively until the arc reaches the destination position). A value of `false`
658 /// causes the arc to be drawn in a "negative-angle" direction (theta starts at an
659 /// angle value corresponding to the current point and decreases until the arc reaches
660 /// the destination position).
661 pub sweep: bool,
662}
663
664fn arc_to_quadratic_beziers_with_t<S, F>(arc: &Arc<S>, callback: &mut F)
665where
666 S: Scalar,
667 F: FnMut(&QuadraticBezierSegment<S>, Range<S>),
668{
669 let sign = arc.sweep_angle.get().signum();
670 let sweep_angle = S::abs(arc.sweep_angle.get()).min(S::PI() * S::TWO);
671
672 let n_steps = S::ceil(sweep_angle / S::FRAC_PI_4());
673 let step = Angle::radians(sweep_angle / n_steps * sign);
674
675 let mut t0 = S::ZERO;
676 let dt = S::ONE / n_steps;
677
678 let n = cast::<S, i32>(n_steps).unwrap();
679 for i in 0..n {
680 let a1 = arc.start_angle + step * cast(i).unwrap();
681 let a2 = arc.start_angle + step * cast(i + 1).unwrap();
682
683 let v1 = sample_ellipse(arc.radii, arc.x_rotation, a1).to_vector();
684 let v2 = sample_ellipse(arc.radii, arc.x_rotation, a2).to_vector();
685 let from = arc.center + v1;
686 let to = arc.center + v2;
687 let l1 = Line {
688 point: from,
689 vector: arc.tangent_at_angle(a1),
690 };
691 let l2 = Line {
692 point: to,
693 vector: arc.tangent_at_angle(a2),
694 };
695 let ctrl = l2.intersection(&l1).unwrap_or(from);
696
697 let t1 = if i + 1 == n { S::ONE } else { t0 + dt };
698
699 callback(&QuadraticBezierSegment { from, ctrl, to }, t0..t1);
700 t0 = t1;
701 }
702}
703
704fn arc_to_cubic_beziers<S, F>(arc: &Arc<S>, callback: &mut F)
705where
706 S: Scalar,
707 F: FnMut(&CubicBezierSegment<S>),
708{
709 let sign = arc.sweep_angle.get().signum();
710 let sweep_angle = S::abs(arc.sweep_angle.get()).min(S::PI() * S::TWO);
711
712 let n_steps = S::ceil(sweep_angle / S::FRAC_PI_2());
713 let step = Angle::radians(sweep_angle / n_steps * sign);
714
715 for i in 0..cast::<S, i32>(n_steps).unwrap() {
716 let a1 = arc.start_angle + step * cast(i).unwrap();
717 let a2 = arc.start_angle + step * cast(i + 1).unwrap();
718
719 let v1 = sample_ellipse(arc.radii, arc.x_rotation, a1).to_vector();
720 let v2 = sample_ellipse(arc.radii, arc.x_rotation, a2).to_vector();
721 let from = arc.center + v1;
722 let to = arc.center + v2;
723
724 // From http://www.spaceroots.org/documents/ellipse/elliptical-arc.pdf
725 // Note that the parameterization used by Arc (see sample_ellipse for
726 // example) is the same as the eta-parameterization used at the link.
727 let delta_a = a2 - a1;
728 let tan_da = Float::tan(delta_a.get() * S::HALF);
729 let alpha_sqrt = S::sqrt(S::FOUR + S::THREE * tan_da * tan_da);
730 let alpha = Float::sin(delta_a.get()) * (alpha_sqrt - S::ONE) / S::THREE;
731 let ctrl1 = from + arc.tangent_at_angle(a1) * alpha;
732 let ctrl2 = to - arc.tangent_at_angle(a2) * alpha;
733
734 callback(&CubicBezierSegment {
735 from,
736 ctrl1,
737 ctrl2,
738 to,
739 });
740 }
741}
742
743fn sample_ellipse<S: Scalar>(radii: Vector<S>, x_rotation: Angle<S>, angle: Angle<S>) -> Point<S> {
744 Rotation::new(angle:x_rotation).transform_point(point(
745 x:radii.x * Float::cos(angle.get()),
746 y:radii.y * Float::sin(self:angle.get()),
747 ))
748}
749
750impl<S: Scalar> Segment for Arc<S> {
751 type Scalar = S;
752 fn from(&self) -> Point<S> {
753 self.from()
754 }
755 fn to(&self) -> Point<S> {
756 self.to()
757 }
758 fn sample(&self, t: S) -> Point<S> {
759 self.sample(t)
760 }
761 fn x(&self, t: S) -> S {
762 self.x(t)
763 }
764 fn y(&self, t: S) -> S {
765 self.y(t)
766 }
767 fn derivative(&self, t: S) -> Vector<S> {
768 self.sample_tangent(t)
769 }
770 fn split(&self, t: S) -> (Self, Self) {
771 self.split(t)
772 }
773 fn before_split(&self, t: S) -> Self {
774 self.before_split(t)
775 }
776 fn after_split(&self, t: S) -> Self {
777 self.after_split(t)
778 }
779 fn split_range(&self, t_range: Range<S>) -> Self {
780 self.split_range(t_range)
781 }
782 fn flip(&self) -> Self {
783 self.flip()
784 }
785 fn approximate_length(&self, tolerance: S) -> S {
786 self.approximate_length(tolerance)
787 }
788
789 fn for_each_flattened_with_t(
790 &self,
791 tolerance: Self::Scalar,
792 callback: &mut dyn FnMut(&LineSegment<S>, Range<S>),
793 ) {
794 self.for_each_flattened_with_t(tolerance, &mut |s, t| callback(s, t));
795 }
796}
797
798impl<S: Scalar> BoundingBox for Arc<S> {
799 type Scalar = S;
800 fn bounding_range_x(&self) -> (S, S) {
801 self.bounding_range_x()
802 }
803 fn bounding_range_y(&self) -> (S, S) {
804 self.bounding_range_y()
805 }
806 fn fast_bounding_range_x(&self) -> (S, S) {
807 self.fast_bounding_range_x()
808 }
809 fn fast_bounding_range_y(&self) -> (S, S) {
810 self.fast_bounding_range_y()
811 }
812}
813
814/// Flattening iterator for arcs.
815///
816/// The iterator starts at the first point *after* the origin of the curve and ends at the
817/// destination.
818pub struct Flattened<S> {
819 arc: Arc<S>,
820 tolerance: S,
821 done: bool,
822}
823
824impl<S: Scalar> Flattened<S> {
825 pub(crate) fn new(arc: Arc<S>, tolerance: S) -> Self {
826 assert!(tolerance > S::ZERO);
827 Flattened {
828 arc,
829 tolerance,
830 done: false,
831 }
832 }
833}
834impl<S: Scalar> Iterator for Flattened<S> {
835 type Item = Point<S>;
836 fn next(&mut self) -> Option<Point<S>> {
837 if self.done {
838 return None;
839 }
840
841 let t: S = self.arc.flattening_step(self.tolerance);
842 if t >= S::ONE {
843 self.done = true;
844 return Some(self.arc.to());
845 }
846 self.arc = self.arc.after_split(t);
847
848 Some(self.arc.from())
849 }
850}
851
852#[test]
853fn test_from_svg_arc() {
854 use crate::vector;
855 use euclid::approxeq::ApproxEq;
856
857 let flags = ArcFlags {
858 large_arc: false,
859 sweep: false,
860 };
861
862 test_endpoints(&SvgArc {
863 from: point(0.0, -10.0),
864 to: point(10.0, 0.0),
865 radii: vector(10.0, 10.0),
866 x_rotation: Angle::radians(0.0),
867 flags,
868 });
869
870 test_endpoints(&SvgArc {
871 from: point(0.0, -10.0),
872 to: point(10.0, 0.0),
873 radii: vector(100.0, 10.0),
874 x_rotation: Angle::radians(0.0),
875 flags,
876 });
877
878 test_endpoints(&SvgArc {
879 from: point(0.0, -10.0),
880 to: point(10.0, 0.0),
881 radii: vector(10.0, 30.0),
882 x_rotation: Angle::radians(1.0),
883 flags,
884 });
885
886 test_endpoints(&SvgArc {
887 from: point(5.0, -10.0),
888 to: point(5.0, 5.0),
889 radii: vector(10.0, 30.0),
890 x_rotation: Angle::radians(-2.0),
891 flags,
892 });
893
894 // This arc has invalid radii (too small to connect the two endpoints),
895 // but the conversion needs to be able to cope with that.
896 test_endpoints(&SvgArc {
897 from: point(0.0, 0.0),
898 to: point(80.0, 60.0),
899 radii: vector(40.0, 40.0),
900 x_rotation: Angle::radians(0.0),
901 flags,
902 });
903
904 fn test_endpoints(svg_arc: &SvgArc<f64>) {
905 do_test_endpoints(&SvgArc {
906 flags: ArcFlags {
907 large_arc: false,
908 sweep: false,
909 },
910 ..svg_arc.clone()
911 });
912
913 do_test_endpoints(&SvgArc {
914 flags: ArcFlags {
915 large_arc: true,
916 sweep: false,
917 },
918 ..svg_arc.clone()
919 });
920
921 do_test_endpoints(&SvgArc {
922 flags: ArcFlags {
923 large_arc: false,
924 sweep: true,
925 },
926 ..svg_arc.clone()
927 });
928
929 do_test_endpoints(&SvgArc {
930 flags: ArcFlags {
931 large_arc: true,
932 sweep: true,
933 },
934 ..svg_arc.clone()
935 });
936 }
937
938 fn do_test_endpoints(svg_arc: &SvgArc<f64>) {
939 let eps = point(0.01, 0.01);
940 let arc = svg_arc.to_arc();
941 assert!(
942 arc.from().approx_eq_eps(&svg_arc.from, &eps),
943 "unexpected arc.from: {:?} == {:?}, flags: {:?}",
944 arc.from(),
945 svg_arc.from,
946 svg_arc.flags,
947 );
948 assert!(
949 arc.to().approx_eq_eps(&svg_arc.to, &eps),
950 "unexpected arc.from: {:?} == {:?}, flags: {:?}",
951 arc.to(),
952 svg_arc.to,
953 svg_arc.flags,
954 );
955 }
956}
957
958#[test]
959fn test_to_quadratics_and_cubics() {
960 use euclid::approxeq::ApproxEq;
961
962 fn do_test(arc: &Arc<f32>, expected_quadratic_count: u32, expected_cubic_count: u32) {
963 let last = arc.to();
964 {
965 let mut prev = arc.from();
966 let mut count = 0;
967 arc.for_each_quadratic_bezier(&mut |c| {
968 assert!(c.from.approx_eq(&prev));
969 prev = c.to;
970 count += 1;
971 });
972 assert!(prev.approx_eq(&last));
973 assert_eq!(count, expected_quadratic_count);
974 }
975 {
976 let mut prev = arc.from();
977 let mut count = 0;
978 arc.for_each_cubic_bezier(&mut |c| {
979 assert!(c.from.approx_eq(&prev));
980 prev = c.to;
981 count += 1;
982 });
983 assert!(prev.approx_eq(&last));
984 assert_eq!(count, expected_cubic_count);
985 }
986 }
987
988 do_test(
989 &Arc {
990 center: point(2.0, 3.0),
991 radii: vector(10.0, 3.0),
992 start_angle: Angle::radians(0.1),
993 sweep_angle: Angle::radians(3.0),
994 x_rotation: Angle::radians(0.5),
995 },
996 4,
997 2,
998 );
999
1000 do_test(
1001 &Arc {
1002 center: point(4.0, 5.0),
1003 radii: vector(3.0, 5.0),
1004 start_angle: Angle::radians(2.0),
1005 sweep_angle: Angle::radians(-3.0),
1006 x_rotation: Angle::radians(1.3),
1007 },
1008 4,
1009 2,
1010 );
1011
1012 do_test(
1013 &Arc {
1014 center: point(0.0, 0.0),
1015 radii: vector(100.0, 0.01),
1016 start_angle: Angle::radians(-1.0),
1017 sweep_angle: Angle::radians(0.1),
1018 x_rotation: Angle::radians(0.3),
1019 },
1020 1,
1021 1,
1022 );
1023
1024 do_test(
1025 &Arc {
1026 center: point(0.0, 0.0),
1027 radii: vector(1.0, 1.0),
1028 start_angle: Angle::radians(3.0),
1029 sweep_angle: Angle::radians(-0.1),
1030 x_rotation: Angle::radians(-0.3),
1031 },
1032 1,
1033 1,
1034 );
1035}
1036
1037#[test]
1038fn test_bounding_box() {
1039 use euclid::approxeq::ApproxEq;
1040
1041 fn approx_eq(r1: Box2D<f32>, r2: Box2D<f32>) -> bool {
1042 if !r1.min.x.approx_eq(&r2.min.x)
1043 || !r1.max.x.approx_eq(&r2.max.x)
1044 || !r1.min.y.approx_eq(&r2.min.y)
1045 || !r1.max.y.approx_eq(&r2.max.y)
1046 {
1047 std::println!("\n left: {r1:?}\n right: {r2:?}");
1048 return false;
1049 }
1050
1051 true
1052 }
1053
1054 let r = Arc {
1055 center: point(0.0, 0.0),
1056 radii: vector(1.0, 1.0),
1057 start_angle: Angle::radians(0.0),
1058 sweep_angle: Angle::pi(),
1059 x_rotation: Angle::zero(),
1060 }
1061 .bounding_box();
1062 assert!(approx_eq(
1063 r,
1064 Box2D {
1065 min: point(-1.0, 0.0),
1066 max: point(1.0, 1.0)
1067 }
1068 ));
1069
1070 let r = Arc {
1071 center: point(0.0, 0.0),
1072 radii: vector(1.0, 1.0),
1073 start_angle: Angle::radians(0.0),
1074 sweep_angle: Angle::pi(),
1075 x_rotation: Angle::pi(),
1076 }
1077 .bounding_box();
1078 assert!(approx_eq(
1079 r,
1080 Box2D {
1081 min: point(-1.0, -1.0),
1082 max: point(1.0, 0.0)
1083 }
1084 ));
1085
1086 let r = Arc {
1087 center: point(0.0, 0.0),
1088 radii: vector(2.0, 1.0),
1089 start_angle: Angle::radians(0.0),
1090 sweep_angle: Angle::pi(),
1091 x_rotation: Angle::pi() * 0.5,
1092 }
1093 .bounding_box();
1094 assert!(approx_eq(
1095 r,
1096 Box2D {
1097 min: point(-1.0, -2.0),
1098 max: point(0.0, 2.0)
1099 }
1100 ));
1101
1102 let r = Arc {
1103 center: point(1.0, 1.0),
1104 radii: vector(1.0, 1.0),
1105 start_angle: Angle::pi(),
1106 sweep_angle: Angle::pi(),
1107 x_rotation: -Angle::pi() * 0.25,
1108 }
1109 .bounding_box();
1110 assert!(approx_eq(
1111 r,
1112 Box2D {
1113 min: point(0.0, 0.0),
1114 max: point(1.707107, 1.707107)
1115 }
1116 ));
1117
1118 let mut angle = Angle::zero();
1119 for _ in 0..10 {
1120 std::println!("angle: {angle:?}");
1121 let r = Arc {
1122 center: point(0.0, 0.0),
1123 radii: vector(4.0, 4.0),
1124 start_angle: angle,
1125 sweep_angle: Angle::pi() * 2.0,
1126 x_rotation: Angle::pi() * 0.25,
1127 }
1128 .bounding_box();
1129 assert!(approx_eq(
1130 r,
1131 Box2D {
1132 min: point(-4.0, -4.0),
1133 max: point(4.0, 4.0)
1134 }
1135 ));
1136 angle += Angle::pi() * 2.0 / 10.0;
1137 }
1138
1139 let mut angle = Angle::zero();
1140 for _ in 0..10 {
1141 std::println!("angle: {angle:?}");
1142 let r = Arc {
1143 center: point(0.0, 0.0),
1144 radii: vector(4.0, 4.0),
1145 start_angle: Angle::zero(),
1146 sweep_angle: Angle::pi() * 2.0,
1147 x_rotation: angle,
1148 }
1149 .bounding_box();
1150 assert!(approx_eq(
1151 r,
1152 Box2D {
1153 min: point(-4.0, -4.0),
1154 max: point(4.0, 4.0)
1155 }
1156 ));
1157 angle += Angle::pi() * 2.0 / 10.0;
1158 }
1159}
1160
1161#[test]
1162fn negative_flattening_step() {
1163 // These parameters were running into a precision issue which led the
1164 // flattening step to never converge towards 1 and cause an infinite loop.
1165
1166 let arc = Arc {
1167 center: point(-100.0, -150.0),
1168 radii: vector(50.0, 50.0),
1169 start_angle: Angle::radians(0.982944787),
1170 sweep_angle: Angle::radians(-898.0),
1171 x_rotation: Angle::zero(),
1172 };
1173
1174 arc.for_each_flattened(0.100000001, &mut |_| {});
1175
1176 // There was also an issue with negative sweep_angle leading to a negative step
1177 // causing the arc to be approximated with a single line segment.
1178
1179 let arc = Arc {
1180 center: point(0.0, 0.0),
1181 radii: vector(100.0, 10.0),
1182 start_angle: Angle::radians(0.2),
1183 sweep_angle: Angle::radians(-2.0),
1184 x_rotation: Angle::zero(),
1185 };
1186
1187 let flattened: std::vec::Vec<_> = arc.flattened(0.1).collect();
1188
1189 assert!(flattened.len() > 1);
1190}
1191