cubic_bezier.rs source code [crates/lyon_geom/src/cubic_bezier.rs]

1	use crate::cubic_bezier_intersections::cubic_bezier_intersections_t;
2	use crate::scalar::Scalar;
3	use crate::segment::{BoundingBox, Segment};
4	use crate::traits::Transformation;
5	use crate::utils::{cubic_polynomial_roots, min_max};
6	use crate::{point, Box2D, Point, Vector};
7	use crate::{Line, LineEquation, LineSegment, QuadraticBezierSegment};
8	use arrayvec::ArrayVec;
9
10	use core::cmp::Ordering::{Equal, Greater, Less};
11	use core::ops::Range;
12
13	#[cfg(test)]
14	use std::vec::Vec;
15
16	/// A 2d curve segment defined by four points: the beginning of the segment, two control
17	/// points and the end of the segment.
18	///
19	/// The curve is defined by equation:²
20	/// ```∀ t ∈ [0..1], P(t) = (1 - t)³ from + 3 * (1 - t)² * t * ctrl1 + 3 * t² * (1 - t) * ctrl2 + t³ * to```*
21	#[derive(Copy, Clone, Debug, PartialEq)]
22	#[cfg_attr(feature = "serialization", derive(Serialize, Deserialize))]
23	pub struct CubicBezierSegment<S> {
24	pub from: Point<S>,
25	pub ctrl1: Point<S>,
26	pub ctrl2: Point<S>,
27	pub to: Point<S>,
28	}
29
30	impl<S: Scalar> CubicBezierSegment<S> {
31	/// Sample the curve at t (expecting t between 0 and 1).
32	pub fn sample(&self, t: S) -> Point<S> {
33	let t2 = t * t;
34	let t3 = t2 * t;
35	let one_t = S::ONE - t;
36	let one_t2 = one_t * one_t;
37	let one_t3 = one_t2 * one_t;
38
39	self.from * one_t3
40	+ self.ctrl1.to_vector() * S::THREE * one_t2 * t
41	+ self.ctrl2.to_vector() * S::THREE * one_t * t2
42	+ self.to.to_vector() * t3
43	}
44
45	/// Sample the x coordinate of the curve at t (expecting t between 0 and 1).
46	pub fn x(&self, t: S) -> S {
47	let t2 = t * t;
48	let t3 = t2 * t;
49	let one_t = S::ONE - t;
50	let one_t2 = one_t * one_t;
51	let one_t3 = one_t2 * one_t;
52
53	self.from.x * one_t3
54	+ self.ctrl1.x * S::THREE * one_t2 * t
55	+ self.ctrl2.x * S::THREE * one_t * t2
56	+ self.to.x * t3
57	}
58
59	/// Sample the y coordinate of the curve at t (expecting t between 0 and 1).
60	pub fn y(&self, t: S) -> S {
61	let t2 = t * t;
62	let t3 = t2 * t;
63	let one_t = S::ONE - t;
64	let one_t2 = one_t * one_t;
65	let one_t3 = one_t2 * one_t;
66
67	self.from.y * one_t3
68	+ self.ctrl1.y * S::THREE * one_t2 * t
69	+ self.ctrl2.y * S::THREE * one_t * t2
70	+ self.to.y * t3
71	}
72
73	/// Return the parameter values corresponding to a given x coordinate.
74	pub fn solve_t_for_x(&self, x: S) -> ArrayVec<S, `3`> {
75	let (min, max) = self.fast_bounding_range_x();
76	if min > x \|\| max < x {
77	return ArrayVec::new();
78	}
79
80	self.parameters_for_xy_value(x, self.from.x, self.ctrl1.x, self.ctrl2.x, self.to.x)
81	}
82
83	/// Return the parameter values corresponding to a given y coordinate.
84	pub fn solve_t_for_y(&self, y: S) -> ArrayVec<S, `3`> {
85	let (min, max) = self.fast_bounding_range_y();
86	if min > y \|\| max < y {
87	return ArrayVec::new();
88	}
89
90	self.parameters_for_xy_value(y, self.from.y, self.ctrl1.y, self.ctrl2.y, self.to.y)
91	}
92
93	fn parameters_for_xy_value(
94	&self,
95	value: S,
96	from: S,
97	ctrl1: S,
98	ctrl2: S,
99	to: S,
100	) -> ArrayVec<S, `3`> {
101	let mut result = ArrayVec::new();
102
103	let a = -from + S::THREE * ctrl1 - S::THREE * ctrl2 + to;
104	let b = S::THREE * from - S::SIX * ctrl1 + S::THREE * ctrl2;
105	let c = -S::THREE * from + S::THREE * ctrl1;
106	let d = from - value;
107
108	let roots = cubic_polynomial_roots(a, b, c, d);
109	for root in roots {
110	if root > S::ZERO && root < S::ONE {
111	result.push(root);
112	}
113	}
114
115	result
116	}
117
118	#[inline]
119	fn derivative_coefficients(&self, t: S) -> (S, S, S, S) {
120	let t2 = t * t;
121	(
122	-S::THREE * t2 + S::SIX * t - S::THREE,
123	S::NINE * t2 - S::value(`12.0`) * t + S::THREE,
124	-S::NINE * t2 + S::SIX * t,
125	S::THREE * t2,
126	)
127	}
128
129	/// Sample the curve's derivative at t (expecting t between 0 and 1).
130	pub fn derivative(&self, t: S) -> Vector<S> {
131	let (c0, c1, c2, c3) = self.derivative_coefficients(t);
132	self.from.to_vector() * c0
133	+ self.ctrl1.to_vector() * c1
134	+ self.ctrl2.to_vector() * c2
135	+ self.to.to_vector() * c3
136	}
137
138	/// Sample the x coordinate of the curve's derivative at t (expecting t between 0 and 1).
139	pub fn dx(&self, t: S) -> S {
140	let (c0, c1, c2, c3) = self.derivative_coefficients(t);
141	self.from.x * c0 + self.ctrl1.x * c1 + self.ctrl2.x * c2 + self.to.x * c3
142	}
143
144	/// Sample the y coordinate of the curve's derivative at t (expecting t between 0 and 1).
145	pub fn dy(&self, t: S) -> S {
146	let (c0, c1, c2, c3) = self.derivative_coefficients(t);
147	self.from.y * c0 + self.ctrl1.y * c1 + self.ctrl2.y * c2 + self.to.y * c3
148	}
149
150	/// Return the sub-curve inside a given range of t.
151	///
152	/// This is equivalent to splitting at the range's end points.
153	pub fn split_range(&self, t_range: Range<S>) -> Self {
154	let (t0, t1) = (t_range.start, t_range.end);
155	let from = self.sample(t0);
156	let to = self.sample(t1);
157
158	let d = QuadraticBezierSegment {
159	from: (self.ctrl1 - self.from).to_point(),
160	ctrl: (self.ctrl2 - self.ctrl1).to_point(),
161	to: (self.to - self.ctrl2).to_point(),
162	};
163
164	let dt = t1 - t0;
165	let ctrl1 = from + d.sample(t0).to_vector() * dt;
166	let ctrl2 = to - d.sample(t1).to_vector() * dt;
167
168	CubicBezierSegment {
169	from,
170	ctrl1,
171	ctrl2,
172	to,
173	}
174	}
175
176	/// Split this curve into two sub-curves.
177	pub fn split(&self, t: S) -> (CubicBezierSegment<S>, CubicBezierSegment<S>) {
178	let ctrl1a = self.from + (self.ctrl1 - self.from) * t;
179	let ctrl2a = self.ctrl1 + (self.ctrl2 - self.ctrl1) * t;
180	let ctrl1aa = ctrl1a + (ctrl2a - ctrl1a) * t;
181	let ctrl3a = self.ctrl2 + (self.to - self.ctrl2) * t;
182	let ctrl2aa = ctrl2a + (ctrl3a - ctrl2a) * t;
183	let ctrl1aaa = ctrl1aa + (ctrl2aa - ctrl1aa) * t;
184
185	(
186	CubicBezierSegment {
187	from: self.from,
188	ctrl1: ctrl1a,
189	ctrl2: ctrl1aa,
190	to: ctrl1aaa,
191	},
192	CubicBezierSegment {
193	from: ctrl1aaa,
194	ctrl1: ctrl2aa,
195	ctrl2: ctrl3a,
196	to: self.to,
197	},
198	)
199	}
200
201	/// Return the curve before the split point.
202	pub fn before_split(&self, t: S) -> CubicBezierSegment<S> {
203	let ctrl1a = self.from + (self.ctrl1 - self.from) * t;
204	let ctrl2a = self.ctrl1 + (self.ctrl2 - self.ctrl1) * t;
205	let ctrl1aa = ctrl1a + (ctrl2a - ctrl1a) * t;
206	let ctrl3a = self.ctrl2 + (self.to - self.ctrl2) * t;
207	let ctrl2aa = ctrl2a + (ctrl3a - ctrl2a) * t;
208	let ctrl1aaa = ctrl1aa + (ctrl2aa - ctrl1aa) * t;
209
210	CubicBezierSegment {
211	from: self.from,
212	ctrl1: ctrl1a,
213	ctrl2: ctrl1aa,
214	to: ctrl1aaa,
215	}
216	}
217
218	/// Return the curve after the split point.
219	pub fn after_split(&self, t: S) -> CubicBezierSegment<S> {
220	let ctrl1a = self.from + (self.ctrl1 - self.from) * t;
221	let ctrl2a = self.ctrl1 + (self.ctrl2 - self.ctrl1) * t;
222	let ctrl1aa = ctrl1a + (ctrl2a - ctrl1a) * t;
223	let ctrl3a = self.ctrl2 + (self.to - self.ctrl2) * t;
224	let ctrl2aa = ctrl2a + (ctrl3a - ctrl2a) * t;
225
226	CubicBezierSegment {
227	from: ctrl1aa + (ctrl2aa - ctrl1aa) * t,
228	ctrl1: ctrl2a + (ctrl3a - ctrl2a) * t,
229	ctrl2: ctrl3a,
230	to: self.to,
231	}
232	}
233
234	#[inline]
235	pub fn baseline(&self) -> LineSegment<S> {
236	LineSegment {
237	from: self.from,
238	to: self.to,
239	}
240	}
241
242	/// Returns true if the curve can be approximated with a single line segment, given
243	/// a tolerance threshold.
244	pub fn is_linear(&self, tolerance: S) -> bool {
245	// Similar to Line::square_distance_to_point, except we keep
246	// the sign of c1 and c2 to compute tighter upper bounds as we
247	// do in fat_line_min_max.
248	let baseline = self.to - self.from;
249	let v1 = self.ctrl1 - self.from;
250	let v2 = self.ctrl2 - self.from;
251	let c1 = baseline.cross(v1);
252	let c2 = baseline.cross(v2);
253	// TODO: it would be faster to multiply the threshold with baseline_len2
254	// instead of dividing d1 and d2, but it changes the behavior when the
255	// baseline length is zero in ways that breaks some of the cubic intersection
256	// tests.
257	let inv_baseline_len2 = S::ONE / baseline.square_length();
258	let d1 = (c1 * c1) * inv_baseline_len2;
259	let d2 = (c2 * c2) * inv_baseline_len2;
260
261	let factor = if (c1 * c2) > S::ZERO {
262	S::THREE / S::FOUR
263	} else {
264	S::FOUR / S::NINE
265	};
266
267	let f2 = factor * factor;
268	let threshold = tolerance * tolerance;
269
270	d1 * f2 <= threshold && d2 * f2 <= threshold
271	}
272
273	/// Returns whether the curve can be approximated with a single point, given
274	/// a tolerance threshold.
275	pub(crate) fn is_a_point(&self, tolerance: S) -> bool {
276	let tolerance_squared = tolerance * tolerance;
277	// Use <= so that tolerance can be zero.
278	(self.from - self.to).square_length() <= tolerance_squared
279	&& (self.from - self.ctrl1).square_length() <= tolerance_squared
280	&& (self.to - self.ctrl2).square_length() <= tolerance_squared
281	}
282
283	/// Computes the signed distances (min <= 0 and max >= 0) from the baseline of this
284	/// curve to its two "fat line" boundary lines.
285	///
286	/// A fat line is two conservative lines between which the segment
287	/// is fully contained.
288	pub(crate) fn fat_line_min_max(&self) -> (S, S) {
289	let baseline = self.baseline().to_line().equation();
290	let (d1, d2) = min_max(
291	baseline.signed_distance_to_point(&self.ctrl1),
292	baseline.signed_distance_to_point(&self.ctrl2),
293	);
294
295	let factor = if (d1 * d2) > S::ZERO {
296	S::THREE / S::FOUR
297	} else {
298	S::FOUR / S::NINE
299	};
300
301	let d_min = factor * S::min(d1, S::ZERO);
302	let d_max = factor * S::max(d2, S::ZERO);
303
304	(d_min, d_max)
305	}
306
307	/// Computes a "fat line" of this segment.
308	///
309	/// A fat line is two conservative lines between which the segment
310	/// is fully contained.
311	pub fn fat_line(&self) -> (LineEquation<S>, LineEquation<S>) {
312	let baseline = self.baseline().to_line().equation();
313	let (d1, d2) = self.fat_line_min_max();
314
315	(baseline.offset(d1), baseline.offset(d2))
316	}
317
318	/// Applies the transform to this curve and returns the results.
319	#[inline]
320	pub fn transformed<T: Transformation<S>>(&self, transform: &T) -> Self {
321	CubicBezierSegment {
322	from: transform.transform_point(self.from),
323	ctrl1: transform.transform_point(self.ctrl1),
324	ctrl2: transform.transform_point(self.ctrl2),
325	to: transform.transform_point(self.to),
326	}
327	}
328
329	/// Swap the beginning and the end of the segment.
330	pub fn flip(&self) -> Self {
331	CubicBezierSegment {
332	from: self.to,
333	ctrl1: self.ctrl2,
334	ctrl2: self.ctrl1,
335	to: self.from,
336	}
337	}
338
339	/// Approximate the curve with a single quadratic bézier segment.
340	///
341	/// This is terrible as a general approximation but works if the cubic
342	/// curve does not have inflection points and is "flat" enough. Typically
343	/// usable after subdividing the curve a few times.
344	pub fn to_quadratic(&self) -> QuadraticBezierSegment<S> {
345	let c1 = (self.ctrl1 * S::THREE - self.from) * S::HALF;
346	let c2 = (self.ctrl2 * S::THREE - self.to) * S::HALF;
347	QuadraticBezierSegment {
348	from: self.from,
349	ctrl: ((c1 + c2) * S::HALF).to_point(),
350	to: self.to,
351	}
352	}
353
354	/// Evaluates an upper bound on the maximum distance between the curve
355	/// and its quadratic approximation obtained using `to_quadratic`.
356	pub fn to_quadratic_error(&self) -> S {
357	// See http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
358	S::sqrt(S::THREE) / S::value(`36.0`)
359	* ((self.to - self.ctrl2 * S::THREE) + (self.ctrl1 * S::THREE - self.from)).length()
360	}
361
362	/// Returns true if the curve can be safely approximated with a single quadratic bézier
363	/// segment given the provided tolerance threshold.
364	///
365	/// Equivalent to comparing `to_quadratic_error` with the tolerance threshold, avoiding
366	/// the cost of two square roots.
367	pub fn is_quadratic(&self, tolerance: S) -> bool {
368	S::THREE / S::value(`1296.0`)
369	* ((self.to - self.ctrl2 * S::THREE) + (self.ctrl1 * S::THREE - self.from))
370	.square_length()
371	<= tolerance * tolerance
372	}
373
374	/// Computes the number of quadratic bézier segments required to approximate this cubic curve
375	/// given a tolerance threshold.
376	///
377	/// Derived by Raph Levien from section 10.6 of Sedeberg's CAGD notes
378	/// <https://scholarsarchive.byu.edu/cgi/viewcontent.cgi?article=1000&context=facpub#section.10.6>
379	/// and the error metric from the caffein owl blog post <http://caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html>
380	pub fn num_quadratics(&self, tolerance: S) -> u32 {
381	self.num_quadratics_impl(tolerance).to_u32().unwrap_or(`1`)
382	}
383
384	fn num_quadratics_impl(&self, tolerance: S) -> S {
385	debug_assert!(tolerance > S::ZERO);
386
387	let x = self.from.x - S::THREE * self.ctrl1.x + S::THREE * self.ctrl2.x - self.to.x;
388	let y = self.from.y - S::THREE * self.ctrl1.y + S::THREE * self.ctrl2.y - self.to.y;
389
390	let err = x * x + y * y;
391
392	(err / (S::value(`432.0`) * tolerance * tolerance))
393	.powf(S::ONE / S::SIX)
394	.ceil()
395	.max(S::ONE)
396	}
397
398	/// Returns the flattened representation of the curve as an iterator, starting after* the*
399	/// current point.
400	pub fn flattened(&self, tolerance: S) -> Flattened<S> {
401	Flattened::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 extrema: ArrayVec<S, `4`> = ArrayVec::new();
410	self.for_each_local_x_extremum_t(&mut \|t\| extrema.push(t));
411	self.for_each_local_y_extremum_t(&mut \|t\| extrema.push(t));
412	extrema.sort_unstable_by(\|a, b\| a.partial_cmp(b).unwrap());
413
414	let mut t0 = S::ZERO;
415	for &t in &extrema {
416	if t != t0 {
417	cb(t0..t);
418	t0 = t;
419	}
420	}
421
422	cb(t0..S::ONE);
423	}
424
425	/// Invokes a callback for each monotonic part of the segment.
426	pub fn for_each_monotonic<F>(&self, cb: &mut F)
427	where
428	F: FnMut(&CubicBezierSegment<S>),
429	{
430	self.for_each_monotonic_range(&mut \|range\| {
431	let mut sub = self.split_range(range);
432	// Due to finite precision the split may actually result in sub-curves
433	// that are almost but not-quite monotonic. Make sure they actually are.
434	let min_x = sub.from.x.min(sub.to.x);
435	let max_x = sub.from.x.max(sub.to.x);
436	let min_y = sub.from.y.min(sub.to.y);
437	let max_y = sub.from.y.max(sub.to.y);
438	sub.ctrl1.x = sub.ctrl1.x.max(min_x).min(max_x);
439	sub.ctrl1.y = sub.ctrl1.y.max(min_y).min(max_y);
440	sub.ctrl2.x = sub.ctrl2.x.max(min_x).min(max_x);
441	sub.ctrl2.y = sub.ctrl2.y.max(min_y).min(max_y);
442	cb(&sub);
443	});
444	}
445
446	/// Invokes a callback for each y-monotonic part of the segment.
447	pub fn for_each_y_monotonic_range<F>(&self, cb: &mut F)
448	where
449	F: FnMut(Range<S>),
450	{
451	let mut t0 = S::ZERO;
452	self.for_each_local_y_extremum_t(&mut \|t\| {
453	cb(t0..t);
454	t0 = t;
455	});
456
457	cb(t0..S::ONE);
458	}
459
460	/// Invokes a callback for each y-monotonic part of the segment.
461	pub fn for_each_y_monotonic<F>(&self, cb: &mut F)
462	where
463	F: FnMut(&CubicBezierSegment<S>),
464	{
465	self.for_each_y_monotonic_range(&mut \|range\| {
466	let mut sub = self.split_range(range);
467	// Due to finite precision the split may actually result in sub-curves
468	// that are almost but not-quite monotonic. Make sure they actually are.
469	let min_y = sub.from.y.min(sub.to.y);
470	let max_y = sub.from.y.max(sub.to.y);
471	sub.ctrl1.y = sub.ctrl1.y.max(min_y).min(max_y);
472	sub.ctrl2.y = sub.ctrl2.y.max(min_y).min(max_y);
473	cb(&sub);
474	});
475	}
476
477	/// Invokes a callback for each x-monotonic part of the segment.
478	pub fn for_each_x_monotonic_range<F>(&self, cb: &mut F)
479	where
480	F: FnMut(Range<S>),
481	{
482	let mut t0 = S::ZERO;
483	self.for_each_local_x_extremum_t(&mut \|t\| {
484	cb(t0..t);
485	t0 = t;
486	});
487
488	cb(t0..S::ONE);
489	}
490
491	/// Invokes a callback for each x-monotonic part of the segment.
492	pub fn for_each_x_monotonic<F>(&self, cb: &mut F)
493	where
494	F: FnMut(&CubicBezierSegment<S>),
495	{
496	self.for_each_x_monotonic_range(&mut \|range\| {
497	let mut sub = self.split_range(range);
498	// Due to finite precision the split may actually result in sub-curves
499	// that are almost but not-quite monotonic. Make sure they actually are.
500	let min_x = sub.from.x.min(sub.to.x);
501	let max_x = sub.from.x.max(sub.to.x);
502	sub.ctrl1.x = sub.ctrl1.x.max(min_x).min(max_x);
503	sub.ctrl2.x = sub.ctrl2.x.max(min_x).min(max_x);
504	cb(&sub);
505	});
506	}
507
508	/// Approximates the cubic bézier curve with sequence of quadratic ones,
509	/// invoking a callback at each step.
510	pub fn for_each_quadratic_bezier<F>(&self, tolerance: S, cb: &mut F)
511	where
512	F: FnMut(&QuadraticBezierSegment<S>),
513	{
514	self.for_each_quadratic_bezier_with_t(tolerance, &mut \|quad, _range\| cb(quad));
515	}
516
517	/// Approximates the cubic bézier curve with sequence of quadratic ones,
518	/// invoking a callback at each step.
519	pub fn for_each_quadratic_bezier_with_t<F>(&self, tolerance: S, cb: &mut F)
520	where
521	F: FnMut(&QuadraticBezierSegment<S>, Range<S>),
522	{
523	debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
524
525	let num_quadratics = self.num_quadratics_impl(tolerance);
526	let step = S::ONE / num_quadratics;
527	let n = num_quadratics.to_u32().unwrap_or(`1`);
528	let mut t0 = S::ZERO;
529	for _ in `0`..(n - `1`) {
530	let t1 = t0 + step;
531
532	let quad = self.split_range(t0..t1).to_quadratic();
533	cb(&quad, t0..t1);
534
535	t0 = t1;
536	}
537
538	// Do the last step manually to make sure we finish at t = 1.0 exactly.
539	let quad = self.split_range(t0..S::ONE).to_quadratic();
540	cb(&quad, t0..S::ONE)
541	}
542
543	/// Approximates the curve with sequence of line segments.
544	///
545	/// The `tolerance` parameter defines the maximum distance between the curve and
546	/// its approximation.
547	pub fn for_each_flattened<F: FnMut(&LineSegment<S>)>(&self, tolerance: S, callback: &mut F) {
548	debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
549	let quadratics_tolerance = tolerance * S::value(`0.4`);
550	let flattening_tolerance = tolerance * S::value(`0.8`);
551
552	self.for_each_quadratic_bezier(quadratics_tolerance, &mut \|quad\| {
553	quad.for_each_flattened(flattening_tolerance, &mut \|segment\| {
554	callback(segment);
555	});
556	});
557	}
558
559	/// Approximates the curve with sequence of line segments.
560	///
561	/// The `tolerance` parameter defines the maximum distance between the curve and
562	/// its approximation.
563	///
564	/// The end of the t parameter range at the final segment is guaranteed to be equal to `1.0`.
565	pub fn for_each_flattened_with_t<F: FnMut(&LineSegment<S>, Range<S>)>(
566	&self,
567	tolerance: S,
568	callback: &mut F,
569	) {
570	debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
571	let quadratics_tolerance = tolerance * S::value(`0.4`);
572	let flattening_tolerance = tolerance * S::value(`0.8`);
573
574	let mut t_from = S::ZERO;
575	self.for_each_quadratic_bezier_with_t(quadratics_tolerance, &mut \|quad, range\| {
576	let last_quad = range.end == S::ONE;
577	let range_len = range.end - range.start;
578	quad.for_each_flattened_with_t(flattening_tolerance, &mut \|segment, range_sub\| {
579	let last_seg = range_sub.end == S::ONE;
580	let t = if last_quad && last_seg {
581	S::ONE
582	} else {
583	range_sub.end * range_len + range.start
584	};
585	callback(segment, t_from..t);
586	t_from = t;
587	});
588	});
589	}
590
591	/// Compute the length of the segment using a flattened approximation.
592	pub fn approximate_length(&self, tolerance: S) -> S {
593	let mut length = S::ZERO;
594
595	self.for_each_quadratic_bezier(tolerance, &mut \|quad\| {
596	length += quad.length();
597	});
598
599	length
600	}
601
602	/// Invokes a callback at each inflection point if any.
603	pub fn for_each_inflection_t<F>(&self, cb: &mut F)
604	where
605	F: FnMut(S),
606	{
607	// Find inflection points.
608	// See www.faculty.idc.ac.il/arik/quality/appendixa.html for an explanation
609	// of this approach.
610	let pa = self.ctrl1 - self.from;
611	let pb = self.ctrl2.to_vector() - (self.ctrl1.to_vector() * S::TWO) + self.from.to_vector();
612	let pc = self.to.to_vector() - (self.ctrl2.to_vector() * S::THREE)
613	+ (self.ctrl1.to_vector() * S::THREE)
614	- self.from.to_vector();
615
616	let a = pb.cross(pc);
617	let b = pa.cross(pc);
618	let c = pa.cross(pb);
619
620	if S::abs(a) < S::EPSILON {
621	// Not a quadratic equation.
622	if S::abs(b) < S::EPSILON {
623	// Instead of a linear acceleration change we have a constant
624	// acceleration change. This means the equation has no solution
625	// and there are no inflection points, unless the constant is 0.
626	// In that case the curve is a straight line, essentially that means
627	// the easiest way to deal with is is by saying there's an inflection
628	// point at t == 0. The inflection point approximation range found will
629	// automatically extend into infinity.
630	if S::abs(c) < S::EPSILON {
631	cb(S::ZERO);
632	}
633	} else {
634	let t = -c / b;
635	if in_range(t) {
636	cb(t);
637	}
638	}
639
640	return;
641	}
642
643	fn in_range<S: Scalar>(t: S) -> bool {
644	t >= S::ZERO && t < S::ONE
645	}
646
647	let discriminant = b * b - S::FOUR * a * c;
648
649	if discriminant < S::ZERO {
650	return;
651	}
652
653	if discriminant < S::EPSILON {
654	let t = -b / (S::TWO * a);
655
656	if in_range(t) {
657	cb(t);
658	}
659
660	return;
661	}
662
663	// This code is derived from https://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf page 184.
664	// Computing the roots this way avoids precision issues when a, c or both are small.
665	let discriminant_sqrt = S::sqrt(discriminant);
666	let sign_b = if b >= S::ZERO { S::ONE } else { -S::ONE };
667	let q = -S::HALF * (b + sign_b * discriminant_sqrt);
668	let mut first_inflection = q / a;
669	let mut second_inflection = c / q;
670
671	if first_inflection > second_inflection {
672	core::mem::swap(&mut first_inflection, &mut second_inflection);
673	}
674
675	if in_range(first_inflection) {
676	cb(first_inflection);
677	}
678
679	if in_range(second_inflection) {
680	cb(second_inflection);
681	}
682	}
683
684	/// Return local x extrema or None if this curve is monotonic.
685	///
686	/// This returns the advancements along the curve, not the actual x position.
687	pub fn for_each_local_x_extremum_t<F>(&self, cb: &mut F)
688	where
689	F: FnMut(S),
690	{
691	Self::for_each_local_extremum(self.from.x, self.ctrl1.x, self.ctrl2.x, self.to.x, cb)
692	}
693
694	/// Return local y extrema or None if this curve is monotonic.
695	///
696	/// This returns the advancements along the curve, not the actual y position.
697	pub fn for_each_local_y_extremum_t<F>(&self, cb: &mut F)
698	where
699	F: FnMut(S),
700	{
701	Self::for_each_local_extremum(self.from.y, self.ctrl1.y, self.ctrl2.y, self.to.y, cb)
702	}
703
704	fn for_each_local_extremum<F>(p0: S, p1: S, p2: S, p3: S, cb: &mut F)
705	where
706	F: FnMut(S),
707	{
708	// See www.faculty.idc.ac.il/arik/quality/appendixa.html for an explanation
709	// The derivative of a cubic bezier curve is a curve representing a second degree polynomial function
710	// f(x) = a x² + b * x + c such as :*
711
712	let a = S::THREE * (p3 + S::THREE * (p1 - p2) - p0);
713	let b = S::SIX * (p2 - S::TWO * p1 + p0);
714	let c = S::THREE * (p1 - p0);
715
716	fn in_range<S: Scalar>(t: S) -> bool {
717	t > S::ZERO && t < S::ONE
718	}
719
720	// If the derivative is a linear function
721	if a == S::ZERO {
722	if b != S::ZERO {
723	let t = -c / b;
724	if in_range(t) {
725	cb(t);
726	}
727	}
728	return;
729	}
730
731	let discriminant = b * b - S::FOUR * a * c;
732
733	// There is no Real solution for the equation
734	if discriminant < S::ZERO {
735	return;
736	}
737
738	// There is one Real solution for the equation
739	if discriminant == S::ZERO {
740	let t = -b / (S::TWO * a);
741	if in_range(t) {
742	cb(t);
743	}
744	return;
745	}
746
747	// There are two Real solutions for the equation
748	let discriminant_sqrt = discriminant.sqrt();
749
750	let mut first_extremum = (-b - discriminant_sqrt) / (S::TWO * a);
751	let mut second_extremum = (-b + discriminant_sqrt) / (S::TWO * a);
752	if first_extremum > second_extremum {
753	core::mem::swap(&mut first_extremum, &mut second_extremum);
754	}
755
756	if in_range(first_extremum) {
757	cb(first_extremum);
758	}
759
760	if in_range(second_extremum) {
761	cb(second_extremum);
762	}
763	}
764
765	/// Find the advancement of the y-most position in the curve.
766	///
767	/// This returns the advancement along the curve, not the actual y position.
768	pub fn y_maximum_t(&self) -> S {
769	let mut max_t = S::ZERO;
770	let mut max_y = self.from.y;
771	if self.to.y > max_y {
772	max_t = S::ONE;
773	max_y = self.to.y;
774	}
775	self.for_each_local_y_extremum_t(&mut \|t\| {
776	let y = self.y(t);
777	if y > max_y {
778	max_t = t;
779	max_y = y;
780	}
781	});
782
783	max_t
784	}
785
786	/// Find the advancement of the y-least position in the curve.
787	///
788	/// This returns the advancement along the curve, not the actual y position.
789	pub fn y_minimum_t(&self) -> S {
790	let mut min_t = S::ZERO;
791	let mut min_y = self.from.y;
792	if self.to.y < min_y {
793	min_t = S::ONE;
794	min_y = self.to.y;
795	}
796	self.for_each_local_y_extremum_t(&mut \|t\| {
797	let y = self.y(t);
798	if y < min_y {
799	min_t = t;
800	min_y = y;
801	}
802	});
803
804	min_t
805	}
806
807	/// Find the advancement of the x-most position in the curve.
808	///
809	/// This returns the advancement along the curve, not the actual x position.
810	pub fn x_maximum_t(&self) -> S {
811	let mut max_t = S::ZERO;
812	let mut max_x = self.from.x;
813	if self.to.x > max_x {
814	max_t = S::ONE;
815	max_x = self.to.x;
816	}
817	self.for_each_local_x_extremum_t(&mut \|t\| {
818	let x = self.x(t);
819	if x > max_x {
820	max_t = t;
821	max_x = x;
822	}
823	});
824
825	max_t
826	}
827
828	/// Find the x-least position in the curve.
829	pub fn x_minimum_t(&self) -> S {
830	let mut min_t = S::ZERO;
831	let mut min_x = self.from.x;
832	if self.to.x < min_x {
833	min_t = S::ONE;
834	min_x = self.to.x;
835	}
836	self.for_each_local_x_extremum_t(&mut \|t\| {
837	let x = self.x(t);
838	if x < min_x {
839	min_t = t;
840	min_x = x;
841	}
842	});
843
844	min_t
845	}
846
847	/// Returns a conservative rectangle the curve is contained in.
848	///
849	/// This method is faster than `bounding_box` but more conservative.
850	pub fn fast_bounding_box(&self) -> Box2D<S> {
851	let (min_x, max_x) = self.fast_bounding_range_x();
852	let (min_y, max_y) = self.fast_bounding_range_y();
853
854	Box2D {
855	min: point(min_x, min_y),
856	max: point(max_x, max_y),
857	}
858	}
859
860	/// Returns a conservative range of x that contains this curve.
861	#[inline]
862	pub fn fast_bounding_range_x(&self) -> (S, S) {
863	let min_x = self
864	.from
865	.x
866	.min(self.ctrl1.x)
867	.min(self.ctrl2.x)
868	.min(self.to.x);
869	let max_x = self
870	.from
871	.x
872	.max(self.ctrl1.x)
873	.max(self.ctrl2.x)
874	.max(self.to.x);
875
876	(min_x, max_x)
877	}
878
879	/// Returns a conservative range of y that contains this curve.
880	#[inline]
881	pub fn fast_bounding_range_y(&self) -> (S, S) {
882	let min_y = self
883	.from
884	.y
885	.min(self.ctrl1.y)
886	.min(self.ctrl2.y)
887	.min(self.to.y);
888	let max_y = self
889	.from
890	.y
891	.max(self.ctrl1.y)
892	.max(self.ctrl2.y)
893	.max(self.to.y);
894
895	(min_y, max_y)
896	}
897
898	/// Returns a conservative rectangle that contains the curve.
899	#[inline]
900	pub fn bounding_box(&self) -> Box2D<S> {
901	let (min_x, max_x) = self.bounding_range_x();
902	let (min_y, max_y) = self.bounding_range_y();
903
904	Box2D {
905	min: point(min_x, min_y),
906	max: point(max_x, max_y),
907	}
908	}
909
910	/// Returns the smallest range of x that contains this curve.
911	#[inline]
912	pub fn bounding_range_x(&self) -> (S, S) {
913	let min_x = self.x(self.x_minimum_t());
914	let max_x = self.x(self.x_maximum_t());
915
916	(min_x, max_x)
917	}
918
919	/// Returns the smallest range of y that contains this curve.
920	#[inline]
921	pub fn bounding_range_y(&self) -> (S, S) {
922	let min_y = self.y(self.y_minimum_t());
923	let max_y = self.y(self.y_maximum_t());
924
925	(min_y, max_y)
926	}
927
928	/// Returns whether this segment is monotonic on the x axis.
929	pub fn is_x_monotonic(&self) -> bool {
930	let mut found = `false`;
931	self.for_each_local_x_extremum_t(&mut \|_\| {
932	found = `true`;
933	});
934	!found
935	}
936
937	/// Returns whether this segment is monotonic on the y axis.
938	pub fn is_y_monotonic(&self) -> bool {
939	let mut found = `false`;
940	self.for_each_local_y_extremum_t(&mut \|_\| {
941	found = `true`;
942	});
943	!found
944	}
945
946	/// Returns whether this segment is fully monotonic.
947	pub fn is_monotonic(&self) -> bool {
948	self.is_x_monotonic() && self.is_y_monotonic()
949	}
950
951	/// Computes the intersections (if any) between this segment and another one.
952	///
953	/// The result is provided in the form of the `t` parameters of each point along the curves. To
954	/// get the intersection points, sample the curves at the corresponding values.
955	///
956	/// Returns endpoint intersections where an endpoint intersects the interior of the other curve,
957	/// but not endpoint/endpoint intersections.
958	///
959	/// Returns no intersections if either curve is a point.
960	pub fn cubic_intersections_t(&self, curve: &CubicBezierSegment<S>) -> ArrayVec<(S, S), `9`> {
961	cubic_bezier_intersections_t(self, curve)
962	}
963
964	/// Computes the intersection points (if any) between this segment and another one.
965	pub fn cubic_intersections(&self, curve: &CubicBezierSegment<S>) -> ArrayVec<Point<S>, `9`> {
966	let intersections = self.cubic_intersections_t(curve);
967
968	let mut result_with_repeats = ArrayVec::<_, `9`>::new();
969	for (t, _) in intersections {
970	result_with_repeats.push(self.sample(t));
971	}
972
973	// We can have up to nine "repeated" values here (for example: two lines, each of which
974	// overlaps itself 3 times, intersecting in their 3-fold overlaps). We make an effort to
975	// dedupe the results, but that's hindered by not having predictable control over how far
976	// the repeated intersections can be from each other (and then by the fact that true
977	// intersections can be arbitrarily close), so the results will never be perfect.
978
979	let pair_cmp = \|s: &Point<S>, t: &Point<S>\| {
980	if s.x < t.x \|\| (s.x == t.x && s.y < t.y) {
981	Less
982	} else if s.x == t.x && s.y == t.y {
983	Equal
984	} else {
985	Greater
986	}
987	};
988	result_with_repeats.sort_unstable_by(pair_cmp);
989	if result_with_repeats.len() <= `1` {
990	return result_with_repeats;
991	}
992
993	#[inline]
994	fn dist_sq<S: Scalar>(p1: &Point<S>, p2: &Point<S>) -> S {
995	(p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)
996	}
997
998	let epsilon_squared = S::EPSILON * S::EPSILON;
999	let mut result = ArrayVec::new();
1000	let mut reference_intersection = &result_with_repeats[`0`];
1001	result.push(*reference_intersection);
1002	for i in `1`..result_with_repeats.len() {
1003	let intersection = &result_with_repeats[i];
1004	if dist_sq(reference_intersection, intersection) < epsilon_squared {
1005	continue;
1006	} else {
1007	result.push(*intersection);
1008	reference_intersection = intersection;
1009	}
1010	}
1011
1012	result
1013	}
1014
1015	/// Computes the intersections (if any) between this segment a quadratic bézier segment.
1016	///
1017	/// The result is provided in the form of the `t` parameters of each point along the curves. To
1018	/// get the intersection points, sample the curves at the corresponding values.
1019	///
1020	/// Returns endpoint intersections where an endpoint intersects the interior of the other curve,
1021	/// but not endpoint/endpoint intersections.
1022	///
1023	/// Returns no intersections if either curve is a point.
1024	pub fn quadratic_intersections_t(
1025	&self,
1026	curve: &QuadraticBezierSegment<S>,
1027	) -> ArrayVec<(S, S), `9`> {
1028	self.cubic_intersections_t(&curve.to_cubic())
1029	}
1030
1031	/// Computes the intersection points (if any) between this segment and a quadratic bézier segment.
1032	pub fn quadratic_intersections(
1033	&self,
1034	curve: &QuadraticBezierSegment<S>,
1035	) -> ArrayVec<Point<S>, `9`> {
1036	self.cubic_intersections(&curve.to_cubic())
1037	}
1038
1039	/// Computes the intersections (if any) between this segment and a line.
1040	///
1041	/// The result is provided in the form of the `t` parameters of each
1042	/// point along curve. To get the intersection points, sample the curve
1043	/// at the corresponding values.
1044	pub fn line_intersections_t(&self, line: &Line<S>) -> ArrayVec<S, `3`> {
1045	if line.vector.square_length() < S::EPSILON {
1046	return ArrayVec::new();
1047	}
1048
1049	let from = self.from.to_vector();
1050	let ctrl1 = self.ctrl1.to_vector();
1051	let ctrl2 = self.ctrl2.to_vector();
1052	let to = self.to.to_vector();
1053
1054	let p1 = to - from + (ctrl1 - ctrl2) * S::THREE;
1055	let p2 = from * S::THREE + (ctrl2 - ctrl1 * S::TWO) * S::THREE;
1056	let p3 = (ctrl1 - from) * S::THREE;
1057	let p4 = from;
1058
1059	let c = line.point.y * line.vector.x - line.point.x * line.vector.y;
1060
1061	let roots = cubic_polynomial_roots(
1062	line.vector.y * p1.x - line.vector.x * p1.y,
1063	line.vector.y * p2.x - line.vector.x * p2.y,
1064	line.vector.y * p3.x - line.vector.x * p3.y,
1065	line.vector.y * p4.x - line.vector.x * p4.y + c,
1066	);
1067
1068	let mut result = ArrayVec::new();
1069
1070	for root in roots {
1071	if root >= S::ZERO && root <= S::ONE {
1072	result.push(root);
1073	}
1074	}
1075
1076	// TODO: sort the intersections?
1077
1078	result
1079	}
1080
1081	/// Computes the intersection points (if any) between this segment and a line.
1082	pub fn line_intersections(&self, line: &Line<S>) -> ArrayVec<Point<S>, `3`> {
1083	let intersections = self.line_intersections_t(line);
1084
1085	let mut result = ArrayVec::new();
1086	for t in intersections {
1087	result.push(self.sample(t));
1088	}
1089
1090	result
1091	}
1092
1093	/// Computes the intersections (if any) between this segment and a line segment.
1094	///
1095	/// The result is provided in the form of the `t` parameters of each
1096	/// point along curve and segment. To get the intersection points, sample
1097	/// the segments at the corresponding values.
1098	pub fn line_segment_intersections_t(&self, segment: &LineSegment<S>) -> ArrayVec<(S, S), `3`> {
1099	if !self
1100	.fast_bounding_box()
1101	.inflate(S::EPSILON, S::EPSILON)
1102	.intersects(&segment.bounding_box().inflate(S::EPSILON, S::EPSILON))
1103	{
1104	return ArrayVec::new();
1105	}
1106
1107	let intersections = self.line_intersections_t(&segment.to_line());
1108
1109	let mut result = ArrayVec::new();
1110	if intersections.is_empty() {
1111	return result;
1112	}
1113
1114	let seg_is_mostly_vertical =
1115	S::abs(segment.from.y - segment.to.y) >= S::abs(segment.from.x - segment.to.x);
1116	let (seg_long_axis_min, seg_long_axis_max) = if seg_is_mostly_vertical {
1117	segment.bounding_range_y()
1118	} else {
1119	segment.bounding_range_x()
1120	};
1121
1122	for t in intersections {
1123	let intersection_xy = if seg_is_mostly_vertical {
1124	self.y(t)
1125	} else {
1126	self.x(t)
1127	};
1128	if intersection_xy >= seg_long_axis_min && intersection_xy <= seg_long_axis_max {
1129	let t2 = (self.sample(t) - segment.from).length() / segment.length();
1130	// Don't take intersections that are on endpoints of both curves at the same time.
1131	if (t != S::ZERO && t != S::ONE) \|\| (t2 != S::ZERO && t2 != S::ONE) {
1132	result.push((t, t2));
1133	}
1134	}
1135	}
1136
1137	result
1138	}
1139
1140	#[inline]
1141	pub fn from(&self) -> Point<S> {
1142	self.from
1143	}
1144
1145	#[inline]
1146	pub fn to(&self) -> Point<S> {
1147	self.to
1148	}
1149
1150	pub fn line_segment_intersections(&self, segment: &LineSegment<S>) -> ArrayVec<Point<S>, `3`> {
1151	let intersections = self.line_segment_intersections_t(segment);
1152
1153	let mut result = ArrayVec::new();
1154	for (t, _) in intersections {
1155	result.push(self.sample(t));
1156	}
1157
1158	result
1159	}
1160
1161	fn baseline_projection(&self, t: S) -> S {
1162	// See https://pomax.github.io/bezierinfo/#abc
1163	// We are computing the interpolation factor between
1164	// `from` and `to` to get the position of C.
1165	let one_t = S::ONE - t;
1166	let one_t3 = one_t * one_t * one_t;
1167	let t3 = t * t * t;
1168
1169	t3 / (t3 + one_t3)
1170	}
1171
1172	fn abc_ratio(&self, t: S) -> S {
1173	// See https://pomax.github.io/bezierinfo/#abc
1174	let one_t = S::ONE - t;
1175	let one_t3 = one_t * one_t * one_t;
1176	let t3 = t * t * t;
1177
1178	((t3 + one_t3 - S::ONE) / (t3 + one_t3)).abs()
1179	}
1180
1181	// Returns a quadratic bézier curve built by dragging this curve's point at `t`
1182	// to a new position, without moving the endpoints.
1183	//
1184	// The relative effect on control points is chosen to give a similar "feel" to
1185	// most vector graphics editors: dragging from near the first endpoint will affect
1186	// the first control point more than the second control point, etc.
1187	pub fn drag(&self, t: S, new_position: Point<S>) -> Self {
1188	// A lot of tweaking could go into making the weight feel as natural as possible.
1189	let min = S::value(`0.1`);
1190	let max = S::value(`0.9`);
1191	let weight = if t < min {
1192	S::ZERO
1193	} else if t > max {
1194	S::ONE
1195	} else {
1196	(t - min) / (max - min)
1197	};
1198
1199	self.drag_with_weight(t, new_position, weight)
1200	}
1201
1202	// Returns a quadratic bézier curve built by dragging this curve's point at `t`
1203	// to a new position, without moving the endpoints.
1204	//
1205	// The provided weight specifies the relative effect on control points.
1206	// - with `weight = 0.5`, `ctrl1` and `ctrl2` are equally affected,
1207	// - with `weight = 0.0`, only `ctrl1` is affected,
1208	// - with `weight = 1.0`, only `ctrl2` is affected,
1209	// - etc.
1210	pub fn drag_with_weight(&self, t: S, new_position: Point<S>, weight: S) -> Self {
1211	// See https://pomax.github.io/bezierinfo/#abc
1212	//
1213	// From-----------Ctrl1
1214	// \| \ d1 \
1215	// C-------P--------A \ d12
1216	// \| \d2 \
1217	// \| \ \
1218	// To-----------------Ctrl2
1219	//
1220	// The ABC relation means we can place the new control points however we like
1221	// as long as the ratios CA/CP, d1/d12 and d2/d12 remain constant.
1222	//
1223	// we use the weight to guide our decisions. A weight of 0.5 would be a uniform
1224	// displacement (d1 and d2 do not change and both control points are moved by the
1225	// same amount).
1226	// The approach is to use the weight interpolate the most constrained control point
1227	// between it's old position and the position it would have with uniform displacement.
1228	// then we determine the position of the least constrained control point such that
1229	// the ratios mentioned earlier remain constant.
1230
1231	let c = self.from.lerp(self.to, self.baseline_projection(t));
1232	let cacp_ratio = self.abc_ratio(t);
1233
1234	let old_pos = self.sample(t);
1235	// Construct A before and after drag using the constance ca/cp ratio
1236	let old_a = old_pos + (old_pos - c) / cacp_ratio;
1237	let new_a = new_position + (new_position - c) / cacp_ratio;
1238
1239	// Sort ctrl1 and ctrl2 such ctrl1 is the least affected (or most constrained).
1240	let mut ctrl1 = self.ctrl1;
1241	let mut ctrl2 = self.ctrl2;
1242	if t < S::HALF {
1243	core::mem::swap(&mut ctrl1, &mut ctrl2);
1244	}
1245
1246	// Move the most constrained control point by a subset of the uniform displacement
1247	// depending on the weight.
1248	let uniform_displacement = new_a - old_a;
1249	let f = if t < S::HALF {
1250	S::TWO * weight
1251	} else {
1252	S::TWO * (S::ONE - weight)
1253	};
1254	let mut new_ctrl1 = ctrl1 + uniform_displacement * f;
1255
1256	// Now that the most constrained control point is placed there is only one position
1257	// for the least constrained control point that satisfies the constant ratios.
1258	let d1_pre = (old_a - ctrl1).length();
1259	let d12_pre = (self.ctrl2 - self.ctrl1).length();
1260
1261	let mut new_ctrl2 = new_ctrl1 + (new_a - new_ctrl1) * (d12_pre / d1_pre);
1262
1263	if t < S::HALF {
1264	core::mem::swap(&mut new_ctrl1, &mut new_ctrl2);
1265	}
1266
1267	CubicBezierSegment {
1268	from: self.from,
1269	ctrl1: new_ctrl1,
1270	ctrl2: new_ctrl2,
1271	to: self.to,
1272	}
1273	}
1274
1275	pub fn to_f32(&self) -> CubicBezierSegment<f32> {
1276	CubicBezierSegment {
1277	from: self.from.to_f32(),
1278	ctrl1: self.ctrl1.to_f32(),
1279	ctrl2: self.ctrl2.to_f32(),
1280	to: self.to.to_f32(),
1281	}
1282	}
1283
1284	pub fn to_f64(&self) -> CubicBezierSegment<f64> {
1285	CubicBezierSegment {
1286	from: self.from.to_f64(),
1287	ctrl1: self.ctrl1.to_f64(),
1288	ctrl2: self.ctrl2.to_f64(),
1289	to: self.to.to_f64(),
1290	}
1291	}
1292	}
1293
1294	impl<S: Scalar> Segment for CubicBezierSegment<S> {
1295	impl_segment!(S);
1296
1297	fn for_each_flattened_with_t(
1298	&self,
1299	tolerance: Self::Scalar,
1300	callback: &mut dyn FnMut(&LineSegment<S>, Range<S>),
1301	) {
1302	self.for_each_flattened_with_t(tolerance, &mut \|s: &LineSegment~~, t: Range~~\| callback(s, t));~~~~
1303	}
1304	}
1305
1306	impl<S: Scalar> BoundingBox for CubicBezierSegment<S> {
1307	type Scalar = S;
1308	fn bounding_range_x(&self) -> (S, S) {
1309	self.bounding_range_x()
1310	}
1311	fn bounding_range_y(&self) -> (S, S) {
1312	self.bounding_range_y()
1313	}
1314	fn fast_bounding_range_x(&self) -> (S, S) {
1315	self.fast_bounding_range_x()
1316	}
1317	fn fast_bounding_range_y(&self) -> (S, S) {
1318	self.fast_bounding_range_y()
1319	}
1320	}
1321
1322	use crate::quadratic_bezier::FlattenedT as FlattenedQuadraticSegment;
1323
1324	pub struct Flattened<S: Scalar> {
1325	curve: CubicBezierSegment<S>,
1326	current_curve: FlattenedQuadraticSegment<S>,
1327	remaining_sub_curves: i32,
1328	tolerance: S,
1329	range_step: S,
1330	range_start: S,
1331	}
1332
1333	impl<S: Scalar> Flattened<S> {
1334	pub(crate) fn new(curve: &CubicBezierSegment<S>, tolerance: S) -> Self {
1335	debug_assert!(tolerance >= S::EPSILON * S::EPSILON);
1336
1337	let quadratics_tolerance: S = tolerance * S::value(`0.4`);
1338	let flattening_tolerance: S = tolerance * S::value(`0.8`);
1339
1340	let num_quadratics: S = curve.num_quadratics_impl(quadratics_tolerance);
1341
1342	let range_step: S = S::ONE / num_quadratics;
1343
1344	let quadratic: QuadraticBezierSegment ~~= curve.split_range(S::ZERO..range_step).to_quadratic();~~
1345	let current_curve: FlattenedT ~~= FlattenedQuadraticSegment::new(&quadratic, flattening_tolerance);~~
1346
1347	Flattened {
1348	curve: *curve,
1349	current_curve,
1350	remaining_sub_curves: num_quadratics.to_i32().unwrap() - `1`,
1351	tolerance: flattening_tolerance,
1352	range_start: S::ZERO,
1353	range_step,
1354	}
1355	}
1356	}
1357
1358	impl<S: Scalar> Iterator for Flattened<S> {
1359	type Item = Point<S>;
1360
1361	fn next(&mut self) -> Option<Point<S>> {
1362	if let Some(t_inner) = self.current_curve.next() {
1363	let t = self.range_start + t_inner * self.range_step;
1364	return Some(self.curve.sample(t));
1365	}
1366
1367	if self.remaining_sub_curves <= `0` {
1368	return None;
1369	}
1370
1371	self.range_start += self.range_step;
1372	let t0 = self.range_start;
1373	let t1 = self.range_start + self.range_step;
1374	self.remaining_sub_curves -= `1`;
1375
1376	let quadratic = self.curve.split_range(t0..t1).to_quadratic();
1377	self.current_curve = FlattenedQuadraticSegment::new(&quadratic, self.tolerance);
1378
1379	let t_inner = self.current_curve.next().unwrap_or(S::ONE);
1380	let t = t0 + t_inner * self.range_step;
1381
1382	Some(self.curve.sample(t))
1383	}
1384
1385	fn size_hint(&self) -> (usize, Option<usize>) {
1386	(
1387	self.remaining_sub_curves as usize * self.current_curve.size_hint().0,
1388	None,
1389	)
1390	}
1391	}
1392
1393	#[cfg(test)]
1394	fn print_arrays(a: &[Point<f32>], b: &[Point<f32>]) {
1395	std::println!("left: {a:?}");
1396	std::println!("right: {b:?}");
1397	}
1398
1399	#[cfg(test)]
1400	fn assert_approx_eq(a: &[Point<f32>], b: &[Point<f32>]) {
1401	if a.len() != b.len() {
1402	print_arrays(a, b);
1403	panic!("Lengths differ ({} != {})", a.len(), b.len());
1404	}
1405	for i in `0`..a.len() {
1406	let threshold = `0.029`;
1407	let dx = f32::abs(a[i].x - b[i].x);
1408	let dy = f32::abs(a[i].y - b[i].y);
1409	if dx > threshold \|\| dy > threshold {
1410	print_arrays(a, b);
1411	std::println!("diff = {dx:?} {dy:?}");
1412	panic!("The arrays are not equal");
1413	}
1414	}
1415	}
1416
1417	#[test]
1418	fn test_iterator_builder_1() {
1419	let tolerance = `0.01`;
1420	let c1 = CubicBezierSegment {
1421	from: Point::new(`0.0`, `0.0`),
1422	ctrl1: Point::new(`1.0`, `0.0`),
1423	ctrl2: Point::new(`1.0`, `1.0`),
1424	to: Point::new(`0.0`, `1.0`),
1425	};
1426	let iter_points: Vec<Point<f32>> = c1.flattened(tolerance).collect();
1427	let mut builder_points = Vec::new();
1428	c1.for_each_flattened(tolerance, &mut \|s\| {
1429	builder_points.push(s.to);
1430	});
1431
1432	assert!(iter_points.len() > `2`);
1433	assert_approx_eq(&iter_points[..], &builder_points[..]);
1434	}
1435
1436	#[test]
1437	fn test_iterator_builder_2() {
1438	let tolerance = `0.01`;
1439	let c1 = CubicBezierSegment {
1440	from: Point::new(`0.0`, `0.0`),
1441	ctrl1: Point::new(`1.0`, `0.0`),
1442	ctrl2: Point::new(`0.0`, `1.0`),
1443	to: Point::new(`1.0`, `1.0`),
1444	};
1445	let iter_points: Vec<Point<f32>> = c1.flattened(tolerance).collect();
1446	let mut builder_points = Vec::new();
1447	c1.for_each_flattened(tolerance, &mut \|s\| {
1448	builder_points.push(s.to);
1449	});
1450
1451	assert!(iter_points.len() > `2`);
1452	assert_approx_eq(&iter_points[..], &builder_points[..]);
1453	}
1454
1455	#[test]
1456	fn test_iterator_builder_3() {
1457	let tolerance = `0.01`;
1458	let c1 = CubicBezierSegment {
1459	from: Point::new(`141.0`, `135.0`),
1460	ctrl1: Point::new(`141.0`, `130.0`),
1461	ctrl2: Point::new(`140.0`, `130.0`),
1462	to: Point::new(`131.0`, `130.0`),
1463	};
1464	let iter_points: Vec<Point<f32>> = c1.flattened(tolerance).collect();
1465	let mut builder_points = Vec::new();
1466	c1.for_each_flattened(tolerance, &mut \|s\| {
1467	builder_points.push(s.to);
1468	});
1469
1470	assert!(iter_points.len() > `2`);
1471	assert_approx_eq(&iter_points[..], &builder_points[..]);
1472	}
1473
1474	#[test]
1475	fn test_issue_19() {
1476	let tolerance = `0.15`;
1477	let c1 = CubicBezierSegment {
1478	from: Point::new(`11.71726`, `9.07143`),
1479	ctrl1: Point::new(`1.889879`, `13.22917`),
1480	ctrl2: Point::new(`18.142855`, `19.27679`),
1481	to: Point::new(`18.142855`, `19.27679`),
1482	};
1483	let iter_points: Vec<Point<f32>> = c1.flattened(tolerance).collect();
1484	let mut builder_points = Vec::new();
1485	c1.for_each_flattened(tolerance, &mut \|s\| {
1486	builder_points.push(s.to);
1487	});
1488
1489	assert_approx_eq(&iter_points[..], &builder_points[..]);
1490
1491	assert!(iter_points.len() > `1`);
1492	}
1493
1494	#[test]
1495	fn test_issue_194() {
1496	let segment = CubicBezierSegment {
1497	from: Point::new(`0.0`, `0.0`),
1498	ctrl1: Point::new(`0.0`, `0.0`),
1499	ctrl2: Point::new(`50.0`, `70.0`),
1500	to: Point::new(`100.0`, `100.0`),
1501	};
1502
1503	let mut points = Vec::new();
1504	segment.for_each_flattened(`0.1`, &mut \|s\| {
1505	points.push(s.to);
1506	});
1507
1508	assert!(points.len() > `2`);
1509	}
1510
1511	#[test]
1512	fn flatten_with_t() {
1513	let segment = CubicBezierSegment {
1514	from: Point::new(`0.0f32`, `0.0`),
1515	ctrl1: Point::new(`0.0`, `0.0`),
1516	ctrl2: Point::new(`50.0`, `70.0`),
1517	to: Point::new(`100.0`, `100.0`),
1518	};
1519
1520	for tolerance in &[`0.1`, `0.01`, `0.001`, `0.0001`] {
1521	let tolerance = *tolerance;
1522
1523	let mut a = Vec::new();
1524	segment.for_each_flattened(tolerance, &mut \|s\| {
1525	a.push(*s);
1526	});
1527
1528	let mut b = Vec::new();
1529	let mut ts = Vec::new();
1530	segment.for_each_flattened_with_t(tolerance, &mut \|s, t\| {
1531	b.push(*s);
1532	ts.push(t);
1533	});
1534
1535	assert_eq!(a, b);
1536
1537	for i in `0`..b.len() {
1538	let sampled = segment.sample(ts[i].start);
1539	let point = b[i].from;
1540	let dist = (sampled - point).length();
1541	assert!(dist <= tolerance);
1542
1543	let sampled = segment.sample(ts[i].end);
1544	let point = b[i].to;
1545	let dist = (sampled - point).length();
1546	assert!(dist <= tolerance);
1547	}
1548	}
1549	}
1550
1551	#[test]
1552	fn test_flatten_end() {
1553	let segment = CubicBezierSegment {
1554	from: Point::new(`0.0`, `0.0`),
1555	ctrl1: Point::new(`100.0`, `0.0`),
1556	ctrl2: Point::new(`100.0`, `100.0`),
1557	to: Point::new(`100.0`, `200.0`),
1558	};
1559
1560	let mut last = segment.from;
1561	segment.for_each_flattened(`0.0001`, &mut \|s\| {
1562	last = s.to;
1563	});
1564
1565	assert_eq!(last, segment.to);
1566	}
1567
1568	#[test]
1569	fn test_flatten_point() {
1570	let segment = CubicBezierSegment {
1571	from: Point::new(`0.0`, `0.0`),
1572	ctrl1: Point::new(`0.0`, `0.0`),
1573	ctrl2: Point::new(`0.0`, `0.0`),
1574	to: Point::new(`0.0`, `0.0`),
1575	};
1576
1577	let mut last = segment.from;
1578	segment.for_each_flattened(`0.0001`, &mut \|s\| {
1579	last = s.to;
1580	});
1581
1582	assert_eq!(last, segment.to);
1583	}
1584
1585	#[test]
1586	fn issue_652() {
1587	use crate::point;
1588
1589	let curve = CubicBezierSegment {
1590	from: point(`-1061.0`, `-3327.0`),
1591	ctrl1: point(`-1061.0`, `-3177.0`),
1592	ctrl2: point(`-1061.0`, `-3477.0`),
1593	to: point(`-1061.0`, `-3327.0`),
1594	};
1595
1596	for _ in curve.flattened(`1.0`) {}
1597	for _ in curve.flattened(`0.1`) {}
1598	for _ in curve.flattened(`0.01`) {}
1599
1600	curve.for_each_flattened(`1.0`, &mut \|_\| {});
1601	curve.for_each_flattened(`0.1`, &mut \|_\| {});
1602	curve.for_each_flattened(`0.01`, &mut \|_\| {});
1603	}
1604
1605	#[test]
1606	fn fast_bounding_box_for_cubic_bezier_segment() {
1607	let a = CubicBezierSegment {
1608	from: Point::new(`0.0`, `0.0`),
1609	ctrl1: Point::new(`0.5`, `1.0`),
1610	ctrl2: Point::new(`1.5`, `-1.0`),
1611	to: Point::new(`2.0`, `0.0`),
1612	};
1613
1614	let expected_aabb = Box2D {
1615	min: point(`0.0`, `-1.0`),
1616	max: point(`2.0`, `1.0`),
1617	};
1618
1619	let actual_aabb = a.fast_bounding_box();
1620
1621	assert_eq!(expected_aabb, actual_aabb)
1622	}
1623
1624	#[test]
1625	fn minimum_bounding_box_for_cubic_bezier_segment() {
1626	let a = CubicBezierSegment {
1627	from: Point::new(`0.0`, `0.0`),
1628	ctrl1: Point::new(`0.5`, `2.0`),
1629	ctrl2: Point::new(`1.5`, `-2.0`),
1630	to: Point::new(`2.0`, `0.0`),
1631	};
1632
1633	let expected_bigger_aabb: Box2D<f32> = Box2D {
1634	min: point(`0.0`, `-0.6`),
1635	max: point(`2.0`, `0.6`),
1636	};
1637	let expected_smaller_aabb: Box2D<f32> = Box2D {
1638	min: point(`0.1`, `-0.5`),
1639	max: point(`2.0`, `0.5`),
1640	};
1641
1642	let actual_minimum_aabb = a.bounding_box();
1643
1644	assert!(expected_bigger_aabb.contains_box(&actual_minimum_aabb));
1645	assert!(actual_minimum_aabb.contains_box(&expected_smaller_aabb));
1646	}
1647
1648	#[test]
1649	fn y_maximum_t_for_simple_cubic_segment() {
1650	let a = CubicBezierSegment {
1651	from: Point::new(`0.0`, `0.0`),
1652	ctrl1: Point::new(`0.5`, `1.0`),
1653	ctrl2: Point::new(`1.5`, `1.0`),
1654	to: Point::new(`2.0`, `2.0`),
1655	};
1656
1657	let expected_y_maximum = `1.0`;
1658
1659	let actual_y_maximum = a.y_maximum_t();
1660
1661	assert_eq!(expected_y_maximum, actual_y_maximum)
1662	}
1663
1664	#[test]
1665	fn y_minimum_t_for_simple_cubic_segment() {
1666	let a = CubicBezierSegment {
1667	from: Point::new(`0.0`, `0.0`),
1668	ctrl1: Point::new(`0.5`, `1.0`),
1669	ctrl2: Point::new(`1.5`, `1.0`),
1670	to: Point::new(`2.0`, `0.0`),
1671	};
1672
1673	let expected_y_minimum = `0.0`;
1674
1675	let actual_y_minimum = a.y_minimum_t();
1676
1677	assert_eq!(expected_y_minimum, actual_y_minimum)
1678	}
1679
1680	#[test]
1681	fn y_extrema_for_simple_cubic_segment() {
1682	let a = CubicBezierSegment {
1683	from: Point::new(`0.0`, `0.0`),
1684	ctrl1: Point::new(`1.0`, `2.0`),
1685	ctrl2: Point::new(`2.0`, `2.0`),
1686	to: Point::new(`3.0`, `0.0`),
1687	};
1688
1689	let mut n: u32 = `0`;
1690	a.for_each_local_y_extremum_t(&mut \|t\| {
1691	assert_eq!(t, `0.5`);
1692	n += `1`;
1693	});
1694	assert_eq!(n, `1`);
1695	}
1696
1697	#[test]
1698	fn x_extrema_for_simple_cubic_segment() {
1699	let a = CubicBezierSegment {
1700	from: Point::new(`0.0`, `0.0`),
1701	ctrl1: Point::new(`1.0`, `2.0`),
1702	ctrl2: Point::new(`1.0`, `2.0`),
1703	to: Point::new(`0.0`, `0.0`),
1704	};
1705
1706	let mut n: u32 = `0`;
1707	a.for_each_local_x_extremum_t(&mut \|t\| {
1708	assert_eq!(t, `0.5`);
1709	n += `1`;
1710	});
1711	assert_eq!(n, `1`);
1712	}
1713
1714	#[test]
1715	fn x_maximum_t_for_simple_cubic_segment() {
1716	let a = CubicBezierSegment {
1717	from: Point::new(`0.0`, `0.0`),
1718	ctrl1: Point::new(`0.5`, `1.0`),
1719	ctrl2: Point::new(`1.5`, `1.0`),
1720	to: Point::new(`2.0`, `0.0`),
1721	};
1722	let expected_x_maximum = `1.0`;
1723
1724	let actual_x_maximum = a.x_maximum_t();
1725
1726	assert_eq!(expected_x_maximum, actual_x_maximum)
1727	}
1728
1729	#[test]
1730	fn x_minimum_t_for_simple_cubic_segment() {
1731	let a = CubicBezierSegment {
1732	from: Point::new(`0.0`, `0.0`),
1733	ctrl1: Point::new(`0.5`, `1.0`),
1734	ctrl2: Point::new(`1.5`, `1.0`),
1735	to: Point::new(`2.0`, `0.0`),
1736	};
1737
1738	let expected_x_minimum = `0.0`;
1739
1740	let actual_x_minimum = a.x_minimum_t();
1741
1742	assert_eq!(expected_x_minimum, actual_x_minimum)
1743	}
1744
1745	#[test]
1746	fn derivatives() {
1747	let c1 = CubicBezierSegment {
1748	from: Point::new(`1.0`, `1.0`),
1749	ctrl1: Point::new(`1.0`, `2.0`),
1750	ctrl2: Point::new(`2.0`, `1.0`),
1751	to: Point::new(`2.0`, `2.0`),
1752	};
1753
1754	assert_eq!(c1.dx(`0.0`), `0.0`);
1755	assert_eq!(c1.dx(`1.0`), `0.0`);
1756	assert_eq!(c1.dy(`0.5`), `0.0`);
1757	}
1758
1759	#[test]
1760	fn fat_line() {
1761	use crate::point;
1762
1763	let c1 = CubicBezierSegment {
1764	from: point(`1.0f32`, `2.0`),
1765	ctrl1: point(`1.0`, `3.0`),
1766	ctrl2: point(`11.0`, `11.0`),
1767	to: point(`11.0`, `12.0`),
1768	};
1769
1770	let (l1, l2) = c1.fat_line();
1771
1772	for i in `0`..`100` {
1773	let t = i as f32 / `99.0`;
1774	assert!(l1.signed_distance_to_point(&c1.sample(t)) >= -`0.000001`);
1775	assert!(l2.signed_distance_to_point(&c1.sample(t)) <= `0.000001`);
1776	}
1777
1778	let c2 = CubicBezierSegment {
1779	from: point(`1.0f32`, `2.0`),
1780	ctrl1: point(`1.0`, `3.0`),
1781	ctrl2: point(`11.0`, `14.0`),
1782	to: point(`11.0`, `12.0`),
1783	};
1784
1785	let (l1, l2) = c2.fat_line();
1786
1787	for i in `0`..`100` {
1788	let t = i as f32 / `99.0`;
1789	assert!(l1.signed_distance_to_point(&c2.sample(t)) >= -`0.000001`);
1790	assert!(l2.signed_distance_to_point(&c2.sample(t)) <= `0.000001`);
1791	}
1792
1793	let c3 = CubicBezierSegment {
1794	from: point(`0.0f32`, `1.0`),
1795	ctrl1: point(`0.5`, `0.0`),
1796	ctrl2: point(`0.5`, `0.0`),
1797	to: point(`1.0`, `1.0`),
1798	};
1799
1800	let (l1, l2) = c3.fat_line();
1801
1802	for i in `0`..`100` {
1803	let t = i as f32 / `99.0`;
1804	assert!(l1.signed_distance_to_point(&c3.sample(t)) >= -`0.000001`);
1805	assert!(l2.signed_distance_to_point(&c3.sample(t)) <= `0.000001`);
1806	}
1807	}
1808
1809	#[test]
1810	fn is_linear() {
1811	let mut angle = `0.0`;
1812	let center = Point::new(`1000.0`, `-700.0`);
1813	for _ in `0`..`100` {
1814	for i in `0`..`10` {
1815	for j in `0`..`10` {
1816	let (sin, cos) = f64::sin_cos(angle);
1817	let endpoint = Vector::new(cos * `100.0`, sin * `100.0`);
1818	let curve = CubicBezierSegment {
1819	from: center - endpoint,
1820	ctrl1: center + endpoint.lerp(-endpoint, i as f64 / `9.0`),
1821	ctrl2: center + endpoint.lerp(-endpoint, j as f64 / `9.0`),
1822	to: center + endpoint,
1823	};
1824	assert!(curve.is_linear(`1e-10`));
1825	}
1826	}
1827	angle += `0.001`;
1828	}
1829	}
1830
1831	#[test]
1832	fn test_monotonic() {
1833	use crate::point;
1834	let curve = CubicBezierSegment {
1835	from: point(`1.0`, `1.0`),
1836	ctrl1: point(`10.0`, `2.0`),
1837	ctrl2: point(`1.0`, `3.0`),
1838	to: point(`10.0`, `4.0`),
1839	};
1840
1841	curve.for_each_monotonic_range(&mut \|range\| {
1842	let sub_curve = curve.split_range(range);
1843	assert!(sub_curve.is_monotonic());
1844	});
1845	}
1846
1847	#[test]
1848	fn test_line_segment_intersections() {
1849	use crate::point;
1850	fn assert_approx_eq(a: ArrayVec<(f32, f32), `3`>, b: &[(f32, f32)], epsilon: f32) {
1851	for i in `0`..a.len() {
1852	if f32::abs(a[i].0 - b[i].0) > epsilon \|\| f32::abs(a[i].1 - b[i].1) > epsilon {
1853	std::println!("{a:?} != {b:?}");
1854	}
1855	assert!((a[i].`0` - b[i].`0`).abs() <= epsilon && (a[i].`1` - b[i].`1`).abs() <= epsilon);
1856	}
1857	assert_eq!(a.len(), b.len());
1858	}
1859
1860	let epsilon = `0.0001`;
1861
1862	// Make sure we find intersections with horizontal and vertical lines.
1863
1864	let curve1 = CubicBezierSegment {
1865	from: point(`-1.0`, `-1.0`),
1866	ctrl1: point(`0.0`, `4.0`),
1867	ctrl2: point(`10.0`, `-4.0`),
1868	to: point(`11.0`, `1.0`),
1869	};
1870	let seg1 = LineSegment {
1871	from: point(`0.0`, `0.0`),
1872	to: point(`10.0`, `0.0`),
1873	};
1874	assert_approx_eq(
1875	curve1.line_segment_intersections_t(&seg1),
1876	&[(`0.5`, `0.5`)],
1877	epsilon,
1878	);
1879
1880	let curve2 = CubicBezierSegment {
1881	from: point(`-1.0`, `0.0`),
1882	ctrl1: point(`0.0`, `5.0`),
1883	ctrl2: point(`0.0`, `5.0`),
1884	to: point(`1.0`, `0.0`),
1885	};
1886	let seg2 = LineSegment {
1887	from: point(`0.0`, `0.0`),
1888	to: point(`0.0`, `5.0`),
1889	};
1890	assert_approx_eq(
1891	curve2.line_segment_intersections_t(&seg2),
1892	&[(`0.5`, `0.75`)],
1893	epsilon,
1894	);
1895	}
1896
1897	#[test]
1898	fn test_parameters_for_value() {
1899	use crate::point;
1900	fn assert_approx_eq(a: ArrayVec<f32, `3`>, b: &[f32], epsilon: f32) {
1901	for i in `0`..a.len() {
1902	if f32::abs(a[i] - b[i]) > epsilon {
1903	std::println!("{a:?} != {b:?}");
1904	}
1905	assert!((a[i] - b[i]).abs() <= epsilon);
1906	}
1907	assert_eq!(a.len(), b.len());
1908	}
1909
1910	{
1911	let curve = CubicBezierSegment {
1912	from: point(`0.0`, `0.0`),
1913	ctrl1: point(`0.0`, `8.0`),
1914	ctrl2: point(`10.0`, `8.0`),
1915	to: point(`10.0`, `0.0`),
1916	};
1917
1918	let epsilon = `1e-4`;
1919	assert_approx_eq(curve.solve_t_for_x(`5.0`), &[`0.5`], epsilon);
1920	assert_approx_eq(curve.solve_t_for_y(`6.0`), &[`0.5`], epsilon);
1921	}
1922	{
1923	let curve = CubicBezierSegment {
1924	from: point(`0.0`, `10.0`),
1925	ctrl1: point(`0.0`, `10.0`),
1926	ctrl2: point(`10.0`, `10.0`),
1927	to: point(`10.0`, `10.0`),
1928	};
1929
1930	assert_approx_eq(curve.solve_t_for_y(`10.0`), &[], `0.0`);
1931	}
1932	}
1933
1934	#[test]
1935	fn test_cubic_intersection_deduping() {
1936	use crate::point;
1937
1938	let epsilon = `0.0001`;
1939
1940	// Two "line segments" with 3-fold overlaps, intersecting in their overlaps for a total of nine
1941	// parameter intersections.
1942	let line1 = CubicBezierSegment {
1943	from: point(`-1_000_000.0`, `0.0`),
1944	ctrl1: point(`2_000_000.0`, `3_000_000.0`),
1945	ctrl2: point(`-2_000_000.0`, `-1_000_000.0`),
1946	to: point(`1_000_000.0`, `2_000_000.0`),
1947	};
1948	let line2 = CubicBezierSegment {
1949	from: point(`-1_000_000.0`, `2_000_000.0`),
1950	ctrl1: point(`2_000_000.0`, `-1_000_000.0`),
1951	ctrl2: point(`-2_000_000.0`, `3_000_000.0`),
1952	to: point(`1_000_000.0`, `0.0`),
1953	};
1954	let intersections = line1.cubic_intersections(&line2);
1955	// (If you increase the coordinates above to 10s of millions, you get two returned intersection
1956	// points; i.e. the test fails.)
1957	assert_eq!(intersections.len(), `1`);
1958	assert!(f64::abs(intersections[`0`].x) < epsilon);
1959	assert!(f64::abs(intersections[`0`].y - `1_000_000.0`) < epsilon);
1960
1961	// Two self-intersecting curves that intersect in their self-intersections, for a total of four
1962	// parameter intersections.
1963	let curve1 = CubicBezierSegment {
1964	from: point(`-10.0`, `-13.636363636363636`),
1965	ctrl1: point(`15.0`, `11.363636363636363`),
1966	ctrl2: point(`-15.0`, `11.363636363636363`),
1967	to: point(`10.0`, `-13.636363636363636`),
1968	};
1969	let curve2 = CubicBezierSegment {
1970	from: point(`13.636363636363636`, `-10.0`),
1971	ctrl1: point(`-11.363636363636363`, `15.0`),
1972	ctrl2: point(`-11.363636363636363`, `-15.0`),
1973	to: point(`13.636363636363636`, `10.0`),
1974	};
1975	let intersections = curve1.cubic_intersections(&curve2);
1976	assert_eq!(intersections.len(), `1`);
1977	assert!(f64::abs(intersections[`0`].x) < epsilon);
1978	assert!(f64::abs(intersections[`0`].y) < epsilon);
1979	}
1980
1981	#[test]
1982	fn cubic_line_intersection_on_endpoint() {
1983	let l1 = LineSegment {
1984	from: Point::new(`0.0`, `-100.0`),
1985	to: Point::new(`0.0`, `100.0`),
1986	};
1987
1988	let cubic = CubicBezierSegment {
1989	from: Point::new(`0.0`, `0.0`),
1990	ctrl1: Point::new(`20.0`, `20.0`),
1991	ctrl2: Point::new(`20.0`, `40.0`),
1992	to: Point::new(`0.0`, `60.0`),
1993	};
1994
1995	let intersections = cubic.line_segment_intersections_t(&l1);
1996
1997	assert_eq!(intersections.len(), `2`);
1998	assert_eq!(intersections[`0`], (`1.0`, `0.8`));
1999	assert_eq!(intersections[`1`], (`0.0`, `0.5`));
2000
2001	let l2 = LineSegment {
2002	from: Point::new(`0.0`, `0.0`),
2003	to: Point::new(`0.0`, `60.0`),
2004	};
2005
2006	let intersections = cubic.line_segment_intersections_t(&l2);
2007
2008	assert!(intersections.is_empty());
2009
2010	let c1 = CubicBezierSegment {
2011	from: Point::new(`0.0`, `0.0`),
2012	ctrl1: Point::new(`20.0`, `0.0`),
2013	ctrl2: Point::new(`20.0`, `20.0`),
2014	to: Point::new(`0.0`, `60.0`),
2015	};
2016
2017	let c2 = CubicBezierSegment {
2018	from: Point::new(`0.0`, `60.0`),
2019	ctrl1: Point::new(`-40.0`, `4.0`),
2020	ctrl2: Point::new(`-20.0`, `20.0`),
2021	to: Point::new(`0.0`, `00.0`),
2022	};
2023
2024	let intersections = c1.cubic_intersections_t(&c2);
2025
2026	assert!(intersections.is_empty());
2027	}
2028
2029	#[test]
2030	fn test_cubic_to_quadratics() {
2031	use euclid::approxeq::ApproxEq;
2032
2033	let quadratic = QuadraticBezierSegment {
2034	from: point(`1.0`, `2.0`),
2035	ctrl: point(`10.0`, `5.0`),
2036	to: point(`0.0`, `1.0`),
2037	};
2038
2039	let mut count = `0`;
2040	assert_eq!(quadratic.to_cubic().num_quadratics(`0.0001`), `1`);
2041	quadratic
2042	.to_cubic()
2043	.for_each_quadratic_bezier(`0.0001`, &mut \|c\| {
2044	assert_eq!(count, `0`);
2045	assert!(c.from.approx_eq(&quadratic.from));
2046	assert!(c.ctrl.approx_eq(&quadratic.ctrl));
2047	assert!(c.to.approx_eq(&quadratic.to));
2048	count += `1`;
2049	});
2050
2051	let cubic = CubicBezierSegment {
2052	from: point(`1.0f32`, `1.0`),
2053	ctrl1: point(`10.0`, `2.0`),
2054	ctrl2: point(`1.0`, `3.0`),
2055	to: point(`10.0`, `4.0`),
2056	};
2057
2058	let mut prev = cubic.from;
2059	let mut count = `0`;
2060	cubic.for_each_quadratic_bezier(`0.01`, &mut \|c\| {
2061	assert!(c.from.approx_eq(&prev));
2062	prev = c.to;
2063	count += `1`;
2064	});
2065	assert!(prev.approx_eq(&cubic.to));
2066	assert!(count < `10`);
2067	assert!(count > `4`);
2068	}
2069