a770fa5a5e5f
spline_fit.rs
//! Fit-point splines: knot parametrisation (chord, square root, uniform), end tangents and fit
//! tolerance (least-squares approximation with fewer control points), as `AutoCAD`'s SPLINE Fit
//! method offers them. Construction follows the textbook global interpolation and approximation
//! schemes (Piegl & Tiller, *The NURBS Book*, ch. 9).
use serde::{Deserialize, Serialize};
use crate::spline::{basis, find_span, solve};
use crate::{Mat3, Spline, Vec2};
/// How fit points are spaced in parameter space (the SPLINE `Knots` option).
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
pub enum KnotParam {
/// Proportional to the distance between fit points.
#[default]
Chord,
/// Proportional to the square root of the distance ("centripetal").
SqrtChord,
/// Equal steps whatever the distance.
Uniform,
}
impl KnotParam {
pub const ALL: [KnotParam; 3] = [KnotParam::Chord, KnotParam::SqrtChord, KnotParam::Uniform];
/// The name as the prompt and the "Current settings" line show it.
pub fn name(self) -> &'static str {
match self {
KnotParam::Chord => "Chord",
KnotParam::SqrtChord => "Square root",
KnotParam::Uniform => "Uniform",
}
}
/// Parse a keyword or JSON value ("chord", "sqrt", "square root", "uniform", or 0/1/2 as in
/// the SPLKNOTS setting).
pub fn parse(s: &str) -> Option<KnotParam> {
Some(match s.trim().to_ascii_lowercase().as_str() {
"c" | "chord" | "0" => KnotParam::Chord,
"s" | "sqrt" | "square root" | "squareroot" | "centripetal" | "1" => KnotParam::SqrtChord,
"u" | "uniform" | "2" => KnotParam::Uniform,
_ => return None,
})
}
/// The SPLKNOTS code (0 chord, 1 square root, 2 uniform).
pub fn code(self) -> i64 {
match self {
KnotParam::Chord => 0,
KnotParam::SqrtChord => 1,
KnotParam::Uniform => 2,
}
}
fn step(self, d: f64) -> f64 {
match self {
KnotParam::Chord => d.max(1e-12),
KnotParam::SqrtChord => d.sqrt().max(1e-12),
KnotParam::Uniform => 1.0,
}
}
}
/// How a spline is built from its fit points. The default interpolates with chord-length
/// parameters and free ends.
#[derive(Clone, Copy, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct FitOptions {
#[serde(default)]
pub knots: KnotParam,
/// Unit tangent direction at the first fit point; `None` lets the end follow the points.
#[serde(default)]
pub start_tangent: Option<Vec2>,
/// Unit tangent direction at the last fit point.
#[serde(default)]
pub end_tangent: Option<Vec2>,
/// Largest allowed distance between the curve and a fit point; 0 passes through them.
#[serde(default)]
pub tolerance: f64,
}
impl FitOptions {
/// Normalised tangents (zero or non-finite directions dropped) and a finite, non-negative
/// tolerance: what a spline stores.
pub fn sanitized(self) -> FitOptions {
let dir = |t: Option<Vec2>| t.filter(|v| v.x.is_finite() && v.y.is_finite() && v.len() > 1e-12).map(Vec2::normalized);
FitOptions {
knots: self.knots,
start_tangent: dir(self.start_tangent),
end_tangent: dir(self.end_tangent),
tolerance: if self.tolerance.is_finite() { self.tolerance.max(0.0) } else { 0.0 },
}
}
}
/// Fit points above this count are always interpolated: the approximation search solves dense
/// systems the size of the point count several times.
const MAX_APPROX_POINTS: usize = 300;
/// Fit points above this count are not interpolated: interpolation solves a dense system the size
/// of the point count squared (twice, about 270 MB at this size), so more points use them as
/// control points instead. Above the 4,001 fit points of a 500-turn helix.
const MAX_INTERP_POINTS: usize = 4_096;
impl Spline {
/// Build a spline through (or, with a tolerance, near) `fit`, open or closed. Closed curves
/// are periodic and ignore end tangents; a tolerance approximates them with fewer periodic
/// control points. A fit point given twice in a row is a kink (SPLINEDIT Fit data Kink): the
/// curve passes through it with a corner (a knot of full multiplicity) and the pieces on
/// either side are fitted on their own.
pub fn fit_with(fit: &[Vec2], closed: bool, opts: FitOptions) -> Spline {
let opts = opts.sanitized();
let kinked = if fit.len() <= MAX_KINK_POINTS { kinked_fit(fit, closed, opts) } else { None };
let mut s = if let Some(s) = kinked {
s
} else {
// Repeats at the ends of an open curve are no corners: fit without them.
let (pts, _) = kinks(fit, false);
let mut s = if closed { closed_fit(&pts, opts.knots, opts.tolerance) } else { open_fit(&pts, opts) };
if pts.len() != fit.len() && !closed {
s.fit = fit.to_vec();
}
s
};
s.fit_opts = if closed { FitOptions { start_tangent: None, end_tangent: None, ..opts } } else { opts };
s
}
/// Rebuild from new fit points with this spline's knot parametrisation, tangents and tolerance.
pub fn refit(&self, fit: &[Vec2], closed: bool) -> Spline {
Spline::fit_with(fit, closed, self.fit_opts)
}
/// Which knot parametrisation produced this spline's knots from its fit points (DXF files
/// keep the knots but not the parametrisation). Compares knot vectors only (no solving), so
/// it is cheap for any number of fit points. Chord when nothing matches.
pub fn infer_knot_param(&self) -> KnotParam {
if self.fit.len() < 3 {
return self.fit_opts.knots;
}
let (Some(k0), Some(k1)) = (self.knots.get(self.degree), self.knots.get(self.control.len())) else { return KnotParam::Chord };
if !(k1 - k0).is_finite() || k1 - k0 <= 1e-300 {
return KnotParam::Chord;
}
let norm: Vec<f64> = self.knots.iter().map(|k| (k - k0) / (k1 - k0)).collect();
let close = |a: f64, b: f64| (a - b).abs() < 1e-6;
let same = |k: &[f64]| k.len() == norm.len() && k.iter().zip(&norm).all(|(a, b)| close(*a, *b));
let p = self.degree;
let o = &self.fit_opts;
KnotParam::ALL
.into_iter()
.find(|kind| {
if self.closed {
// Our periodic knots run from the parameter of fit point 0 (at 0) to 1.
let mut pts = self.fit.clone();
if pts.len() > 3 && pts.first().zip(pts.last()).is_some_and(|(a, b)| a.near(*b, 1e-12)) {
pts.pop();
}
let t = params(&pts, *kind, true);
let pk = periodic_knots(&t, pts.len(), p);
if same(&pk) {
return true;
}
}
let u = params(&self.fit, *kind, self.closed);
if !self.closed {
if same(&interp_knots(&u, o.start_tangent.is_some(), o.end_tangent.is_some()).1) {
return true;
}
let m = self.control.len();
if p < m && m < u.len() && same(&lsq_knots(&u, m, p)) {
return true;
}
}
// Other writers use the parameters themselves as interior knots. Both `u` and
// `norm` are ascending, so a single linear merge decides containment instead of
// re-scanning `norm` from the start for every parameter, which is quadratic on an
// otherwise valid spline (CWE-407).
if u.len() <= 2 {
return false;
}
let interior = u.get(1..u.len() - 1).unwrap_or(&[]);
let mut j = 0usize;
interior.iter().all(|q| {
while j < norm.len() && norm[j] < *q && !close(norm[j], *q) {
j += 1;
}
norm.get(j).is_some_and(|k| close(*k, *q))
})
})
.unwrap_or(KnotParam::Chord)
}
/// Apply an affine map to the control and fit points and turn the end tangents with it.
pub fn transform(&mut self, m: &Mat3) {
for c in self.control.iter_mut().chain(self.fit.iter_mut()) {
*c = m.apply(*c);
}
let turn = |t: Option<Vec2>| t.map(|v| m.apply_vec(v).normalized()).filter(|v| v.len() > 0.5);
self.fit_opts.start_tangent = turn(self.fit_opts.start_tangent);
self.fit_opts.end_tangent = turn(self.fit_opts.end_tangent);
}
}
/// Normalised parameters of the fit points: `n` values for an open curve, `n + 1` for a closed
/// one (the last is the return to the first point).
pub(crate) fn params(pts: &[Vec2], kind: KnotParam, closed: bool) -> Vec<f64> {
let n = pts.len();
let count = if closed { n + 1 } else { n };
let mut u = vec![0.0; count];
let mut total = 0.0;
for i in 1..count {
total += pts.get(i - 1).zip(pts.get(i % n.max(1))).map_or(1.0, |(a, b)| kind.step(a.dist(*b)));
if let Some(x) = u.get_mut(i) {
*x = total;
}
}
for x in &mut u {
*x /= total.max(1e-300);
}
u
}
fn chord_length(pts: &[Vec2]) -> f64 {
pts.windows(2).map(|w| w.first().zip(w.get(1)).map_or(0.0, |(a, b)| a.dist(*b))).sum()
}
fn open_fit(fit: &[Vec2], opts: FitOptions) -> Spline {
let n = fit.len();
let tangents = opts.start_tangent.is_some() || opts.end_tangent.is_some();
if n < 2 || (n == 2 && !tangents) {
let mut s = if n < 2 {
Spline { degree: 1, knots: vec![0.0, 0.0, 1.0, 1.0], control: fit.to_vec(), ..Spline::default() }
} else {
Spline::from_control(fit.to_vec(), 1)
};
s.fit = fit.to_vec();
return s;
}
let u = params(fit, opts.knots, false);
// Tangents are directions; the derivative's length is the curve length in parameter space.
let len = chord_length(fit).max(1e-12);
let d0 = opts.start_tangent.map(|t| t * len);
let d1 = opts.end_tangent.map(|t| t * len);
if opts.tolerance > 0.0
&& n <= MAX_APPROX_POINTS
&& let Some(s) = approximate(fit, &u, d0, d1, opts.tolerance)
{
return s;
}
let through_control = || {
let mut s = Spline::from_control(fit.to_vec(), 3.min(n - 1));
s.fit = fit.to_vec();
s
};
if n > MAX_INTERP_POINTS {
return through_control();
}
interpolate(fit, &u, d0, d1).unwrap_or_else(through_control)
}
/// Global interpolation: one control point per fit point plus one per end-derivative
/// constraint, knots by averaging the parameters (an end with a derivative counts its
/// parameter twice).
#[expect(
clippy::cast_precision_loss,
clippy::many_single_char_names,
reason = "Interpolation uses NURBS matrix notation, and its degree is capped at three, so p is exact as f64."
)]
fn interpolate(fit: &[Vec2], u: &[f64], d0: Option<Vec2>, d1: Option<Vec2>) -> Option<Spline> {
let (p, knots) = interp_knots(u, d0.is_some(), d1.is_some());
let m = knots.len().checked_sub(p + 1)?;
let mut a = vec![vec![0.0; m]; m];
let (mut xs, mut ys) = (vec![0.0; m], vec![0.0; m]);
let mut row = 0;
let mut put = |coeffs: &[(usize, f64)], rhs: Vec2, a: &mut Vec<Vec<f64>>| {
if let Some(r) = a.get_mut(row) {
for (j, v) in coeffs {
if let Some(c) = r.get_mut(*j) {
*c += *v;
}
}
}
if let (Some(x), Some(y)) = (xs.get_mut(row), ys.get_mut(row)) {
(*x, *y) = (rhs.x, rhs.y);
}
row += 1;
};
for (ui, q) in u.iter().zip(fit) {
let span = find_span(m - 1, p, *ui, &knots);
let coeffs: Vec<(usize, f64)> = basis(span, *ui, p, &knots).into_iter().enumerate().map(|(k, v)| (span + k - p, v)).collect();
put(&coeffs, *q, &mut a);
}
// Clamped ends: C'(0) = p / u_(p+1) (P1 - P0), C'(1) = p / (1 - u_(m-1)) (P_(m-1) - P_(m-2)).
if let Some(d) = d0 {
let c = p as f64 / knots.get(p + 1).copied().unwrap_or(1.0).max(1e-12);
put(&[(0, -c), (1, c)], d, &mut a);
}
if let Some(d) = d1 {
let c = p as f64 / (1.0 - knots.get(m - 1).copied().unwrap_or(0.0)).max(1e-12);
put(&[(m - 2, -c), (m - 1, c)], d, &mut a);
}
let (cx, cy) = (solve(a.clone(), xs)?, solve(a, ys)?);
let control: Vec<Vec2> = cx.into_iter().zip(cy).map(|(x, y)| Vec2::new(x, y)).collect();
if control.iter().any(|c| !c.x.is_finite() || !c.y.is_finite()) {
return None;
}
Some(Spline { degree: p, knots, control, fit: fit.to_vec(), ..Spline::default() })
}
/// Degree and clamped knots for interpolating at parameters `u`, with optional end derivatives:
/// knots average the parameters, an end with a derivative counting its parameter twice.
#[expect(clippy::cast_precision_loss, reason = "The interpolation degree is capped at three, so p is exact as f64.")]
fn interp_knots(u: &[f64], d0: bool, d1: bool) -> (usize, Vec<f64>) {
let m = u.len() + usize::from(d0) + usize::from(d1);
let p = 3.min(m.saturating_sub(1)).max(1);
let mut seq = Vec::with_capacity(m);
seq.extend(u.first().copied().filter(|_| d0));
seq.extend_from_slice(u);
seq.extend(u.last().copied().filter(|_| d1));
let mut knots = vec![0.0; p + 1];
for j in 1..m.saturating_sub(p) {
let s: f64 = (j..j + p).filter_map(|i| seq.get(i)).sum();
knots.push(s / p as f64);
}
knots.extend(std::iter::repeat_n(1.0, p + 1));
(p, knots)
}
/// Clamped knots for a least-squares fit with `m` control points of degree `p` so every span
/// holds parameters (The NURBS Book eq. 9.69). Needs `p < m < u.len()`.
#[expect(
clippy::cast_precision_loss,
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::many_single_char_names,
reason = "Fit sizes are bounded by MAX_APPROX_POINTS, knot indices are nonnegative and clamped, and the equations use NURBS Book notation."
)]
fn lsq_knots(u: &[f64], m: usize, p: usize) -> Vec<f64> {
let n = u.len();
let d = n as f64 / m.saturating_sub(p).max(1) as f64;
let mut knots = vec![0.0; p + 1];
for j in 1..m.saturating_sub(p) {
let jd = j as f64 * d;
let i = (jd.floor() as usize).clamp(1, n.saturating_sub(1).max(1));
let a = jd - i as f64;
knots.push((1.0 - a) * u.get(i - 1).copied().unwrap_or(0.0) + a * u.get(i).copied().unwrap_or(1.0));
}
knots.extend(std::iter::repeat_n(1.0, p + 1));
knots
}
/// Periodic knots for `n` points with closed parameters `t` (`n + 1` values): knots[j] =
/// t_(j-p), extended by whole periods on both sides.
#[expect(
clippy::cast_precision_loss,
clippy::cast_possible_wrap,
clippy::many_single_char_names,
reason = "Indices are bounded by slice lengths, period offsets are f64 by design, and the periodic equations use standard notation."
)]
fn periodic_knots(t: &[f64], n: usize, p: usize) -> Vec<f64> {
let tk = |i: isize| {
let (q, r) = (i.div_euclid(n.max(1) as isize), i.rem_euclid(n.max(1) as isize) as usize);
t.get(r).copied().unwrap_or(0.0) + q as f64
};
(0..=(n + 2 * p)).map(|j| tk(j as isize - p as isize)).collect()
}
/// Least-squares approximation within `tol`: the fewest control points (searched by bisection)
/// whose curve passes within `tol` of every fit point, the end points (and end tangents) kept
/// exact. `None` when only interpolation meets the tolerance.
fn approximate(fit: &[Vec2], u: &[f64], d0: Option<Vec2>, d1: Option<Vec2>, tol: f64) -> Option<Spline> {
let n = fit.len();
let p = 3;
// Fewer control points than fit points, or it is not an approximation.
let (mut lo, mut hi) = (p + 1, n.checked_sub(1)?);
let mut best = None;
while lo <= hi {
let mid = usize::midpoint(lo, hi);
match least_squares(fit, u, mid, p, d0, d1) {
Some(s) if max_deviation(&s, fit, u) <= tol => {
best = Some(s);
hi = mid - 1;
}
_ => lo = mid + 1,
}
}
best
}
fn max_deviation(s: &Spline, fit: &[Vec2], u: &[f64]) -> f64 {
fit.iter().zip(u).map(|(q, t)| s.eval(*t).dist(*q)).fold(0.0, f64::max)
}
#[expect(
clippy::cast_precision_loss,
clippy::many_single_char_names,
reason = "Open least-squares fitting is cubic and keeps the NURBS Book matrix notation, so p is exact as f64."
)]
fn least_squares(fit: &[Vec2], u: &[f64], m: usize, p: usize, d0: Option<Vec2>, d1: Option<Vec2>) -> Option<Spline> {
let n = fit.len();
if m <= p || m >= n {
return None;
}
let knots = lsq_knots(u, m, p);
let (first, last) = (*fit.first()?, *fit.last()?);
let mut fixed: Vec<Option<Vec2>> = vec![None; m];
let mut fix = |j: usize, q: Vec2| {
if let Some(f) = fixed.get_mut(j) {
*f = Some(q);
}
};
fix(0, first);
fix(m - 1, last);
// An end tangent fixes the neighbouring control point (clamped-end derivative).
if let Some(d) = d0 {
fix(1, first + d * (knots.get(p + 1).copied().unwrap_or(1.0) / p as f64));
}
if let Some(d) = d1 {
fix(m - 2, last - d * ((1.0 - knots.get(m - 1).copied().unwrap_or(0.0)) / p as f64));
}
let free: Vec<usize> = (0..m).filter(|j| fixed.get(*j).is_some_and(Option::is_none)).collect();
let k = free.len();
let mut a = vec![vec![0.0; k]; k];
let (mut bx, mut by) = (vec![0.0; k], vec![0.0; k]);
for (t, q) in u.iter().zip(fit).skip(1).take(n.saturating_sub(2)) {
let span = find_span(m - 1, p, *t, &knots);
let mut row = vec![0.0; m];
for (i, v) in basis(span, *t, p, &knots).into_iter().enumerate() {
if let Some(c) = row.get_mut(span + i - p) {
*c = v;
}
}
let mut r = *q;
for (j, c) in row.iter().enumerate() {
if let Some(Some(f)) = fixed.get(j) {
r -= *f * *c;
}
}
for (ri, &fi) in free.iter().enumerate() {
let ni = row.get(fi).copied().unwrap_or(0.0);
if ni == 0.0 {
continue;
}
if let (Some(x), Some(y)) = (bx.get_mut(ri), by.get_mut(ri)) {
*x += ni * r.x;
*y += ni * r.y;
}
for (ci, &fj) in free.iter().enumerate() {
if let Some(cell) = a.get_mut(ri).and_then(|rr| rr.get_mut(ci)) {
*cell += ni * row.get(fj).copied().unwrap_or(0.0);
}
}
}
}
let (cx, cy) = if k == 0 { (Vec::new(), Vec::new()) } else { (solve(a.clone(), bx)?, solve(a, by)?) };
let mut solved = free.iter().zip(cx.into_iter().zip(cy));
let control: Vec<Vec2> = fixed.into_iter().map(|f| f.or_else(|| solved.next().map(|(_, (x, y))| Vec2::new(x, y)))).collect::<Option<_>>()?;
if control.iter().any(|c| !c.x.is_finite() || !c.y.is_finite()) {
return None;
}
Some(Spline { degree: p, knots, control, fit: fit.to_vec(), ..Spline::default() })
}
/// Fit point counts above this ignore kinks (each piece is fitted and joined separately).
const MAX_KINK_POINTS: usize = 20_000;
/// Kink positions: `fit` with consecutive repeats removed and, per kept point, whether it was
/// repeated (a kink). A closed list's repeated closing point is not a kink.
fn kinks(fit: &[Vec2], closed: bool) -> (Vec<Vec2>, Vec<bool>) {
let mut pts: Vec<Vec2> = Vec::with_capacity(fit.len());
let mut kink: Vec<bool> = Vec::with_capacity(fit.len());
for q in fit {
if pts.last().is_some_and(|l| l.near(*q, 1e-12)) {
if let Some(k) = kink.last_mut() {
*k = true;
}
} else {
pts.push(*q);
kink.push(false);
}
}
if closed && pts.len() > 3 && pts.first().zip(pts.last()).is_some_and(|(a, b)| a.near(*b, 1e-12)) {
pts.pop();
let last = kink.pop().unwrap_or(false);
if let Some(k) = kink.first_mut() {
*k |= last;
}
}
(pts, kink)
}
/// A curve with corners at repeated fit points: each run between kinks is fitted open (the
/// outer ends keep the end tangents) and the cubic pieces are joined end to end. A closed curve
/// starts and ends at its first kink. `None` without kinks.
fn kinked_fit(fit: &[Vec2], closed: bool, opts: FitOptions) -> Option<Spline> {
let (mut pts, mut kink) = kinks(fit, closed);
let n = pts.len();
if n < 2 {
return None;
}
// Ends of an open curve are corners anyway, so only interior kinks count.
let interior = |i: usize| closed || (i > 0 && i + 1 < n);
let first = (0..n).find(|i| kink.get(*i).copied().unwrap_or(false) && interior(*i))?;
if closed {
pts.rotate_left(first);
kink.rotate_left(first);
pts.push(*pts.first()?);
kink.push(true);
}
let last = pts.len() - 1;
let mut pieces: Vec<Spline> = Vec::new();
let mut start = 0;
for i in 1..=last {
if i < last && !kink.get(i).copied().unwrap_or(false) {
continue;
}
let run = pts.get(start..=i)?;
let o = FitOptions {
start_tangent: if start == 0 && !closed { opts.start_tangent } else { None },
end_tangent: if i == last && !closed { opts.end_tangent } else { None },
..opts
};
pieces.push(cubic(open_fit(run, o))?);
start = i;
}
let lens: Vec<f64> = pieces.iter().map(|p| chord_length(&p.fit).max(1e-12)).collect();
let total: f64 = lens.iter().sum();
let p = 3;
let mut knots: Vec<f64> = Vec::new();
let mut control: Vec<Vec2> = Vec::new();
let mut at = 0.0;
let count = pieces.len();
for (j, (piece, len)) in pieces.iter().zip(&lens).enumerate() {
let (lo, hi) = piece.domain();
let scale = len / total.max(1e-300) / (hi - lo).max(1e-300);
let mapped = piece.knots.iter().map(|k| at + (k - lo) * scale);
let keep = piece.knots.len() - usize::from(j + 1 < count);
knots.extend(mapped.take(keep).skip(if j == 0 { 0 } else { p + 1 }));
control.extend(piece.control.iter().skip(usize::from(j > 0)).copied());
at += len / total.max(1e-300);
}
let s = Spline { degree: p, knots, control, fit: fit.to_vec(), closed, ..Spline::default() };
s.is_valid().then_some(s)
}
/// A clamped, non-rational fitted piece raised to degree 3: interpolation through two or three
/// points gives a single Bézier segment of lower degree, which is raised exactly.
#[expect(
clippy::cast_precision_loss,
clippy::many_single_char_names,
reason = "Degree elevation stops at three and keeps the Bézier coefficient notation, so all indices are exact as f64."
)]
fn cubic(mut s: Spline) -> Option<Spline> {
if s.degree == 3 {
return Some(s);
}
if s.degree > 3 || s.control.len() != s.degree + 1 {
return None;
}
let (lo, hi) = s.domain();
while s.degree < 3 {
let p = s.degree;
let c = &s.control;
let mut q = Vec::with_capacity(p + 2);
q.push(*c.first()?);
for i in 1..=p {
let a = i as f64 / (p + 1) as f64;
q.push(*c.get(i - 1)? * a + *c.get(i)? * (1.0 - a));
}
q.push(*c.last()?);
s.degree = p + 1;
s.control = q;
}
s.knots = [lo; 4].into_iter().chain([hi; 4]).collect();
Some(s)
}
/// Least-squares approximation of a closed curve within `tol`: the fewest periodic control
/// points (searched by bisection) whose curve passes within `tol` of every fit point. `None`
/// when only interpolation meets the tolerance.
fn approximate_closed(pts: &[Vec2], t: &[f64], p: usize, tol: f64) -> Option<Spline> {
let n = pts.len();
let (mut lo, mut hi) = (p + 1, n.checked_sub(1)?);
let mut best = None;
while lo <= hi {
let mid = usize::midpoint(lo, hi);
match periodic_least_squares(pts, t, mid, p) {
Some(s) if pts.iter().zip(t).all(|(q, u)| s.eval(*u).dist(*q) <= tol) => {
best = Some(s);
hi = mid - 1;
}
_ => lo = mid + 1,
}
}
best
}
/// A periodic spline with `m` distinct control points (`p < m < pts.len()`) closest in the
/// least-squares sense to `pts` at closed parameters `t`. The period's breakpoints spread over
/// the parameters so every span holds some (the closed counterpart of `lsq_knots`).
#[expect(
clippy::cast_precision_loss,
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::many_single_char_names,
reason = "Fit sizes are bounded by MAX_APPROX_POINTS, periodic indices are nonnegative and bounded, and the matrix equations use standard notation."
)]
fn periodic_least_squares(pts: &[Vec2], t: &[f64], m: usize, p: usize) -> Option<Spline> {
let n = pts.len();
if m <= p || m >= n || t.len() != n + 1 {
return None;
}
let mut b = Vec::with_capacity(m + 1);
for j in 0..=m {
let jd = j as f64 * n as f64 / m as f64;
let i = (jd.floor() as usize).min(n - 1);
let a = jd - i as f64;
b.push((1.0 - a) * t.get(i).copied()? + a * t.get(i + 1).copied()?);
}
if b.windows(2).any(|w| w.first().zip(w.get(1)).is_none_or(|(x, y)| y - x <= 1e-12)) {
return None;
}
let knots = periodic_knots(&b, m, p);
let mut a = vec![vec![0.0; m]; m];
let (mut bx, mut by) = (vec![0.0; m], vec![0.0; m]);
for (q, u) in pts.iter().zip(t) {
let span = find_span(m + p - 1, p, *u, &knots);
let mut row = vec![0.0; m];
for (k, v) in basis(span, *u, p, &knots).into_iter().enumerate() {
if let Some(c) = (span + k).checked_sub(p).and_then(|i| row.get_mut(i % m)) {
*c += v;
}
}
for (i, ri) in row.iter().enumerate() {
if *ri == 0.0 {
continue;
}
if let (Some(x), Some(y)) = (bx.get_mut(i), by.get_mut(i)) {
*x += ri * q.x;
*y += ri * q.y;
}
if let Some(ar) = a.get_mut(i) {
for (cell, rj) in ar.iter_mut().zip(&row) {
*cell += ri * rj;
}
}
}
}
let (cx, cy) = (solve(a.clone(), bx)?, solve(a, by)?);
let mut control: Vec<Vec2> = cx.into_iter().zip(cy).map(|(x, y)| Vec2::new(x, y)).collect();
if control.iter().any(|c| !c.x.is_finite() || !c.y.is_finite()) {
return None;
}
control.extend_from_within(..p);
Some(Spline { degree: p, knots, control, fit: pts.to_vec(), closed: true, ..Spline::default() })
}
#[expect(clippy::many_single_char_names, reason = "Closed interpolation keeps the NURBS Book parameter, degree and matrix notation.")]
fn closed_fit(fit: &[Vec2], kind: KnotParam, tol: f64) -> Spline {
let mut pts = fit.to_vec();
if pts.len() > 3 && pts.first().zip(pts.last()).is_some_and(|(a, b)| a.near(*b, 1e-12)) {
pts.pop();
}
let n = pts.len();
let fallback = |pts: &[Vec2]| {
let mut f = pts.to_vec();
f.extend(pts.first().copied());
let mut s = open_fit(&f, FitOptions { knots: kind, ..FitOptions::default() });
s.fit = pts.to_vec();
s.closed = true;
s
};
let p = 3;
// The open fallback runs through n + 1 points, so above the cap it does not interpolate.
if n < p || n > MAX_INTERP_POINTS {
return fallback(&pts);
}
// Parameters t_0 = 0 .. t_n = 1 (t_n is the return to the first point).
let t = params(&pts, kind, true);
if tol > 0.0
&& n <= MAX_APPROX_POINTS
&& let Some(s) = approximate_closed(&pts, &t, p, tol)
{
return s;
}
let m = n + p;
let knots = periodic_knots(&t, n, p);
// Interpolation at t_i; control index k and k + n are the same unknown.
let mut a = vec![vec![0.0; n]; n];
for (i, row) in a.iter_mut().enumerate() {
let u = t.get(i).copied().unwrap_or(0.0);
let span = find_span(m - 1, p, u, &knots);
for (k, v) in basis(span, u, p, &knots).iter().enumerate() {
if let Some(cell) = row.get_mut((span + k - p) % n) {
*cell += *v;
}
}
}
let xs: Vec<f64> = pts.iter().map(|q| q.x).collect();
let ys: Vec<f64> = pts.iter().map(|q| q.y).collect();
let (Some(cx), Some(cy)) = (solve(a.clone(), xs), solve(a, ys)) else { return fallback(&pts) };
let mut control: Vec<Vec2> = cx.into_iter().zip(cy).map(|(x, y)| Vec2::new(x, y)).collect();
if control.iter().any(|c| !c.x.is_finite() || !c.y.is_finite()) {
return fallback(&pts);
}
control.extend_from_within(..p);
Spline { degree: p, knots, control, fit: pts, closed: true, ..Spline::default() }
}
#[cfg(test)]
mod tests {
use super::*;
fn pts() -> Vec<Vec2> {
vec![Vec2::new(0.0, 0.0), Vec2::new(1.0, 0.2), Vec2::new(5.0, 3.0), Vec2::new(6.0, 3.1), Vec2::new(9.0, 0.0)]
}
fn passes_through(s: &Spline, fit: &[Vec2], tol: f64) -> bool {
let u = params(fit, s.fit_opts.knots, s.closed);
fit.iter().zip(&u).all(|(f, t)| s.eval(*t).dist(*f) < tol)
}
#[test]
fn default_options_match_the_plain_fit() {
let fit = pts();
assert_eq!(Spline::fit_with(&fit, false, FitOptions::default()), Spline::from_fit_points(&fit));
assert_eq!(Spline::fit_with(&fit, true, FitOptions::default()), Spline::from_fit_points_closed(&fit));
}
#[test]
fn knot_parametrisations_differ_and_still_interpolate() {
let fit = pts();
let knots: Vec<Vec<f64>> = KnotParam::ALL
.iter()
.map(|k| {
let s = Spline::fit_with(&fit, false, FitOptions { knots: *k, ..FitOptions::default() });
assert!(s.is_valid() && passes_through(&s, &fit, 1e-3), "{k:?}");
assert_eq!(s.fit_opts.knots, *k);
assert_eq!(s.infer_knot_param(), *k, "the knots identify the parametrisation");
s.knots
})
.collect();
assert!(knots[0] != knots[1] && knots[1] != knots[2] && knots[0] != knots[2]);
// Uniform: equally spaced parameters, so the interior knots are 1/2 (five points, cubic).
assert!(knots[2].iter().any(|k| (k - 0.5).abs() < 1e-12));
for k in KnotParam::ALL {
let s = Spline::fit_with(&fit, true, FitOptions { knots: k, ..FitOptions::default() });
assert!(s.is_valid() && s.is_periodic() && passes_through(&s, &fit, 1e-3), "closed {k:?}");
assert_eq!(s.infer_knot_param(), k);
}
}
#[test]
fn end_tangents_set_the_end_directions() {
let fit = pts();
let opts = FitOptions { start_tangent: Some(Vec2::new(0.0, 2.0)), end_tangent: Some(Vec2::new(1.0, -1.0)), ..FitOptions::default() };
let s = Spline::fit_with(&fit, false, opts);
assert!(s.is_valid() && passes_through(&s, &fit, 1e-3));
assert_eq!(s.control.len(), fit.len() + 2);
assert_eq!(s.fit_opts.start_tangent, Some(Vec2::new(0.0, 1.0)), "stored as a unit vector");
let (lo, hi) = s.domain();
let h = 1e-7;
let start = (s.eval(lo + h) - s.eval(lo)).normalized();
let end = (s.eval(hi) - s.eval(hi - h)).normalized();
assert!(start.near(Vec2::new(0.0, 1.0), 1e-4), "{start:?}");
assert!(end.near(Vec2::new(1.0, -1.0).normalized(), 1e-4), "{end:?}");
// One tangent only, and two fit points with tangents (a cubic Bezier).
let one = Spline::fit_with(&fit, false, FitOptions { start_tangent: Some(Vec2::Y), ..FitOptions::default() });
assert!(one.is_valid() && one.control.len() == fit.len() + 1 && passes_through(&one, &fit, 1e-3));
let two = [Vec2::ZERO, Vec2::new(4.0, 0.0)];
let b = Spline::fit_with(
&two,
false,
FitOptions { start_tangent: Some(Vec2::Y), end_tangent: Some(Vec2::new(0.0, -1.0)), ..FitOptions::default() },
);
assert!(b.is_valid() && b.degree == 3 && b.control.len() == 4);
assert!(b.eval(0.5).y > 0.5, "the tangents bow the curve up");
// Closed curves ignore tangents.
assert_eq!(Spline::fit_with(&fit, true, opts).fit_opts.start_tangent, None);
}
#[test]
fn tolerance_approximates_with_fewer_control_points() {
// Thirty noisy points along a gentle arc.
let fit: Vec<Vec2> = (0..30)
.map(|i| {
let t = f64::from(i) / 29.0;
Vec2::new(t * 10.0, (t * 3.0).sin() * 2.0 + if i % 2 == 0 { 0.01 } else { -0.01 })
})
.collect();
let exact = Spline::fit_with(&fit, false, FitOptions::default());
let tol = 0.1;
let s = Spline::fit_with(&fit, false, FitOptions { tolerance: tol, ..FitOptions::default() });
assert!(s.is_valid());
assert!(s.control.len() < exact.control.len(), "{} control points", s.control.len());
let u = params(&fit, KnotParam::Chord, false);
assert!(max_deviation(&s, &fit, &u) <= tol + 1e-9);
assert!(s.eval(0.0).near(fit[0], 1e-9) && s.eval(1.0).near(fit[29], 1e-9), "ends stay exact");
assert_eq!(s.fit, fit, "the fit points are kept");
assert_eq!(s.fit_opts.tolerance.to_bits(), tol.to_bits());
// With tangents too.
let t = Spline::fit_with(
&fit,
false,
FitOptions { tolerance: tol, start_tangent: Some(Vec2::X), end_tangent: Some(Vec2::X), ..FitOptions::default() },
);
assert!(t.is_valid() && max_deviation(&t, &fit, &u) <= tol + 1e-9);
let h = 1e-7;
assert!((t.eval(h) - t.eval(0.0)).normalized().near(Vec2::X, 1e-4));
// A tolerance too small to approximate interpolates instead.
let tiny = Spline::fit_with(&fit, false, FitOptions { tolerance: 1e-9, ..FitOptions::default() });
assert_eq!(tiny.control.len(), exact.control.len());
}
#[test]
fn tolerance_approximates_closed_curves() {
// Forty slightly noisy points round a circle.
let fit: Vec<Vec2> = (0..40)
.map(|i| {
let a = f64::from(i) / 40.0 * std::f64::consts::TAU;
let r = 5.0 + if i % 2 == 0 { 0.01 } else { -0.01 };
Vec2::new(a.cos() * r, a.sin() * r)
})
.collect();
let exact = Spline::fit_with(&fit, true, FitOptions::default());
let tol = 0.05;
let s = Spline::fit_with(&fit, true, FitOptions { tolerance: tol, ..FitOptions::default() });
assert!(s.is_valid() && s.is_periodic() && s.closed);
assert!(s.control.len() < exact.control.len(), "{} control points", s.control.len());
let u = params(&fit, KnotParam::Chord, true);
assert!(fit.iter().zip(&u).all(|(q, t)| s.eval(*t).dist(*q) <= tol + 1e-9));
let (lo, hi) = s.domain();
assert!(s.eval(lo).near(s.eval(hi), 1e-9), "still closed");
assert_eq!(s.fit, fit);
assert_eq!(s.fit_opts.tolerance.to_bits(), tol.to_bits());
// Too tight a tolerance interpolates.
let tiny = Spline::fit_with(&fit, true, FitOptions { tolerance: 1e-9, ..FitOptions::default() });
assert_eq!(tiny.control.len(), exact.control.len());
// Every parametrisation approximates.
for k in KnotParam::ALL {
let s = Spline::fit_with(&fit, true, FitOptions { tolerance: tol, knots: k, ..FitOptions::default() });
assert!(s.is_valid() && s.control.len() < exact.control.len(), "{k:?}");
}
}
fn on_curve(s: &Spline, q: Vec2) -> bool {
let (lo, hi) = s.domain();
(0..=4000).any(|i| s.eval(lo + (hi - lo) * f64::from(i) / 4000.0).dist(q) < 1e-2)
}
#[test]
#[expect(
clippy::many_single_char_names,
reason = "The test names spline values and points with the same short notation as the fitting equations."
)]
fn repeated_fit_points_make_kinks() {
let fit = [Vec2::new(0.0, 0.0), Vec2::new(2.0, 2.0), Vec2::new(4.0, 0.0), Vec2::new(4.0, 0.0), Vec2::new(6.0, 2.0), Vec2::new(8.0, 0.0)];
let s = Spline::fit_with(&fit, false, FitOptions::default());
assert!(s.is_valid() && s.degree == 3 && !s.closed);
assert_eq!(s.fit, fit, "the kink stays in the fit data");
assert!(fit.iter().all(|q| on_curve(&s, *q)));
// A knot of multiplicity 3 at the corner, where the tangent turns.
let k = s.knots.iter().copied().find(|k| s.knots.iter().filter(|x| (*x - k).abs() < 1e-12).count() == 3).unwrap();
assert!(s.eval(k).near(Vec2::new(4.0, 0.0), 1e-9));
let h = 1e-6;
let before = (s.eval(k) - s.eval(k - h)).normalized();
let after = (s.eval(k + h) - s.eval(k)).normalized();
assert!(before.dot(after) < 0.5, "a corner: {before:?} {after:?}");
// Two-point pieces become straight cubic pieces.
let l = [Vec2::ZERO, Vec2::new(1.0, 0.0), Vec2::new(1.0, 0.0), Vec2::new(1.0, 1.0)];
let s = Spline::fit_with(&l, false, FitOptions::default());
assert!(s.is_valid() && s.degree == 3 && s.control.len() == 7);
assert!(on_curve(&s, Vec2::new(0.5, 0.0)) && on_curve(&s, Vec2::new(1.0, 0.5)));
// Closed: the curve starts and ends at the kink, clamped.
let c = [Vec2::ZERO, Vec2::ZERO, Vec2::new(4.0, 0.0), Vec2::new(4.0, 4.0), Vec2::new(0.0, 4.0)];
let s = Spline::fit_with(&c, true, FitOptions::default());
assert!(s.is_valid() && s.closed && !s.is_periodic());
let (lo, hi) = s.domain();
assert!(s.eval(lo).near(Vec2::ZERO, 1e-9) && s.eval(hi).near(Vec2::ZERO, 1e-9));
assert!(c.iter().all(|q| on_curve(&s, *q)));
// Kinks at the ends of an open curve change nothing.
let e = [Vec2::ZERO, Vec2::ZERO, Vec2::new(2.0, 2.0), Vec2::new(4.0, 0.0)];
let plain = Spline::fit_with(&e[1..], false, FitOptions::default());
assert_eq!(Spline::fit_with(&e, false, FitOptions::default()).control.len(), plain.control.len());
}
#[test]
fn hostile_options_never_panic() {
let fit = pts();
let bad = FitOptions {
knots: KnotParam::Uniform,
start_tangent: Some(Vec2::new(f64::NAN, 1.0)),
end_tangent: Some(Vec2::ZERO),
tolerance: f64::INFINITY,
};
let s = Spline::fit_with(&fit, false, bad);
assert!(s.is_valid() && s.fit_opts.start_tangent.is_none() && s.fit_opts.end_tangent.is_none() && s.fit_opts.tolerance == 0.0);
for n in 0..4 {
let few: Vec<Vec2> = fit.iter().take(n).copied().collect();
let _ = Spline::fit_with(
&few,
false,
FitOptions { start_tangent: Some(Vec2::Y), end_tangent: Some(Vec2::X), tolerance: 1.0, ..FitOptions::default() },
);
let _ = Spline::fit_with(&few, true, FitOptions { knots: KnotParam::SqrtChord, ..FitOptions::default() });
}
let same = [Vec2::ZERO; 5];
let _ = Spline::fit_with(&same, false, FitOptions { tolerance: 0.5, start_tangent: Some(Vec2::X), ..FitOptions::default() });
let _ = Spline::fit_with(&same, true, FitOptions { tolerance: 0.5, ..FitOptions::default() });
let pairs = [Vec2::ZERO, Vec2::ZERO, Vec2::X, Vec2::X, Vec2::Y, Vec2::Y];
for closed in [false, true] {
for n in 0..=pairs.len() {
let _ = Spline::fit_with(&pairs[..n], closed, FitOptions { tolerance: 0.1, ..FitOptions::default() });
}
}
let tight: Vec<Vec2> = (0..8).map(|i| Vec2::new(f64::from(i) * 1e-13, 0.0)).collect();
let _ = Spline::fit_with(&tight, true, FitOptions { tolerance: 1.0, ..FitOptions::default() });
}
/// Above the interpolation cap the fit points become control points instead of a dense
/// system the size of their count squared (issue #702); just below it they still interpolate.
#[test]
#[expect(
clippy::cast_precision_loss,
reason = "The generated test grids are bounded by MAX_INTERP_POINTS + 1, so their indices are exact as f64."
)]
fn too_many_fit_points_are_not_interpolated() {
let wave = |n: usize| -> Vec<Vec2> { (0..n).map(|i| Vec2::new((i * i) as f64 * 1e-3, (i % 5) as f64)).collect() };
let fit = wave(MAX_INTERP_POINTS + 1);
let s = Spline::fit_with(&fit, false, FitOptions::default());
assert_eq!(s.control, fit);
assert_eq!(s.knots, Spline::from_control(fit.clone(), 3).knots);
assert_eq!(s.fit, fit);
let c = Spline::fit_with(&fit, true, FitOptions::default());
let mut ring = fit.clone();
ring.extend(fit.first().copied());
assert!(c.closed);
assert_eq!(c.control, ring);
assert_eq!(c.fit, fit);
let few = wave(64);
assert!(passes_through(&Spline::fit_with(&few, false, FitOptions::default()), &few, 1e-6));
assert!(passes_through(&Spline::fit_with(&few, true, FitOptions::default()), &few, 1e-6));
}
#[test]
fn transform_turns_the_tangents() {
let fit = pts();
let mut s = Spline::fit_with(&fit, false, FitOptions { start_tangent: Some(Vec2::X), ..FitOptions::default() });
s.transform(&Mat3::rotate(std::f64::consts::FRAC_PI_2));
assert!(s.fit_opts.start_tangent.is_some_and(|t| t.near(Vec2::Y, 1e-12)));
}
}
#[cfg(test)]
mod knot_boundary_tests {
use super::*;
#[test]
fn uniform_knots_skip_the_strict_lower_tolerance_boundary() {
let q = 2.0 / 3.0;
let mut s = Spline::from_control(vec![Vec2::ZERO; 5], 1);
s.fit = vec![Vec2::new(0.0, 0.0), Vec2::new(1.0, 0.0), Vec2::new(4.0, 0.0), Vec2::new(9.0, 0.0)];
s.knots = vec![0.0, 0.0, 1.0 / 3.0, q - 1e-6, q, 1.0, 1.0];
assert!(s.is_valid());
assert_eq!(s.infer_knot_param(), KnotParam::Uniform);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.