1use crate::scalar::Scalar;
2use crate::segment::Segment;
3use crate::traits::Transformation;
4use crate::{point, Box2D, Point, Vector};
5use crate::{CubicBezierSegment, Line, LineEquation, LineSegment, Triangle};
6use arrayvec::ArrayVec;
7use num_traits::NumCast;
8
9use core::mem;
10use core::ops::Range;
11
12#[derive(Copy, Clone, Debug, PartialEq)]
18#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
19pub struct QuadraticBezierSegment<S> {
20 pub from: Point<S>,
21 pub ctrl: Point<S>,
22 pub to: Point<S>,
23}
24
25impl<S: Scalar> QuadraticBezierSegment<S> {
26 pub fn cast<NewS: NumCast>(self) -> QuadraticBezierSegment<NewS> {
27 QuadraticBezierSegment {
28 from: self.from.cast(),
29 ctrl: self.ctrl.cast(),
30 to: self.to.cast(),
31 }
32 }
33
34 pub fn sample(&self, t: S) -> Point<S> {
36 let t2 = t * t;
37 let one_t = S::ONE - t;
38 let one_t2 = one_t * one_t;
39
40 self.from * one_t2 + self.ctrl.to_vector() * S::TWO * one_t * t + self.to.to_vector() * t2
41 }
42
43 pub fn x(&self, t: S) -> S {
45 let t2 = t * t;
46 let one_t = S::ONE - t;
47 let one_t2 = one_t * one_t;
48
49 self.from.x * one_t2 + self.ctrl.x * S::TWO * one_t * t + self.to.x * t2
50 }
51
52 pub fn y(&self, t: S) -> S {
54 let t2 = t * t;
55 let one_t = S::ONE - t;
56 let one_t2 = one_t * one_t;
57
58 self.from.y * one_t2 + self.ctrl.y * S::TWO * one_t * t + self.to.y * t2
59 }
60
61 #[inline]
62 fn derivative_coefficients(&self, t: S) -> (S, S, S) {
63 (S::TWO * t - S::TWO, -S::FOUR * t + S::TWO, S::TWO * t)
64 }
65
66 pub fn derivative(&self, t: S) -> Vector<S> {
68 let (c0, c1, c2) = self.derivative_coefficients(t);
69 self.from.to_vector() * c0 + self.ctrl.to_vector() * c1 + self.to.to_vector() * c2
70 }
71
72 pub fn dx(&self, t: S) -> S {
74 let (c0, c1, c2) = self.derivative_coefficients(t);
75 self.from.x * c0 + self.ctrl.x * c1 + self.to.x * c2
76 }
77
78 pub fn dy(&self, t: S) -> S {
80 let (c0, c1, c2) = self.derivative_coefficients(t);
81 self.from.y * c0 + self.ctrl.y * c1 + self.to.y * c2
82 }
83
84 pub fn flip(&self) -> Self {
86 QuadraticBezierSegment {
87 from: self.to,
88 ctrl: self.ctrl,
89 to: self.from,
90 }
91 }
92
93 pub fn y_maximum_t(&self) -> S {
97 if let Some(t) = self.local_y_extremum_t() {
98 let y = self.y(t);
99 if y > self.from.y && y > self.to.y {
100 return t;
101 }
102 }
103
104 if self.from.y > self.to.y {
105 S::ZERO
106 } else {
107 S::ONE
108 }
109 }
110
111 pub fn y_minimum_t(&self) -> S {
115 if let Some(t) = self.local_y_extremum_t() {
116 let y = self.y(t);
117 if y < self.from.y && y < self.to.y {
118 return t;
119 }
120 }
121
122 if self.from.y < self.to.y {
123 S::ZERO
124 } else {
125 S::ONE
126 }
127 }
128
129 pub fn local_y_extremum_t(&self) -> Option<S> {
131 let div = self.from.y - S::TWO * self.ctrl.y + self.to.y;
132 if div == S::ZERO {
133 return None;
134 }
135 let t = (self.from.y - self.ctrl.y) / div;
136 if t > S::ZERO && t < S::ONE {
137 return Some(t);
138 }
139
140 None
141 }
142
143 pub fn x_maximum_t(&self) -> S {
147 if let Some(t) = self.local_x_extremum_t() {
148 let x = self.x(t);
149 if x > self.from.x && x > self.to.x {
150 return t;
151 }
152 }
153
154 if self.from.x > self.to.x {
155 S::ZERO
156 } else {
157 S::ONE
158 }
159 }
160
161 pub fn x_minimum_t(&self) -> S {
165 if let Some(t) = self.local_x_extremum_t() {
166 let x = self.x(t);
167 if x < self.from.x && x < self.to.x {
168 return t;
169 }
170 }
171
172 if self.from.x < self.to.x {
173 S::ZERO
174 } else {
175 S::ONE
176 }
177 }
178
179 pub fn local_x_extremum_t(&self) -> Option<S> {
181 let div = self.from.x - S::TWO * self.ctrl.x + self.to.x;
182 if div == S::ZERO {
183 return None;
184 }
185 let t = (self.from.x - self.ctrl.x) / div;
186 if t > S::ZERO && t < S::ONE {
187 return Some(t);
188 }
189
190 None
191 }
192
193 pub fn split_range(&self, t_range: Range<S>) -> Self {
197 let t0 = t_range.start;
198 let t1 = t_range.end;
199
200 let from = self.sample(t0);
201 let to = self.sample(t1);
202 let ctrl = from + (self.ctrl - self.from).lerp(self.to - self.ctrl, t0) * (t1 - t0);
203
204 QuadraticBezierSegment { from, ctrl, to }
205 }
206
207 pub fn split(&self, t: S) -> (QuadraticBezierSegment<S>, QuadraticBezierSegment<S>) {
209 let split_point = self.sample(t);
210
211 (
212 QuadraticBezierSegment {
213 from: self.from,
214 ctrl: self.from.lerp(self.ctrl, t),
215 to: split_point,
216 },
217 QuadraticBezierSegment {
218 from: split_point,
219 ctrl: self.ctrl.lerp(self.to, t),
220 to: self.to,
221 },
222 )
223 }
224
225 pub fn before_split(&self, t: S) -> QuadraticBezierSegment<S> {
227 QuadraticBezierSegment {
228 from: self.from,
229 ctrl: self.from.lerp(self.ctrl, t),
230 to: self.sample(t),
231 }
232 }
233
234 pub fn after_split(&self, t: S) -> QuadraticBezierSegment<S> {
236 QuadraticBezierSegment {
237 from: self.sample(t),
238 ctrl: self.ctrl.lerp(self.to, t),
239 to: self.to,
240 }
241 }
242
243 pub fn to_cubic(&self) -> CubicBezierSegment<S> {
245 CubicBezierSegment {
246 from: self.from,
247 ctrl1: (self.from + self.ctrl.to_vector() * S::TWO) / S::THREE,
248 ctrl2: (self.to + self.ctrl.to_vector() * S::TWO) / S::THREE,
249 to: self.to,
250 }
251 }
252
253 #[inline]
254 pub fn baseline(&self) -> LineSegment<S> {
255 LineSegment {
256 from: self.from,
257 to: self.to,
258 }
259 }
260
261 pub fn is_a_point(&self, tolerance: S) -> bool {
264 let tol2 = tolerance * tolerance;
265 (self.from - self.to).square_length() <= tol2
266 && (self.from - self.ctrl).square_length() <= tol2
267 }
268
269 pub fn is_linear(&self, tolerance: S) -> bool {
272 if self.from == self.to {
273 return true;
274 }
275
276 let d = self
277 .baseline()
278 .to_line()
279 .square_distance_to_point(self.ctrl);
280
281 d <= (tolerance * tolerance * S::FOUR)
282 }
283
284 pub fn fat_line(&self) -> (LineEquation<S>, LineEquation<S>) {
289 let l1 = self.baseline().to_line().equation();
290 let d = S::HALF * l1.signed_distance_to_point(&self.ctrl);
291 let l2 = l1.offset(d);
292 if d >= S::ZERO {
293 (l1, l2)
294 } else {
295 (l2, l1)
296 }
297 }
298
299 #[inline]
301 pub fn transformed<T: Transformation<S>>(&self, transform: &T) -> Self {
302 QuadraticBezierSegment {
303 from: transform.transform_point(self.from),
304 ctrl: transform.transform_point(self.ctrl),
305 to: transform.transform_point(self.to),
306 }
307 }
308
309 pub fn flattening_step(&self, tolerance: S) -> S {
312 let v1 = self.ctrl - self.from;
313 let v2 = self.to - self.from;
314
315 let v1_cross_v2 = v2.x * v1.y - v2.y * v1.x;
316 let h = S::sqrt(v1.x * v1.x + v1.y * v1.y);
317
318 if S::abs(v1_cross_v2 * h) <= S::EPSILON {
319 return S::ONE;
320 }
321
322 let s2inv = h / v1_cross_v2;
323
324 let t = S::TWO * S::sqrt(tolerance * S::abs(s2inv) / S::THREE);
325
326 if t > S::ONE {
327 return S::ONE;
328 }
329
330 t
331 }
332
333 pub fn for_each_flattened<F>(&self, tolerance: S, callback: &mut F)
338 where
339 F: FnMut(&LineSegment<S>),
340 {
341 debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
342
343 let n = flattened_segments_wang(self, tolerance);
344 let step = S::ONE / n;
345 let mut t = step;
346
347 let curve = self.polynomial_form();
348
349 let n = n.to_u32().unwrap_or(1) - 1;
350 let mut from = self.from;
351 for _ in 0..n {
352 let to = curve.sample(t);
353 callback(&LineSegment { from, to });
354 from = to;
355 t += step;
356 }
357
358 callback(&LineSegment { from, to: self.to });
359 }
360
361 pub fn for_each_flattened_with_t<F>(&self, tolerance: S, callback: &mut F)
369 where
370 F: FnMut(&LineSegment<S>, Range<S>),
371 {
372 debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
373
374 let n = flattened_segments_wang(self, tolerance);
375 let step = S::ONE / n;
376 let mut t0 = S::ZERO;
377
378 let curve = self.polynomial_form();
379
380 let n = n.to_u32().unwrap_or(1) - 1;
381 let mut from = self.from;
382 for _ in 0..n {
383 let t1 = t0 + step;
384 let to = curve.sample(t1);
385 callback(&LineSegment { from, to }, t0..t1);
386 from = to;
387 t0 = t1;
388 }
389
390 callback(&LineSegment { from, to: self.to }, t0..S::ONE);
391 }
392
393 pub fn flattened(&self, tolerance: S) -> Flattened<S> {
396 Flattened::new(self, tolerance)
397 }
398 pub fn flattened_t(&self, tolerance: S) -> FlattenedT<S> {
401 FlattenedT::new(self, tolerance)
402 }
403
404 pub fn for_each_monotonic_range<F>(&self, cb: &mut F)
406 where
407 F: FnMut(Range<S>),
408 {
409 let mut t0 = self.local_x_extremum_t();
410 let mut t1 = self.local_y_extremum_t();
411
412 let swap = match (t0, t1) {
413 (Some(tx), Some(ty)) => tx > ty,
414 _ => false,
415 };
416
417 if swap {
418 mem::swap(&mut t0, &mut t1);
419 }
420
421 let mut start = S::ZERO;
422
423 if let Some(t) = t0 {
424 cb(start..t);
425 start = t;
426 }
427
428 if let Some(t) = t1 {
429 if t != start {
431 cb(start..t);
432 start = t
433 }
434 }
435
436 cb(start..S::ONE);
437 }
438
439 pub fn for_each_monotonic<F>(&self, cb: &mut F)
441 where
442 F: FnMut(&QuadraticBezierSegment<S>),
443 {
444 self.for_each_monotonic_range(&mut |range| {
445 let mut sub = self.split_range(range);
446 let min_x = sub.from.x.min(sub.to.x);
449 let max_x = sub.from.x.max(sub.to.x);
450 let min_y = sub.from.y.min(sub.to.y);
451 let max_y = sub.from.y.max(sub.to.y);
452 sub.ctrl.x = sub.ctrl.x.max(min_x).min(max_x);
453 sub.ctrl.y = sub.ctrl.y.max(min_y).min(max_y);
454 cb(&sub);
455 });
456 }
457
458 pub fn for_each_y_monotonic_range<F>(&self, cb: &mut F)
460 where
461 F: FnMut(Range<S>),
462 {
463 match self.local_y_extremum_t() {
464 Some(t) => {
465 cb(S::ZERO..t);
466 cb(t..S::ONE);
467 }
468 None => {
469 cb(S::ZERO..S::ONE);
470 }
471 }
472 }
473
474 pub fn for_each_y_monotonic<F>(&self, cb: &mut F)
476 where
477 F: FnMut(&QuadraticBezierSegment<S>),
478 {
479 match self.local_y_extremum_t() {
480 Some(t) => {
481 let (a, b) = self.split(t);
482 cb(&a);
483 cb(&b);
484 }
485 None => {
486 cb(self);
487 }
488 }
489 }
490
491 pub fn for_each_x_monotonic_range<F>(&self, cb: &mut F)
493 where
494 F: FnMut(Range<S>),
495 {
496 match self.local_x_extremum_t() {
497 Some(t) => {
498 cb(S::ZERO..t);
499 cb(t..S::ONE);
500 }
501 None => {
502 cb(S::ZERO..S::ONE);
503 }
504 }
505 }
506
507 pub fn for_each_x_monotonic<F>(&self, cb: &mut F)
509 where
510 F: FnMut(&QuadraticBezierSegment<S>),
511 {
512 match self.local_x_extremum_t() {
513 Some(t) => {
514 let (mut a, mut b) = self.split(t);
515 let a_min = a.from.x.min(a.to.x);
518 let a_max = a.from.x.max(a.to.x);
519 let b_min = b.from.x.min(b.to.x);
520 let b_max = b.from.x.max(b.to.x);
521 a.ctrl.x = a.ctrl.x.max(a_min).min(a_max);
522 b.ctrl.x = b.ctrl.x.max(b_min).min(b_max);
523 cb(&a);
524 cb(&b);
525 }
526 None => {
527 cb(self);
528 }
529 }
530 }
531
532 pub fn bounding_triangle(&self) -> Triangle<S> {
534 Triangle {
535 a: self.from,
536 b: self.ctrl,
537 c: self.to,
538 }
539 }
540
541 pub fn fast_bounding_box(&self) -> Box2D<S> {
543 let (min_x, max_x) = self.fast_bounding_range_x();
544 let (min_y, max_y) = self.fast_bounding_range_y();
545
546 Box2D {
547 min: point(min_x, min_y),
548 max: point(max_x, max_y),
549 }
550 }
551
552 pub fn fast_bounding_range_x(&self) -> (S, S) {
554 let min_x = self.from.x.min(self.ctrl.x).min(self.to.x);
555 let max_x = self.from.x.max(self.ctrl.x).max(self.to.x);
556
557 (min_x, max_x)
558 }
559
560 pub fn fast_bounding_range_y(&self) -> (S, S) {
562 let min_y = self.from.y.min(self.ctrl.y).min(self.to.y);
563 let max_y = self.from.y.max(self.ctrl.y).max(self.to.y);
564
565 (min_y, max_y)
566 }
567
568 pub fn bounding_box(&self) -> Box2D<S> {
570 let (min_x, max_x) = self.bounding_range_x();
571 let (min_y, max_y) = self.bounding_range_y();
572
573 Box2D {
574 min: point(min_x, min_y),
575 max: point(max_x, max_y),
576 }
577 }
578
579 pub fn bounding_range_x(&self) -> (S, S) {
581 let min_x = self.x(self.x_minimum_t());
582 let max_x = self.x(self.x_maximum_t());
583
584 (min_x, max_x)
585 }
586
587 pub fn bounding_range_y(&self) -> (S, S) {
589 let min_y = self.y(self.y_minimum_t());
590 let max_y = self.y(self.y_maximum_t());
591
592 (min_y, max_y)
593 }
594
595 pub fn is_x_monotonic(&self) -> bool {
597 self.local_x_extremum_t().is_none()
598 }
599
600 pub fn is_y_monotonic(&self) -> bool {
602 self.local_y_extremum_t().is_none()
603 }
604
605 pub fn is_monotonic(&self) -> bool {
607 self.is_x_monotonic() && self.is_y_monotonic()
608 }
609
610 pub fn line_intersections_t(&self, line: &Line<S>) -> ArrayVec<S, 2> {
616 let eqn = line.equation();
619 let i = eqn.a() * self.from.x + eqn.b() * self.from.y;
620 let j = eqn.a() * self.ctrl.x + eqn.b() * self.ctrl.y;
621 let k = eqn.a() * self.to.x + eqn.b() * self.to.y;
622 let a = i - j - j + k;
624 let b = j + j - i - i;
625 let c = i + eqn.c();
626
627 let mut result = ArrayVec::new();
628
629 if a == S::ZERO {
630 let t = c / b;
632 if t >= S::ZERO && t <= S::ONE {
633 result.push(t);
634 return result;
635 }
636 }
637
638 let delta = b * b - S::FOUR * a * c;
639 if delta >= S::ZERO {
640 let sqrt_delta = S::sqrt(delta);
644 let s_sqrt_delta = -b.signum() * sqrt_delta;
645 let mut t1 = (-b + s_sqrt_delta) / (S::TWO * a);
646 let mut t2 = c / (a * t1);
647
648 if t1 > t2 {
649 mem::swap(&mut t1, &mut t2);
650 }
651
652 if t1 >= S::ZERO && t1 <= S::ONE {
653 result.push(t1);
654 }
655
656 if t2 >= S::ZERO && t2 <= S::ONE && t1 != t2 {
657 result.push(t2);
658 }
659 }
660
661 result
662 }
663
664 pub fn line_intersections(&self, line: &Line<S>) -> ArrayVec<Point<S>, 2> {
666 let intersections = self.line_intersections_t(line);
667
668 let mut result = ArrayVec::new();
669 for t in intersections {
670 result.push(self.sample(t));
671 }
672
673 result
674 }
675
676 pub fn line_segment_intersections_t(&self, segment: &LineSegment<S>) -> ArrayVec<(S, S), 2> {
682 if !self
683 .fast_bounding_box()
684 .inflate(S::EPSILON, S::EPSILON)
685 .intersects(&segment.bounding_box().inflate(S::EPSILON, S::EPSILON))
686 {
687 return ArrayVec::new();
688 }
689
690 let intersections = self.line_intersections_t(&segment.to_line());
691
692 let mut result = ArrayVec::new();
693 if intersections.is_empty() {
694 return result;
695 }
696
697 let seg_is_mostly_vertical =
698 S::abs(segment.from.y - segment.to.y) >= S::abs(segment.from.x - segment.to.x);
699 let (seg_long_axis_min, seg_long_axis_max) = if seg_is_mostly_vertical {
700 segment.bounding_range_y()
701 } else {
702 segment.bounding_range_x()
703 };
704
705 for t in intersections {
706 let intersection_xy = if seg_is_mostly_vertical {
707 self.y(t)
708 } else {
709 self.x(t)
710 };
711 if intersection_xy >= seg_long_axis_min && intersection_xy <= seg_long_axis_max {
712 let t2 = (self.sample(t) - segment.from).length() / segment.length();
713 if (t != S::ZERO && t != S::ONE) || (t2 != S::ZERO && t2 != S::ONE) {
715 result.push((t, t2));
716 }
717 }
718 }
719
720 result
721 }
722
723 #[inline]
724 pub fn from(&self) -> Point<S> {
725 self.from
726 }
727
728 #[inline]
729 pub fn to(&self) -> Point<S> {
730 self.to
731 }
732
733 pub fn line_segment_intersections(&self, segment: &LineSegment<S>) -> ArrayVec<Point<S>, 2> {
735 let intersections = self.line_segment_intersections_t(segment);
736
737 let mut result = ArrayVec::new();
738 for (t, _) in intersections {
739 result.push(self.sample(t));
740 }
741
742 result
743 }
744
745 pub fn closest_point(&self, pos: Point<S>) -> S {
747 let a = self.from - pos;
750 let b = self.ctrl - self.from;
751 let c = self.from + self.to.to_vector() - self.ctrl * S::TWO;
752
753 let c0 = c.dot(c);
755 let c1 = b.dot(c) * S::THREE;
756 let c2 = b.dot(b) * S::TWO + a.dot(c);
757 let c3 = a.dot(b);
758
759 let roots = crate::utils::cubic_polynomial_roots(c0, c1, c2, c3);
760
761 let mut sq_dist = a.square_length();
762 let mut t = S::ZERO;
763 let to_dist = (self.to - pos).square_length();
764 if to_dist < sq_dist {
765 sq_dist = to_dist;
766 t = S::ONE
767 }
768 for root in roots {
769 if root >= S::ZERO && root <= S::ONE {
770 let p = self.sample(root);
771 let d = (pos - p).square_length();
772 if d < sq_dist {
773 sq_dist = d;
774 t = root;
775 }
776 }
777 }
778
779 t
780 }
781
782 pub fn distance_to_point(&self, pos: Point<S>) -> S {
784 (self.sample(self.closest_point(pos)) - pos).length()
785 }
786
787 pub fn square_distance_to_point(&self, pos: Point<S>) -> S {
792 (self.sample(self.closest_point(pos)) - pos).square_length()
793 }
794
795 pub fn drag(&self, t: S, new_position: Point<S>) -> Self {
798 let t2 = t * t;
799 let one_t = S::ONE - t;
800 let one_t2 = one_t * one_t;
801
802 let u = t2 / (t2 + one_t2);
803 let c = self.from.lerp(self.to, u);
804
805 let inv_r = S::abs((t2 + one_t2) / (t2 + one_t2 - S::ONE));
806
807 QuadraticBezierSegment {
808 from: self.from,
809 ctrl: new_position + (new_position - c) * inv_r,
810 to: self.to,
811 }
812 }
813
814 pub fn length(&self) -> S {
819 let d2 = self.from - self.ctrl * S::TWO + self.to.to_vector();
822 let d1 = self.ctrl - self.from;
823 let a = d2.square_length();
824 let c = d1.square_length();
825 if a < S::value(1e-4) * c {
826 let v0 = (self.from.to_vector() * S::value(-0.492943519233745)
831 + self.ctrl.to_vector() * S::value(0.430331482911935)
832 + self.to.to_vector() * S::value(0.0626120363218102))
833 .length();
834 let v1 = ((self.to - self.from) * S::value(0.4444444444444444)).length();
835 let v2 = (self.from.to_vector() * S::value(-0.0626120363218102)
836 + self.ctrl.to_vector() * S::value(-0.430331482911935)
837 + self.to.to_vector() * S::value(0.492943519233745))
838 .length();
839 return v0 + v1 + v2;
840 }
841
842 let b = S::TWO * d2.dot(d1);
843
844 let sqr_abc = (a + b + c).sqrt();
845 let a2 = a.powf(-S::HALF);
846 let a32 = a2.powi(3);
847 let c2 = S::TWO * c.sqrt();
848 let ba_c2 = b * a2 + c2;
849
850 let v0 = S::HALF * S::HALF * a2 * a2 * b * (S::TWO * sqr_abc - c2) + sqr_abc;
851
852 if ba_c2 < S::EPSILON {
853 v0
855 } else {
856 v0 + S::HALF
857 * S::HALF
858 * a32
859 * (S::FOUR * c * a - b * b)
860 * (((S::TWO * a + b) * a2 + S::TWO * sqr_abc) / ba_c2).ln()
861 }
862 }
863
864 fn approximate_length(&self, _tolerance: S) -> S {
866 self.length()
867 }
868
869 pub fn to_f32(&self) -> QuadraticBezierSegment<f32> {
870 QuadraticBezierSegment {
871 from: self.from.to_f32(),
872 ctrl: self.ctrl.to_f32(),
873 to: self.to.to_f32(),
874 }
875 }
876
877 pub fn to_f64(&self) -> QuadraticBezierSegment<f64> {
878 QuadraticBezierSegment {
879 from: self.from.to_f64(),
880 ctrl: self.ctrl.to_f64(),
881 to: self.to.to_f64(),
882 }
883 }
884
885 #[inline]
886 pub fn polynomial_form(&self) -> QuadraticBezierPolynomial<S> {
887 let from = self.from.to_vector();
888 let ctrl = self.ctrl.to_vector();
889 let to = self.to.to_vector();
890 QuadraticBezierPolynomial {
891 a0: from,
892 a1: (ctrl - from) * S::TWO,
893 a2: from + to - ctrl * S::TWO,
894 }
895 }
896}
897
898pub struct FlatteningParameters<S> {
902 _marker: std::marker::PhantomData<S>
903}
904
905impl<S: Scalar> FlatteningParameters<S> {
906 pub fn new(_curve: &QuadraticBezierSegment<S>, _tolerance: S) -> Self {
907 Self { _marker: std::marker::PhantomData }
908 }
909}
910
911#[derive(Copy, Clone, Debug, PartialEq)]
916pub struct QuadraticBezierPolynomial<S> {
917 pub a0: Vector<S>,
918 pub a1: Vector<S>,
919 pub a2: Vector<S>,
920}
921
922impl<S: Scalar> QuadraticBezierPolynomial<S> {
923 #[inline(always)]
924 pub fn sample(&self, t: S) -> Point<S> {
925 let mut v = self.a0;
927 let mut t2 = t;
928 v += self.a1 * t2;
929 t2 *= t;
930 v += self.a2 * t2;
931
932 v.to_point()
933 }
934}
935
936fn flattened_segments_wang<S: Scalar>(curve: &QuadraticBezierSegment<S>, tolerance: S) -> S {
939 let from = curve.from.to_vector();
940 let ctrl = curve.ctrl.to_vector();
941 let to = curve.to.to_vector();
942 let l = (from - ctrl * S::TWO + to) * S::TWO;
943 let d = S::ONE / (S::EIGHT * tolerance);
944 let err4 = l.dot(l) * d * d;
945 let err4_f32 = err4.to_f32().unwrap_or(1.0);
946
947 const N: usize = 24;
950 const LUT: [f32; N] = [
951 1.0, 16.0, 81.0, 256.0, 625.0, 1296.0, 2401.0, 4096.0, 6561.0,
952 10000.0, 14641.0, 20736.0, 28561.0, 38416.0, 50625.0, 65536.0,
953 83521.0, 104976.0, 130321.0, 160000.0, 194481.0, 234256.0,
954 279841.0, 331776.0
955 ];
956
957 if err4_f32 <= 331776.0 {
959 #[allow(clippy::needless_range_loop)]
960 for i in 0..N {
961 if err4_f32 <= LUT[i] {
962 return S::from(i + 1).unwrap_or(S::ONE);
963 }
964 }
965 }
966
967 err4.sqrt().sqrt().max(S::ONE)
969}
970
971pub struct Flattened<S> {
975 curve: QuadraticBezierPolynomial<S>,
976 to: Point<S>,
977 segments: u32,
978 step: S,
979 t: S,
980}
981
982impl<S: Scalar> Flattened<S> {
983 #[inline]
984 pub(crate) fn new(curve: &QuadraticBezierSegment<S>, tolerance: S) -> Self {
985 debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
986
987 let n = flattened_segments_wang(curve, tolerance);
988
989 let step = S::ONE / n;
990
991 Flattened {
992 curve: curve.polynomial_form(),
993 to: curve.to,
994 segments: n.to_u32().unwrap_or(1),
995 step,
996 t: step
997 }
998 }
999}
1000
1001impl<S: Scalar> Iterator for Flattened<S> {
1002 type Item = Point<S>;
1003
1004 #[inline]
1005 fn next(&mut self) -> Option<Point<S>> {
1006 if self.segments == 0 {
1007 return None;
1008 }
1009
1010 self.segments -= 1;
1011 if self.segments == 0 {
1012 return Some(self.to)
1013 }
1014
1015 let p = self.curve.sample(self.t);
1016 self.t += self.step;
1017
1018 Some(p)
1019 }
1020
1021 #[inline]
1022 fn size_hint(&self) -> (usize, Option<usize>) {
1023 let n = self.segments as usize;
1024 (n, Some(n))
1025 }
1026}
1027
1028pub struct FlattenedT<S> {
1034 segments: u32,
1035 step: S,
1036 t: S,
1037}
1038
1039impl<S: Scalar> FlattenedT<S> {
1040 #[inline]
1041 pub(crate) fn new(curve: &QuadraticBezierSegment<S>, tolerance: S) -> Self {
1042 debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
1043
1044 let n = flattened_segments_wang(curve, tolerance);
1045
1046 let step = S::ONE / n;
1047
1048 FlattenedT {
1049 segments: n.to_u32().unwrap_or(1),
1050 step,
1051 t: step
1052 }
1053 }
1054}
1055
1056impl<S: Scalar> Iterator for FlattenedT<S> {
1057 type Item = S;
1058
1059 #[inline]
1060 fn next(&mut self) -> Option<S> {
1061 if self.segments == 0 {
1062 return None;
1063 }
1064
1065 self.segments -= 1;
1066 if self.segments == 0 {
1067 return Some(S::ONE)
1068 }
1069
1070 self.t += self.step;
1071
1072 Some(self.t)
1073 }
1074
1075 #[inline]
1076 fn size_hint(&self) -> (usize, Option<usize>) {
1077 let n = self.segments as usize;
1078 (n, Some(n))
1079 }
1080}
1081
1082impl<S: Scalar> Segment for QuadraticBezierSegment<S> {
1083 impl_segment!(S);
1084
1085 fn for_each_flattened_with_t(
1086 &self,
1087 tolerance: Self::Scalar,
1088 callback: &mut dyn FnMut(&LineSegment<S>, Range<S>),
1089 ) {
1090 self.for_each_flattened_with_t(tolerance, &mut |s, t| callback(s, t));
1091 }
1092}
1093
1094#[test]
1095fn bounding_box_for_monotonic_quadratic_bezier_segment() {
1096 let a = QuadraticBezierSegment {
1097 from: Point::new(0.0, 0.0),
1098 ctrl: Point::new(0.0, 0.0),
1099 to: Point::new(2.0, 0.0),
1100 };
1101
1102 let expected_aabb = Box2D {
1103 min: point(0.0, 0.0),
1104 max: point(2.0, 0.0),
1105 };
1106
1107 let actual_aabb = a.bounding_box();
1108
1109 assert_eq!(expected_aabb, actual_aabb)
1110}
1111
1112#[test]
1113fn fast_bounding_box_for_quadratic_bezier_segment() {
1114 let a = QuadraticBezierSegment {
1115 from: Point::new(0.0, 0.0),
1116 ctrl: Point::new(1.0, 1.0),
1117 to: Point::new(2.0, 0.0),
1118 };
1119
1120 let expected_aabb = Box2D {
1121 min: point(0.0, 0.0),
1122 max: point(2.0, 1.0),
1123 };
1124
1125 let actual_aabb = a.fast_bounding_box();
1126
1127 assert_eq!(expected_aabb, actual_aabb)
1128}
1129
1130#[test]
1131fn minimum_bounding_box_for_quadratic_bezier_segment() {
1132 let a = QuadraticBezierSegment {
1133 from: Point::new(0.0, 0.0),
1134 ctrl: Point::new(1.0, 1.0),
1135 to: Point::new(2.0, 0.0),
1136 };
1137
1138 let expected_aabb = Box2D {
1139 min: point(0.0, 0.0),
1140 max: point(2.0, 0.5),
1141 };
1142
1143 let actual_aabb = a.bounding_box();
1144
1145 assert_eq!(expected_aabb, actual_aabb)
1146}
1147
1148#[test]
1149fn y_maximum_t_for_simple_segment() {
1150 let a = QuadraticBezierSegment {
1151 from: Point::new(0.0, 0.0),
1152 ctrl: Point::new(1.0, 1.0),
1153 to: Point::new(2.0, 0.0),
1154 };
1155
1156 let expected_y_maximum = 0.5;
1157
1158 let actual_y_maximum = a.y_maximum_t();
1159
1160 assert_eq!(expected_y_maximum, actual_y_maximum)
1161}
1162
1163#[test]
1164fn local_y_extremum_for_simple_segment() {
1165 let a = QuadraticBezierSegment {
1166 from: Point::new(0.0, 0.0),
1167 ctrl: Point::new(1.0, 1.0),
1168 to: Point::new(2.0, 0.0),
1169 };
1170
1171 let expected_y_inflection = 0.5;
1172
1173 match a.local_y_extremum_t() {
1174 Some(actual_y_inflection) => assert_eq!(expected_y_inflection, actual_y_inflection),
1175 None => panic!(),
1176 }
1177}
1178
1179#[test]
1180fn y_minimum_t_for_simple_segment() {
1181 let a = QuadraticBezierSegment {
1182 from: Point::new(0.0, 0.0),
1183 ctrl: Point::new(1.0, -1.0),
1184 to: Point::new(2.0, 0.0),
1185 };
1186
1187 let expected_y_minimum = 0.5;
1188
1189 let actual_y_minimum = a.y_minimum_t();
1190
1191 assert_eq!(expected_y_minimum, actual_y_minimum)
1192}
1193
1194#[test]
1195fn x_maximum_t_for_simple_segment() {
1196 let a = QuadraticBezierSegment {
1197 from: Point::new(0.0, 0.0),
1198 ctrl: Point::new(1.0, 1.0),
1199 to: Point::new(0.0, 2.0),
1200 };
1201
1202 let expected_x_maximum = 0.5;
1203
1204 let actual_x_maximum = a.x_maximum_t();
1205
1206 assert_eq!(expected_x_maximum, actual_x_maximum)
1207}
1208
1209#[test]
1210fn local_x_extremum_for_simple_segment() {
1211 let a = QuadraticBezierSegment {
1212 from: Point::new(0.0, 0.0),
1213 ctrl: Point::new(1.0, 1.0),
1214 to: Point::new(0.0, 2.0),
1215 };
1216
1217 let expected_x_inflection = 0.5;
1218
1219 match a.local_x_extremum_t() {
1220 Some(actual_x_inflection) => assert_eq!(expected_x_inflection, actual_x_inflection),
1221 None => panic!(),
1222 }
1223}
1224
1225#[test]
1226fn x_minimum_t_for_simple_segment() {
1227 let a = QuadraticBezierSegment {
1228 from: Point::new(2.0, 0.0),
1229 ctrl: Point::new(1.0, 1.0),
1230 to: Point::new(2.0, 2.0),
1231 };
1232
1233 let expected_x_minimum = 0.5;
1234
1235 let actual_x_minimum = a.x_minimum_t();
1236
1237 assert_eq!(expected_x_minimum, actual_x_minimum)
1238}
1239
1240#[test]
1241fn length_straight_line() {
1242 let len = QuadraticBezierSegment {
1246 from: Point::new(0.0f64, 0.0),
1247 ctrl: Point::new(1.0, 0.0),
1248 to: Point::new(2.0, 0.0),
1249 }
1250 .length();
1251 assert!((len - 2.0).abs() < 0.000001);
1252
1253 let len = CubicBezierSegment {
1254 from: Point::new(0.0f64, 0.0),
1255 ctrl1: Point::new(1.0, 0.0),
1256 ctrl2: Point::new(1.0, 0.0),
1257 to: Point::new(2.0, 0.0),
1258 }
1259 .approximate_length(0.0001);
1260 assert!((len - 2.0).abs() < 0.000001);
1261}
1262
1263#[test]
1264fn derivatives() {
1265 let c1 = QuadraticBezierSegment {
1266 from: Point::new(1.0, 1.0),
1267 ctrl: Point::new(2.0, 1.0),
1268 to: Point::new(2.0, 2.0),
1269 };
1270
1271 assert_eq!(c1.dy(0.0), 0.0);
1272 assert_eq!(c1.dx(1.0), 0.0);
1273 assert_eq!(c1.dy(0.5), c1.dx(0.5));
1274}
1275
1276#[test]
1277fn fat_line() {
1278 use crate::point;
1279
1280 let c1 = QuadraticBezierSegment {
1281 from: point(1.0f32, 2.0),
1282 ctrl: point(1.0, 3.0),
1283 to: point(11.0, 12.0),
1284 };
1285
1286 let (l1, l2) = c1.fat_line();
1287
1288 for i in 0..100 {
1289 let t = i as f32 / 99.0;
1290 assert!(l1.signed_distance_to_point(&c1.sample(t)) >= -0.000001);
1291 assert!(l2.signed_distance_to_point(&c1.sample(t)) <= 0.000001);
1292 }
1293}
1294
1295#[test]
1296fn is_linear() {
1297 let mut angle = 0.0;
1298 let center = Point::new(1000.0, -700.0);
1299 for _ in 0..100 {
1300 for i in 0..10 {
1301 let (sin, cos) = f64::sin_cos(angle);
1302 let endpoint = Vector::new(cos * 100.0, sin * 100.0);
1303 let curve = QuadraticBezierSegment {
1304 from: center - endpoint,
1305 ctrl: center + endpoint.lerp(-endpoint, i as f64 / 9.0),
1306 to: center + endpoint,
1307 };
1308
1309 assert!(curve.is_linear(1e-10));
1310 }
1311 angle += 0.001;
1312 }
1313}
1314
1315#[test]
1316fn test_flattening() {
1317 use crate::point;
1318
1319 let c1 = QuadraticBezierSegment {
1320 from: point(0.0, 0.0),
1321 ctrl: point(5.0, 0.0),
1322 to: point(5.0, 5.0),
1323 };
1324
1325 let c2 = QuadraticBezierSegment {
1326 from: point(0.0, 0.0),
1327 ctrl: point(50.0, 0.0),
1328 to: point(50.0, 50.0),
1329 };
1330
1331 let c3 = QuadraticBezierSegment {
1332 from: point(0.0, 0.0),
1333 ctrl: point(100.0, 100.0),
1334 to: point(5.0, 0.0),
1335 };
1336
1337 fn check_tolerance(curve: &QuadraticBezierSegment<f64>, tolerance: f64) {
1338 let mut c = curve.clone();
1339 loop {
1340 let t = c.flattening_step(tolerance);
1341 if t >= 1.0 {
1342 break;
1343 }
1344 let (before, after) = c.split(t);
1345 let mid_point = before.sample(0.5);
1346 let distance = before
1347 .baseline()
1348 .to_line()
1349 .equation()
1350 .distance_to_point(&mid_point);
1351 assert!(distance <= tolerance);
1352 c = after;
1353 }
1354 }
1355
1356 check_tolerance(&c1, 1.0);
1357 check_tolerance(&c1, 0.1);
1358 check_tolerance(&c1, 0.01);
1359 check_tolerance(&c1, 0.001);
1360 check_tolerance(&c1, 0.0001);
1361
1362 check_tolerance(&c2, 1.0);
1363 check_tolerance(&c2, 0.1);
1364 check_tolerance(&c2, 0.01);
1365 check_tolerance(&c2, 0.001);
1366 check_tolerance(&c2, 0.0001);
1367
1368 check_tolerance(&c3, 1.0);
1369 check_tolerance(&c3, 0.1);
1370 check_tolerance(&c3, 0.01);
1371 check_tolerance(&c3, 0.001);
1372 check_tolerance(&c3, 0.0001);
1373}
1374
1375#[test]
1376fn test_flattening_empty_curve() {
1377 use crate::point;
1378
1379 let curve = QuadraticBezierSegment {
1380 from: point(0.0, 0.0),
1381 ctrl: point(0.0, 0.0),
1382 to: point(0.0, 0.0),
1383 };
1384
1385 let mut iter = FlattenedT::new(&curve, 0.1);
1386
1387 assert_eq!(iter.next(), Some(1.0));
1388 assert_eq!(iter.next(), None);
1389
1390 let mut count: u32 = 0;
1391 curve.for_each_flattened(0.1, &mut |_| count += 1);
1392 assert_eq!(count, 1);
1393}
1394
1395#[test]
1396fn test_flattening_straight_line() {
1397 use crate::point;
1398
1399 let curve = QuadraticBezierSegment {
1400 from: point(0.0, 0.0),
1401 ctrl: point(10.0, 0.0),
1402 to: point(20.0, 0.0),
1403 };
1404
1405 let mut iter = FlattenedT::new(&curve, 0.1);
1406
1407 assert_eq!(iter.next(), Some(1.0));
1408 assert!(iter.next().is_none());
1409
1410 let mut count: u32 = 0;
1411 curve.for_each_flattened(0.1, &mut |_| count += 1);
1412 assert_eq!(count, 1);
1413}
1414
1415#[test]
1416fn issue_678() {
1417 let points = [
1418 [-7768.80859375f32, -35563.80859375],
1419 [-38463.125, -10941.41796875],
1420 [-21846.12890625, -13518.1953125],
1421 [-11727.439453125, -22080.33203125],
1422 ];
1423
1424 let quadratic = QuadraticBezierSegment {
1425 from: Point::new(points[0][0], points[0][1]),
1426 ctrl: Point::new(points[1][0], points[1][1]),
1427 to: Point::new(points[2][0], points[2][1]),
1428 };
1429
1430 let line = Line {
1431 point: Point::new(points[3][0], points[3][1]),
1432 vector: Vector::new(-0.5, -0.5).normalize(),
1433 };
1434
1435 let intersections = quadratic.line_intersections(&line);
1436 std::println!("{intersections:?}");
1437
1438 assert_eq!(intersections.len(), 1);
1439}
1440
1441#[test]
1442fn line_intersections_t() {
1443 let curve = QuadraticBezierSegment {
1444 from: point(0.0f64, 0.0),
1445 ctrl: point(100.0, 0.0),
1446 to: point(100.0, 500.0),
1447 };
1448 let cubic = curve.to_cubic();
1449
1450 let line = Line {
1451 point: point(0.0, -50.0),
1452 vector: crate::vector(100.0, 500.0),
1453 };
1454
1455 let mut i1 = curve.line_intersections_t(&line);
1456 let mut i2 = curve.to_cubic().line_intersections_t(&line);
1457
1458 use std::cmp::Ordering::{Equal, Greater, Less};
1459 i1.sort_by(|a, b| {
1460 if a == b {
1461 Equal
1462 } else if a > b {
1463 Greater
1464 } else {
1465 Less
1466 }
1467 });
1468 i2.sort_by(|a, b| {
1469 if a == b {
1470 Equal
1471 } else if a > b {
1472 Greater
1473 } else {
1474 Less
1475 }
1476 });
1477
1478 for (t1, t2) in i1.iter().zip(i2.iter()) {
1479 use euclid::approxeq::ApproxEq;
1480 let p1 = curve.sample(*t1);
1481 let p2 = cubic.sample(*t2);
1482 assert!(p1.approx_eq(&p2), "{:?} == {:?}", p1, p2);
1483 }
1484 assert_eq!(i2.len(), 2);
1485 assert_eq!(i1.len(), 2);
1486}
1487
1488#[test]
1489fn drag() {
1490 let curve = QuadraticBezierSegment {
1491 from: point(0.0f32, 0.0),
1492 ctrl: point(100.0, 0.0),
1493 to: point(100.0, 100.0),
1494 };
1495
1496 for t in [0.5, 0.25, 0.1, 0.4, 0.7] {
1497 let target = point(0.0, 10.0);
1498
1499 let dragged = curve.drag(t, target);
1500
1501 use euclid::approxeq::ApproxEq;
1502 let p1 = dragged.sample(t);
1503 assert!(
1504 p1.approx_eq_eps(&target, &point(0.001, 0.001)),
1505 "{:?} == {:?}",
1506 p1,
1507 target
1508 );
1509 }
1510}
1511
1512#[test]
1513fn arc_length() {
1514 let curves = [
1515 QuadraticBezierSegment {
1516 from: point(0.0f64, 0.0),
1517 ctrl: point(100.0, 0.0),
1518 to: point(0.0, 100.0),
1519 },
1520 QuadraticBezierSegment {
1521 from: point(0.0, 0.0),
1522 ctrl: point(100.0, 0.0),
1523 to: point(200.0, 0.0),
1524 },
1525 QuadraticBezierSegment {
1526 from: point(100.0, 0.0),
1527 ctrl: point(0.0, 0.0),
1528 to: point(50.0, 1.0),
1529 },
1530 ];
1531
1532 for (idx, curve) in curves.iter().enumerate() {
1533 let length = curve.length();
1534 let mut accum = 0.0;
1535 curve.for_each_flattened(0.00000001, &mut |line| {
1536 accum += line.length();
1537 });
1538
1539 assert!(
1540 (length - accum).abs() < 0.00001,
1541 "curve {:?}, {:?} == {:?}",
1542 idx,
1543 length,
1544 accum
1545 );
1546 }
1547}