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