1// Copyright 2018 the Kurbo Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Bézier paths (up to cubic).
5
6#![allow(clippy::many_single_char_names)]
7
8use core::iter::{Extend, FromIterator};
9use core::mem;
10use core::ops::{Mul, Range};
11
12use alloc::vec::Vec;
13
14use arrayvec::ArrayVec;
15
16use crate::common::{solve_cubic, solve_quadratic};
17use crate::MAX_EXTREMA;
18use crate::{
19 Affine, CubicBez, Line, Nearest, ParamCurve, ParamCurveArclen, ParamCurveArea,
20 ParamCurveExtrema, ParamCurveNearest, Point, QuadBez, Rect, Shape, TranslateScale, Vec2,
21};
22
23#[cfg(not(feature = "std"))]
24use crate::common::FloatFuncs;
25
26/// A Bézier path.
27///
28/// These docs assume basic familiarity with Bézier curves; for an introduction,
29/// see Pomax's wonderful [A Primer on Bézier Curves].
30///
31/// This path can contain lines, quadratics ([`QuadBez`]) and cubics
32/// ([`CubicBez`]), and may contain multiple subpaths.
33///
34/// # Elements and Segments
35///
36/// A Bézier path can be represented in terms of either 'elements' ([`PathEl`])
37/// or 'segments' ([`PathSeg`]). Elements map closely to how Béziers are
38/// generally used in PostScript-style drawing APIs; they can be thought of as
39/// instructions for drawing the path. Segments more directly describe the
40/// path itself, with each segment being an independent line or curve.
41///
42/// These different representations are useful in different contexts.
43/// For tasks like drawing, elements are a natural fit, but when doing
44/// hit-testing or subdividing, we need to have access to the segments.
45///
46/// Conceptually, a `BezPath` contains zero or more subpaths. Each subpath
47/// *always* begins with a `MoveTo`, then has zero or more `LineTo`, `QuadTo`,
48/// and `CurveTo` elements, and optionally ends with a `ClosePath`.
49///
50/// Internally, a `BezPath` is a list of [`PathEl`]s; as such it implements
51/// [`FromIterator<PathEl>`] and [`Extend<PathEl>`]:
52///
53/// ```
54/// use kurbo::{BezPath, Rect, Shape, Vec2};
55/// let accuracy = 0.1;
56/// let rect = Rect::from_origin_size((0., 0.,), (10., 10.));
57/// // these are equivalent
58/// let path1 = rect.to_path(accuracy);
59/// let path2: BezPath = rect.path_elements(accuracy).collect();
60///
61/// // extend a path with another path:
62/// let mut path = rect.to_path(accuracy);
63/// let shifted_rect = rect + Vec2::new(5.0, 10.0);
64/// path.extend(shifted_rect.to_path(accuracy));
65/// ```
66///
67/// You can iterate the elements of a `BezPath` with the [`iter`] method,
68/// and the segments with the [`segments`] method:
69///
70/// ```
71/// use kurbo::{BezPath, Line, PathEl, PathSeg, Point, Rect, Shape};
72/// let accuracy = 0.1;
73/// let rect = Rect::from_origin_size((0., 0.,), (10., 10.));
74/// // these are equivalent
75/// let path = rect.to_path(accuracy);
76/// let first_el = PathEl::MoveTo(Point::ZERO);
77/// let first_seg = PathSeg::Line(Line::new((0., 0.), (10., 0.)));
78/// assert_eq!(path.iter().next(), Some(first_el));
79/// assert_eq!(path.segments().next(), Some(first_seg));
80/// ```
81/// In addition, if you have some other type that implements
82/// `Iterator<Item=PathEl>`, you can adapt that to an iterator of segments with
83/// the [`segments` free function].
84///
85/// # Advanced functionality
86///
87/// In addition to the basic API, there are several useful pieces of advanced
88/// functionality available on `BezPath`:
89///
90/// - [`flatten`] does Bézier flattening, converting a curve to a series of
91/// line segments
92/// - [`intersect_line`] computes intersections of a path with a line, useful
93/// for things like subdividing
94///
95/// [A Primer on Bézier Curves]: https://pomax.github.io/bezierinfo/
96/// [`iter`]: BezPath::iter
97/// [`segments`]: BezPath::segments
98/// [`flatten`]: flatten
99/// [`intersect_line`]: PathSeg::intersect_line
100/// [`segments` free function]: segments
101/// [`FromIterator<PathEl>`]: std::iter::FromIterator
102/// [`Extend<PathEl>`]: std::iter::Extend
103#[derive(Clone, Default, Debug, PartialEq)]
104#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
105#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
106pub struct BezPath(Vec<PathEl>);
107
108/// The element of a Bézier path.
109///
110/// A valid path has `MoveTo` at the beginning of each subpath.
111#[derive(Clone, Copy, Debug, PartialEq)]
112#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
113#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
114pub enum PathEl {
115 /// Move directly to the point without drawing anything, starting a new
116 /// subpath.
117 MoveTo(Point),
118 /// Draw a line from the current location to the point.
119 LineTo(Point),
120 /// Draw a quadratic bezier using the current location and the two points.
121 QuadTo(Point, Point),
122 /// Draw a cubic bezier using the current location and the three points.
123 CurveTo(Point, Point, Point),
124 /// Close off the path.
125 ClosePath,
126}
127
128/// A segment of a Bézier path.
129#[derive(Clone, Copy, Debug, PartialEq)]
130#[cfg_attr(feature = "schemars", derive(schemars::JsonSchema))]
131#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
132pub enum PathSeg {
133 /// A line segment.
134 Line(Line),
135 /// A quadratic bezier segment.
136 Quad(QuadBez),
137 /// A cubic bezier segment.
138 Cubic(CubicBez),
139}
140
141/// An intersection of a [`Line`] and a [`PathSeg`].
142///
143/// This can be generated with the [`PathSeg::intersect_line`] method.
144#[derive(Debug, Clone, Copy)]
145pub struct LineIntersection {
146 /// The 'time' that the intersection occurs, on the line.
147 ///
148 /// This value is in the range 0..1.
149 pub line_t: f64,
150
151 /// The 'time' that the intersection occurs, on the path segment.
152 ///
153 /// This value is nominally in the range 0..1, although it may slightly exceed
154 /// that range at the boundaries of segments.
155 pub segment_t: f64,
156}
157
158/// The minimum distance between two Bézier curves.
159pub struct MinDistance {
160 /// The shortest distance between any two points on the two curves.
161 pub distance: f64,
162 /// The position of the nearest point on the first curve, as a parameter.
163 ///
164 /// To resolve this to a [`Point`], use [`ParamCurve::eval`].
165 ///
166 /// [`ParamCurve::eval`]: crate::ParamCurve::eval
167 pub t1: f64,
168 /// The position of the nearest point on the second curve, as a parameter.
169 ///
170 /// To resolve this to a [`Point`], use [`ParamCurve::eval`].
171 ///
172 /// [`ParamCurve::eval`]: crate::ParamCurve::eval
173 pub t2: f64,
174}
175
176impl BezPath {
177 /// Create a new path.
178 pub fn new() -> BezPath {
179 Default::default()
180 }
181
182 /// Create a path from a vector of path elements.
183 ///
184 /// `BezPath` also implements `FromIterator<PathEl>`, so it works with `collect`:
185 ///
186 /// ```
187 /// // a very contrived example:
188 /// use kurbo::{BezPath, PathEl};
189 ///
190 /// let path = BezPath::new();
191 /// let as_vec: Vec<PathEl> = path.into_iter().collect();
192 /// let back_to_path: BezPath = as_vec.into_iter().collect();
193 /// ```
194 pub fn from_vec(v: Vec<PathEl>) -> BezPath {
195 debug_assert!(
196 v.first().is_none() || matches!(v.first(), Some(PathEl::MoveTo(_))),
197 "BezPath must begin with MoveTo"
198 );
199 BezPath(v)
200 }
201
202 /// Removes the last [`PathEl`] from the path and returns it, or `None` if the path is empty.
203 pub fn pop(&mut self) -> Option<PathEl> {
204 self.0.pop()
205 }
206
207 /// Push a generic path element onto the path.
208 pub fn push(&mut self, el: PathEl) {
209 self.0.push(el);
210 debug_assert!(
211 matches!(self.0.first(), Some(PathEl::MoveTo(_))),
212 "BezPath must begin with MoveTo"
213 );
214 }
215
216 /// Push a "move to" element onto the path.
217 pub fn move_to<P: Into<Point>>(&mut self, p: P) {
218 self.push(PathEl::MoveTo(p.into()));
219 }
220
221 /// Push a "line to" element onto the path.
222 ///
223 /// Will panic with a debug assert when the path is empty and there is no
224 /// "move to" element on the path.
225 ///
226 /// If `line_to` is called immediately after `close_path` then the current
227 /// subpath starts at the initial point of the previous subpath.
228 pub fn line_to<P: Into<Point>>(&mut self, p: P) {
229 debug_assert!(!self.0.is_empty(), "uninitialized subpath (missing MoveTo)");
230 self.push(PathEl::LineTo(p.into()));
231 }
232
233 /// Push a "quad to" element onto the path.
234 ///
235 /// Will panic with a debug assert when the path is empty and there is no
236 /// "move to" element on the path.
237 ///
238 /// If `quad_to` is called immediately after `close_path` then the current
239 /// subpath starts at the initial point of the previous subpath.
240 pub fn quad_to<P: Into<Point>>(&mut self, p1: P, p2: P) {
241 debug_assert!(!self.0.is_empty(), "uninitialized subpath (missing MoveTo)");
242 self.push(PathEl::QuadTo(p1.into(), p2.into()));
243 }
244
245 /// Push a "curve to" element onto the path.
246 ///
247 /// Will panic with a debug assert when the path is empty and there is no
248 /// "move to" element on the path.
249 ///
250 /// If `curve_to` is called immediately after `close_path` then the current
251 /// subpath starts at the initial point of the previous subpath.
252 pub fn curve_to<P: Into<Point>>(&mut self, p1: P, p2: P, p3: P) {
253 debug_assert!(!self.0.is_empty(), "uninitialized subpath (missing MoveTo)");
254 self.push(PathEl::CurveTo(p1.into(), p2.into(), p3.into()));
255 }
256
257 /// Push a "close path" element onto the path.
258 ///
259 /// Will panic with a debug assert when the path is empty and there is no
260 /// "move to" element on the path.
261 pub fn close_path(&mut self) {
262 debug_assert!(!self.0.is_empty(), "uninitialized subpath (missing MoveTo)");
263 self.push(PathEl::ClosePath);
264 }
265
266 /// Get the path elements.
267 pub fn elements(&self) -> &[PathEl] {
268 &self.0
269 }
270
271 /// Get the path elements (mut version).
272 pub fn elements_mut(&mut self) -> &mut [PathEl] {
273 &mut self.0
274 }
275
276 /// Returns an iterator over the path's elements.
277 pub fn iter(&self) -> impl Iterator<Item = PathEl> + Clone + '_ {
278 self.0.iter().copied()
279 }
280
281 /// Iterate over the path segments.
282 pub fn segments(&self) -> impl Iterator<Item = PathSeg> + Clone + '_ {
283 segments(self.iter())
284 }
285
286 /// Shorten the path, keeping the first `len` elements.
287 pub fn truncate(&mut self, len: usize) {
288 self.0.truncate(len);
289 }
290
291 /// Flatten the path, invoking the callback repeatedly.
292 ///
293 /// See [`flatten`] for more discussion.
294 #[deprecated(since = "0.11.1", note = "use the free function flatten instead")]
295 pub fn flatten(&self, tolerance: f64, callback: impl FnMut(PathEl)) {
296 flatten(self, tolerance, callback);
297 }
298
299 /// Get the segment at the given element index.
300 ///
301 /// If you need to access all segments, [`segments`] provides a better
302 /// API. This is intended for random access of specific elements, for clients
303 /// that require this specifically.
304 ///
305 /// **note**: This returns the segment that ends at the provided element
306 /// index. In effect this means it is *1-indexed*: since no segment ends at
307 /// the first element (which is presumed to be a `MoveTo`) `get_seg(0)` will
308 /// always return `None`.
309 pub fn get_seg(&self, ix: usize) -> Option<PathSeg> {
310 if ix == 0 || ix >= self.0.len() {
311 return None;
312 }
313 let last = match self.0[ix - 1] {
314 PathEl::MoveTo(p) => p,
315 PathEl::LineTo(p) => p,
316 PathEl::QuadTo(_, p2) => p2,
317 PathEl::CurveTo(_, _, p3) => p3,
318 _ => return None,
319 };
320 match self.0[ix] {
321 PathEl::LineTo(p) => Some(PathSeg::Line(Line::new(last, p))),
322 PathEl::QuadTo(p1, p2) => Some(PathSeg::Quad(QuadBez::new(last, p1, p2))),
323 PathEl::CurveTo(p1, p2, p3) => Some(PathSeg::Cubic(CubicBez::new(last, p1, p2, p3))),
324 PathEl::ClosePath => self.0[..ix].iter().rev().find_map(|el| match *el {
325 PathEl::MoveTo(start) if start != last => {
326 Some(PathSeg::Line(Line::new(last, start)))
327 }
328 _ => None,
329 }),
330 _ => None,
331 }
332 }
333
334 /// Returns `true` if the path contains no segments.
335 pub fn is_empty(&self) -> bool {
336 self.0
337 .iter()
338 .all(|el| matches!(el, PathEl::MoveTo(..) | PathEl::ClosePath))
339 }
340
341 /// Apply an affine transform to the path.
342 pub fn apply_affine(&mut self, affine: Affine) {
343 for el in self.0.iter_mut() {
344 *el = affine * (*el);
345 }
346 }
347
348 /// Is this path finite?
349 #[inline]
350 pub fn is_finite(&self) -> bool {
351 self.0.iter().all(|v| v.is_finite())
352 }
353
354 /// Is this path NaN?
355 #[inline]
356 pub fn is_nan(&self) -> bool {
357 self.0.iter().any(|v| v.is_nan())
358 }
359
360 /// Returns a rectangle that conservatively encloses the path.
361 ///
362 /// Unlike the `bounding_box` method, this uses control points directly
363 /// rather than computing tight bounds for curve elements.
364 pub fn control_box(&self) -> Rect {
365 let mut cbox: Option<Rect> = None;
366 let mut add_pts = |pts: &[Point]| {
367 for pt in pts {
368 cbox = match cbox {
369 Some(cbox) => Some(cbox.union_pt(*pt)),
370 _ => Some(Rect::from_points(*pt, *pt)),
371 };
372 }
373 };
374 for &el in self.elements() {
375 match el {
376 PathEl::MoveTo(p0) | PathEl::LineTo(p0) => add_pts(&[p0]),
377 PathEl::QuadTo(p0, p1) => add_pts(&[p0, p1]),
378 PathEl::CurveTo(p0, p1, p2) => add_pts(&[p0, p1, p2]),
379 PathEl::ClosePath => {}
380 }
381 }
382 cbox.unwrap_or_default()
383 }
384
385 /// Returns a new path with the winding direction of all subpaths reversed.
386 pub fn reverse_subpaths(&self) -> BezPath {
387 let elements = self.elements();
388 let mut start_ix = 1;
389 let mut start_pt = Point::default();
390 let mut reversed = BezPath(Vec::with_capacity(elements.len()));
391 // Pending move is used to capture degenerate subpaths that should
392 // remain in the reversed output.
393 let mut pending_move = false;
394 for (ix, el) in elements.iter().enumerate() {
395 match el {
396 PathEl::MoveTo(pt) => {
397 if pending_move {
398 reversed.push(PathEl::MoveTo(start_pt));
399 }
400 if start_ix < ix {
401 reverse_subpath(start_pt, &elements[start_ix..ix], &mut reversed);
402 }
403 pending_move = true;
404 start_pt = *pt;
405 start_ix = ix + 1;
406 }
407 PathEl::ClosePath => {
408 if start_ix <= ix {
409 reverse_subpath(start_pt, &elements[start_ix..ix], &mut reversed);
410 }
411 reversed.push(PathEl::ClosePath);
412 start_ix = ix + 1;
413 pending_move = false;
414 }
415 _ => {
416 pending_move = false;
417 }
418 }
419 }
420 if start_ix < elements.len() {
421 reverse_subpath(start_pt, &elements[start_ix..], &mut reversed);
422 } else if pending_move {
423 reversed.push(PathEl::MoveTo(start_pt));
424 }
425 reversed
426 }
427}
428
429/// Helper for reversing a subpath.
430///
431/// The `els` parameter must not contain any `MoveTo` or `ClosePath` elements.
432fn reverse_subpath(start_pt: Point, els: &[PathEl], reversed: &mut BezPath) {
433 let end_pt: Point = els.last().and_then(|el| el.end_point()).unwrap_or(default:start_pt);
434 reversed.push(el:PathEl::MoveTo(end_pt));
435 for (ix: usize, el: &PathEl) in els.iter().enumerate().rev() {
436 let end_pt: Point = if ix > 0 {
437 els[ix - 1].end_point().unwrap()
438 } else {
439 start_pt
440 };
441 match el {
442 PathEl::LineTo(_) => reversed.push(el:PathEl::LineTo(end_pt)),
443 PathEl::QuadTo(c0: &Point, _) => reversed.push(el:PathEl::QuadTo(*c0, end_pt)),
444 PathEl::CurveTo(c0: &Point, c1: &Point, _) => reversed.push(el:PathEl::CurveTo(*c1, *c0, end_pt)),
445 _ => panic!("reverse_subpath expects MoveTo and ClosePath to be removed"),
446 }
447 }
448}
449
450impl FromIterator<PathEl> for BezPath {
451 fn from_iter<T: IntoIterator<Item = PathEl>>(iter: T) -> Self {
452 let el_vec: Vec<_> = iter.into_iter().collect();
453 BezPath::from_vec(el_vec)
454 }
455}
456
457/// Allow iteration over references to `BezPath`.
458///
459/// Note: the semantics are slightly different from simply iterating over the
460/// slice, as it returns `PathEl` items, rather than references.
461impl<'a> IntoIterator for &'a BezPath {
462 type Item = PathEl;
463 type IntoIter = core::iter::Cloned<core::slice::Iter<'a, PathEl>>;
464
465 fn into_iter(self) -> Self::IntoIter {
466 self.elements().iter().cloned()
467 }
468}
469
470impl IntoIterator for BezPath {
471 type Item = PathEl;
472 type IntoIter = alloc::vec::IntoIter<PathEl>;
473
474 fn into_iter(self) -> Self::IntoIter {
475 self.0.into_iter()
476 }
477}
478
479impl Extend<PathEl> for BezPath {
480 fn extend<I: IntoIterator<Item = PathEl>>(&mut self, iter: I) {
481 self.0.extend(iter);
482 }
483}
484
485/// Proportion of tolerance budget that goes to cubic to quadratic conversion.
486const TO_QUAD_TOL: f64 = 0.1;
487
488/// Flatten the path, invoking the callback repeatedly.
489///
490/// Flattening is the action of approximating a curve with a succession of line segments.
491///
492/// <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 120 30" height="30mm" width="120mm">
493/// <path d="M26.7 24.94l.82-11.15M44.46 5.1L33.8 7.34" fill="none" stroke="#55d400" stroke-width=".5"/>
494/// <path d="M26.7 24.94c.97-11.13 7.17-17.6 17.76-19.84M75.27 24.94l1.13-5.5 2.67-5.48 4-4.42L88 6.7l5.02-1.6" fill="none" stroke="#000"/>
495/// <path d="M77.57 19.37a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
496/// <path d="M77.57 19.37a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="#fff"/>
497/// <path d="M80.22 13.93a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.08 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
498/// <path d="M80.22 13.93a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.08 1.08" color="#000" fill="#fff"/>
499/// <path d="M84.08 9.55a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
500/// <path d="M84.08 9.55a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
501/// <path d="M89.1 6.66a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.08-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
502/// <path d="M89.1 6.66a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.08-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="#fff"/>
503/// <path d="M94.4 5a1.1 1.1 0 0 1-1.1 1.1A1.1 1.1 0 0 1 92.23 5a1.1 1.1 0 0 1 1.08-1.08A1.1 1.1 0 0 1 94.4 5" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
504/// <path d="M94.4 5a1.1 1.1 0 0 1-1.1 1.1A1.1 1.1 0 0 1 92.23 5a1.1 1.1 0 0 1 1.08-1.08A1.1 1.1 0 0 1 94.4 5" color="#000" fill="#fff"/>
505/// <path d="M76.44 25.13a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
506/// <path d="M76.44 25.13a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
507/// <path d="M27.78 24.9a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
508/// <path d="M27.78 24.9a1.1 1.1 0 0 1-1.08 1.08 1.1 1.1 0 0 1-1.1-1.08 1.1 1.1 0 0 1 1.1-1.1 1.1 1.1 0 0 1 1.08 1.1" color="#000" fill="#fff"/>
509/// <path d="M45.4 5.14a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
510/// <path d="M45.4 5.14a1.1 1.1 0 0 1-1.08 1.1 1.1 1.1 0 0 1-1.1-1.1 1.1 1.1 0 0 1 1.1-1.08 1.1 1.1 0 0 1 1.1 1.08" color="#000" fill="#fff"/>
511/// <path d="M28.67 13.8a1.1 1.1 0 0 1-1.1 1.08 1.1 1.1 0 0 1-1.08-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
512/// <path d="M28.67 13.8a1.1 1.1 0 0 1-1.1 1.08 1.1 1.1 0 0 1-1.08-1.08 1.1 1.1 0 0 1 1.08-1.1 1.1 1.1 0 0 1 1.1 1.1" color="#000" fill="#fff"/>
513/// <path d="M35 7.32a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1A1.1 1.1 0 0 1 35 7.33" color="#000" fill="none" stroke="#030303" stroke-linecap="round" stroke-opacity=".5"/>
514/// <path d="M35 7.32a1.1 1.1 0 0 1-1.1 1.1 1.1 1.1 0 0 1-1.08-1.1 1.1 1.1 0 0 1 1.1-1.1A1.1 1.1 0 0 1 35 7.33" color="#000" fill="#fff"/>
515/// <text style="line-height:6.61458302px" x="35.74" y="284.49" font-size="5.29" font-family="Sans" letter-spacing="0" word-spacing="0" fill="#b3b3b3" stroke-width=".26" transform="translate(19.595 -267)">
516/// <tspan x="35.74" y="284.49" font-size="10.58">→</tspan>
517/// </text>
518/// </svg>
519///
520/// The tolerance value controls the maximum distance between the curved input
521/// segments and their polyline approximations. (In technical terms, this is the
522/// Hausdorff distance). The algorithm attempts to bound this distance between
523/// by `tolerance` but this is not absolutely guaranteed. The appropriate value
524/// depends on the use, but for antialiased rendering, a value of 0.25 has been
525/// determined to give good results. The number of segments tends to scale as the
526/// inverse square root of tolerance.
527///
528/// <svg viewBox="0 0 47.5 13.2" height="100" width="350" xmlns="http://www.w3.org/2000/svg">
529/// <path d="M-2.44 9.53c16.27-8.5 39.68-7.93 52.13 1.9" fill="none" stroke="#dde9af" stroke-width="4.6"/>
530/// <path d="M-1.97 9.3C14.28 1.03 37.36 1.7 49.7 11.4" fill="none" stroke="#00d400" stroke-width=".57" stroke-linecap="round" stroke-dasharray="4.6, 2.291434"/>
531/// <path d="M-1.94 10.46L6.2 6.08l28.32-1.4 15.17 6.74" fill="none" stroke="#000" stroke-width=".6"/>
532/// <path d="M6.83 6.57a.9.9 0 0 1-1.25.15.9.9 0 0 1-.15-1.25.9.9 0 0 1 1.25-.15.9.9 0 0 1 .15 1.25" color="#000" stroke="#000" stroke-width=".57" stroke-linecap="round" stroke-opacity=".5"/>
533/// <path d="M35.35 5.3a.9.9 0 0 1-1.25.15.9.9 0 0 1-.15-1.25.9.9 0 0 1 1.25-.15.9.9 0 0 1 .15 1.24" color="#000" stroke="#000" stroke-width=".6" stroke-opacity=".5"/>
534/// <g fill="none" stroke="#ff7f2a" stroke-width=".26">
535/// <path d="M20.4 3.8l.1 1.83M19.9 4.28l.48-.56.57.52M21.02 5.18l-.5.56-.6-.53" stroke-width=".2978872"/>
536/// </g>
537/// </svg>
538///
539/// The callback will be called in order with each element of the generated
540/// path. Because the result is made of polylines, these will be straight-line
541/// path elements only, no curves.
542///
543/// This algorithm is based on the blog post [Flattening quadratic Béziers]
544/// but with some refinements. For one, there is a more careful approximation
545/// at cusps. For two, the algorithm is extended to work with cubic Béziers
546/// as well, by first subdividing into quadratics and then computing the
547/// subdivision of each quadratic. However, as a clever trick, these quadratics
548/// are subdivided fractionally, and their endpoints are not included.
549///
550/// TODO: write a paper explaining this in more detail.
551///
552/// [Flattening quadratic Béziers]: https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html
553pub fn flatten(
554 path: impl IntoIterator<Item = PathEl>,
555 tolerance: f64,
556 mut callback: impl FnMut(PathEl),
557) {
558 let sqrt_tol = tolerance.sqrt();
559 let mut last_pt = None;
560 let mut quad_buf = Vec::new();
561 for el in path {
562 match el {
563 PathEl::MoveTo(p) => {
564 last_pt = Some(p);
565 callback(PathEl::MoveTo(p));
566 }
567 PathEl::LineTo(p) => {
568 last_pt = Some(p);
569 callback(PathEl::LineTo(p));
570 }
571 PathEl::QuadTo(p1, p2) => {
572 if let Some(p0) = last_pt {
573 let q = QuadBez::new(p0, p1, p2);
574 let params = q.estimate_subdiv(sqrt_tol);
575 let n = ((0.5 * params.val / sqrt_tol).ceil() as usize).max(1);
576 let step = 1.0 / (n as f64);
577 for i in 1..n {
578 let u = (i as f64) * step;
579 let t = q.determine_subdiv_t(&params, u);
580 let p = q.eval(t);
581 callback(PathEl::LineTo(p));
582 }
583 callback(PathEl::LineTo(p2));
584 }
585 last_pt = Some(p2);
586 }
587 PathEl::CurveTo(p1, p2, p3) => {
588 if let Some(p0) = last_pt {
589 let c = CubicBez::new(p0, p1, p2, p3);
590
591 // Subdivide into quadratics, and estimate the number of
592 // subdivisions required for each, summing to arrive at an
593 // estimate for the number of subdivisions for the cubic.
594 // Also retain these parameters for later.
595 let iter = c.to_quads(tolerance * TO_QUAD_TOL);
596 quad_buf.clear();
597 quad_buf.reserve(iter.size_hint().0);
598 let sqrt_remain_tol = sqrt_tol * (1.0 - TO_QUAD_TOL).sqrt();
599 let mut sum = 0.0;
600 for (_, _, q) in iter {
601 let params = q.estimate_subdiv(sqrt_remain_tol);
602 sum += params.val;
603 quad_buf.push((q, params));
604 }
605 let n = ((0.5 * sum / sqrt_remain_tol).ceil() as usize).max(1);
606
607 // Iterate through the quadratics, outputting the points of
608 // subdivisions that fall within that quadratic.
609 let step = sum / (n as f64);
610 let mut i = 1;
611 let mut val_sum = 0.0;
612 for (q, params) in &quad_buf {
613 let mut target = (i as f64) * step;
614 let recip_val = params.val.recip();
615 while target < val_sum + params.val {
616 let u = (target - val_sum) * recip_val;
617 let t = q.determine_subdiv_t(params, u);
618 let p = q.eval(t);
619 callback(PathEl::LineTo(p));
620 i += 1;
621 if i == n + 1 {
622 break;
623 }
624 target = (i as f64) * step;
625 }
626 val_sum += params.val;
627 }
628 callback(PathEl::LineTo(p3));
629 }
630 last_pt = Some(p3);
631 }
632 PathEl::ClosePath => {
633 last_pt = None;
634 callback(PathEl::ClosePath);
635 }
636 }
637 }
638}
639
640impl Mul<PathEl> for Affine {
641 type Output = PathEl;
642
643 fn mul(self, other: PathEl) -> PathEl {
644 match other {
645 PathEl::MoveTo(p: Point) => PathEl::MoveTo(self * p),
646 PathEl::LineTo(p: Point) => PathEl::LineTo(self * p),
647 PathEl::QuadTo(p1: Point, p2: Point) => PathEl::QuadTo(self * p1, self * p2),
648 PathEl::CurveTo(p1: Point, p2: Point, p3: Point) => PathEl::CurveTo(self * p1, self * p2, self * p3),
649 PathEl::ClosePath => PathEl::ClosePath,
650 }
651 }
652}
653
654impl Mul<PathSeg> for Affine {
655 type Output = PathSeg;
656
657 fn mul(self, other: PathSeg) -> PathSeg {
658 match other {
659 PathSeg::Line(line: Line) => PathSeg::Line(self * line),
660 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(self * quad),
661 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(self * cubic),
662 }
663 }
664}
665
666impl Mul<BezPath> for Affine {
667 type Output = BezPath;
668
669 fn mul(self, other: BezPath) -> BezPath {
670 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
671 }
672}
673
674impl<'a> Mul<&'a BezPath> for Affine {
675 type Output = BezPath;
676
677 fn mul(self, other: &BezPath) -> BezPath {
678 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
679 }
680}
681
682impl Mul<PathEl> for TranslateScale {
683 type Output = PathEl;
684
685 fn mul(self, other: PathEl) -> PathEl {
686 match other {
687 PathEl::MoveTo(p: Point) => PathEl::MoveTo(self * p),
688 PathEl::LineTo(p: Point) => PathEl::LineTo(self * p),
689 PathEl::QuadTo(p1: Point, p2: Point) => PathEl::QuadTo(self * p1, self * p2),
690 PathEl::CurveTo(p1: Point, p2: Point, p3: Point) => PathEl::CurveTo(self * p1, self * p2, self * p3),
691 PathEl::ClosePath => PathEl::ClosePath,
692 }
693 }
694}
695
696impl Mul<PathSeg> for TranslateScale {
697 type Output = PathSeg;
698
699 fn mul(self, other: PathSeg) -> PathSeg {
700 match other {
701 PathSeg::Line(line: Line) => PathSeg::Line(self * line),
702 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(self * quad),
703 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(self * cubic),
704 }
705 }
706}
707
708impl Mul<BezPath> for TranslateScale {
709 type Output = BezPath;
710
711 fn mul(self, other: BezPath) -> BezPath {
712 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
713 }
714}
715
716impl<'a> Mul<&'a BezPath> for TranslateScale {
717 type Output = BezPath;
718
719 fn mul(self, other: &BezPath) -> BezPath {
720 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
721 }
722}
723
724/// Transform an iterator over path elements into one over path
725/// segments.
726///
727/// See also [`BezPath::segments`].
728/// This signature is a bit more general, allowing `&[PathEl]` slices
729/// and other iterators yielding `PathEl`.
730pub fn segments<I>(elements: I) -> Segments<I::IntoIter>
731where
732 I: IntoIterator<Item = PathEl>,
733{
734 Segments {
735 elements: elements.into_iter(),
736 start_last: None,
737 }
738}
739
740/// An iterator that transforms path elements to path segments.
741///
742/// This struct is created by the [`segments`] function.
743#[derive(Clone)]
744pub struct Segments<I: Iterator<Item = PathEl>> {
745 elements: I,
746 start_last: Option<(Point, Point)>,
747}
748
749impl<I: Iterator<Item = PathEl>> Iterator for Segments<I> {
750 type Item = PathSeg;
751
752 fn next(&mut self) -> Option<PathSeg> {
753 for el in &mut self.elements {
754 // We first need to check whether this is the first
755 // path element we see to fill in the start position.
756 let (start, last) = self.start_last.get_or_insert_with(|| {
757 let point = match el {
758 PathEl::MoveTo(p) => p,
759 PathEl::LineTo(p) => p,
760 PathEl::QuadTo(_, p2) => p2,
761 PathEl::CurveTo(_, _, p3) => p3,
762 PathEl::ClosePath => panic!("Can't start a segment on a ClosePath"),
763 };
764 (point, point)
765 });
766
767 return Some(match el {
768 PathEl::MoveTo(p) => {
769 *start = p;
770 *last = p;
771 continue;
772 }
773 PathEl::LineTo(p) => PathSeg::Line(Line::new(mem::replace(last, p), p)),
774 PathEl::QuadTo(p1, p2) => {
775 PathSeg::Quad(QuadBez::new(mem::replace(last, p2), p1, p2))
776 }
777 PathEl::CurveTo(p1, p2, p3) => {
778 PathSeg::Cubic(CubicBez::new(mem::replace(last, p3), p1, p2, p3))
779 }
780 PathEl::ClosePath => {
781 if *last != *start {
782 PathSeg::Line(Line::new(mem::replace(last, *start), *start))
783 } else {
784 continue;
785 }
786 }
787 });
788 }
789
790 None
791 }
792}
793
794impl<I: Iterator<Item = PathEl>> Segments<I> {
795 /// Here, `accuracy` specifies the accuracy for each Bézier segment. At worst,
796 /// the total error is `accuracy` times the number of Bézier segments.
797
798 // TODO: pub? Or is this subsumed by method of &[PathEl]?
799 pub(crate) fn perimeter(self, accuracy: f64) -> f64 {
800 self.map(|seg| seg.arclen(accuracy)).sum()
801 }
802
803 // Same
804 pub(crate) fn area(self) -> f64 {
805 self.map(|seg| seg.signed_area()).sum()
806 }
807
808 // Same
809 pub(crate) fn winding(self, p: Point) -> i32 {
810 self.map(|seg| seg.winding(p)).sum()
811 }
812
813 // Same
814 pub(crate) fn bounding_box(self) -> Rect {
815 let mut bbox: Option<Rect> = None;
816 for seg in self {
817 let seg_bb = ParamCurveExtrema::bounding_box(&seg);
818 if let Some(bb) = bbox {
819 bbox = Some(bb.union(seg_bb));
820 } else {
821 bbox = Some(seg_bb);
822 }
823 }
824 bbox.unwrap_or_default()
825 }
826}
827
828impl ParamCurve for PathSeg {
829 fn eval(&self, t: f64) -> Point {
830 match *self {
831 PathSeg::Line(line: Line) => line.eval(t),
832 PathSeg::Quad(quad: QuadBez) => quad.eval(t),
833 PathSeg::Cubic(cubic: CubicBez) => cubic.eval(t),
834 }
835 }
836
837 fn subsegment(&self, range: Range<f64>) -> PathSeg {
838 match *self {
839 PathSeg::Line(line: Line) => PathSeg::Line(line.subsegment(range)),
840 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(quad.subsegment(range)),
841 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(cubic.subsegment(range)),
842 }
843 }
844}
845
846impl ParamCurveArclen for PathSeg {
847 fn arclen(&self, accuracy: f64) -> f64 {
848 match *self {
849 PathSeg::Line(line: Line) => line.arclen(accuracy),
850 PathSeg::Quad(quad: QuadBez) => quad.arclen(accuracy),
851 PathSeg::Cubic(cubic: CubicBez) => cubic.arclen(accuracy),
852 }
853 }
854
855 fn inv_arclen(&self, arclen: f64, accuracy: f64) -> f64 {
856 match *self {
857 PathSeg::Line(line: Line) => line.inv_arclen(arclen, accuracy),
858 PathSeg::Quad(quad: QuadBez) => quad.inv_arclen(arclen, accuracy),
859 PathSeg::Cubic(cubic: CubicBez) => cubic.inv_arclen(arclen, accuracy),
860 }
861 }
862}
863
864impl ParamCurveArea for PathSeg {
865 fn signed_area(&self) -> f64 {
866 match *self {
867 PathSeg::Line(line: Line) => line.signed_area(),
868 PathSeg::Quad(quad: QuadBez) => quad.signed_area(),
869 PathSeg::Cubic(cubic: CubicBez) => cubic.signed_area(),
870 }
871 }
872}
873
874impl ParamCurveNearest for PathSeg {
875 fn nearest(&self, p: Point, accuracy: f64) -> Nearest {
876 match *self {
877 PathSeg::Line(line: Line) => line.nearest(p, accuracy),
878 PathSeg::Quad(quad: QuadBez) => quad.nearest(p, accuracy),
879 PathSeg::Cubic(cubic: CubicBez) => cubic.nearest(p, accuracy),
880 }
881 }
882}
883
884impl ParamCurveExtrema for PathSeg {
885 fn extrema(&self) -> ArrayVec<f64, MAX_EXTREMA> {
886 match *self {
887 PathSeg::Line(line: Line) => line.extrema(),
888 PathSeg::Quad(quad: QuadBez) => quad.extrema(),
889 PathSeg::Cubic(cubic: CubicBez) => cubic.extrema(),
890 }
891 }
892}
893
894impl PathSeg {
895 /// Get the [`PathEl`] that is equivalent to discarding the segment start point.
896 pub fn as_path_el(&self) -> PathEl {
897 match self {
898 PathSeg::Line(line) => PathEl::LineTo(line.p1),
899 PathSeg::Quad(q) => PathEl::QuadTo(q.p1, q.p2),
900 PathSeg::Cubic(c) => PathEl::CurveTo(c.p1, c.p2, c.p3),
901 }
902 }
903
904 /// Returns a new `PathSeg` describing the same path as `self`, but with
905 /// the points reversed.
906 pub fn reverse(&self) -> PathSeg {
907 match self {
908 PathSeg::Line(Line { p0, p1 }) => PathSeg::Line(Line::new(*p1, *p0)),
909 PathSeg::Quad(q) => PathSeg::Quad(QuadBez::new(q.p2, q.p1, q.p0)),
910 PathSeg::Cubic(c) => PathSeg::Cubic(CubicBez::new(c.p3, c.p2, c.p1, c.p0)),
911 }
912 }
913
914 /// Convert this segment to a cubic bezier.
915 pub fn to_cubic(&self) -> CubicBez {
916 match *self {
917 PathSeg::Line(Line { p0, p1 }) => CubicBez::new(p0, p0, p1, p1),
918 PathSeg::Cubic(c) => c,
919 PathSeg::Quad(q) => q.raise(),
920 }
921 }
922
923 // Assumes split at extrema.
924 fn winding_inner(&self, p: Point) -> i32 {
925 let start = self.start();
926 let end = self.end();
927 let sign = if end.y > start.y {
928 if p.y < start.y || p.y >= end.y {
929 return 0;
930 }
931 -1
932 } else if end.y < start.y {
933 if p.y < end.y || p.y >= start.y {
934 return 0;
935 }
936 1
937 } else {
938 return 0;
939 };
940 match *self {
941 PathSeg::Line(_line) => {
942 if p.x < start.x.min(end.x) {
943 return 0;
944 }
945 if p.x >= start.x.max(end.x) {
946 return sign;
947 }
948 // line equation ax + by = c
949 let a = end.y - start.y;
950 let b = start.x - end.x;
951 let c = a * start.x + b * start.y;
952 if (a * p.x + b * p.y - c) * (sign as f64) <= 0.0 {
953 sign
954 } else {
955 0
956 }
957 }
958 PathSeg::Quad(quad) => {
959 let p1 = quad.p1;
960 if p.x < start.x.min(end.x).min(p1.x) {
961 return 0;
962 }
963 if p.x >= start.x.max(end.x).max(p1.x) {
964 return sign;
965 }
966 let a = end.y - 2.0 * p1.y + start.y;
967 let b = 2.0 * (p1.y - start.y);
968 let c = start.y - p.y;
969 for t in solve_quadratic(c, b, a) {
970 if (0.0..=1.0).contains(&t) {
971 let x = quad.eval(t).x;
972 if p.x >= x {
973 return sign;
974 } else {
975 return 0;
976 }
977 }
978 }
979 0
980 }
981 PathSeg::Cubic(cubic) => {
982 let p1 = cubic.p1;
983 let p2 = cubic.p2;
984 if p.x < start.x.min(end.x).min(p1.x).min(p2.x) {
985 return 0;
986 }
987 if p.x >= start.x.max(end.x).max(p1.x).max(p2.x) {
988 return sign;
989 }
990 let a = end.y - 3.0 * p2.y + 3.0 * p1.y - start.y;
991 let b = 3.0 * (p2.y - 2.0 * p1.y + start.y);
992 let c = 3.0 * (p1.y - start.y);
993 let d = start.y - p.y;
994 for t in solve_cubic(d, c, b, a) {
995 if (0.0..=1.0).contains(&t) {
996 let x = cubic.eval(t).x;
997 if p.x >= x {
998 return sign;
999 } else {
1000 return 0;
1001 }
1002 }
1003 }
1004 0
1005 }
1006 }
1007 }
1008
1009 /// Compute the winding number contribution of a single segment.
1010 ///
1011 /// Cast a ray to the left and count intersections.
1012 fn winding(&self, p: Point) -> i32 {
1013 self.extrema_ranges()
1014 .into_iter()
1015 .map(|range| self.subsegment(range).winding_inner(p))
1016 .sum()
1017 }
1018
1019 /// Compute intersections against a line.
1020 ///
1021 /// Returns a vector of the intersections. For each intersection,
1022 /// the `t` value of the segment and line are given.
1023 ///
1024 /// Note: This test is designed to be inclusive of points near the endpoints
1025 /// of the segment. This is so that testing a line against multiple
1026 /// contiguous segments of a path will be guaranteed to catch at least one
1027 /// of them. In such cases, use higher level logic to coalesce the hits
1028 /// (the `t` value may be slightly outside the range of 0..1).
1029 ///
1030 /// # Examples
1031 ///
1032 /// ```
1033 /// # use kurbo::*;
1034 /// let seg = PathSeg::Line(Line::new((0.0, 0.0), (2.0, 0.0)));
1035 /// let line = Line::new((1.0, 2.0), (1.0, -2.0));
1036 /// let intersection = seg.intersect_line(line);
1037 /// assert_eq!(intersection.len(), 1);
1038 /// let intersection = intersection[0];
1039 /// assert_eq!(intersection.segment_t, 0.5);
1040 /// assert_eq!(intersection.line_t, 0.5);
1041 ///
1042 /// let point = seg.eval(intersection.segment_t);
1043 /// assert_eq!(point, Point::new(1.0, 0.0));
1044 /// ```
1045 pub fn intersect_line(&self, line: Line) -> ArrayVec<LineIntersection, 3> {
1046 const EPSILON: f64 = 1e-9;
1047 let p0 = line.p0;
1048 let p1 = line.p1;
1049 let dx = p1.x - p0.x;
1050 let dy = p1.y - p0.y;
1051 let mut result = ArrayVec::new();
1052 match self {
1053 PathSeg::Line(l) => {
1054 let det = dx * (l.p1.y - l.p0.y) - dy * (l.p1.x - l.p0.x);
1055 if det.abs() < EPSILON {
1056 // Lines are coincident (or nearly so).
1057 return result;
1058 }
1059 let t = dx * (p0.y - l.p0.y) - dy * (p0.x - l.p0.x);
1060 // t = position on self
1061 let t = t / det;
1062 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
1063 // u = position on probe line
1064 let u =
1065 (l.p0.x - p0.x) * (l.p1.y - l.p0.y) - (l.p0.y - p0.y) * (l.p1.x - l.p0.x);
1066 let u = u / det;
1067 if (0.0..=1.0).contains(&u) {
1068 result.push(LineIntersection::new(u, t));
1069 }
1070 }
1071 }
1072 PathSeg::Quad(q) => {
1073 // The basic technique here is to determine x and y as a quadratic polynomial
1074 // as a function of t. Then plug those values into the line equation for the
1075 // probe line (giving a sort of signed distance from the probe line) and solve
1076 // that for t.
1077 let (px0, px1, px2) = quadratic_bez_coefs(q.p0.x, q.p1.x, q.p2.x);
1078 let (py0, py1, py2) = quadratic_bez_coefs(q.p0.y, q.p1.y, q.p2.y);
1079 let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
1080 let c1 = dy * px1 - dx * py1;
1081 let c2 = dy * px2 - dx * py2;
1082 let invlen2 = (dx * dx + dy * dy).recip();
1083 for t in solve_quadratic(c0, c1, c2) {
1084 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
1085 let x = px0 + t * px1 + t * t * px2;
1086 let y = py0 + t * py1 + t * t * py2;
1087 let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
1088 if (0.0..=1.0).contains(&u) {
1089 result.push(LineIntersection::new(u, t));
1090 }
1091 }
1092 }
1093 }
1094 PathSeg::Cubic(c) => {
1095 // Same technique as above, but cubic polynomial.
1096 let (px0, px1, px2, px3) = cubic_bez_coefs(c.p0.x, c.p1.x, c.p2.x, c.p3.x);
1097 let (py0, py1, py2, py3) = cubic_bez_coefs(c.p0.y, c.p1.y, c.p2.y, c.p3.y);
1098 let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
1099 let c1 = dy * px1 - dx * py1;
1100 let c2 = dy * px2 - dx * py2;
1101 let c3 = dy * px3 - dx * py3;
1102 let invlen2 = (dx * dx + dy * dy).recip();
1103 for t in solve_cubic(c0, c1, c2, c3) {
1104 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
1105 let x = px0 + t * px1 + t * t * px2 + t * t * t * px3;
1106 let y = py0 + t * py1 + t * t * py2 + t * t * t * py3;
1107 let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
1108 if (0.0..=1.0).contains(&u) {
1109 result.push(LineIntersection::new(u, t));
1110 }
1111 }
1112 }
1113 }
1114 }
1115 result
1116 }
1117
1118 /// Is this Bezier path finite?
1119 #[inline]
1120 pub fn is_finite(&self) -> bool {
1121 match self {
1122 PathSeg::Line(line) => line.is_finite(),
1123 PathSeg::Quad(quad_bez) => quad_bez.is_finite(),
1124 PathSeg::Cubic(cubic_bez) => cubic_bez.is_finite(),
1125 }
1126 }
1127
1128 /// Is this Bezier path NaN?
1129 #[inline]
1130 pub fn is_nan(&self) -> bool {
1131 match self {
1132 PathSeg::Line(line) => line.is_nan(),
1133 PathSeg::Quad(quad_bez) => quad_bez.is_nan(),
1134 PathSeg::Cubic(cubic_bez) => cubic_bez.is_nan(),
1135 }
1136 }
1137
1138 #[inline]
1139 fn as_vec2_vec(&self) -> ArrayVec<Vec2, 4> {
1140 let mut a = ArrayVec::new();
1141 match self {
1142 PathSeg::Line(l) => {
1143 a.push(l.p0.to_vec2());
1144 a.push(l.p1.to_vec2());
1145 }
1146 PathSeg::Quad(q) => {
1147 a.push(q.p0.to_vec2());
1148 a.push(q.p1.to_vec2());
1149 a.push(q.p2.to_vec2());
1150 }
1151 PathSeg::Cubic(c) => {
1152 a.push(c.p0.to_vec2());
1153 a.push(c.p1.to_vec2());
1154 a.push(c.p2.to_vec2());
1155 a.push(c.p3.to_vec2());
1156 }
1157 };
1158 a
1159 }
1160
1161 /// Minimum distance between two [`PathSeg`]s.
1162 ///
1163 /// Returns a tuple of the distance, the path time `t1` of the closest point
1164 /// on the first `PathSeg`, and the path time `t2` of the closest point on the
1165 /// second `PathSeg`.
1166 pub fn min_dist(&self, other: PathSeg, accuracy: f64) -> MinDistance {
1167 let (distance, t1, t2) = crate::mindist::min_dist_param(
1168 &self.as_vec2_vec(),
1169 &other.as_vec2_vec(),
1170 (0.0, 1.0),
1171 (0.0, 1.0),
1172 accuracy,
1173 None,
1174 );
1175 MinDistance {
1176 distance: distance.sqrt(),
1177 t1,
1178 t2,
1179 }
1180 }
1181
1182 /// Compute endpoint tangents of a path segment.
1183 ///
1184 /// This version is robust to the path segment not being a regular curve.
1185 pub(crate) fn tangents(&self) -> (Vec2, Vec2) {
1186 const EPS: f64 = 1e-12;
1187 match self {
1188 PathSeg::Line(l) => {
1189 let d = l.p1 - l.p0;
1190 (d, d)
1191 }
1192 PathSeg::Quad(q) => {
1193 let d01 = q.p1 - q.p0;
1194 let d0 = if d01.hypot2() > EPS { d01 } else { q.p2 - q.p0 };
1195 let d12 = q.p2 - q.p1;
1196 let d1 = if d12.hypot2() > EPS { d12 } else { q.p2 - q.p0 };
1197 (d0, d1)
1198 }
1199 PathSeg::Cubic(c) => {
1200 let d01 = c.p1 - c.p0;
1201 let d0 = if d01.hypot2() > EPS {
1202 d01
1203 } else {
1204 let d02 = c.p2 - c.p0;
1205 if d02.hypot2() > EPS {
1206 d02
1207 } else {
1208 c.p3 - c.p0
1209 }
1210 };
1211 let d23 = c.p3 - c.p2;
1212 let d1 = if d23.hypot2() > EPS {
1213 d23
1214 } else {
1215 let d13 = c.p3 - c.p1;
1216 if d13.hypot2() > EPS {
1217 d13
1218 } else {
1219 c.p3 - c.p0
1220 }
1221 };
1222 (d0, d1)
1223 }
1224 }
1225 }
1226}
1227
1228impl LineIntersection {
1229 fn new(line_t: f64, segment_t: f64) -> Self {
1230 LineIntersection { line_t, segment_t }
1231 }
1232
1233 /// Is this line intersection finite?
1234 #[inline]
1235 pub fn is_finite(self) -> bool {
1236 self.line_t.is_finite() && self.segment_t.is_finite()
1237 }
1238
1239 /// Is this line intersection NaN?
1240 #[inline]
1241 pub fn is_nan(self) -> bool {
1242 self.line_t.is_nan() || self.segment_t.is_nan()
1243 }
1244}
1245
1246// Return polynomial coefficients given cubic bezier coordinates.
1247fn quadratic_bez_coefs(x0: f64, x1: f64, x2: f64) -> (f64, f64, f64) {
1248 let p0: f64 = x0;
1249 let p1: f64 = 2.0 * x1 - 2.0 * x0;
1250 let p2: f64 = x2 - 2.0 * x1 + x0;
1251 (p0, p1, p2)
1252}
1253
1254// Return polynomial coefficients given cubic bezier coordinates.
1255fn cubic_bez_coefs(x0: f64, x1: f64, x2: f64, x3: f64) -> (f64, f64, f64, f64) {
1256 let p0: f64 = x0;
1257 let p1: f64 = 3.0 * x1 - 3.0 * x0;
1258 let p2: f64 = 3.0 * x2 - 6.0 * x1 + 3.0 * x0;
1259 let p3: f64 = x3 - 3.0 * x2 + 3.0 * x1 - x0;
1260 (p0, p1, p2, p3)
1261}
1262
1263impl From<CubicBez> for PathSeg {
1264 fn from(cubic_bez: CubicBez) -> PathSeg {
1265 PathSeg::Cubic(cubic_bez)
1266 }
1267}
1268
1269impl From<Line> for PathSeg {
1270 fn from(line: Line) -> PathSeg {
1271 PathSeg::Line(line)
1272 }
1273}
1274
1275impl From<QuadBez> for PathSeg {
1276 fn from(quad_bez: QuadBez) -> PathSeg {
1277 PathSeg::Quad(quad_bez)
1278 }
1279}
1280
1281impl Shape for BezPath {
1282 type PathElementsIter<'iter> = core::iter::Copied<core::slice::Iter<'iter, PathEl>>;
1283
1284 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1285 self.0.iter().copied()
1286 }
1287
1288 fn to_path(&self, _tolerance: f64) -> BezPath {
1289 self.clone()
1290 }
1291
1292 fn into_path(self, _tolerance: f64) -> BezPath {
1293 self
1294 }
1295
1296 /// Signed area.
1297 fn area(&self) -> f64 {
1298 self.elements().area()
1299 }
1300
1301 fn perimeter(&self, accuracy: f64) -> f64 {
1302 self.elements().perimeter(accuracy)
1303 }
1304
1305 /// Winding number of point.
1306 fn winding(&self, pt: Point) -> i32 {
1307 self.elements().winding(pt)
1308 }
1309
1310 fn bounding_box(&self) -> Rect {
1311 self.elements().bounding_box()
1312 }
1313
1314 fn as_path_slice(&self) -> Option<&[PathEl]> {
1315 Some(&self.0)
1316 }
1317}
1318
1319impl PathEl {
1320 /// Is this path element finite?
1321 #[inline]
1322 pub fn is_finite(&self) -> bool {
1323 match self {
1324 PathEl::MoveTo(p) => p.is_finite(),
1325 PathEl::LineTo(p) => p.is_finite(),
1326 PathEl::QuadTo(p, p2) => p.is_finite() && p2.is_finite(),
1327 PathEl::CurveTo(p, p2, p3) => p.is_finite() && p2.is_finite() && p3.is_finite(),
1328 PathEl::ClosePath => true,
1329 }
1330 }
1331
1332 /// Is this path element NaN?
1333 #[inline]
1334 pub fn is_nan(&self) -> bool {
1335 match self {
1336 PathEl::MoveTo(p) => p.is_nan(),
1337 PathEl::LineTo(p) => p.is_nan(),
1338 PathEl::QuadTo(p, p2) => p.is_nan() || p2.is_nan(),
1339 PathEl::CurveTo(p, p2, p3) => p.is_nan() || p2.is_nan() || p3.is_nan(),
1340 PathEl::ClosePath => false,
1341 }
1342 }
1343
1344 /// Get the end point of the path element, if it exists.
1345 pub fn end_point(&self) -> Option<Point> {
1346 match self {
1347 PathEl::MoveTo(p) => Some(*p),
1348 PathEl::LineTo(p1) => Some(*p1),
1349 PathEl::QuadTo(_, p2) => Some(*p2),
1350 PathEl::CurveTo(_, _, p3) => Some(*p3),
1351 _ => None,
1352 }
1353 }
1354}
1355
1356/// Implements [`Shape`] for a slice of [`PathEl`], provided that the first element of the slice is
1357/// not a `PathEl::ClosePath`. If it is, several of these functions will panic.
1358///
1359/// If the slice starts with `LineTo`, `QuadTo`, or `CurveTo`, it will be treated as a `MoveTo`.
1360impl<'a> Shape for &'a [PathEl] {
1361 type PathElementsIter<'iter>
1362
1363 = core::iter::Copied<core::slice::Iter<'a, PathEl>> where 'a: 'iter;
1364
1365 #[inline]
1366 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1367 self.iter().copied()
1368 }
1369
1370 fn to_path(&self, _tolerance: f64) -> BezPath {
1371 BezPath::from_vec(self.to_vec())
1372 }
1373
1374 /// Signed area.
1375 fn area(&self) -> f64 {
1376 segments(self.iter().copied()).area()
1377 }
1378
1379 fn perimeter(&self, accuracy: f64) -> f64 {
1380 segments(self.iter().copied()).perimeter(accuracy)
1381 }
1382
1383 /// Winding number of point.
1384 fn winding(&self, pt: Point) -> i32 {
1385 segments(self.iter().copied()).winding(pt)
1386 }
1387
1388 fn bounding_box(&self) -> Rect {
1389 segments(self.iter().copied()).bounding_box()
1390 }
1391
1392 #[inline]
1393 fn as_path_slice(&self) -> Option<&[PathEl]> {
1394 Some(self)
1395 }
1396}
1397
1398/// Implements [`Shape`] for an array of [`PathEl`], provided that the first element of the array is
1399/// not a `PathEl::ClosePath`. If it is, several of these functions will panic.
1400///
1401/// If the array starts with `LineTo`, `QuadTo`, or `CurveTo`, it will be treated as a `MoveTo`.
1402impl<const N: usize> Shape for [PathEl; N] {
1403 type PathElementsIter<'iter> = core::iter::Copied<core::slice::Iter<'iter, PathEl>>;
1404
1405 #[inline]
1406 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1407 self.iter().copied()
1408 }
1409
1410 fn to_path(&self, _tolerance: f64) -> BezPath {
1411 BezPath::from_vec(self.to_vec())
1412 }
1413
1414 /// Signed area.
1415 fn area(&self) -> f64 {
1416 segments(self.iter().copied()).area()
1417 }
1418
1419 fn perimeter(&self, accuracy: f64) -> f64 {
1420 segments(self.iter().copied()).perimeter(accuracy)
1421 }
1422
1423 /// Winding number of point.
1424 fn winding(&self, pt: Point) -> i32 {
1425 segments(self.iter().copied()).winding(pt)
1426 }
1427
1428 fn bounding_box(&self) -> Rect {
1429 segments(self.iter().copied()).bounding_box()
1430 }
1431
1432 #[inline]
1433 fn as_path_slice(&self) -> Option<&[PathEl]> {
1434 Some(self)
1435 }
1436}
1437
1438/// An iterator for path segments.
1439pub struct PathSegIter {
1440 seg: PathSeg,
1441 ix: usize,
1442}
1443
1444impl Shape for PathSeg {
1445 type PathElementsIter<'iter> = PathSegIter;
1446
1447 #[inline]
1448 fn path_elements(&self, _tolerance: f64) -> PathSegIter {
1449 PathSegIter { seg: *self, ix: 0 }
1450 }
1451
1452 /// The area under the curve.
1453 ///
1454 /// We could just return `0`, but this seems more useful.
1455 fn area(&self) -> f64 {
1456 self.signed_area()
1457 }
1458
1459 #[inline]
1460 fn perimeter(&self, accuracy: f64) -> f64 {
1461 self.arclen(accuracy)
1462 }
1463
1464 fn winding(&self, _pt: Point) -> i32 {
1465 0
1466 }
1467
1468 #[inline]
1469 fn bounding_box(&self) -> Rect {
1470 ParamCurveExtrema::bounding_box(self)
1471 }
1472
1473 fn as_line(&self) -> Option<Line> {
1474 if let PathSeg::Line(line) = self {
1475 Some(*line)
1476 } else {
1477 None
1478 }
1479 }
1480}
1481
1482impl Iterator for PathSegIter {
1483 type Item = PathEl;
1484
1485 fn next(&mut self) -> Option<PathEl> {
1486 self.ix += 1;
1487 match (self.ix, self.seg) {
1488 // yes I could do some fancy bindings thing here but... :shrug:
1489 (1, PathSeg::Line(seg: Line)) => Some(PathEl::MoveTo(seg.p0)),
1490 (1, PathSeg::Quad(seg: QuadBez)) => Some(PathEl::MoveTo(seg.p0)),
1491 (1, PathSeg::Cubic(seg: CubicBez)) => Some(PathEl::MoveTo(seg.p0)),
1492 (2, PathSeg::Line(seg: Line)) => Some(PathEl::LineTo(seg.p1)),
1493 (2, PathSeg::Quad(seg: QuadBez)) => Some(PathEl::QuadTo(seg.p1, seg.p2)),
1494 (2, PathSeg::Cubic(seg: CubicBez)) => Some(PathEl::CurveTo(seg.p1, seg.p2, seg.p3)),
1495 _ => None,
1496 }
1497 }
1498}
1499
1500#[cfg(test)]
1501mod tests {
1502 use crate::{Circle, DEFAULT_ACCURACY};
1503
1504 use super::*;
1505
1506 fn assert_approx_eq(x: f64, y: f64) {
1507 assert!((x - y).abs() < 1e-8, "{x} != {y}");
1508 }
1509
1510 #[test]
1511 #[should_panic(expected = "uninitialized subpath")]
1512 fn test_elements_to_segments_starts_on_closepath() {
1513 let mut path = BezPath::new();
1514 path.close_path();
1515 path.segments().next();
1516 }
1517
1518 #[test]
1519 fn test_elements_to_segments_closepath_refers_to_last_moveto() {
1520 let mut path = BezPath::new();
1521 path.move_to((5.0, 5.0));
1522 path.line_to((15.0, 15.0));
1523 path.move_to((10.0, 10.0));
1524 path.line_to((15.0, 15.0));
1525 path.close_path();
1526 assert_eq!(
1527 path.segments().collect::<Vec<_>>().last(),
1528 Some(&Line::new((15.0, 15.0), (10.0, 10.0)).into()),
1529 );
1530 }
1531
1532 #[test]
1533 #[should_panic(expected = "uninitialized subpath")]
1534 fn test_must_not_start_on_quad() {
1535 let mut path = BezPath::new();
1536 path.quad_to((5.0, 5.0), (10.0, 10.0));
1537 path.line_to((15.0, 15.0));
1538 path.close_path();
1539 }
1540
1541 #[test]
1542 fn test_intersect_line() {
1543 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1544 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1545 let intersection = PathSeg::Line(h_line).intersect_line(v_line)[0];
1546 assert_approx_eq(intersection.segment_t, 0.1);
1547 assert_approx_eq(intersection.line_t, 0.5);
1548
1549 let v_line = Line::new((-10.0, -10.0), (-10.0, 10.0));
1550 assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
1551
1552 let v_line = Line::new((10.0, 10.0), (10.0, 20.0));
1553 assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
1554 }
1555
1556 #[test]
1557 fn test_intersect_qad() {
1558 let q = QuadBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -10.0));
1559 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1560 assert_eq!(PathSeg::Quad(q).intersect_line(v_line).len(), 1);
1561 let intersection = PathSeg::Quad(q).intersect_line(v_line)[0];
1562 assert_approx_eq(intersection.segment_t, 0.5);
1563 assert_approx_eq(intersection.line_t, 0.75);
1564
1565 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1566 assert_eq!(PathSeg::Quad(q).intersect_line(h_line).len(), 2);
1567 }
1568
1569 #[test]
1570 fn test_intersect_cubic() {
1571 let c = CubicBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -20.0), (30.0, 10.0));
1572 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1573 assert_eq!(PathSeg::Cubic(c).intersect_line(v_line).len(), 1);
1574 let intersection = PathSeg::Cubic(c).intersect_line(v_line)[0];
1575 assert_approx_eq(intersection.segment_t, 0.333333333);
1576 assert_approx_eq(intersection.line_t, 0.592592592);
1577
1578 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1579 assert_eq!(PathSeg::Cubic(c).intersect_line(h_line).len(), 3);
1580 }
1581
1582 #[test]
1583 fn test_contains() {
1584 let mut path = BezPath::new();
1585 path.move_to((0.0, 0.0));
1586 path.line_to((1.0, 1.0));
1587 path.line_to((2.0, 0.0));
1588 path.close_path();
1589 assert_eq!(path.winding(Point::new(1.0, 0.5)), -1);
1590 assert!(path.contains(Point::new(1.0, 0.5)));
1591 }
1592
1593 // get_seg(i) should produce the same results as path_segments().nth(i - 1).
1594 #[test]
1595 fn test_get_seg() {
1596 let circle = Circle::new((10.0, 10.0), 2.0).to_path(DEFAULT_ACCURACY);
1597 let segments = circle.path_segments(DEFAULT_ACCURACY).collect::<Vec<_>>();
1598 let get_segs = (1..usize::MAX)
1599 .map_while(|i| circle.get_seg(i))
1600 .collect::<Vec<_>>();
1601 assert_eq!(segments, get_segs);
1602 }
1603
1604 #[test]
1605 fn test_control_box() {
1606 // a sort of map ping looking thing drawn with a single cubic
1607 // cbox is wildly different than tight box
1608 let path = BezPath::from_svg("M200,300 C50,50 350,50 200,300").unwrap();
1609 assert_eq!(Rect::new(50.0, 50.0, 350.0, 300.0), path.control_box());
1610 assert!(path.control_box().area() > path.bounding_box().area());
1611 }
1612
1613 #[test]
1614 fn test_reverse_unclosed() {
1615 let path = BezPath::from_svg("M10,10 Q40,40 60,10 L100,10 C125,10 150,50 125,60").unwrap();
1616 let reversed = path.reverse_subpaths();
1617 assert_eq!(
1618 "M125,60 C150,50 125,10 100,10 L60,10 Q40,40 10,10",
1619 reversed.to_svg()
1620 );
1621 }
1622
1623 #[test]
1624 fn test_reverse_closed_triangle() {
1625 let path = BezPath::from_svg("M100,100 L150,200 L50,200 Z").unwrap();
1626 let reversed = path.reverse_subpaths();
1627 assert_eq!("M50,200 L150,200 L100,100 Z", reversed.to_svg());
1628 }
1629
1630 #[test]
1631 fn test_reverse_closed_shape() {
1632 let path = BezPath::from_svg(
1633 "M125,100 Q200,150 175,300 C150,150 50,150 25,300 Q0,150 75,100 L100,50 Z",
1634 )
1635 .unwrap();
1636 let reversed = path.reverse_subpaths();
1637 assert_eq!(
1638 "M100,50 L75,100 Q0,150 25,300 C50,150 150,150 175,300 Q200,150 125,100 Z",
1639 reversed.to_svg()
1640 );
1641 }
1642
1643 #[test]
1644 fn test_reverse_multiple_subpaths() {
1645 let svg = "M10,10 Q40,40 60,10 L100,10 C125,10 150,50 125,60 M100,100 L150,200 L50,200 Z M125,100 Q200,150 175,300 C150,150 50,150 25,300 Q0,150 75,100 L100,50 Z";
1646 let expected_svg = "M125,60 C150,50 125,10 100,10 L60,10 Q40,40 10,10 M50,200 L150,200 L100,100 Z M100,50 L75,100 Q0,150 25,300 C50,150 150,150 175,300 Q200,150 125,100 Z";
1647 let path = BezPath::from_svg(svg).unwrap();
1648 let reversed = path.reverse_subpaths();
1649 assert_eq!(expected_svg, reversed.to_svg());
1650 }
1651
1652 // https://github.com/fonttools/fonttools/blob/bf265ce49e0cae6f032420a4c80c31d8e16285b8/Tests/pens/reverseContourPen_test.py#L7
1653 #[test]
1654 fn test_reverse_lines() {
1655 let mut path = BezPath::new();
1656 path.move_to((0.0, 0.0));
1657 path.line_to((1.0, 1.0));
1658 path.line_to((2.0, 2.0));
1659 path.line_to((3.0, 3.0));
1660 path.close_path();
1661 let rev = path.reverse_subpaths();
1662 assert_eq!("M3,3 L2,2 L1,1 L0,0 Z", rev.to_svg());
1663 }
1664
1665 #[test]
1666 fn test_reverse_multiple_moves() {
1667 reverse_test_helper(
1668 vec![
1669 PathEl::MoveTo((2.0, 2.0).into()),
1670 PathEl::MoveTo((3.0, 3.0).into()),
1671 PathEl::ClosePath,
1672 PathEl::MoveTo((4.0, 4.0).into()),
1673 ],
1674 vec![
1675 PathEl::MoveTo((2.0, 2.0).into()),
1676 PathEl::MoveTo((3.0, 3.0).into()),
1677 PathEl::ClosePath,
1678 PathEl::MoveTo((4.0, 4.0).into()),
1679 ],
1680 );
1681 }
1682
1683 // The following are direct port of fonttools'
1684 // reverseContourPen_test.py::test_reverse_pen, adapted to rust, excluding
1685 // test cases that don't apply because we don't implement
1686 // outputImpliedClosingLine=False.
1687 // https://github.com/fonttools/fonttools/blob/85c80be/Tests/pens/reverseContourPen_test.py#L6-L467
1688
1689 #[test]
1690 fn test_reverse_closed_last_line_not_on_move() {
1691 reverse_test_helper(
1692 vec![
1693 PathEl::MoveTo((0.0, 0.0).into()),
1694 PathEl::LineTo((1.0, 1.0).into()),
1695 PathEl::LineTo((2.0, 2.0).into()),
1696 PathEl::LineTo((3.0, 3.0).into()),
1697 PathEl::ClosePath,
1698 ],
1699 vec![
1700 PathEl::MoveTo((3.0, 3.0).into()),
1701 PathEl::LineTo((2.0, 2.0).into()),
1702 PathEl::LineTo((1.0, 1.0).into()),
1703 PathEl::LineTo((0.0, 0.0).into()), // closing line NOT implied
1704 PathEl::ClosePath,
1705 ],
1706 );
1707 }
1708
1709 #[test]
1710 fn test_reverse_closed_last_line_overlaps_move() {
1711 reverse_test_helper(
1712 vec![
1713 PathEl::MoveTo((0.0, 0.0).into()),
1714 PathEl::LineTo((1.0, 1.0).into()),
1715 PathEl::LineTo((2.0, 2.0).into()),
1716 PathEl::LineTo((0.0, 0.0).into()),
1717 PathEl::ClosePath,
1718 ],
1719 vec![
1720 PathEl::MoveTo((0.0, 0.0).into()),
1721 PathEl::LineTo((2.0, 2.0).into()),
1722 PathEl::LineTo((1.0, 1.0).into()),
1723 PathEl::LineTo((0.0, 0.0).into()), // closing line NOT implied
1724 PathEl::ClosePath,
1725 ],
1726 );
1727 }
1728
1729 #[test]
1730 fn test_reverse_closed_duplicate_line_following_move() {
1731 reverse_test_helper(
1732 vec![
1733 PathEl::MoveTo((0.0, 0.0).into()),
1734 PathEl::LineTo((0.0, 0.0).into()),
1735 PathEl::LineTo((1.0, 1.0).into()),
1736 PathEl::LineTo((2.0, 2.0).into()),
1737 PathEl::ClosePath,
1738 ],
1739 vec![
1740 PathEl::MoveTo((2.0, 2.0).into()),
1741 PathEl::LineTo((1.0, 1.0).into()),
1742 PathEl::LineTo((0.0, 0.0).into()), // duplicate line retained
1743 PathEl::LineTo((0.0, 0.0).into()),
1744 PathEl::ClosePath,
1745 ],
1746 );
1747 }
1748
1749 #[test]
1750 fn test_reverse_closed_two_lines() {
1751 reverse_test_helper(
1752 vec![
1753 PathEl::MoveTo((0.0, 0.0).into()),
1754 PathEl::LineTo((1.0, 1.0).into()),
1755 PathEl::ClosePath,
1756 ],
1757 vec![
1758 PathEl::MoveTo((1.0, 1.0).into()),
1759 PathEl::LineTo((0.0, 0.0).into()), // closing line NOT implied
1760 PathEl::ClosePath,
1761 ],
1762 );
1763 }
1764
1765 #[test]
1766 fn test_reverse_closed_last_curve_overlaps_move() {
1767 reverse_test_helper(
1768 vec![
1769 PathEl::MoveTo((0.0, 0.0).into()),
1770 PathEl::CurveTo((1.0, 1.0).into(), (2.0, 2.0).into(), (3.0, 3.0).into()),
1771 PathEl::CurveTo((4.0, 4.0).into(), (5.0, 5.0).into(), (0.0, 0.0).into()),
1772 PathEl::ClosePath,
1773 ],
1774 vec![
1775 PathEl::MoveTo((0.0, 0.0).into()), // no extra lineTo added here
1776 PathEl::CurveTo((5.0, 5.0).into(), (4.0, 4.0).into(), (3.0, 3.0).into()),
1777 PathEl::CurveTo((2.0, 2.0).into(), (1.0, 1.0).into(), (0.0, 0.0).into()),
1778 PathEl::ClosePath,
1779 ],
1780 );
1781 }
1782
1783 #[test]
1784 fn test_reverse_closed_last_curve_not_on_move() {
1785 reverse_test_helper(
1786 vec![
1787 PathEl::MoveTo((0.0, 0.0).into()),
1788 PathEl::CurveTo((1.0, 1.0).into(), (2.0, 2.0).into(), (3.0, 3.0).into()),
1789 PathEl::CurveTo((4.0, 4.0).into(), (5.0, 5.0).into(), (6.0, 6.0).into()),
1790 PathEl::ClosePath,
1791 ],
1792 vec![
1793 PathEl::MoveTo((6.0, 6.0).into()), // the previously implied line
1794 PathEl::CurveTo((5.0, 5.0).into(), (4.0, 4.0).into(), (3.0, 3.0).into()),
1795 PathEl::CurveTo((2.0, 2.0).into(), (1.0, 1.0).into(), (0.0, 0.0).into()),
1796 PathEl::ClosePath,
1797 ],
1798 );
1799 }
1800
1801 #[test]
1802 fn test_reverse_closed_line_curve_line() {
1803 reverse_test_helper(
1804 vec![
1805 PathEl::MoveTo((0.0, 0.0).into()),
1806 PathEl::LineTo((1.0, 1.0).into()), // this line...
1807 PathEl::CurveTo((2.0, 2.0).into(), (3.0, 3.0).into(), (4.0, 4.0).into()),
1808 PathEl::CurveTo((5.0, 5.0).into(), (6.0, 6.0).into(), (7.0, 7.0).into()),
1809 PathEl::ClosePath,
1810 ],
1811 vec![
1812 PathEl::MoveTo((7.0, 7.0).into()),
1813 PathEl::CurveTo((6.0, 6.0).into(), (5.0, 5.0).into(), (4.0, 4.0).into()),
1814 PathEl::CurveTo((3.0, 3.0).into(), (2.0, 2.0).into(), (1.0, 1.0).into()),
1815 PathEl::LineTo((0.0, 0.0).into()), // ... does NOT become implied
1816 PathEl::ClosePath,
1817 ],
1818 );
1819 }
1820
1821 #[test]
1822 fn test_reverse_closed_last_quad_overlaps_move() {
1823 reverse_test_helper(
1824 vec![
1825 PathEl::MoveTo((0.0, 0.0).into()),
1826 PathEl::QuadTo((1.0, 1.0).into(), (2.0, 2.0).into()),
1827 PathEl::QuadTo((3.0, 3.0).into(), (0.0, 0.0).into()),
1828 PathEl::ClosePath,
1829 ],
1830 vec![
1831 PathEl::MoveTo((0.0, 0.0).into()), // no extra lineTo added here
1832 PathEl::QuadTo((3.0, 3.0).into(), (2.0, 2.0).into()),
1833 PathEl::QuadTo((1.0, 1.0).into(), (0.0, 0.0).into()),
1834 PathEl::ClosePath,
1835 ],
1836 );
1837 }
1838
1839 #[test]
1840 fn test_reverse_closed_last_quad_not_on_move() {
1841 reverse_test_helper(
1842 vec![
1843 PathEl::MoveTo((0.0, 0.0).into()),
1844 PathEl::QuadTo((1.0, 1.0).into(), (2.0, 2.0).into()),
1845 PathEl::QuadTo((3.0, 3.0).into(), (4.0, 4.0).into()),
1846 PathEl::ClosePath,
1847 ],
1848 vec![
1849 PathEl::MoveTo((4.0, 4.0).into()), // the previously implied line
1850 PathEl::QuadTo((3.0, 3.0).into(), (2.0, 2.0).into()),
1851 PathEl::QuadTo((1.0, 1.0).into(), (0.0, 0.0).into()),
1852 PathEl::ClosePath,
1853 ],
1854 );
1855 }
1856
1857 #[test]
1858 fn test_reverse_closed_line_quad_line() {
1859 reverse_test_helper(
1860 vec![
1861 PathEl::MoveTo((0.0, 0.0).into()),
1862 PathEl::LineTo((1.0, 1.0).into()), // this line...
1863 PathEl::QuadTo((2.0, 2.0).into(), (3.0, 3.0).into()),
1864 PathEl::ClosePath,
1865 ],
1866 vec![
1867 PathEl::MoveTo((3.0, 3.0).into()),
1868 PathEl::QuadTo((2.0, 2.0).into(), (1.0, 1.0).into()),
1869 PathEl::LineTo((0.0, 0.0).into()), // ... does NOT become implied
1870 PathEl::ClosePath,
1871 ],
1872 );
1873 }
1874
1875 #[test]
1876 fn test_reverse_empty() {
1877 reverse_test_helper(vec![], vec![]);
1878 }
1879
1880 #[test]
1881 fn test_reverse_single_point() {
1882 reverse_test_helper(
1883 vec![PathEl::MoveTo((0.0, 0.0).into())],
1884 vec![PathEl::MoveTo((0.0, 0.0).into())],
1885 );
1886 }
1887
1888 #[test]
1889 fn test_reverse_single_point_closed() {
1890 reverse_test_helper(
1891 vec![PathEl::MoveTo((0.0, 0.0).into()), PathEl::ClosePath],
1892 vec![PathEl::MoveTo((0.0, 0.0).into()), PathEl::ClosePath],
1893 );
1894 }
1895
1896 #[test]
1897 fn test_reverse_single_line_open() {
1898 reverse_test_helper(
1899 vec![
1900 PathEl::MoveTo((0.0, 0.0).into()),
1901 PathEl::LineTo((1.0, 1.0).into()),
1902 ],
1903 vec![
1904 PathEl::MoveTo((1.0, 1.0).into()),
1905 PathEl::LineTo((0.0, 0.0).into()),
1906 ],
1907 );
1908 }
1909
1910 #[test]
1911 fn test_reverse_single_curve_open() {
1912 reverse_test_helper(
1913 vec![
1914 PathEl::MoveTo((0.0, 0.0).into()),
1915 PathEl::CurveTo((1.0, 1.0).into(), (2.0, 2.0).into(), (3.0, 3.0).into()),
1916 ],
1917 vec![
1918 PathEl::MoveTo((3.0, 3.0).into()),
1919 PathEl::CurveTo((2.0, 2.0).into(), (1.0, 1.0).into(), (0.0, 0.0).into()),
1920 ],
1921 );
1922 }
1923
1924 #[test]
1925 fn test_reverse_curve_line_open() {
1926 reverse_test_helper(
1927 vec![
1928 PathEl::MoveTo((0.0, 0.0).into()),
1929 PathEl::CurveTo((1.0, 1.0).into(), (2.0, 2.0).into(), (3.0, 3.0).into()),
1930 PathEl::LineTo((4.0, 4.0).into()),
1931 ],
1932 vec![
1933 PathEl::MoveTo((4.0, 4.0).into()),
1934 PathEl::LineTo((3.0, 3.0).into()),
1935 PathEl::CurveTo((2.0, 2.0).into(), (1.0, 1.0).into(), (0.0, 0.0).into()),
1936 ],
1937 );
1938 }
1939
1940 #[test]
1941 fn test_reverse_line_curve_open() {
1942 reverse_test_helper(
1943 vec![
1944 PathEl::MoveTo((0.0, 0.0).into()),
1945 PathEl::LineTo((1.0, 1.0).into()),
1946 PathEl::CurveTo((2.0, 2.0).into(), (3.0, 3.0).into(), (4.0, 4.0).into()),
1947 ],
1948 vec![
1949 PathEl::MoveTo((4.0, 4.0).into()),
1950 PathEl::CurveTo((3.0, 3.0).into(), (2.0, 2.0).into(), (1.0, 1.0).into()),
1951 PathEl::LineTo((0.0, 0.0).into()),
1952 ],
1953 );
1954 }
1955
1956 #[test]
1957 fn test_reverse_duplicate_point_after_move() {
1958 // Test case from: https://github.com/googlei18n/cu2qu/issues/51#issue-179370514
1959 // Simplified to only use atomic PathEl::QuadTo (no QuadSplines).
1960 reverse_test_helper(
1961 vec![
1962 PathEl::MoveTo((848.0, 348.0).into()),
1963 PathEl::LineTo((848.0, 348.0).into()),
1964 PathEl::QuadTo((848.0, 526.0).into(), (449.0, 704.0).into()),
1965 PathEl::QuadTo((848.0, 171.0).into(), (848.0, 348.0).into()),
1966 PathEl::ClosePath,
1967 ],
1968 vec![
1969 PathEl::MoveTo((848.0, 348.0).into()),
1970 PathEl::QuadTo((848.0, 171.0).into(), (449.0, 704.0).into()),
1971 PathEl::QuadTo((848.0, 526.0).into(), (848.0, 348.0).into()),
1972 PathEl::LineTo((848.0, 348.0).into()),
1973 PathEl::ClosePath,
1974 ],
1975 );
1976 }
1977
1978 #[test]
1979 fn test_reverse_duplicate_point_at_end() {
1980 // Test case from: https://github.com/googlefonts/fontmake/issues/572
1981 reverse_test_helper(
1982 vec![
1983 PathEl::MoveTo((0.0, 651.0).into()),
1984 PathEl::LineTo((0.0, 101.0).into()),
1985 PathEl::LineTo((0.0, 101.0).into()),
1986 PathEl::LineTo((0.0, 651.0).into()),
1987 PathEl::LineTo((0.0, 651.0).into()),
1988 PathEl::ClosePath,
1989 ],
1990 vec![
1991 PathEl::MoveTo((0.0, 651.0).into()),
1992 PathEl::LineTo((0.0, 651.0).into()),
1993 PathEl::LineTo((0.0, 101.0).into()),
1994 PathEl::LineTo((0.0, 101.0).into()),
1995 PathEl::LineTo((0.0, 651.0).into()),
1996 PathEl::ClosePath,
1997 ],
1998 );
1999 }
2000
2001 fn reverse_test_helper(contour: Vec<PathEl>, expected: Vec<PathEl>) {
2002 assert_eq!(BezPath(contour).reverse_subpaths().0, expected);
2003 }
2004}
2005