/rust/registry/src/index.crates.io-1949cf8c6b5b557f/kurbo-0.12.0/src/param_curve.rs

Source
// Copyright 2018 the Kurbo Authors
// SPDX-License-Identifier: Apache-2.0 OR MIT

//! A trait for curves parameterized by a scalar.

use core::ops::Range;

use arrayvec::ArrayVec;

use crate::{common, Point, Rect};

#[cfg(not(feature = "std"))]
use crate::common::FloatFuncs;

/// A default value for methods that take an 'accuracy' argument.
///
/// This value is intended to be suitable for general-purpose use, such as
/// 2d graphics.
pub const DEFAULT_ACCURACY: f64 = 1e-6;

/// A curve parameterized by a scalar.
///
/// If the result is interpreted as a point, this represents a curve.
/// But the result can be interpreted as a vector as well.
pub trait ParamCurve: Sized {
    /// Evaluate the curve at parameter `t`.
    ///
    /// Generally `t` is in the range [0..1].
    fn eval(&self, t: f64) -> Point;

    /// Get a subsegment of the curve for the given parameter range.
    fn subsegment(&self, range: Range<f64>) -> Self;

    /// Subdivide into (roughly) halves.
    #[inline]
    fn subdivide(&self) -> (Self, Self) {
        (self.subsegment(0.0..0.5), self.subsegment(0.5..1.0))
    }

    /// The start point.
    fn start(&self) -> Point {
        self.eval(0.0)
    }

    /// The end point.
    fn end(&self) -> Point {
        self.eval(1.0)
    }
}

// TODO: I might not want to have separate traits for all these.

/// A differentiable parameterized curve.
pub trait ParamCurveDeriv {
    /// The parametric curve obtained by taking the derivative of this one.
    type DerivResult: ParamCurve;

    /// The derivative of the curve.
    ///
    /// Note that the type of the return value is somewhat inaccurate, as
    /// the derivative of a curve (mapping of param to point) is a mapping
    /// of param to vector. We choose to accept this rather than have a
    /// more complex type scheme.
    fn deriv(&self) -> Self::DerivResult;

    /// Estimate arclength using Gaussian quadrature.
    ///
    /// The coefficients are assumed to cover the range (-1..1), which is
    /// traditional.
    #[inline]
    fn gauss_arclen(&self, coeffs: &[(f64, f64)]) -> f64 {
        let d = self.deriv();
        coeffs
            .iter()
            .map(|(wi, xi)| wi * d.eval(0.5 * (xi + 1.0)).to_vec2().hypot())
            .sum::<f64>()
            * 0.5
    }
}

/// A parameterized curve that can have its arc length measured.
pub trait ParamCurveArclen: ParamCurve {
    /// The arc length of the curve.
    ///
    /// The result is accurate to the given accuracy (subject to
    /// roundoff errors for ridiculously low values). Compute time
    /// may vary with accuracy, if the curve needs to be subdivided.
    fn arclen(&self, accuracy: f64) -> f64;

    /// Solve for the parameter that has the given arc length from the start.
    ///
    /// This implementation uses the IPT method, as provided by
    /// [`common::solve_itp`]. This is as robust as bisection but
    /// typically converges faster. In addition, the method takes
    /// care to compute arc lengths of increasingly smaller segments
    /// of the curve, as that is likely faster than repeatedly
    /// computing the arc length of the segment starting at t=0.
    fn inv_arclen(&self, arclen: f64, accuracy: f64) -> f64 {
        if arclen <= 0.0 {
            return 0.0;
        }
        let total_arclen = self.arclen(accuracy);
        if arclen >= total_arclen {
            return 1.0;
        }
        let mut t_last = 0.0;
        let mut arclen_last = 0.0;
        let epsilon = accuracy / total_arclen;
        let n = 1.0 - epsilon.log2().ceil().min(0.0);
        let inner_accuracy = accuracy / n;
        let f = |t: f64| {
            let (range, dir) = if t > t_last {
                (t_last..t, 1.0)
            } else {
                (t..t_last, -1.0)
            };
            let arc = self.subsegment(range).arclen(inner_accuracy);
            arclen_last += arc * dir;
            t_last = t;
            arclen_last - arclen
        };
        common::solve_itp(f, 0.0, 1.0, epsilon, 1, 0.2, -arclen, total_arclen - arclen)
    }
}

/// A parameterized curve that can have its signed area measured.
pub trait ParamCurveArea {
    /// Compute the signed area under the curve.
    ///
    /// For a closed path, the signed area of the path is the sum of signed
    /// areas of the segments. This is a variant of the "shoelace formula."
    /// See:
    /// <https://github.com/Pomax/bezierinfo/issues/44> and
    /// <http://ich.deanmcnamee.com/graphics/2016/03/30/CurveArea.html>
    ///
    /// This can be computed exactly for Béziers thanks to Green's theorem,
    /// and also for simple curves such as circular arcs. For more exotic
    /// curves, it's probably best to subdivide to cubics. We leave that
    /// to the caller, which is why we don't give an accuracy param here.
    fn signed_area(&self) -> f64;
}

/// The nearest position on a curve to some point.
///
/// This is returned by [`ParamCurveNearest::nearest`]
#[derive(Debug, Clone, Copy)]
pub struct Nearest {
    /// The square of the distance from the nearest position on the curve
    /// to the given point.
    pub distance_sq: f64,
    /// The position on the curve of the nearest point, as a parameter.
    ///
    /// To resolve this to a [`Point`], use [`ParamCurve::eval`].
    pub t: f64,
}

/// A parameterized curve that reports the nearest point.
pub trait ParamCurveNearest {
    /// Find the position on the curve that is nearest to the given point.
    ///
    /// This returns a [`Nearest`] struct that contains information about
    /// the position.
    fn nearest(&self, p: Point, accuracy: f64) -> Nearest;
}

/// A parameterized curve that reports its curvature.
pub trait ParamCurveCurvature: ParamCurveDeriv
where
    Self::DerivResult: ParamCurveDeriv,
{
    /// Compute the signed curvature at parameter `t`.
    #[inline]
    fn curvature(&self, t: f64) -> f64 {
        let deriv = self.deriv();
        let deriv2 = deriv.deriv();
        let d = deriv.eval(t).to_vec2();
        let d2 = deriv2.eval(t).to_vec2();
        // TODO: What's the convention for sign? I think it should match signed
        // area - a positive area curve should have positive curvature.
        d2.cross(d) * d.hypot2().powf(-1.5)
    }
}

/// The maximum number of extrema that can be reported in the `ParamCurveExtrema` trait.
///
/// This is 4 to support cubic Béziers. If other curves are used, they should be
/// subdivided to limit the number of extrema.
pub const MAX_EXTREMA: usize = 4;

/// A parameterized curve that reports its extrema.
pub trait ParamCurveExtrema: ParamCurve {
    /// Compute the extrema of the curve.
    ///
    /// Only extrema within the interior of the curve count.
    /// At most four extrema can be reported, which is sufficient for
    /// cubic Béziers.
    ///
    /// The extrema should be reported in increasing parameter order.
    fn extrema(&self) -> ArrayVec<f64, MAX_EXTREMA>;

    /// Return parameter ranges, each of which is monotonic within the range.
    fn extrema_ranges(&self) -> ArrayVec<Range<f64>, { MAX_EXTREMA + 1 }> {
        let mut result = ArrayVec::new();
        let mut t0 = 0.0;
        for t in self.extrema() {
            result.push(t0..t);
            t0 = t;
        }
        result.push(t0..1.0);
        result
    }

    /// The smallest rectangle that encloses the curve in the range (0..1).
    fn bounding_box(&self) -> Rect {
        let mut bbox = Rect::from_points(self.start(), self.end());
        for t in self.extrema() {
            bbox = bbox.union_pt(self.eval(t));
        }
        bbox
    }
}

Coverage Report

Created: 2025-09-27 07:40

Line	Count	Source
1		// Copyright 2018 the Kurbo Authors
2		// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4		//! A trait for curves parameterized by a scalar.
5
6		use core::ops::Range;
7
8		use arrayvec::ArrayVec;
9
10		use crate::{common, Point, Rect};
11
12		#[cfg(not(feature = "std"))]
13		use crate::common::FloatFuncs;
14
15		/// A default value for methods that take an 'accuracy' argument.
16		///
17		/// This value is intended to be suitable for general-purpose use, such as
18		/// 2d graphics.
19		pub const DEFAULT_ACCURACY: f64 = 1e-6;
20
21		/// A curve parameterized by a scalar.
22		///
23		/// If the result is interpreted as a point, this represents a curve.
24		/// But the result can be interpreted as a vector as well.
25		pub trait ParamCurve: Sized {
26		/// Evaluate the curve at parameter `t`.
27		///
28		/// Generally `t` is in the range [0..1].
29		fn eval(&self, t: f64) -> Point;
30
31		/// Get a subsegment of the curve for the given parameter range.
32		fn subsegment(&self, range: Range<f64>) -> Self;
33
34		/// Subdivide into (roughly) halves.
35		#[inline]
36	0	fn subdivide(&self) -> (Self, Self) {
37	0	(self.subsegment(0.0..0.5), self.subsegment(0.5..1.0))
38	0	}
39
40		/// The start point.
41	0	fn start(&self) -> Point {
42	0	self.eval(0.0)
43	0	}
44
45		/// The end point.
46	0	fn end(&self) -> Point {
47	0	self.eval(1.0)
48	0	}
49		}
50
51		// TODO: I might not want to have separate traits for all these.
52
53		/// A differentiable parameterized curve.
54		pub trait ParamCurveDeriv {
55		/// The parametric curve obtained by taking the derivative of this one.
56		type DerivResult: ParamCurve;
57
58		/// The derivative of the curve.
59		///
60		/// Note that the type of the return value is somewhat inaccurate, as
61		/// the derivative of a curve (mapping of param to point) is a mapping
62		/// of param to vector. We choose to accept this rather than have a
63		/// more complex type scheme.
64		fn deriv(&self) -> Self::DerivResult;
65
66		/// Estimate arclength using Gaussian quadrature.
67		///
68		/// The coefficients are assumed to cover the range (-1..1), which is
69		/// traditional.
70		#[inline]
71	0	fn gauss_arclen(&self, coeffs: &[(f64, f64)]) -> f64 {
72	0	let d = self.deriv();
73	0	coeffs
74	0	.iter()
75	0	.map(\|(wi, xi)\| wi * d.eval(0.5 * (xi + 1.0)).to_vec2().hypot())
76	0	.sum::<f64>()
77		* 0.5
78	0	}
79		}
80
81		/// A parameterized curve that can have its arc length measured.
82		pub trait ParamCurveArclen: ParamCurve {
83		/// The arc length of the curve.
84		///
85		/// The result is accurate to the given accuracy (subject to
86		/// roundoff errors for ridiculously low values). Compute time
87		/// may vary with accuracy, if the curve needs to be subdivided.
88		fn arclen(&self, accuracy: f64) -> f64;
89
90		/// Solve for the parameter that has the given arc length from the start.
91		///
92		/// This implementation uses the IPT method, as provided by
93		/// [`common::solve_itp`]. This is as robust as bisection but
94		/// typically converges faster. In addition, the method takes
95		/// care to compute arc lengths of increasingly smaller segments
96		/// of the curve, as that is likely faster than repeatedly
97		/// computing the arc length of the segment starting at t=0.
98	0	fn inv_arclen(&self, arclen: f64, accuracy: f64) -> f64 {
99	0	if arclen <= 0.0 {
100	0	return 0.0;
101	0	}
102	0	let total_arclen = self.arclen(accuracy);
103	0	if arclen >= total_arclen {
104	0	return 1.0;
105	0	}
106	0	let mut t_last = 0.0;
107	0	let mut arclen_last = 0.0;
108	0	let epsilon = accuracy / total_arclen;
109	0	let n = 1.0 - epsilon.log2().ceil().min(0.0);
110	0	let inner_accuracy = accuracy / n;
111	0	let f = \|t: f64\| {
112	0	let (range, dir) = if t > t_last {
113	0	(t_last..t, 1.0)
114		} else {
115	0	(t..t_last, -1.0)
116		};
117	0	let arc = self.subsegment(range).arclen(inner_accuracy);
118	0	arclen_last += arc * dir;
119	0	t_last = t;
120	0	arclen_last - arclen
121	0	}; Unexecuted instantiation: <kurbo::quadbez::QuadBez as kurbo::param_curve::ParamCurveArclen>::inv_arclen::{closure#0} Unexecuted instantiation: <kurbo::cubicbez::CubicBez as kurbo::param_curve::ParamCurveArclen>::inv_arclen::{closure#0}
122	0	common::solve_itp(f, 0.0, 1.0, epsilon, 1, 0.2, -arclen, total_arclen - arclen)
123	0	} Unexecuted instantiation: <kurbo::cubicbez::CubicBez as kurbo::param_curve::ParamCurveArclen>::inv_arclen Unexecuted instantiation: <kurbo::quadbez::QuadBez as kurbo::param_curve::ParamCurveArclen>::inv_arclen
124		}
125
126		/// A parameterized curve that can have its signed area measured.
127		pub trait ParamCurveArea {
128		/// Compute the signed area under the curve.
129		///
130		/// For a closed path, the signed area of the path is the sum of signed
131		/// areas of the segments. This is a variant of the "shoelace formula."
132		/// See:
133		/// <https://github.com/Pomax/bezierinfo/issues/44> and
134		/// <http://ich.deanmcnamee.com/graphics/2016/03/30/CurveArea.html>
135		///
136		/// This can be computed exactly for Béziers thanks to Green's theorem,
137		/// and also for simple curves such as circular arcs. For more exotic
138		/// curves, it's probably best to subdivide to cubics. We leave that
139		/// to the caller, which is why we don't give an accuracy param here.
140		fn signed_area(&self) -> f64;
141		}
142
143		/// The nearest position on a curve to some point.
144		///
145		/// This is returned by [`ParamCurveNearest::nearest`]
146		#[derive(Debug, Clone, Copy)]
147		pub struct Nearest {
148		/// The square of the distance from the nearest position on the curve
149		/// to the given point.
150		pub distance_sq: f64,
151		/// The position on the curve of the nearest point, as a parameter.
152		///
153		/// To resolve this to a [`Point`], use [`ParamCurve::eval`].
154		pub t: f64,
155		}
156
157		/// A parameterized curve that reports the nearest point.
158		pub trait ParamCurveNearest {
159		/// Find the position on the curve that is nearest to the given point.
160		///
161		/// This returns a [`Nearest`] struct that contains information about
162		/// the position.
163		fn nearest(&self, p: Point, accuracy: f64) -> Nearest;
164		}
165
166		/// A parameterized curve that reports its curvature.
167		pub trait ParamCurveCurvature: ParamCurveDeriv
168		where
169		Self::DerivResult: ParamCurveDeriv,
170		{
171		/// Compute the signed curvature at parameter `t`.
172		#[inline]
173	0	fn curvature(&self, t: f64) -> f64 {
174	0	let deriv = self.deriv();
175	0	let deriv2 = deriv.deriv();
176	0	let d = deriv.eval(t).to_vec2();
177	0	let d2 = deriv2.eval(t).to_vec2();
178		// TODO: What's the convention for sign? I think it should match signed
179		// area - a positive area curve should have positive curvature.
180	0	d2.cross(d) * d.hypot2().powf(-1.5)
181	0	}
182		}
183
184		/// The maximum number of extrema that can be reported in the `ParamCurveExtrema` trait.
185		///
186		/// This is 4 to support cubic Béziers. If other curves are used, they should be
187		/// subdivided to limit the number of extrema.
188		pub const MAX_EXTREMA: usize = 4;
189
190		/// A parameterized curve that reports its extrema.
191		pub trait ParamCurveExtrema: ParamCurve {
192		/// Compute the extrema of the curve.
193		///
194		/// Only extrema within the interior of the curve count.
195		/// At most four extrema can be reported, which is sufficient for
196		/// cubic Béziers.
197		///
198		/// The extrema should be reported in increasing parameter order.
199		fn extrema(&self) -> ArrayVec<f64, MAX_EXTREMA>;
200
201		/// Return parameter ranges, each of which is monotonic within the range.
202	0	fn extrema_ranges(&self) -> ArrayVec<Range<f64>, { MAX_EXTREMA + 1 }> {
203	0	let mut result = ArrayVec::new();
204	0	let mut t0 = 0.0;
205	0	for t in self.extrema() {
206	0	result.push(t0..t);
207	0	t0 = t;
208	0	}
209	0	result.push(t0..1.0);
210	0	result
211	0	}
212
213		/// The smallest rectangle that encloses the curve in the range (0..1).
214	0	fn bounding_box(&self) -> Rect {
215	0	let mut bbox = Rect::from_points(self.start(), self.end());
216	0	for t in self.extrema() {
217	0	bbox = bbox.union_pt(self.eval(t));
218	0	}
219	0	bbox
220	0	}
221		}