lyon_geom/
quadratic_bezier.rs

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/// A 2d curve segment defined by three points: the beginning of the segment, a control
13/// point and the end of the segment.
14///
15/// The curve is defined by equation:
16/// ```∀ t ∈ [0..1],  P(t) = (1 - t)² * from + 2 * (1 - t) * t * ctrl + t² * to```
17#[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    /// Sample the curve at t (expecting t between 0 and 1).
35    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    /// Sample the x coordinate of the curve at t (expecting t between 0 and 1).
44    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    /// Sample the y coordinate of the curve at t (expecting t between 0 and 1).
53    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    /// Sample the curve's derivative at t (expecting t between 0 and 1).
67    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    /// Sample the x coordinate of the curve's derivative at t (expecting t between 0 and 1).
73    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    /// Sample the y coordinate of the curve's derivative at t (expecting t between 0 and 1).
79    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    /// Swap the beginning and the end of the segment.
85    pub fn flip(&self) -> Self {
86        QuadraticBezierSegment {
87            from: self.to,
88            ctrl: self.ctrl,
89            to: self.from,
90        }
91    }
92
93    /// Find the advancement of the y-most position in the curve.
94    ///
95    /// This returns the advancement along the curve, not the actual y position.
96    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    /// Find the advancement of the y-least position in the curve.
112    ///
113    /// This returns the advancement along the curve, not the actual y position.
114    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    /// Return the y inflection point or None if this curve is y-monotonic.
130    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    /// Find the advancement of the x-most position in the curve.
144    ///
145    /// This returns the advancement along the curve, not the actual x position.
146    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    /// Find the advancement of the x-least position in the curve.
162    ///
163    /// This returns the advancement along the curve, not the actual x position.
164    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    /// Return the x inflection point or None if this curve is x-monotonic.
180    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    /// Return the sub-curve inside a given range of t.
194    ///
195    /// This is equivalent splitting at the range's end points.
196    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    /// Split this curve into two sub-curves.
208    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    /// Return the curve before the split point.
226    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    /// Return the curve after the split point.
235    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    /// Elevate this curve to a third order bézier.
244    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    /// Returns whether the curve can be approximated with a single point, given
262    /// a tolerance threshold.
263    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    /// Returns true if the curve can be approximated with a single line segment
270    /// given a tolerance threshold.
271    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    /// Computes a "fat line" of this segment.
285    ///
286    /// A fat line is two conservative lines between which the segment
287    /// is fully contained.
288    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    /// Applies the transform to this curve and returns the results.
300    #[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    /// Find the interval of the beginning of the curve that can be approximated with a
310    /// line segment.
311    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    /// 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    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    /// Compute a flattened approximation of the curve, invoking a callback at
362    /// each step.
363    ///
364    /// The `tolerance` parameter defines the maximum distance between the curve and
365    /// its approximation.
366    ///
367    /// The end of the t parameter range at the final segment is guaranteed to be equal to `1.0`.
368    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    /// Returns the flattened representation of the curve as an iterator, starting *after* the
394    /// current point.
395    pub fn flattened(&self, tolerance: S) -> Flattened<S> {
396        Flattened::new(self, tolerance)
397    }
398    /// Returns the flattened representation of the curve as an iterator, starting *after* the
399    /// current point.
400    pub fn flattened_t(&self, tolerance: S) -> FlattenedT<S> {
401        FlattenedT::new(self, tolerance)
402    }
403
404    /// Invokes a callback for each monotonic part of the segment.
405    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            // In extreme cases the same point can be an x and y inflection point.
430            if t != start {
431                cb(start..t);
432                start = t
433            }
434        }
435
436        cb(start..S::ONE);
437    }
438
439    /// Invokes a callback for each monotonic part of the segment.
440    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            // Due to finite precision the split may actually result in sub-curves
447            // that are almost but not-quite monotonic. Make sure they actually are.
448            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    /// Invokes a callback for each y-monotonic part of the segment.
459    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    /// Invokes a callback for each y-monotonic part of the segment.
475    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    /// Invokes a callback for each x-monotonic part of the segment.
492    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    /// Invokes a callback for each x-monotonic part of the segment.
508    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                // Due to finite precision the split may actually result in sub-curves
516                // that are almost but not-quite monotonic. Make sure they actually are.
517                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    /// Returns a triangle containing this curve segment.
533    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    /// Returns a conservative rectangle that contains the curve.
542    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    /// Returns a conservative range of x that contains this curve.
553    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    /// Returns a conservative range of y that contains this curve.
561    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    /// Returns the smallest rectangle the curve is contained in
569    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    /// Returns the smallest range of x that contains this curve.
580    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    /// Returns the smallest range of y that contains this curve.
588    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    /// Returns whether this segment is monotonic on the x axis.
596    pub fn is_x_monotonic(&self) -> bool {
597        self.local_x_extremum_t().is_none()
598    }
599
600    /// Returns whether this segment is monotonic on the y axis.
601    pub fn is_y_monotonic(&self) -> bool {
602        self.local_y_extremum_t().is_none()
603    }
604
605    /// Returns whether this segment is fully monotonic.
606    pub fn is_monotonic(&self) -> bool {
607        self.is_x_monotonic() && self.is_y_monotonic()
608    }
609
610    /// Computes the intersections (if any) between this segment a line.
611    ///
612    /// The result is provided in the form of the `t` parameters of each
613    /// point along curve. To get the intersection points, sample the curve
614    /// at the corresponding values.
615    pub fn line_intersections_t(&self, line: &Line<S>) -> ArrayVec<S, 2> {
616        // take the quadratic bezier formulation and inject it in
617        // the line equation ax + by + c = 0.
618        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        // Solve "(i - 2j + k)t² + (2j - 2i)t + (i + c) = 0"
623        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            // Linear equation bt + c = 0.
631            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            // To avoid potential float precision issues when b is close to
641            // sqrt_delta, we exploit the fact that given the roots t1 and t2,
642            // t2 = c / (a * t1) and t1 = c / (a * t2).
643            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    /// Computes the intersection points (if any) between this segment a line.
665    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    /// Computes the intersections (if any) between this segment and a line segment.
677    ///
678    /// The result is provided in the form of the `t` parameters of each
679    /// point along curve and segment. To get the intersection points, sample
680    /// the segments at the corresponding values.
681    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                // Don't take intersections that are on endpoints of both curves at the same time.
714                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    /// Computes the intersection points (if any) between this segment a line segment.
734    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    /// Analytic solution to finding the closest point on the curve to `pos`.
746    pub fn closest_point(&self, pos: Point<S>) -> S {
747        // We are looking for the points in the curve where the line passing through pos
748        // and these points are perpendicular to the curve.
749        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        // Polynomial coefficients
754        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    /// Returns the shortest distance between this segment and a point.
783    pub fn distance_to_point(&self, pos: Point<S>) -> S {
784        (self.sample(self.closest_point(pos)) - pos).length()
785    }
786
787    /// Returns the shortest squared distance between this segment and a point.
788    ///
789    /// May be useful to avoid the cost of a square root when comparing against a distance
790    /// that can be squared instead.
791    pub fn square_distance_to_point(&self, pos: Point<S>) -> S {
792        (self.sample(self.closest_point(pos)) - pos).square_length()
793    }
794
795    // Returns a quadratic bézier curve built by dragging this curve's point at `t`
796    // to a new position without moving the endpoints.
797    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    /// Computes the length of this segment.
815    ///
816    /// Implements Raph Levien's analytical approach described in
817    /// https://raphlinus.github.io/curves/2018/12/28/bezier-arclength.html
818    pub fn length(&self) -> S {
819        // This is ported from kurbo's implementation.
820        // https://github.com/linebender/kurbo/blob/d0b956b47f219ba2303b4e2f2d904ea7b946e783/src/quadbez.rs#L239
821        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            // The segment is almost straight.
827            //
828            // Legendre-Gauss quadrature using formula from Behdad
829            // in https://github.com/Pomax/BezierInfo-2/issues/77
830            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            // The curve has a sharp turns.
854            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    // This is to conform to the `impl_segment!` macro
865    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
898// TODO(breaking change): This should not have been a public struct.
899// It's not useful to users of the crate but removing it is a breaking change so it
900// stays empty for now.
901pub 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/// The polynomial form of a quadratic bézier segment.
912///
913/// The `sample` implementation uses Horner's method and tends to be faster than
914/// `QuadraticBezierSegment::sample`.
915#[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        // Horner's method.
926        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
936/// Computes the number of line segments required to build a flattened approximation
937/// of the curve with segments placed at regular `t` intervals.
938fn 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    // Avoid two square roots using a lookup table that contains
948    // i^4 for  i in 1..25.
949    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 the value we are looking for is within the LUT, take the fast path
958    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    // Otherwise fall back to computing via two square roots.
968    err4.sqrt().sqrt().max(S::ONE)
969}
970
971/// A flattening iterator for quadratic bézier segments.
972///
973/// Yields points at each iteration.
974pub 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
1028// TODO(breaking change): is this useful? Either remove
1029// it or add the equivalent for cubic curves.
1030/// A flattening iterator for quadratic bézier segments.
1031///
1032/// Yields the curve parameter at each iteration.
1033pub 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    // Sanity check: aligned points so both these curves are straight lines
1243    // that go form (0.0, 0.0) to (2.0, 0.0).
1244
1245    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}