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