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
420impl FromIterator<PathEl> for BezPath {
421 fn from_iter<T: IntoIterator<Item = PathEl>>(iter: T) -> Self {
422 let el_vec: Vec<_> = iter.into_iter().collect();
423 BezPath::from_vec(el_vec)
424 }
425}
426
427/// Allow iteration over references to `BezPath`.
428///
429/// Note: the semantics are slightly different from simply iterating over the
430/// slice, as it returns `PathEl` items, rather than references.
431impl<'a> IntoIterator for &'a BezPath {
432 type Item = PathEl;
433 type IntoIter = core::iter::Cloned<core::slice::Iter<'a, PathEl>>;
434
435 fn into_iter(self) -> Self::IntoIter {
436 self.elements().iter().cloned()
437 }
438}
439
440impl IntoIterator for BezPath {
441 type Item = PathEl;
442 type IntoIter = alloc::vec::IntoIter<PathEl>;
443
444 fn into_iter(self) -> Self::IntoIter {
445 self.0.into_iter()
446 }
447}
448
449impl Extend<PathEl> for BezPath {
450 fn extend<I: IntoIterator<Item = PathEl>>(&mut self, iter: I) {
451 self.0.extend(iter);
452 }
453}
454
455/// Proportion of tolerance budget that goes to cubic to quadratic conversion.
456const TO_QUAD_TOL: f64 = 0.1;
457
458/// Flatten the path, invoking the callback repeatedly.
459///
460/// See [`BezPath::flatten`] for more discussion.
461/// This signature is a bit more general, allowing flattening of `&[PathEl]` slices
462/// and other iterators yielding `PathEl`.
463pub fn flatten(
464 path: impl IntoIterator<Item = PathEl>,
465 tolerance: f64,
466 mut callback: impl FnMut(PathEl),
467) {
468 let sqrt_tol = tolerance.sqrt();
469 let mut last_pt = None;
470 let mut quad_buf = Vec::new();
471 for el in path {
472 match el {
473 PathEl::MoveTo(p) => {
474 last_pt = Some(p);
475 callback(PathEl::MoveTo(p));
476 }
477 PathEl::LineTo(p) => {
478 last_pt = Some(p);
479 callback(PathEl::LineTo(p));
480 }
481 PathEl::QuadTo(p1, p2) => {
482 if let Some(p0) = last_pt {
483 let q = QuadBez::new(p0, p1, p2);
484 let params = q.estimate_subdiv(sqrt_tol);
485 let n = ((0.5 * params.val / sqrt_tol).ceil() as usize).max(1);
486 let step = 1.0 / (n as f64);
487 for i in 1..n {
488 let u = (i as f64) * step;
489 let t = q.determine_subdiv_t(&params, u);
490 let p = q.eval(t);
491 callback(PathEl::LineTo(p));
492 }
493 callback(PathEl::LineTo(p2));
494 }
495 last_pt = Some(p2);
496 }
497 PathEl::CurveTo(p1, p2, p3) => {
498 if let Some(p0) = last_pt {
499 let c = CubicBez::new(p0, p1, p2, p3);
500
501 // Subdivide into quadratics, and estimate the number of
502 // subdivisions required for each, summing to arrive at an
503 // estimate for the number of subdivisions for the cubic.
504 // Also retain these parameters for later.
505 let iter = c.to_quads(tolerance * TO_QUAD_TOL);
506 quad_buf.clear();
507 quad_buf.reserve(iter.size_hint().0);
508 let sqrt_remain_tol = sqrt_tol * (1.0 - TO_QUAD_TOL).sqrt();
509 let mut sum = 0.0;
510 for (_, _, q) in iter {
511 let params = q.estimate_subdiv(sqrt_remain_tol);
512 sum += params.val;
513 quad_buf.push((q, params));
514 }
515 let n = ((0.5 * sum / sqrt_remain_tol).ceil() as usize).max(1);
516
517 // Iterate through the quadratics, outputting the points of
518 // subdivisions that fall within that quadratic.
519 let step = sum / (n as f64);
520 let mut i = 1;
521 let mut val_sum = 0.0;
522 for (q, params) in &quad_buf {
523 let mut target = (i as f64) * step;
524 let recip_val = params.val.recip();
525 while target < val_sum + params.val {
526 let u = (target - val_sum) * recip_val;
527 let t = q.determine_subdiv_t(params, u);
528 let p = q.eval(t);
529 callback(PathEl::LineTo(p));
530 i += 1;
531 if i == n + 1 {
532 break;
533 }
534 target = (i as f64) * step;
535 }
536 val_sum += params.val;
537 }
538 callback(PathEl::LineTo(p3));
539 }
540 last_pt = Some(p3);
541 }
542 PathEl::ClosePath => {
543 last_pt = None;
544 callback(PathEl::ClosePath);
545 }
546 }
547 }
548}
549
550impl Mul<PathEl> for Affine {
551 type Output = PathEl;
552
553 fn mul(self, other: PathEl) -> PathEl {
554 match other {
555 PathEl::MoveTo(p: Point) => PathEl::MoveTo(self * p),
556 PathEl::LineTo(p: Point) => PathEl::LineTo(self * p),
557 PathEl::QuadTo(p1: Point, p2: Point) => PathEl::QuadTo(self * p1, self * p2),
558 PathEl::CurveTo(p1: Point, p2: Point, p3: Point) => PathEl::CurveTo(self * p1, self * p2, self * p3),
559 PathEl::ClosePath => PathEl::ClosePath,
560 }
561 }
562}
563
564impl Mul<PathSeg> for Affine {
565 type Output = PathSeg;
566
567 fn mul(self, other: PathSeg) -> PathSeg {
568 match other {
569 PathSeg::Line(line: Line) => PathSeg::Line(self * line),
570 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(self * quad),
571 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(self * cubic),
572 }
573 }
574}
575
576impl Mul<BezPath> for Affine {
577 type Output = BezPath;
578
579 fn mul(self, other: BezPath) -> BezPath {
580 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
581 }
582}
583
584impl<'a> Mul<&'a BezPath> for Affine {
585 type Output = BezPath;
586
587 fn mul(self, other: &BezPath) -> BezPath {
588 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
589 }
590}
591
592impl Mul<PathEl> for TranslateScale {
593 type Output = PathEl;
594
595 fn mul(self, other: PathEl) -> PathEl {
596 match other {
597 PathEl::MoveTo(p: Point) => PathEl::MoveTo(self * p),
598 PathEl::LineTo(p: Point) => PathEl::LineTo(self * p),
599 PathEl::QuadTo(p1: Point, p2: Point) => PathEl::QuadTo(self * p1, self * p2),
600 PathEl::CurveTo(p1: Point, p2: Point, p3: Point) => PathEl::CurveTo(self * p1, self * p2, self * p3),
601 PathEl::ClosePath => PathEl::ClosePath,
602 }
603 }
604}
605
606impl Mul<PathSeg> for TranslateScale {
607 type Output = PathSeg;
608
609 fn mul(self, other: PathSeg) -> PathSeg {
610 match other {
611 PathSeg::Line(line: Line) => PathSeg::Line(self * line),
612 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(self * quad),
613 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(self * cubic),
614 }
615 }
616}
617
618impl Mul<BezPath> for TranslateScale {
619 type Output = BezPath;
620
621 fn mul(self, other: BezPath) -> BezPath {
622 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
623 }
624}
625
626impl<'a> Mul<&'a BezPath> for TranslateScale {
627 type Output = BezPath;
628
629 fn mul(self, other: &BezPath) -> BezPath {
630 BezPath(other.0.iter().map(|&el: PathEl| self * el).collect())
631 }
632}
633
634/// Transform an iterator over path elements into one over path
635/// segments.
636///
637/// See also [`BezPath::segments`].
638/// This signature is a bit more general, allowing `&[PathEl]` slices
639/// and other iterators yielding `PathEl`.
640pub fn segments<I>(elements: I) -> Segments<I::IntoIter>
641where
642 I: IntoIterator<Item = PathEl>,
643{
644 Segments {
645 elements: elements.into_iter(),
646 start_last: None,
647 }
648}
649
650/// An iterator that transforms path elements to path segments.
651///
652/// This struct is created by the [`segments`] function.
653#[derive(Clone)]
654pub struct Segments<I: Iterator<Item = PathEl>> {
655 elements: I,
656 start_last: Option<(Point, Point)>,
657}
658
659impl<I: Iterator<Item = PathEl>> Iterator for Segments<I> {
660 type Item = PathSeg;
661
662 fn next(&mut self) -> Option<PathSeg> {
663 for el in &mut self.elements {
664 // We first need to check whether this is the first
665 // path element we see to fill in the start position.
666 let (start, last) = self.start_last.get_or_insert_with(|| {
667 let point = match el {
668 PathEl::MoveTo(p) => p,
669 PathEl::LineTo(p) => p,
670 PathEl::QuadTo(_, p2) => p2,
671 PathEl::CurveTo(_, _, p3) => p3,
672 PathEl::ClosePath => panic!("Can't start a segment on a ClosePath"),
673 };
674 (point, point)
675 });
676
677 return Some(match el {
678 PathEl::MoveTo(p) => {
679 *start = p;
680 *last = p;
681 continue;
682 }
683 PathEl::LineTo(p) => PathSeg::Line(Line::new(mem::replace(last, p), p)),
684 PathEl::QuadTo(p1, p2) => {
685 PathSeg::Quad(QuadBez::new(mem::replace(last, p2), p1, p2))
686 }
687 PathEl::CurveTo(p1, p2, p3) => {
688 PathSeg::Cubic(CubicBez::new(mem::replace(last, p3), p1, p2, p3))
689 }
690 PathEl::ClosePath => {
691 if *last != *start {
692 PathSeg::Line(Line::new(mem::replace(last, *start), *start))
693 } else {
694 continue;
695 }
696 }
697 });
698 }
699
700 None
701 }
702}
703
704impl<I: Iterator<Item = PathEl>> Segments<I> {
705 /// Here, `accuracy` specifies the accuracy for each Bézier segment. At worst,
706 /// the total error is `accuracy` times the number of Bézier segments.
707
708 // TODO: pub? Or is this subsumed by method of &[PathEl]?
709 pub(crate) fn perimeter(self, accuracy: f64) -> f64 {
710 self.map(|seg| seg.arclen(accuracy)).sum()
711 }
712
713 // Same
714 pub(crate) fn area(self) -> f64 {
715 self.map(|seg| seg.signed_area()).sum()
716 }
717
718 // Same
719 pub(crate) fn winding(self, p: Point) -> i32 {
720 self.map(|seg| seg.winding(p)).sum()
721 }
722
723 // Same
724 pub(crate) fn bounding_box(self) -> Rect {
725 let mut bbox: Option<Rect> = None;
726 for seg in self {
727 let seg_bb = ParamCurveExtrema::bounding_box(&seg);
728 if let Some(bb) = bbox {
729 bbox = Some(bb.union(seg_bb));
730 } else {
731 bbox = Some(seg_bb)
732 }
733 }
734 bbox.unwrap_or_default()
735 }
736}
737
738impl ParamCurve for PathSeg {
739 fn eval(&self, t: f64) -> Point {
740 match *self {
741 PathSeg::Line(line: Line) => line.eval(t),
742 PathSeg::Quad(quad: QuadBez) => quad.eval(t),
743 PathSeg::Cubic(cubic: CubicBez) => cubic.eval(t),
744 }
745 }
746
747 fn subsegment(&self, range: Range<f64>) -> PathSeg {
748 match *self {
749 PathSeg::Line(line: Line) => PathSeg::Line(line.subsegment(range)),
750 PathSeg::Quad(quad: QuadBez) => PathSeg::Quad(quad.subsegment(range)),
751 PathSeg::Cubic(cubic: CubicBez) => PathSeg::Cubic(cubic.subsegment(range)),
752 }
753 }
754}
755
756impl ParamCurveArclen for PathSeg {
757 fn arclen(&self, accuracy: f64) -> f64 {
758 match *self {
759 PathSeg::Line(line: Line) => line.arclen(accuracy),
760 PathSeg::Quad(quad: QuadBez) => quad.arclen(accuracy),
761 PathSeg::Cubic(cubic: CubicBez) => cubic.arclen(accuracy),
762 }
763 }
764
765 fn inv_arclen(&self, arclen: f64, accuracy: f64) -> f64 {
766 match *self {
767 PathSeg::Line(line: Line) => line.inv_arclen(arclen, accuracy),
768 PathSeg::Quad(quad: QuadBez) => quad.inv_arclen(arclen, accuracy),
769 PathSeg::Cubic(cubic: CubicBez) => cubic.inv_arclen(arclen, accuracy),
770 }
771 }
772}
773
774impl ParamCurveArea for PathSeg {
775 fn signed_area(&self) -> f64 {
776 match *self {
777 PathSeg::Line(line: Line) => line.signed_area(),
778 PathSeg::Quad(quad: QuadBez) => quad.signed_area(),
779 PathSeg::Cubic(cubic: CubicBez) => cubic.signed_area(),
780 }
781 }
782}
783
784impl ParamCurveNearest for PathSeg {
785 fn nearest(&self, p: Point, accuracy: f64) -> Nearest {
786 match *self {
787 PathSeg::Line(line: Line) => line.nearest(p, accuracy),
788 PathSeg::Quad(quad: QuadBez) => quad.nearest(p, accuracy),
789 PathSeg::Cubic(cubic: CubicBez) => cubic.nearest(p, accuracy),
790 }
791 }
792}
793
794impl ParamCurveExtrema for PathSeg {
795 fn extrema(&self) -> ArrayVec<f64, MAX_EXTREMA> {
796 match *self {
797 PathSeg::Line(line: Line) => line.extrema(),
798 PathSeg::Quad(quad: QuadBez) => quad.extrema(),
799 PathSeg::Cubic(cubic: CubicBez) => cubic.extrema(),
800 }
801 }
802}
803
804impl PathSeg {
805 /// Get the [`PathEl`] that is equivalent to discarding the segment start point.
806 pub fn as_path_el(&self) -> PathEl {
807 match self {
808 PathSeg::Line(line) => PathEl::LineTo(line.p1),
809 PathSeg::Quad(q) => PathEl::QuadTo(q.p1, q.p2),
810 PathSeg::Cubic(c) => PathEl::CurveTo(c.p1, c.p2, c.p3),
811 }
812 }
813
814 /// Returns a new `PathSeg` describing the same path as `self`, but with
815 /// the points reversed.
816 pub fn reverse(&self) -> PathSeg {
817 match self {
818 PathSeg::Line(Line { p0, p1 }) => PathSeg::Line(Line::new(*p1, *p0)),
819 PathSeg::Quad(q) => PathSeg::Quad(QuadBez::new(q.p2, q.p1, q.p0)),
820 PathSeg::Cubic(c) => PathSeg::Cubic(CubicBez::new(c.p3, c.p2, c.p1, c.p0)),
821 }
822 }
823
824 /// Convert this segment to a cubic bezier.
825 pub fn to_cubic(&self) -> CubicBez {
826 match *self {
827 PathSeg::Line(Line { p0, p1 }) => CubicBez::new(p0, p0, p1, p1),
828 PathSeg::Cubic(c) => c,
829 PathSeg::Quad(q) => q.raise(),
830 }
831 }
832
833 // Assumes split at extrema.
834 fn winding_inner(&self, p: Point) -> i32 {
835 let start = self.start();
836 let end = self.end();
837 let sign = if end.y > start.y {
838 if p.y < start.y || p.y >= end.y {
839 return 0;
840 }
841 -1
842 } else if end.y < start.y {
843 if p.y < end.y || p.y >= start.y {
844 return 0;
845 }
846 1
847 } else {
848 return 0;
849 };
850 match *self {
851 PathSeg::Line(_line) => {
852 if p.x < start.x.min(end.x) {
853 return 0;
854 }
855 if p.x >= start.x.max(end.x) {
856 return sign;
857 }
858 // line equation ax + by = c
859 let a = end.y - start.y;
860 let b = start.x - end.x;
861 let c = a * start.x + b * start.y;
862 if (a * p.x + b * p.y - c) * (sign as f64) <= 0.0 {
863 sign
864 } else {
865 0
866 }
867 }
868 PathSeg::Quad(quad) => {
869 let p1 = quad.p1;
870 if p.x < start.x.min(end.x).min(p1.x) {
871 return 0;
872 }
873 if p.x >= start.x.max(end.x).max(p1.x) {
874 return sign;
875 }
876 let a = end.y - 2.0 * p1.y + start.y;
877 let b = 2.0 * (p1.y - start.y);
878 let c = start.y - p.y;
879 for t in solve_quadratic(c, b, a) {
880 if (0.0..=1.0).contains(&t) {
881 let x = quad.eval(t).x;
882 if p.x >= x {
883 return sign;
884 } else {
885 return 0;
886 }
887 }
888 }
889 0
890 }
891 PathSeg::Cubic(cubic) => {
892 let p1 = cubic.p1;
893 let p2 = cubic.p2;
894 if p.x < start.x.min(end.x).min(p1.x).min(p2.x) {
895 return 0;
896 }
897 if p.x >= start.x.max(end.x).max(p1.x).max(p2.x) {
898 return sign;
899 }
900 let a = end.y - 3.0 * p2.y + 3.0 * p1.y - start.y;
901 let b = 3.0 * (p2.y - 2.0 * p1.y + start.y);
902 let c = 3.0 * (p1.y - start.y);
903 let d = start.y - p.y;
904 for t in solve_cubic(d, c, b, a) {
905 if (0.0..=1.0).contains(&t) {
906 let x = cubic.eval(t).x;
907 if p.x >= x {
908 return sign;
909 } else {
910 return 0;
911 }
912 }
913 }
914 0
915 }
916 }
917 }
918
919 /// Compute the winding number contribution of a single segment.
920 ///
921 /// Cast a ray to the left and count intersections.
922 fn winding(&self, p: Point) -> i32 {
923 self.extrema_ranges()
924 .into_iter()
925 .map(|range| self.subsegment(range).winding_inner(p))
926 .sum()
927 }
928
929 /// Compute intersections against a line.
930 ///
931 /// Returns a vector of the intersections. For each intersection,
932 /// the `t` value of the segment and line are given.
933 ///
934 /// Note: This test is designed to be inclusive of points near the endpoints
935 /// of the segment. This is so that testing a line against multiple
936 /// contiguous segments of a path will be guaranteed to catch at least one
937 /// of them. In such cases, use higher level logic to coalesce the hits
938 /// (the `t` value may be slightly outside the range of 0..1).
939 ///
940 /// # Examples
941 ///
942 /// ```
943 /// # use kurbo::*;
944 /// let seg = PathSeg::Line(Line::new((0.0, 0.0), (2.0, 0.0)));
945 /// let line = Line::new((1.0, 2.0), (1.0, -2.0));
946 /// let intersection = seg.intersect_line(line);
947 /// assert_eq!(intersection.len(), 1);
948 /// let intersection = intersection[0];
949 /// assert_eq!(intersection.segment_t, 0.5);
950 /// assert_eq!(intersection.line_t, 0.5);
951 ///
952 /// let point = seg.eval(intersection.segment_t);
953 /// assert_eq!(point, Point::new(1.0, 0.0));
954 /// ```
955 pub fn intersect_line(&self, line: Line) -> ArrayVec<LineIntersection, 3> {
956 const EPSILON: f64 = 1e-9;
957 let p0 = line.p0;
958 let p1 = line.p1;
959 let dx = p1.x - p0.x;
960 let dy = p1.y - p0.y;
961 let mut result = ArrayVec::new();
962 match self {
963 PathSeg::Line(l) => {
964 let det = dx * (l.p1.y - l.p0.y) - dy * (l.p1.x - l.p0.x);
965 if det.abs() < EPSILON {
966 // Lines are coincident (or nearly so).
967 return result;
968 }
969 let t = dx * (p0.y - l.p0.y) - dy * (p0.x - l.p0.x);
970 // t = position on self
971 let t = t / det;
972 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
973 // u = position on probe line
974 let u =
975 (l.p0.x - p0.x) * (l.p1.y - l.p0.y) - (l.p0.y - p0.y) * (l.p1.x - l.p0.x);
976 let u = u / det;
977 if (0.0..=1.0).contains(&u) {
978 result.push(LineIntersection::new(u, t));
979 }
980 }
981 }
982 PathSeg::Quad(q) => {
983 // The basic technique here is to determine x and y as a quadratic polynomial
984 // as a function of t. Then plug those values into the line equation for the
985 // probe line (giving a sort of signed distance from the probe line) and solve
986 // that for t.
987 let (px0, px1, px2) = quadratic_bez_coefs(q.p0.x, q.p1.x, q.p2.x);
988 let (py0, py1, py2) = quadratic_bez_coefs(q.p0.y, q.p1.y, q.p2.y);
989 let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
990 let c1 = dy * px1 - dx * py1;
991 let c2 = dy * px2 - dx * py2;
992 let invlen2 = (dx * dx + dy * dy).recip();
993 for t in crate::common::solve_quadratic(c0, c1, c2) {
994 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
995 let x = px0 + t * px1 + t * t * px2;
996 let y = py0 + t * py1 + t * t * py2;
997 let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
998 if (0.0..=1.0).contains(&u) {
999 result.push(LineIntersection::new(u, t));
1000 }
1001 }
1002 }
1003 }
1004 PathSeg::Cubic(c) => {
1005 // Same technique as above, but cubic polynomial.
1006 let (px0, px1, px2, px3) = cubic_bez_coefs(c.p0.x, c.p1.x, c.p2.x, c.p3.x);
1007 let (py0, py1, py2, py3) = cubic_bez_coefs(c.p0.y, c.p1.y, c.p2.y, c.p3.y);
1008 let c0 = dy * (px0 - p0.x) - dx * (py0 - p0.y);
1009 let c1 = dy * px1 - dx * py1;
1010 let c2 = dy * px2 - dx * py2;
1011 let c3 = dy * px3 - dx * py3;
1012 let invlen2 = (dx * dx + dy * dy).recip();
1013 for t in crate::common::solve_cubic(c0, c1, c2, c3) {
1014 if (-EPSILON..=(1.0 + EPSILON)).contains(&t) {
1015 let x = px0 + t * px1 + t * t * px2 + t * t * t * px3;
1016 let y = py0 + t * py1 + t * t * py2 + t * t * t * py3;
1017 let u = ((x - p0.x) * dx + (y - p0.y) * dy) * invlen2;
1018 if (0.0..=1.0).contains(&u) {
1019 result.push(LineIntersection::new(u, t));
1020 }
1021 }
1022 }
1023 }
1024 }
1025 result
1026 }
1027
1028 /// Is this Bezier path finite?
1029 #[inline]
1030 pub fn is_finite(&self) -> bool {
1031 match self {
1032 PathSeg::Line(line) => line.is_finite(),
1033 PathSeg::Quad(quad_bez) => quad_bez.is_finite(),
1034 PathSeg::Cubic(cubic_bez) => cubic_bez.is_finite(),
1035 }
1036 }
1037
1038 /// Is this Bezier path NaN?
1039 #[inline]
1040 pub fn is_nan(&self) -> bool {
1041 match self {
1042 PathSeg::Line(line) => line.is_nan(),
1043 PathSeg::Quad(quad_bez) => quad_bez.is_nan(),
1044 PathSeg::Cubic(cubic_bez) => cubic_bez.is_nan(),
1045 }
1046 }
1047
1048 #[inline]
1049 fn as_vec2_vec(&self) -> ArrayVec<Vec2, 4> {
1050 let mut a = ArrayVec::new();
1051 match self {
1052 PathSeg::Line(l) => {
1053 a.push(l.p0.to_vec2());
1054 a.push(l.p1.to_vec2());
1055 }
1056 PathSeg::Quad(q) => {
1057 a.push(q.p0.to_vec2());
1058 a.push(q.p1.to_vec2());
1059 a.push(q.p2.to_vec2());
1060 }
1061 PathSeg::Cubic(c) => {
1062 a.push(c.p0.to_vec2());
1063 a.push(c.p1.to_vec2());
1064 a.push(c.p2.to_vec2());
1065 a.push(c.p3.to_vec2());
1066 }
1067 };
1068 a
1069 }
1070
1071 /// Minimum distance between two PathSegs
1072 ///
1073 /// Returns a tuple of the distance, the path time `t1` of the closest point
1074 /// on the first PathSeg, and the path time `t2` of the closest point on the
1075 /// second PathSeg.
1076 pub fn min_dist(&self, other: PathSeg, accuracy: f64) -> MinDistance {
1077 let (distance, t1, t2) = crate::mindist::min_dist_param(
1078 &self.as_vec2_vec(),
1079 &other.as_vec2_vec(),
1080 (0.0, 1.0),
1081 (0.0, 1.0),
1082 accuracy,
1083 None,
1084 );
1085 MinDistance {
1086 distance: distance.sqrt(),
1087 t1,
1088 t2,
1089 }
1090 }
1091
1092 /// Compute endpoint tangents of a path segment.
1093 ///
1094 /// This version is robust to the path segment not being a regular curve.
1095 pub(crate) fn tangents(&self) -> (Vec2, Vec2) {
1096 const EPS: f64 = 1e-12;
1097 match self {
1098 PathSeg::Line(l) => {
1099 let d = l.p1 - l.p0;
1100 (d, d)
1101 }
1102 PathSeg::Quad(q) => {
1103 let d01 = q.p1 - q.p0;
1104 let d0 = if d01.hypot2() > EPS { d01 } else { q.p2 - q.p0 };
1105 let d12 = q.p2 - q.p1;
1106 let d1 = if d12.hypot2() > EPS { d12 } else { q.p2 - q.p0 };
1107 (d0, d1)
1108 }
1109 PathSeg::Cubic(c) => {
1110 let d01 = c.p1 - c.p0;
1111 let d0 = if d01.hypot2() > EPS {
1112 d01
1113 } else {
1114 let d02 = c.p2 - c.p0;
1115 if d02.hypot2() > EPS {
1116 d02
1117 } else {
1118 c.p3 - c.p0
1119 }
1120 };
1121 let d23 = c.p3 - c.p2;
1122 let d1 = if d23.hypot2() > EPS {
1123 d23
1124 } else {
1125 let d13 = c.p3 - c.p1;
1126 if d13.hypot2() > EPS {
1127 d13
1128 } else {
1129 c.p3 - c.p0
1130 }
1131 };
1132 (d0, d1)
1133 }
1134 }
1135 }
1136}
1137
1138impl LineIntersection {
1139 fn new(line_t: f64, segment_t: f64) -> Self {
1140 LineIntersection { line_t, segment_t }
1141 }
1142
1143 /// Is this line intersection finite?
1144 #[inline]
1145 pub fn is_finite(self) -> bool {
1146 self.line_t.is_finite() && self.segment_t.is_finite()
1147 }
1148
1149 /// Is this line intersection NaN?
1150 #[inline]
1151 pub fn is_nan(self) -> bool {
1152 self.line_t.is_nan() || self.segment_t.is_nan()
1153 }
1154}
1155
1156// Return polynomial coefficients given cubic bezier coordinates.
1157fn quadratic_bez_coefs(x0: f64, x1: f64, x2: f64) -> (f64, f64, f64) {
1158 let p0: f64 = x0;
1159 let p1: f64 = 2.0 * x1 - 2.0 * x0;
1160 let p2: f64 = x2 - 2.0 * x1 + x0;
1161 (p0, p1, p2)
1162}
1163
1164// Return polynomial coefficients given cubic bezier coordinates.
1165fn cubic_bez_coefs(x0: f64, x1: f64, x2: f64, x3: f64) -> (f64, f64, f64, f64) {
1166 let p0: f64 = x0;
1167 let p1: f64 = 3.0 * x1 - 3.0 * x0;
1168 let p2: f64 = 3.0 * x2 - 6.0 * x1 + 3.0 * x0;
1169 let p3: f64 = x3 - 3.0 * x2 + 3.0 * x1 - x0;
1170 (p0, p1, p2, p3)
1171}
1172
1173impl From<CubicBez> for PathSeg {
1174 fn from(cubic_bez: CubicBez) -> PathSeg {
1175 PathSeg::Cubic(cubic_bez)
1176 }
1177}
1178
1179impl From<Line> for PathSeg {
1180 fn from(line: Line) -> PathSeg {
1181 PathSeg::Line(line)
1182 }
1183}
1184
1185impl From<QuadBez> for PathSeg {
1186 fn from(quad_bez: QuadBez) -> PathSeg {
1187 PathSeg::Quad(quad_bez)
1188 }
1189}
1190
1191impl Shape for BezPath {
1192 type PathElementsIter<'iter> = core::iter::Copied<core::slice::Iter<'iter, PathEl>>;
1193
1194 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1195 self.0.iter().copied()
1196 }
1197
1198 fn to_path(&self, _tolerance: f64) -> BezPath {
1199 self.clone()
1200 }
1201
1202 fn into_path(self, _tolerance: f64) -> BezPath {
1203 self
1204 }
1205
1206 /// Signed area.
1207 fn area(&self) -> f64 {
1208 self.elements().area()
1209 }
1210
1211 fn perimeter(&self, accuracy: f64) -> f64 {
1212 self.elements().perimeter(accuracy)
1213 }
1214
1215 /// Winding number of point.
1216 fn winding(&self, pt: Point) -> i32 {
1217 self.elements().winding(pt)
1218 }
1219
1220 fn bounding_box(&self) -> Rect {
1221 self.elements().bounding_box()
1222 }
1223
1224 fn as_path_slice(&self) -> Option<&[PathEl]> {
1225 Some(&self.0)
1226 }
1227}
1228
1229impl PathEl {
1230 /// Is this path element finite?
1231 #[inline]
1232 pub fn is_finite(&self) -> bool {
1233 match self {
1234 PathEl::MoveTo(p) => p.is_finite(),
1235 PathEl::LineTo(p) => p.is_finite(),
1236 PathEl::QuadTo(p, p2) => p.is_finite() && p2.is_finite(),
1237 PathEl::CurveTo(p, p2, p3) => p.is_finite() && p2.is_finite() && p3.is_finite(),
1238 PathEl::ClosePath => true,
1239 }
1240 }
1241
1242 /// Is this path element NaN?
1243 #[inline]
1244 pub fn is_nan(&self) -> bool {
1245 match self {
1246 PathEl::MoveTo(p) => p.is_nan(),
1247 PathEl::LineTo(p) => p.is_nan(),
1248 PathEl::QuadTo(p, p2) => p.is_nan() || p2.is_nan(),
1249 PathEl::CurveTo(p, p2, p3) => p.is_nan() || p2.is_nan() || p3.is_nan(),
1250 PathEl::ClosePath => false,
1251 }
1252 }
1253}
1254
1255/// Implements [`Shape`] for a slice of [`PathEl`], provided that the first element of the slice is
1256/// not a `PathEl::ClosePath`. If it is, several of these functions will panic.
1257///
1258/// If the slice starts with `LineTo`, `QuadTo`, or `CurveTo`, it will be treated as a `MoveTo`.
1259impl<'a> Shape for &'a [PathEl] {
1260 type PathElementsIter<'iter>
1261
1262 = core::iter::Copied<core::slice::Iter<'a, PathEl>> where 'a: 'iter;
1263
1264 #[inline]
1265 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1266 self.iter().copied()
1267 }
1268
1269 fn to_path(&self, _tolerance: f64) -> BezPath {
1270 BezPath::from_vec(self.to_vec())
1271 }
1272
1273 /// Signed area.
1274 fn area(&self) -> f64 {
1275 segments(self.iter().copied()).area()
1276 }
1277
1278 fn perimeter(&self, accuracy: f64) -> f64 {
1279 segments(self.iter().copied()).perimeter(accuracy)
1280 }
1281
1282 /// Winding number of point.
1283 fn winding(&self, pt: Point) -> i32 {
1284 segments(self.iter().copied()).winding(pt)
1285 }
1286
1287 fn bounding_box(&self) -> Rect {
1288 segments(self.iter().copied()).bounding_box()
1289 }
1290
1291 #[inline]
1292 fn as_path_slice(&self) -> Option<&[PathEl]> {
1293 Some(self)
1294 }
1295}
1296
1297/// Implements [`Shape`] for an array of [`PathEl`], provided that the first element of the array is
1298/// not a `PathEl::ClosePath`. If it is, several of these functions will panic.
1299///
1300/// If the array starts with `LineTo`, `QuadTo`, or `CurveTo`, it will be treated as a `MoveTo`.
1301impl<const N: usize> Shape for [PathEl; N] {
1302 type PathElementsIter<'iter> = core::iter::Copied<core::slice::Iter<'iter, PathEl>>;
1303
1304 #[inline]
1305 fn path_elements(&self, _tolerance: f64) -> Self::PathElementsIter<'_> {
1306 self.iter().copied()
1307 }
1308
1309 fn to_path(&self, _tolerance: f64) -> BezPath {
1310 BezPath::from_vec(self.to_vec())
1311 }
1312
1313 /// Signed area.
1314 fn area(&self) -> f64 {
1315 segments(self.iter().copied()).area()
1316 }
1317
1318 fn perimeter(&self, accuracy: f64) -> f64 {
1319 segments(self.iter().copied()).perimeter(accuracy)
1320 }
1321
1322 /// Winding number of point.
1323 fn winding(&self, pt: Point) -> i32 {
1324 segments(self.iter().copied()).winding(pt)
1325 }
1326
1327 fn bounding_box(&self) -> Rect {
1328 segments(self.iter().copied()).bounding_box()
1329 }
1330
1331 #[inline]
1332 fn as_path_slice(&self) -> Option<&[PathEl]> {
1333 Some(self)
1334 }
1335}
1336
1337/// An iterator for path segments.
1338pub struct PathSegIter {
1339 seg: PathSeg,
1340 ix: usize,
1341}
1342
1343impl Shape for PathSeg {
1344 type PathElementsIter<'iter> = PathSegIter;
1345
1346 #[inline]
1347 fn path_elements(&self, _tolerance: f64) -> PathSegIter {
1348 PathSegIter { seg: *self, ix: 0 }
1349 }
1350
1351 /// The area under the curve.
1352 ///
1353 /// We could just return 0, but this seems more useful.
1354 fn area(&self) -> f64 {
1355 self.signed_area()
1356 }
1357
1358 #[inline]
1359 fn perimeter(&self, accuracy: f64) -> f64 {
1360 self.arclen(accuracy)
1361 }
1362
1363 fn winding(&self, _pt: Point) -> i32 {
1364 0
1365 }
1366
1367 #[inline]
1368 fn bounding_box(&self) -> Rect {
1369 ParamCurveExtrema::bounding_box(self)
1370 }
1371
1372 fn as_line(&self) -> Option<Line> {
1373 if let PathSeg::Line(line) = self {
1374 Some(*line)
1375 } else {
1376 None
1377 }
1378 }
1379}
1380
1381impl Iterator for PathSegIter {
1382 type Item = PathEl;
1383
1384 fn next(&mut self) -> Option<PathEl> {
1385 self.ix += 1;
1386 match (self.ix, self.seg) {
1387 // yes I could do some fancy bindings thing here but... :shrug:
1388 (1, PathSeg::Line(seg: Line)) => Some(PathEl::MoveTo(seg.p0)),
1389 (1, PathSeg::Quad(seg: QuadBez)) => Some(PathEl::MoveTo(seg.p0)),
1390 (1, PathSeg::Cubic(seg: CubicBez)) => Some(PathEl::MoveTo(seg.p0)),
1391 (2, PathSeg::Line(seg: Line)) => Some(PathEl::LineTo(seg.p1)),
1392 (2, PathSeg::Quad(seg: QuadBez)) => Some(PathEl::QuadTo(seg.p1, seg.p2)),
1393 (2, PathSeg::Cubic(seg: CubicBez)) => Some(PathEl::CurveTo(seg.p1, seg.p2, seg.p3)),
1394 _ => None,
1395 }
1396 }
1397}
1398
1399#[cfg(test)]
1400mod tests {
1401 use crate::{Circle, DEFAULT_ACCURACY};
1402
1403 use super::*;
1404
1405 fn assert_approx_eq(x: f64, y: f64) {
1406 assert!((x - y).abs() < 1e-8, "{x} != {y}");
1407 }
1408
1409 #[test]
1410 #[should_panic(expected = "no open subpath")]
1411 fn test_elements_to_segments_starts_on_closepath() {
1412 let mut path = BezPath::new();
1413 path.close_path();
1414 path.segments().next();
1415 }
1416
1417 #[test]
1418 fn test_elements_to_segments_closepath_refers_to_last_moveto() {
1419 let mut path = BezPath::new();
1420 path.move_to((5.0, 5.0));
1421 path.line_to((15.0, 15.0));
1422 path.move_to((10.0, 10.0));
1423 path.line_to((15.0, 15.0));
1424 path.close_path();
1425 assert_eq!(
1426 path.segments().collect::<Vec<_>>().last(),
1427 Some(&Line::new((15.0, 15.0), (10.0, 10.0)).into()),
1428 );
1429 }
1430
1431 #[test]
1432 #[should_panic(expected = "no open subpath")]
1433 fn test_must_not_start_on_quad() {
1434 let mut path = BezPath::new();
1435 path.quad_to((5.0, 5.0), (10.0, 10.0));
1436 path.line_to((15.0, 15.0));
1437 path.close_path();
1438 }
1439
1440 #[test]
1441 fn test_intersect_line() {
1442 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1443 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1444 let intersection = PathSeg::Line(h_line).intersect_line(v_line)[0];
1445 assert_approx_eq(intersection.segment_t, 0.1);
1446 assert_approx_eq(intersection.line_t, 0.5);
1447
1448 let v_line = Line::new((-10.0, -10.0), (-10.0, 10.0));
1449 assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
1450
1451 let v_line = Line::new((10.0, 10.0), (10.0, 20.0));
1452 assert!(PathSeg::Line(h_line).intersect_line(v_line).is_empty());
1453 }
1454
1455 #[test]
1456 fn test_intersect_qad() {
1457 let q = QuadBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -10.0));
1458 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1459 assert_eq!(PathSeg::Quad(q).intersect_line(v_line).len(), 1);
1460 let intersection = PathSeg::Quad(q).intersect_line(v_line)[0];
1461 assert_approx_eq(intersection.segment_t, 0.5);
1462 assert_approx_eq(intersection.line_t, 0.75);
1463
1464 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1465 assert_eq!(PathSeg::Quad(q).intersect_line(h_line).len(), 2);
1466 }
1467
1468 #[test]
1469 fn test_intersect_cubic() {
1470 let c = CubicBez::new((0.0, -10.0), (10.0, 20.0), (20.0, -20.0), (30.0, 10.0));
1471 let v_line = Line::new((10.0, -10.0), (10.0, 10.0));
1472 assert_eq!(PathSeg::Cubic(c).intersect_line(v_line).len(), 1);
1473 let intersection = PathSeg::Cubic(c).intersect_line(v_line)[0];
1474 assert_approx_eq(intersection.segment_t, 0.333333333);
1475 assert_approx_eq(intersection.line_t, 0.592592592);
1476
1477 let h_line = Line::new((0.0, 0.0), (100.0, 0.0));
1478 assert_eq!(PathSeg::Cubic(c).intersect_line(h_line).len(), 3);
1479 }
1480
1481 #[test]
1482 fn test_contains() {
1483 let mut path = BezPath::new();
1484 path.move_to((0.0, 0.0));
1485 path.line_to((1.0, 1.0));
1486 path.line_to((2.0, 0.0));
1487 path.close_path();
1488 assert_eq!(path.winding(Point::new(1.0, 0.5)), -1);
1489 assert!(path.contains(Point::new(1.0, 0.5)));
1490 }
1491
1492 // get_seg(i) should produce the same results as path_segments().nth(i - 1).
1493 #[test]
1494 fn test_get_seg() {
1495 let circle = Circle::new((10.0, 10.0), 2.0).to_path(DEFAULT_ACCURACY);
1496 let segments = circle.path_segments(DEFAULT_ACCURACY).collect::<Vec<_>>();
1497 let get_segs = (1..usize::MAX)
1498 .map_while(|i| circle.get_seg(i))
1499 .collect::<Vec<_>>();
1500 assert_eq!(segments, get_segs);
1501 }
1502}
1503