1use crate::scalar::Scalar;
2use crate::segment::{BoundingBox, 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 ///
338 /// This implements the algorithm described by Raph Levien at
339 /// <https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html>
340 pub fn for_each_flattened<F>(&self, tolerance: S, callback: &mut F)
341 where
342 F: FnMut(&LineSegment<S>),
343 {
344 self.for_each_flattened_with_t(tolerance, &mut |segment, _| callback(segment));
345 }
346
347 /// Compute a flattened approximation of the curve, invoking a callback at
348 /// each step.
349 ///
350 /// The `tolerance` parameter defines the maximum distance between the curve and
351 /// its approximation.
352 ///
353 /// The end of the t parameter range at the final segment is guaranteed to be equal to `1.0`.
354 ///
355 /// This implements the algorithm described by Raph Levien at
356 /// <https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html>
357 pub fn for_each_flattened_with_t<F>(&self, tolerance: S, callback: &mut F)
358 where
359 F: FnMut(&LineSegment<S>, Range<S>),
360 {
361 let params = FlatteningParameters::new(self, tolerance);
362
363 let mut i = S::ONE;
364 let mut from = self.from;
365 let mut t_from = S::ZERO;
366 for _ in 1..params.count.to_u32().unwrap() {
367 let t = params.t_at_iteration(i);
368 i += S::ONE;
369 let s = LineSegment {
370 from,
371 to: self.sample(t),
372 };
373
374 callback(&s, t_from..t);
375 from = s.to;
376 t_from = t;
377 }
378
379 let s = LineSegment { from, to: self.to };
380
381 callback(&s, t_from..S::ONE);
382 }
383
384 /// Returns the flattened representation of the curve as an iterator, starting *after* the
385 /// current point.
386 pub fn flattened(&self, tolerance: S) -> Flattened<S> {
387 Flattened::new(self, tolerance)
388 }
389 /// Returns the flattened representation of the curve as an iterator, starting *after* the
390 /// current point.
391 pub fn flattened_t(&self, tolerance: S) -> FlattenedT<S> {
392 FlattenedT::new(self, tolerance)
393 }
394
395 /// Invokes a callback for each monotonic part of the segment.
396 pub fn for_each_monotonic_range<F>(&self, cb: &mut F)
397 where
398 F: FnMut(Range<S>),
399 {
400 let mut t0 = self.local_x_extremum_t();
401 let mut t1 = self.local_y_extremum_t();
402
403 let swap = match (t0, t1) {
404 (Some(tx), Some(ty)) => tx > ty,
405 _ => false,
406 };
407
408 if swap {
409 mem::swap(&mut t0, &mut t1);
410 }
411
412 let mut start = S::ZERO;
413
414 if let Some(t) = t0 {
415 cb(start..t);
416 start = t;
417 }
418
419 if let Some(t) = t1 {
420 // In extreme cases the same point can be an x and y inflection point.
421 if t != start {
422 cb(start..t);
423 start = t
424 }
425 }
426
427 cb(start..S::ONE);
428 }
429
430 /// Invokes a callback for each monotonic part of the segment.
431 pub fn for_each_monotonic<F>(&self, cb: &mut F)
432 where
433 F: FnMut(&QuadraticBezierSegment<S>),
434 {
435 self.for_each_monotonic_range(&mut |range| {
436 let mut sub = self.split_range(range);
437 // Due to finite precision the split may actually result in sub-curves
438 // that are almost but not-quite monotonic. Make sure they actually are.
439 let min_x = sub.from.x.min(sub.to.x);
440 let max_x = sub.from.x.max(sub.to.x);
441 let min_y = sub.from.y.min(sub.to.y);
442 let max_y = sub.from.y.max(sub.to.y);
443 sub.ctrl.x = sub.ctrl.x.max(min_x).min(max_x);
444 sub.ctrl.y = sub.ctrl.y.max(min_y).min(max_y);
445 cb(&sub);
446 });
447 }
448
449 /// Invokes a callback for each y-monotonic part of the segment.
450 pub fn for_each_y_monotonic_range<F>(&self, cb: &mut F)
451 where
452 F: FnMut(Range<S>),
453 {
454 match self.local_y_extremum_t() {
455 Some(t) => {
456 cb(S::ZERO..t);
457 cb(t..S::ONE);
458 }
459 None => {
460 cb(S::ZERO..S::ONE);
461 }
462 }
463 }
464
465 /// Invokes a callback for each y-monotonic part of the segment.
466 pub fn for_each_y_monotonic<F>(&self, cb: &mut F)
467 where
468 F: FnMut(&QuadraticBezierSegment<S>),
469 {
470 match self.local_y_extremum_t() {
471 Some(t) => {
472 let (a, b) = self.split(t);
473 cb(&a);
474 cb(&b);
475 }
476 None => {
477 cb(self);
478 }
479 }
480 }
481
482 /// Invokes a callback for each x-monotonic part of the segment.
483 pub fn for_each_x_monotonic_range<F>(&self, cb: &mut F)
484 where
485 F: FnMut(Range<S>),
486 {
487 match self.local_x_extremum_t() {
488 Some(t) => {
489 cb(S::ZERO..t);
490 cb(t..S::ONE);
491 }
492 None => {
493 cb(S::ZERO..S::ONE);
494 }
495 }
496 }
497
498 /// Invokes a callback for each x-monotonic part of the segment.
499 pub fn for_each_x_monotonic<F>(&self, cb: &mut F)
500 where
501 F: FnMut(&QuadraticBezierSegment<S>),
502 {
503 match self.local_x_extremum_t() {
504 Some(t) => {
505 let (mut a, mut b) = self.split(t);
506 // Due to finite precision the split may actually result in sub-curves
507 // that are almost but not-quite monotonic. Make sure they actually are.
508 let a_min = a.from.x.min(a.to.x);
509 let a_max = a.from.x.max(a.to.x);
510 let b_min = b.from.x.min(b.to.x);
511 let b_max = b.from.x.max(b.to.x);
512 a.ctrl.x = a.ctrl.x.max(a_min).min(a_max);
513 b.ctrl.x = b.ctrl.x.max(b_min).min(b_max);
514 cb(&a);
515 cb(&b);
516 }
517 None => {
518 cb(self);
519 }
520 }
521 }
522
523 /// Returns a triangle containing this curve segment.
524 pub fn bounding_triangle(&self) -> Triangle<S> {
525 Triangle {
526 a: self.from,
527 b: self.ctrl,
528 c: self.to,
529 }
530 }
531
532 /// Returns a conservative rectangle that contains the curve.
533 pub fn fast_bounding_box(&self) -> Box2D<S> {
534 let (min_x, max_x) = self.fast_bounding_range_x();
535 let (min_y, max_y) = self.fast_bounding_range_y();
536
537 Box2D {
538 min: point(min_x, min_y),
539 max: point(max_x, max_y),
540 }
541 }
542
543 /// Returns a conservative range of x that contains this curve.
544 pub fn fast_bounding_range_x(&self) -> (S, S) {
545 let min_x = self.from.x.min(self.ctrl.x).min(self.to.x);
546 let max_x = self.from.x.max(self.ctrl.x).max(self.to.x);
547
548 (min_x, max_x)
549 }
550
551 /// Returns a conservative range of y that contains this curve.
552 pub fn fast_bounding_range_y(&self) -> (S, S) {
553 let min_y = self.from.y.min(self.ctrl.y).min(self.to.y);
554 let max_y = self.from.y.max(self.ctrl.y).max(self.to.y);
555
556 (min_y, max_y)
557 }
558
559 /// Returns the smallest rectangle the curve is contained in
560 pub fn bounding_box(&self) -> Box2D<S> {
561 let (min_x, max_x) = self.bounding_range_x();
562 let (min_y, max_y) = self.bounding_range_y();
563
564 Box2D {
565 min: point(min_x, min_y),
566 max: point(max_x, max_y),
567 }
568 }
569
570 /// Returns the smallest range of x that contains this curve.
571 pub fn bounding_range_x(&self) -> (S, S) {
572 let min_x = self.x(self.x_minimum_t());
573 let max_x = self.x(self.x_maximum_t());
574
575 (min_x, max_x)
576 }
577
578 /// Returns the smallest range of y that contains this curve.
579 pub fn bounding_range_y(&self) -> (S, S) {
580 let min_y = self.y(self.y_minimum_t());
581 let max_y = self.y(self.y_maximum_t());
582
583 (min_y, max_y)
584 }
585
586 /// Returns whether this segment is monotonic on the x axis.
587 pub fn is_x_monotonic(&self) -> bool {
588 self.local_x_extremum_t().is_none()
589 }
590
591 /// Returns whether this segment is monotonic on the y axis.
592 pub fn is_y_monotonic(&self) -> bool {
593 self.local_y_extremum_t().is_none()
594 }
595
596 /// Returns whether this segment is fully monotonic.
597 pub fn is_monotonic(&self) -> bool {
598 self.is_x_monotonic() && self.is_y_monotonic()
599 }
600
601 /// Computes the intersections (if any) between this segment a line.
602 ///
603 /// The result is provided in the form of the `t` parameters of each
604 /// point along curve. To get the intersection points, sample the curve
605 /// at the corresponding values.
606 pub fn line_intersections_t(&self, line: &Line<S>) -> ArrayVec<S, 2> {
607 // take the quadratic bezier formulation and inject it in
608 // the line equation ax + by + c = 0.
609 let eqn = line.equation();
610 let i = eqn.a() * self.from.x + eqn.b() * self.from.y;
611 let j = eqn.a() * self.ctrl.x + eqn.b() * self.ctrl.y;
612 let k = eqn.a() * self.to.x + eqn.b() * self.to.y;
613 // Solve "(i - 2j + k)t² + (2j - 2i)t + (i + c) = 0"
614 let a = i - j - j + k;
615 let b = j + j - i - i;
616 let c = i + eqn.c();
617
618 let mut result = ArrayVec::new();
619
620 if a == S::ZERO {
621 // Linear equation bt + c = 0.
622 let t = c / b;
623 if t >= S::ZERO && t <= S::ONE {
624 result.push(t);
625 return result;
626 }
627 }
628
629 let delta = b * b - S::FOUR * a * c;
630 if delta >= S::ZERO {
631 // To avoid potential float precision issues when b is close to
632 // sqrt_delta, we exploit the fact that given the roots t1 and t2,
633 // t2 = c / (a * t1) and t1 = c / (a * t2).
634 let sqrt_delta = S::sqrt(delta);
635 let s_sqrt_delta = -b.signum() * sqrt_delta;
636 let mut t1 = (-b + s_sqrt_delta) / (S::TWO * a);
637 let mut t2 = c / (a * t1);
638
639 if t1 > t2 {
640 mem::swap(&mut t1, &mut t2);
641 }
642
643 if t1 >= S::ZERO && t1 <= S::ONE {
644 result.push(t1);
645 }
646
647 if t2 >= S::ZERO && t2 <= S::ONE && t1 != t2 {
648 result.push(t2);
649 }
650 }
651
652 result
653 }
654
655 /// Computes the intersection points (if any) between this segment a line.
656 pub fn line_intersections(&self, line: &Line<S>) -> ArrayVec<Point<S>, 2> {
657 let intersections = self.line_intersections_t(line);
658
659 let mut result = ArrayVec::new();
660 for t in intersections {
661 result.push(self.sample(t));
662 }
663
664 result
665 }
666
667 /// Computes the intersections (if any) between this segment and a line segment.
668 ///
669 /// The result is provided in the form of the `t` parameters of each
670 /// point along curve and segment. To get the intersection points, sample
671 /// the segments at the corresponding values.
672 pub fn line_segment_intersections_t(&self, segment: &LineSegment<S>) -> ArrayVec<(S, S), 2> {
673 if !self
674 .fast_bounding_box()
675 .inflate(S::EPSILON, S::EPSILON)
676 .intersects(&segment.bounding_box().inflate(S::EPSILON, S::EPSILON))
677 {
678 return ArrayVec::new();
679 }
680
681 let intersections = self.line_intersections_t(&segment.to_line());
682
683 let mut result = ArrayVec::new();
684 if intersections.is_empty() {
685 return result;
686 }
687
688 let seg_is_mostly_vertical =
689 S::abs(segment.from.y - segment.to.y) >= S::abs(segment.from.x - segment.to.x);
690 let (seg_long_axis_min, seg_long_axis_max) = if seg_is_mostly_vertical {
691 segment.bounding_range_y()
692 } else {
693 segment.bounding_range_x()
694 };
695
696 for t in intersections {
697 let intersection_xy = if seg_is_mostly_vertical {
698 self.y(t)
699 } else {
700 self.x(t)
701 };
702 if intersection_xy >= seg_long_axis_min && intersection_xy <= seg_long_axis_max {
703 let t2 = (self.sample(t) - segment.from).length() / segment.length();
704 // Don't take intersections that are on endpoints of both curves at the same time.
705 if (t != S::ZERO && t != S::ONE) || (t2 != S::ZERO && t2 != S::ONE) {
706 result.push((t, t2));
707 }
708 }
709 }
710
711 result
712 }
713
714 #[inline]
715 pub fn from(&self) -> Point<S> {
716 self.from
717 }
718
719 #[inline]
720 pub fn to(&self) -> Point<S> {
721 self.to
722 }
723
724 /// Computes the intersection points (if any) between this segment a line segment.
725 pub fn line_segment_intersections(&self, segment: &LineSegment<S>) -> ArrayVec<Point<S>, 2> {
726 let intersections = self.line_segment_intersections_t(segment);
727
728 let mut result = ArrayVec::new();
729 for (t, _) in intersections {
730 result.push(self.sample(t));
731 }
732
733 result
734 }
735
736 /// Analytic solution to finding the closest point on the curve to `pos`.
737 pub fn closest_point(&self, pos: Point<S>) -> S {
738 // We are looking for the points in the curve where the line passing through pos
739 // and these points are perpendicular to the curve.
740 let a = self.from - pos;
741 let b = self.ctrl - self.from;
742 let c = self.from + self.to.to_vector() - self.ctrl * S::TWO;
743
744 // Polynomial coefficients
745 let c0 = c.dot(c);
746 let c1 = b.dot(c) * S::THREE;
747 let c2 = b.dot(b) * S::TWO + a.dot(c);
748 let c3 = a.dot(b);
749
750 let roots = crate::utils::cubic_polynomial_roots(c0, c1, c2, c3);
751
752 let mut sq_dist = a.square_length();
753 let mut t = S::ZERO;
754 let to_dist = (self.to - pos).square_length();
755 if to_dist < sq_dist {
756 sq_dist = to_dist;
757 t = S::ONE
758 }
759 for root in roots {
760 if root >= S::ZERO && root <= S::ONE {
761 let p = self.sample(root);
762 let d = (pos - p).square_length();
763 if d < sq_dist {
764 sq_dist = d;
765 t = root;
766 }
767 }
768 }
769
770 t
771 }
772
773 /// Returns the shortest distance between this segment and a point.
774 pub fn distance_to_point(&self, pos: Point<S>) -> S {
775 (self.sample(self.closest_point(pos)) - pos).length()
776 }
777
778 /// Returns the shortest squared distance between this segment and a point.
779 ///
780 /// May be useful to avoid the cost of a square root when comparing against a distance
781 /// that can be squared instead.
782 pub fn square_distance_to_point(&self, pos: Point<S>) -> S {
783 (self.sample(self.closest_point(pos)) - pos).square_length()
784 }
785
786 // Returns a quadratic bézier curve built by dragging this curve's point at `t`
787 // to a new position without moving the endpoints.
788 pub fn drag(&self, t: S, new_position: Point<S>) -> Self {
789 let t2 = t * t;
790 let one_t = S::ONE - t;
791 let one_t2 = one_t * one_t;
792
793 let u = t2 / (t2 + one_t2);
794 let c = self.from.lerp(self.to, u);
795
796 let inv_r = S::abs((t2 + one_t2) / (t2 + one_t2 - S::ONE));
797
798 QuadraticBezierSegment {
799 from: self.from,
800 ctrl: new_position + (new_position - c) * inv_r,
801 to: self.to,
802 }
803 }
804
805 /// Computes the length of this segment.
806 ///
807 /// Implements Raph Levien's analytical approach described in
808 /// https://raphlinus.github.io/curves/2018/12/28/bezier-arclength.html
809 pub fn length(&self) -> S {
810 // This is ported from kurbo's implementation.
811 // https://github.com/linebender/kurbo/blob/d0b956b47f219ba2303b4e2f2d904ea7b946e783/src/quadbez.rs#L239
812 let d2 = self.from - self.ctrl * S::TWO + self.to.to_vector();
813 let d1 = self.ctrl - self.from;
814 let a = d2.square_length();
815 let c = d1.square_length();
816 if a < S::value(1e-4) * c {
817 // The segment is almost straight.
818 //
819 // Legendre-Gauss quadrature using formula from Behdad
820 // in https://github.com/Pomax/BezierInfo-2/issues/77
821 let v0 = (self.from.to_vector() * S::value(-0.492943519233745)
822 + self.ctrl.to_vector() * S::value(0.430331482911935)
823 + self.to.to_vector() * S::value(0.0626120363218102))
824 .length();
825 let v1 = ((self.to - self.from) * S::value(0.4444444444444444)).length();
826 let v2 = (self.from.to_vector() * S::value(-0.0626120363218102)
827 + self.ctrl.to_vector() * S::value(-0.430331482911935)
828 + self.to.to_vector() * S::value(0.492943519233745))
829 .length();
830 return v0 + v1 + v2;
831 }
832
833 let b = S::TWO * d2.dot(d1);
834
835 let sqr_abc = (a + b + c).sqrt();
836 let a2 = a.powf(-S::HALF);
837 let a32 = a2.powi(3);
838 let c2 = S::TWO * c.sqrt();
839 let ba_c2 = b * a2 + c2;
840
841 let v0 = S::HALF * S::HALF * a2 * a2 * b * (S::TWO * sqr_abc - c2) + sqr_abc;
842
843 if ba_c2 < S::EPSILON {
844 // The curve has a sharp turns.
845 v0
846 } else {
847 v0 + S::HALF
848 * S::HALF
849 * a32
850 * (S::FOUR * c * a - b * b)
851 * (((S::TWO * a + b) * a2 + S::TWO * sqr_abc) / ba_c2).ln()
852 }
853 }
854
855 // This is to conform to the `impl_segment!` macro
856 fn approximate_length(&self, _tolerance: S) -> S {
857 self.length()
858 }
859
860 pub fn to_f32(&self) -> QuadraticBezierSegment<f32> {
861 QuadraticBezierSegment {
862 from: self.from.to_f32(),
863 ctrl: self.ctrl.to_f32(),
864 to: self.to.to_f32(),
865 }
866 }
867
868 pub fn to_f64(&self) -> QuadraticBezierSegment<f64> {
869 QuadraticBezierSegment {
870 from: self.from.to_f64(),
871 ctrl: self.ctrl.to_f64(),
872 to: self.to.to_f64(),
873 }
874 }
875}
876
877pub struct FlatteningParameters<S> {
878 count: S,
879 integral_from: S,
880 integral_step: S,
881 inv_integral_from: S,
882 div_inv_integral_diff: S,
883}
884
885impl<S: Scalar> FlatteningParameters<S> {
886 // See https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html
887 pub fn new(curve: &QuadraticBezierSegment<S>, tolerance: S) -> Self {
888 // Checking for the single segment approximation is much cheaper than evaluating
889 // the general flattening approximation.
890 if curve.is_linear(tolerance) {
891 return FlatteningParameters {
892 count: S::ZERO,
893 // This are irrelevant as if count is 0.
894 integral_from: S::ZERO,
895 integral_step: S::ZERO,
896 inv_integral_from: S::ZERO,
897 div_inv_integral_diff: S::ZERO,
898 };
899 }
900
901 // Map the quadratic bézier segment to y = x^2 parabola.
902 let ddx = S::TWO * curve.ctrl.x - curve.from.x - curve.to.x;
903 let ddy = S::TWO * curve.ctrl.y - curve.from.y - curve.to.y;
904 let cross = (curve.to.x - curve.from.x) * ddy - (curve.to.y - curve.from.y) * ddx;
905 let inv_cross = S::ONE / cross;
906 let parabola_from =
907 ((curve.ctrl.x - curve.from.x) * ddx + (curve.ctrl.y - curve.from.y) * ddy) * inv_cross;
908 let parabola_to =
909 ((curve.to.x - curve.ctrl.x) * ddx + (curve.to.y - curve.ctrl.y) * ddy) * inv_cross;
910 // Note, scale can be NaN, for example with straight lines. When it happens the NaN will
911 // propagate to other parameters. We catch it all by setting the iteration count to zero
912 // and leave the rest as garbage.
913 let scale =
914 cross.abs() / (S::sqrt(ddx * ddx + ddy * ddy) * (parabola_to - parabola_from).abs());
915
916 let integral_from = approx_parabola_integral(parabola_from);
917 let integral_to = approx_parabola_integral(parabola_to);
918 let integral_diff = integral_to - integral_from;
919
920 let inv_integral_from = approx_parabola_inv_integral(integral_from);
921 let inv_integral_to = approx_parabola_inv_integral(integral_to);
922 let div_inv_integral_diff = S::ONE / (inv_integral_to - inv_integral_from);
923
924 // We could store this as an integer but the generic code makes that awkward and we'll
925 // use it as a scalar again while iterating, so it's kept as a scalar.
926 let mut count = (S::HALF * integral_diff.abs() * (scale / tolerance).sqrt()).ceil();
927 // If count is NaN the curve can be approximated by a single straight line or a point.
928 if !count.is_finite() {
929 count = S::ZERO;
930 }
931
932 let integral_step = integral_diff / count;
933
934 FlatteningParameters {
935 count,
936 integral_from,
937 integral_step,
938 inv_integral_from,
939 div_inv_integral_diff,
940 }
941 }
942
943 fn t_at_iteration(&self, iteration: S) -> S {
944 let u = approx_parabola_inv_integral(self.integral_from + self.integral_step * iteration);
945 let t = (u - self.inv_integral_from) * self.div_inv_integral_diff;
946
947 t
948 }
949}
950
951/// Compute an approximation to integral (1 + 4x^2) ^ -0.25 dx used in the flattening code.
952fn approx_parabola_integral<S: Scalar>(x: S) -> S {
953 let d: S = S::value(0.67);
954 let quarter: S = S::HALF * S::HALF;
955 x / (S::ONE - d + (d.powi(4) + quarter * x * x).sqrt().sqrt())
956}
957
958/// Approximate the inverse of the function above.
959fn approx_parabola_inv_integral<S: Scalar>(x: S) -> S {
960 let b: S = S::value(0.39);
961 let quarter: S = S::HALF * S::HALF;
962 x * (S::ONE - b + (b * b + quarter * x * x).sqrt())
963}
964
965/// A flattening iterator for quadratic bézier segments.
966///
967/// Yields points at each iteration.
968pub struct Flattened<S> {
969 curve: QuadraticBezierSegment<S>,
970 params: FlatteningParameters<S>,
971 i: S,
972 done: bool,
973}
974
975impl<S: Scalar> Flattened<S> {
976 #[inline]
977 pub(crate) fn new(curve: &QuadraticBezierSegment<S>, tolerance: S) -> Self {
978 let params: FlatteningParameters = FlatteningParameters::new(curve, tolerance);
979
980 Flattened {
981 curve: *curve,
982 params,
983 i: S::ONE,
984 done: false,
985 }
986 }
987}
988
989impl<S: Scalar> Iterator for Flattened<S> {
990 type Item = Point<S>;
991
992 #[inline]
993 fn next(&mut self) -> Option<Point<S>> {
994 if self.done {
995 return None;
996 }
997
998 if self.i >= self.params.count - S::EPSILON {
999 self.done = true;
1000 return Some(self.curve.to);
1001 }
1002
1003 let t = self.params.t_at_iteration(self.i);
1004 self.i += S::ONE;
1005
1006 Some(self.curve.sample(t))
1007 }
1008
1009 #[inline]
1010 fn size_hint(&self) -> (usize, Option<usize>) {
1011 let count = (self.params.count + S::ONE - self.i).to_usize().unwrap();
1012 (count, Some(count))
1013 }
1014}
1015
1016/// A flattening iterator for quadratic bézier segments.
1017///
1018/// Yields the curve parameter at each iteration.
1019pub struct FlattenedT<S> {
1020 params: FlatteningParameters<S>,
1021 i: S,
1022 done: bool,
1023}
1024
1025impl<S: Scalar> FlattenedT<S> {
1026 #[inline]
1027 pub(crate) fn new(curve: &QuadraticBezierSegment<S>, tolerance: S) -> Self {
1028 let params: FlatteningParameters = FlatteningParameters::new(curve, tolerance);
1029 FlattenedT {
1030 i: S::ONE,
1031 params,
1032 done: false,
1033 }
1034 }
1035}
1036
1037impl<S: Scalar> Iterator for FlattenedT<S> {
1038 type Item = S;
1039
1040 #[inline]
1041 fn next(&mut self) -> Option<S> {
1042 if self.done {
1043 return None;
1044 }
1045
1046 if self.i >= self.params.count - S::EPSILON {
1047 self.done = true;
1048 return Some(S::ONE);
1049 }
1050
1051 let t = self.params.t_at_iteration(self.i);
1052 self.i += S::ONE;
1053
1054 Some(t)
1055 }
1056
1057 #[inline]
1058 fn size_hint(&self) -> (usize, Option<usize>) {
1059 let count = (self.params.count + S::ONE - self.i).to_usize().unwrap();
1060 (count, Some(count))
1061 }
1062}
1063
1064impl<S: Scalar> Segment for QuadraticBezierSegment<S> {
1065 impl_segment!(S);
1066
1067 fn for_each_flattened_with_t(
1068 &self,
1069 tolerance: Self::Scalar,
1070 callback: &mut dyn FnMut(&LineSegment<S>, Range<S>),
1071 ) {
1072 self.for_each_flattened_with_t(tolerance, &mut |s: &LineSegment, t: Range| callback(s, t));
1073 }
1074}
1075
1076impl<S: Scalar> BoundingBox for QuadraticBezierSegment<S> {
1077 type Scalar = S;
1078 fn bounding_box(&self) -> Box2D<S> {
1079 self.bounding_box()
1080 }
1081 fn fast_bounding_box(&self) -> Box2D<S> {
1082 self.fast_bounding_box()
1083 }
1084 fn bounding_range_x(&self) -> (S, S) {
1085 self.bounding_range_x()
1086 }
1087 fn bounding_range_y(&self) -> (S, S) {
1088 self.bounding_range_y()
1089 }
1090 fn fast_bounding_range_x(&self) -> (S, S) {
1091 self.fast_bounding_range_x()
1092 }
1093 fn fast_bounding_range_y(&self) -> (S, S) {
1094 self.fast_bounding_range_y()
1095 }
1096}
1097
1098#[test]
1099fn bounding_box_for_monotonic_quadratic_bezier_segment() {
1100 let a = QuadraticBezierSegment {
1101 from: Point::new(0.0, 0.0),
1102 ctrl: Point::new(0.0, 0.0),
1103 to: Point::new(2.0, 0.0),
1104 };
1105
1106 let expected_aabb = Box2D {
1107 min: point(0.0, 0.0),
1108 max: point(2.0, 0.0),
1109 };
1110
1111 let actual_aabb = a.bounding_box();
1112
1113 assert_eq!(expected_aabb, actual_aabb)
1114}
1115
1116#[test]
1117fn fast_bounding_box_for_quadratic_bezier_segment() {
1118 let a = QuadraticBezierSegment {
1119 from: Point::new(0.0, 0.0),
1120 ctrl: Point::new(1.0, 1.0),
1121 to: Point::new(2.0, 0.0),
1122 };
1123
1124 let expected_aabb = Box2D {
1125 min: point(0.0, 0.0),
1126 max: point(2.0, 1.0),
1127 };
1128
1129 let actual_aabb = a.fast_bounding_box();
1130
1131 assert_eq!(expected_aabb, actual_aabb)
1132}
1133
1134#[test]
1135fn minimum_bounding_box_for_quadratic_bezier_segment() {
1136 let a = QuadraticBezierSegment {
1137 from: Point::new(0.0, 0.0),
1138 ctrl: Point::new(1.0, 1.0),
1139 to: Point::new(2.0, 0.0),
1140 };
1141
1142 let expected_aabb = Box2D {
1143 min: point(0.0, 0.0),
1144 max: point(2.0, 0.5),
1145 };
1146
1147 let actual_aabb = a.bounding_box();
1148
1149 assert_eq!(expected_aabb, actual_aabb)
1150}
1151
1152#[test]
1153fn y_maximum_t_for_simple_segment() {
1154 let a = QuadraticBezierSegment {
1155 from: Point::new(0.0, 0.0),
1156 ctrl: Point::new(1.0, 1.0),
1157 to: Point::new(2.0, 0.0),
1158 };
1159
1160 let expected_y_maximum = 0.5;
1161
1162 let actual_y_maximum = a.y_maximum_t();
1163
1164 assert_eq!(expected_y_maximum, actual_y_maximum)
1165}
1166
1167#[test]
1168fn local_y_extremum_for_simple_segment() {
1169 let a = QuadraticBezierSegment {
1170 from: Point::new(0.0, 0.0),
1171 ctrl: Point::new(1.0, 1.0),
1172 to: Point::new(2.0, 0.0),
1173 };
1174
1175 let expected_y_inflection = 0.5;
1176
1177 match a.local_y_extremum_t() {
1178 Some(actual_y_inflection) => assert_eq!(expected_y_inflection, actual_y_inflection),
1179 None => panic!(),
1180 }
1181}
1182
1183#[test]
1184fn y_minimum_t_for_simple_segment() {
1185 let a = QuadraticBezierSegment {
1186 from: Point::new(0.0, 0.0),
1187 ctrl: Point::new(1.0, -1.0),
1188 to: Point::new(2.0, 0.0),
1189 };
1190
1191 let expected_y_minimum = 0.5;
1192
1193 let actual_y_minimum = a.y_minimum_t();
1194
1195 assert_eq!(expected_y_minimum, actual_y_minimum)
1196}
1197
1198#[test]
1199fn x_maximum_t_for_simple_segment() {
1200 let a = QuadraticBezierSegment {
1201 from: Point::new(0.0, 0.0),
1202 ctrl: Point::new(1.0, 1.0),
1203 to: Point::new(0.0, 2.0),
1204 };
1205
1206 let expected_x_maximum = 0.5;
1207
1208 let actual_x_maximum = a.x_maximum_t();
1209
1210 assert_eq!(expected_x_maximum, actual_x_maximum)
1211}
1212
1213#[test]
1214fn local_x_extremum_for_simple_segment() {
1215 let a = QuadraticBezierSegment {
1216 from: Point::new(0.0, 0.0),
1217 ctrl: Point::new(1.0, 1.0),
1218 to: Point::new(0.0, 2.0),
1219 };
1220
1221 let expected_x_inflection = 0.5;
1222
1223 match a.local_x_extremum_t() {
1224 Some(actual_x_inflection) => assert_eq!(expected_x_inflection, actual_x_inflection),
1225 None => panic!(),
1226 }
1227}
1228
1229#[test]
1230fn x_minimum_t_for_simple_segment() {
1231 let a = QuadraticBezierSegment {
1232 from: Point::new(2.0, 0.0),
1233 ctrl: Point::new(1.0, 1.0),
1234 to: Point::new(2.0, 2.0),
1235 };
1236
1237 let expected_x_minimum = 0.5;
1238
1239 let actual_x_minimum = a.x_minimum_t();
1240
1241 assert_eq!(expected_x_minimum, actual_x_minimum)
1242}
1243
1244#[test]
1245fn length_straight_line() {
1246 // Sanity check: aligned points so both these curves are straight lines
1247 // that go form (0.0, 0.0) to (2.0, 0.0).
1248
1249 let len = QuadraticBezierSegment {
1250 from: Point::new(0.0f64, 0.0),
1251 ctrl: Point::new(1.0, 0.0),
1252 to: Point::new(2.0, 0.0),
1253 }
1254 .length();
1255 assert!((len - 2.0).abs() < 0.000001);
1256
1257 let len = CubicBezierSegment {
1258 from: Point::new(0.0f64, 0.0),
1259 ctrl1: Point::new(1.0, 0.0),
1260 ctrl2: Point::new(1.0, 0.0),
1261 to: Point::new(2.0, 0.0),
1262 }
1263 .approximate_length(0.0001);
1264 assert!((len - 2.0).abs() < 0.000001);
1265}
1266
1267#[test]
1268fn derivatives() {
1269 let c1 = QuadraticBezierSegment {
1270 from: Point::new(1.0, 1.0),
1271 ctrl: Point::new(2.0, 1.0),
1272 to: Point::new(2.0, 2.0),
1273 };
1274
1275 assert_eq!(c1.dy(0.0), 0.0);
1276 assert_eq!(c1.dx(1.0), 0.0);
1277 assert_eq!(c1.dy(0.5), c1.dx(0.5));
1278}
1279
1280#[test]
1281fn fat_line() {
1282 use crate::point;
1283
1284 let c1 = QuadraticBezierSegment {
1285 from: point(1.0f32, 2.0),
1286 ctrl: point(1.0, 3.0),
1287 to: point(11.0, 12.0),
1288 };
1289
1290 let (l1, l2) = c1.fat_line();
1291
1292 for i in 0..100 {
1293 let t = i as f32 / 99.0;
1294 assert!(l1.signed_distance_to_point(&c1.sample(t)) >= -0.000001);
1295 assert!(l2.signed_distance_to_point(&c1.sample(t)) <= 0.000001);
1296 }
1297}
1298
1299#[test]
1300fn is_linear() {
1301 let mut angle = 0.0;
1302 let center = Point::new(1000.0, -700.0);
1303 for _ in 0..100 {
1304 for i in 0..10 {
1305 let (sin, cos) = f64::sin_cos(angle);
1306 let endpoint = Vector::new(cos * 100.0, sin * 100.0);
1307 let curve = QuadraticBezierSegment {
1308 from: center - endpoint,
1309 ctrl: center + endpoint.lerp(-endpoint, i as f64 / 9.0),
1310 to: center + endpoint,
1311 };
1312
1313 assert!(curve.is_linear(1e-10));
1314 }
1315 angle += 0.001;
1316 }
1317}
1318
1319#[test]
1320fn test_flattening() {
1321 use crate::point;
1322
1323 let c1 = QuadraticBezierSegment {
1324 from: point(0.0, 0.0),
1325 ctrl: point(5.0, 0.0),
1326 to: point(5.0, 5.0),
1327 };
1328
1329 let c2 = QuadraticBezierSegment {
1330 from: point(0.0, 0.0),
1331 ctrl: point(50.0, 0.0),
1332 to: point(50.0, 50.0),
1333 };
1334
1335 let c3 = QuadraticBezierSegment {
1336 from: point(0.0, 0.0),
1337 ctrl: point(100.0, 100.0),
1338 to: point(5.0, 0.0),
1339 };
1340
1341 fn check_tolerance(curve: &QuadraticBezierSegment<f64>, tolerance: f64) {
1342 let mut c = curve.clone();
1343 loop {
1344 let t = c.flattening_step(tolerance);
1345 if t >= 1.0 {
1346 break;
1347 }
1348 let (before, after) = c.split(t);
1349 let mid_point = before.sample(0.5);
1350 let distance = before
1351 .baseline()
1352 .to_line()
1353 .equation()
1354 .distance_to_point(&mid_point);
1355 assert!(distance <= tolerance);
1356 c = after;
1357 }
1358 }
1359
1360 check_tolerance(&c1, 1.0);
1361 check_tolerance(&c1, 0.1);
1362 check_tolerance(&c1, 0.01);
1363 check_tolerance(&c1, 0.001);
1364 check_tolerance(&c1, 0.0001);
1365
1366 check_tolerance(&c2, 1.0);
1367 check_tolerance(&c2, 0.1);
1368 check_tolerance(&c2, 0.01);
1369 check_tolerance(&c2, 0.001);
1370 check_tolerance(&c2, 0.0001);
1371
1372 check_tolerance(&c3, 1.0);
1373 check_tolerance(&c3, 0.1);
1374 check_tolerance(&c3, 0.01);
1375 check_tolerance(&c3, 0.001);
1376 check_tolerance(&c3, 0.0001);
1377}
1378
1379#[test]
1380fn test_flattening_empty_curve() {
1381 use crate::point;
1382
1383 let curve = QuadraticBezierSegment {
1384 from: point(0.0, 0.0),
1385 ctrl: point(0.0, 0.0),
1386 to: point(0.0, 0.0),
1387 };
1388
1389 let mut iter = FlattenedT::new(&curve, 0.1);
1390
1391 assert_eq!(iter.next(), Some(1.0));
1392 assert_eq!(iter.next(), None);
1393
1394 let mut count: u32 = 0;
1395 curve.for_each_flattened(0.1, &mut |_| count += 1);
1396 assert_eq!(count, 1);
1397}
1398
1399#[test]
1400fn test_flattening_straight_line() {
1401 use crate::point;
1402
1403 let curve = QuadraticBezierSegment {
1404 from: point(0.0, 0.0),
1405 ctrl: point(10.0, 0.0),
1406 to: point(20.0, 0.0),
1407 };
1408
1409 let mut iter = FlattenedT::new(&curve, 0.1);
1410
1411 assert_eq!(iter.next(), Some(1.0));
1412 assert!(iter.next().is_none());
1413
1414 let mut count: u32 = 0;
1415 curve.for_each_flattened(0.1, &mut |_| count += 1);
1416 assert_eq!(count, 1);
1417}
1418
1419#[test]
1420fn issue_678() {
1421 let points = [
1422 [-7768.80859375f32, -35563.80859375],
1423 [-38463.125, -10941.41796875],
1424 [-21846.12890625, -13518.1953125],
1425 [-11727.439453125, -22080.33203125],
1426 ];
1427
1428 let quadratic = QuadraticBezierSegment {
1429 from: Point::new(points[0][0], points[0][1]),
1430 ctrl: Point::new(points[1][0], points[1][1]),
1431 to: Point::new(points[2][0], points[2][1]),
1432 };
1433
1434 let line = Line {
1435 point: Point::new(points[3][0], points[3][1]),
1436 vector: Vector::new(-0.5, -0.5).normalize(),
1437 };
1438
1439 let intersections = quadratic.line_intersections(&line);
1440 std::println!("{intersections:?}");
1441
1442 assert_eq!(intersections.len(), 1);
1443}
1444
1445#[test]
1446fn line_intersections_t() {
1447 let curve = QuadraticBezierSegment {
1448 from: point(0.0f64, 0.0),
1449 ctrl: point(100.0, 0.0),
1450 to: point(100.0, 500.0),
1451 };
1452 let cubic = curve.to_cubic();
1453
1454 let line = Line {
1455 point: point(0.0, -50.0),
1456 vector: crate::vector(100.0, 500.0),
1457 };
1458
1459 let mut i1 = curve.line_intersections_t(&line);
1460 let mut i2 = curve.to_cubic().line_intersections_t(&line);
1461
1462 use std::cmp::Ordering::{Equal, Greater, Less};
1463 i1.sort_by(|a, b| {
1464 if a == b {
1465 Equal
1466 } else if a > b {
1467 Greater
1468 } else {
1469 Less
1470 }
1471 });
1472 i2.sort_by(|a, b| {
1473 if a == b {
1474 Equal
1475 } else if a > b {
1476 Greater
1477 } else {
1478 Less
1479 }
1480 });
1481
1482 for (t1, t2) in i1.iter().zip(i2.iter()) {
1483 use euclid::approxeq::ApproxEq;
1484 let p1 = curve.sample(*t1);
1485 let p2 = cubic.sample(*t2);
1486 assert!(p1.approx_eq(&p2), "{:?} == {:?}", p1, p2);
1487 }
1488 assert_eq!(i2.len(), 2);
1489 assert_eq!(i1.len(), 2);
1490}
1491
1492#[test]
1493fn drag() {
1494 let curve = QuadraticBezierSegment {
1495 from: point(0.0f32, 0.0),
1496 ctrl: point(100.0, 0.0),
1497 to: point(100.0, 100.0),
1498 };
1499
1500 for t in [0.5, 0.25, 0.1, 0.4, 0.7] {
1501 let target = point(0.0, 10.0);
1502
1503 let dragged = curve.drag(t, target);
1504
1505 use euclid::approxeq::ApproxEq;
1506 let p1 = dragged.sample(t);
1507 assert!(
1508 p1.approx_eq_eps(&target, &point(0.001, 0.001)),
1509 "{:?} == {:?}",
1510 p1,
1511 target
1512 );
1513 }
1514}
1515
1516#[test]
1517fn arc_length() {
1518 let curves = [
1519 QuadraticBezierSegment {
1520 from: point(0.0f64, 0.0),
1521 ctrl: point(100.0, 0.0),
1522 to: point(0.0, 100.0),
1523 },
1524 QuadraticBezierSegment {
1525 from: point(0.0, 0.0),
1526 ctrl: point(100.0, 0.0),
1527 to: point(200.0, 0.0),
1528 },
1529 QuadraticBezierSegment {
1530 from: point(100.0, 0.0),
1531 ctrl: point(0.0, 0.0),
1532 to: point(50.0, 1.0),
1533 },
1534 ];
1535
1536 for (idx, curve) in curves.iter().enumerate() {
1537 let length = curve.length();
1538 let mut accum = 0.0;
1539 curve.for_each_flattened(0.00000001, &mut |line| {
1540 accum += line.length();
1541 });
1542
1543 assert!(
1544 (length - accum).abs() < 0.00001,
1545 "curve {:?}, {:?} == {:?}",
1546 idx,
1547 length,
1548 accum
1549 );
1550 }
1551}
1552