1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218

//! A trait for curves parametrized by a scalar. use std::ops::Range; use arrayvec::ArrayVec; use crate::{Point, Rect}; /// 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 parametrized 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 parametrized 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 parametrized 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 arclength from the start. /// /// This implementation is bisection, which is very robust but not /// necessarily the fastest. It does measure increasingly short /// segments, though, which should be good for subdivision algorithms. fn inv_arclen(&self, arclen: f64, accuracy: f64) -> f64 { // invariant: the curve's arclen on [0..t_last] + remaining = arclen let mut remaining = arclen; let mut t_last = 0.0; let mut t0 = 0.0; let mut t1 = 1.0; let n = (self.arclen(accuracy) / accuracy).log2().ceil().max(1.0); let inner_accuracy = accuracy / n; let n = n as usize; for i in 0..n { let tm = 0.5 * (t0 + t1); let (range, dir) = if tm > t_last { (t_last..tm, 1.0) } else { (tm..t_last, -1.0) }; let range_size = range.end - range.start; let arc = self.subsegment(range).arclen(inner_accuracy); remaining -= arc * dir; if i == n - 1 || (remaining).abs() < accuracy { // Allocate remaining arc evenly. return tm + range_size * remaining / arc; } if remaining > 0.0 { t0 = tm; } else { t1 = tm; } t_last = tm; } unreachable!(); } } /// A parametrized 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 parametrized 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 parametrized 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 parametrized 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 } }