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