use std::fmt;
use crate::Point;
use crate::numeric::pow;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BezierError {
Empty,
RaggedControlPoints,
NotIntersecting,
PathMissesRegion,
ParallelLines,
}
impl fmt::Display for BezierError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(match self {
Self::Empty => "a Bézier segment needs at least one control point",
Self::RaggedControlPoints => "all control points must have the same dimension",
Self::NotIntersecting => "both points are on the same side of the closed path",
Self::PathMissesRegion => "The path does not intersect with the patch",
Self::ParallelLines => "the lines do not intersect",
})
}
}
impl std::error::Error for BezierError {}
#[derive(Clone, Debug, PartialEq)]
pub struct BezierSegment {
dimension: usize,
coordinates: Vec<f64>,
}
fn fused_sum(terms: impl Iterator<Item = (f64, f64)>) -> f64 {
terms.fold(0.0, |sum, (a, b)| a.mul_add(b, sum))
}
fn binomial(n: usize, k: usize) -> f64 {
(0..k).fold(1.0, |acc, i| acc * (n - i) as f64 / (i + 1) as f64)
}
impl BezierSegment {
pub fn new(dimension: usize, coordinates: Vec<f64>) -> Result<Self, BezierError> {
if dimension == 0 || coordinates.is_empty() {
return Err(BezierError::Empty);
}
if !coordinates.len().is_multiple_of(dimension) {
return Err(BezierError::RaggedControlPoints);
}
Ok(Self {
dimension,
coordinates,
})
}
pub fn from_rows<R: AsRef<[f64]>>(rows: &[R]) -> Result<Self, BezierError> {
let dimension = rows.first().ok_or(BezierError::Empty)?.as_ref().len();
if rows.iter().any(|r| r.as_ref().len() != dimension) {
return Err(BezierError::RaggedControlPoints);
}
Self::new(
dimension,
rows.iter()
.flat_map(|r| r.as_ref().iter().copied())
.collect(),
)
}
pub fn from_points(points: &[Point]) -> Result<Self, BezierError> {
Self::new(2, points.iter().flat_map(|p| [p.x, p.y]).collect())
}
pub const fn dimension(&self) -> usize {
self.dimension
}
pub fn degree(&self) -> usize {
self.coordinates.len() / self.dimension - 1
}
pub fn control_points(&self) -> impl ExactSizeIterator<Item = &[f64]> {
self.coordinates.chunks_exact(self.dimension)
}
pub fn points(&self) -> Option<Vec<Point>> {
(self.dimension == 2).then(|| {
self.control_points()
.map(|c| Point::new(c[0], c[1]))
.collect()
})
}
pub fn eval(&self, t: f64) -> Vec<f64> {
let n = self.degree();
let weights: Vec<f64> = (0..=n)
.map(|i| pow(1.0 - t, (n - i) as f64) * pow(t, i as f64))
.collect();
let scaled: Vec<Vec<f64>> = self
.control_points()
.enumerate()
.map(|(i, point)| point.iter().map(|c| c * binomial(n, i)).collect())
.collect();
(0..self.dimension)
.map(|d| fused_sum(weights.iter().zip(&scaled).map(|(&w, row)| (w, row[d]))))
.collect()
}
pub fn point_at(&self, t: f64) -> Point {
let v = self.eval(t);
Point::new(v[0], v.get(1).copied().unwrap_or(0.0))
}
pub fn polynomial_coefficients(&self) -> Vec<Vec<f64>> {
let n = self.degree();
let points: Vec<&[f64]> = self.control_points().collect();
let factor = |j: usize, i: usize| {
if i > j {
return 0.0;
}
let sign = if (i + j).is_multiple_of(2) { 1.0 } else { -1.0 };
binomial(n, j) * sign * binomial(j, i)
};
(0..=n)
.map(|j| {
(0..self.dimension)
.map(|d| {
fused_sum(
points
.iter()
.enumerate()
.map(|(i, point)| (factor(j, i), point[d])),
)
})
.collect()
})
.collect()
}
pub fn axis_aligned_extrema(&self) -> (Vec<usize>, Vec<f64>) {
let n = self.degree();
let mut dims = Vec::new();
let mut roots = Vec::new();
if n <= 1 {
return (dims, roots);
}
let coefficients = self.polynomial_coefficients();
for d in 0..self.dimension {
let derivative: Vec<f64> = coefficients[1..]
.iter()
.enumerate()
.map(|(k, row)| (k + 1) as f64 * row[d])
.collect();
for root in real_roots_in_01(&derivative) {
dims.push(d);
roots.push(root);
}
}
(dims, roots)
}
pub fn split(&self, t: f64) -> (Self, Self) {
let d = self.dimension;
let mut level = self.coordinates.clone();
let mut left = level[..d].to_vec();
let mut right_rev = level[level.len() - d..].to_vec();
while level.len() > d {
level = level
.chunks_exact(d)
.zip(level.chunks_exact(d).skip(1))
.flat_map(|(a, b)| a.iter().zip(b).map(|(a, b)| a * (1.0 - t) + b * t))
.collect();
left.extend_from_slice(&level[..d]);
right_rev.extend_from_slice(&level[level.len() - d..]);
}
let right = right_rev.chunks_exact(d).rev().flatten().copied().collect();
(
Self {
dimension: d,
coordinates: left,
},
Self {
dimension: d,
coordinates: right,
},
)
}
}
pub fn real_roots_in_01(coefficients: &[f64]) -> Vec<f64> {
let Some(degree) = coefficients.iter().rposition(|c| c.abs() >= 1e-12) else {
return Vec::new();
};
let c = &coefficients[..=degree];
let mut roots = match degree {
0 => Vec::new(),
1 => vec![-c[0] / c[1]],
2 => quadratic_roots(c[0], c[1], c[2]),
_ => {
const EPS: f64 = 1e-10;
polynomial_roots(c, -EPS, 1.0 + EPS)
.into_iter()
.map(|r| r.clamp(0.0, 1.0))
.collect()
}
};
roots.retain(|r| (0.0..=1.0).contains(r));
roots.sort_by(f64::total_cmp);
roots
}
fn quadratic_roots(c0: f64, c1: f64, c2: f64) -> Vec<f64> {
let disc = c1 * c1 - 4.0 * c2 * c0;
if disc < 0.0 {
return Vec::new();
}
let sqrt_disc = disc.sqrt();
let q = if c1 >= 0.0 {
-0.5 * (c1 + sqrt_disc)
} else {
-0.5 * (c1 - sqrt_disc)
};
let mut roots = Vec::with_capacity(2);
if q.abs() > 1e-12 {
roots.push(c0 / q);
}
if c2.abs() > 1e-12 {
roots.push(q / c2);
}
roots
}
fn horner(c: &[f64], t: f64) -> f64 {
c.iter().rev().fold(0.0, |acc, k| acc * t + k)
}
fn polynomial_roots(c: &[f64], lo: f64, hi: f64) -> Vec<f64> {
if c.len() == 2 {
let r = -c[0] / c[1];
return if (lo..=hi).contains(&r) {
vec![r]
} else {
Vec::new()
};
}
let derivative: Vec<f64> = c[1..]
.iter()
.enumerate()
.map(|(k, v)| (k + 1) as f64 * v)
.collect();
let mut knots = vec![lo];
knots.extend(polynomial_roots(&derivative, lo, hi));
knots.push(hi);
let mut roots = Vec::new();
for pair in knots.windows(2) {
let (mut a, mut b) = (pair[0], pair[1]);
let (fa, fb) = (horner(c, a), horner(c, b));
if fa == 0.0 {
roots.push(a);
continue;
}
if fa.signum() == fb.signum() {
continue;
}
while b - a > f64::EPSILON * b.abs().max(1.0) {
let m = f64::midpoint(a, b);
if horner(c, m).signum() == fa.signum() {
a = m;
} else {
b = m;
}
}
roots.push(f64::midpoint(a, b));
}
if horner(c, hi) == 0.0 {
roots.push(hi);
}
roots.dedup();
roots
}
#[cfg(test)]
mod tests {
use super::*;
fn cubic() -> BezierSegment {
BezierSegment::from_rows(&[[0.0, 0.0], [0.0, 1.0], [1.0, 1.0], [1.0, 0.0]]).expect("valid")
}
#[test]
fn evaluation_and_properties() {
let c = cubic();
assert_eq!((c.degree(), c.dimension()), (3, 2));
assert_eq!(c.eval(0.5), vec![0.5, 0.75]);
assert_eq!(c.point_at(0.0), Point::new(0.0, 0.0));
assert_eq!(
c.polynomial_coefficients(),
vec![
vec![0.0, 0.0],
vec![0.0, 3.0],
vec![3.0, -3.0],
vec![-2.0, 0.0]
]
);
assert_eq!(
BezierSegment::from_rows::<[f64; 2]>(&[]),
Err(BezierError::Empty)
);
assert_eq!(
BezierSegment::from_rows(&[vec![0.0, 0.0], vec![1.0]]),
Err(BezierError::RaggedControlPoints)
);
}
#[test]
fn extrema_like_matplotlib() {
assert_eq!(
cubic().axis_aligned_extrema(),
(vec![0, 0, 1], vec![0.0, 1.0, 0.5])
);
let line = BezierSegment::from_rows(&[[0.0, 0.0], [4.0, 2.0]]).expect("valid");
assert_eq!(line.axis_aligned_extrema(), (vec![], vec![]));
let quartic = BezierSegment::from_rows(&[
[0.0, 0.0],
[1.0, 3.0],
[2.0, -2.0],
[3.0, 2.0],
[4.0, 0.0],
])
.expect("valid");
let (dims, roots) = quartic.axis_aligned_extrema();
assert_eq!(dims, vec![1, 1, 1]);
for (got, want) in roots.iter().zip([
0.197_868_915_336_342_77,
0.582_517_508_272_926_4,
0.813_363_576_390_730_6,
]) {
assert!((got - want).abs() < 1e-12);
}
}
#[test]
fn evaluation_rounds_as_numpy() {
let curve = BezierSegment::from_rows(&[
[0.499_999_910_593_032_6, -0.692_820_340_394_973_8],
[0.586_602_464_318_274_8, -0.692_820_340_394_973_8],
[0.586_602_464_318_274_8, -0.866_025_447_845_459],
[0.499_999_910_593_032_6, -0.866_025_447_845_459],
])
.expect("valid");
let (dims, roots) = curve.axis_aligned_extrema();
assert_eq!(dims, [0, 1, 1]);
assert_eq!(
curve.eval(roots[0]),
[0.564_951_825_886_964_2, -0.779_422_894_120_216_6]
);
}
#[test]
fn de_casteljau_split() {
let (left, right) = cubic().split(0.5);
assert_eq!(left.points().expect("2-D")[3], Point::new(0.5, 0.75));
assert_eq!(right.points().expect("2-D")[0], Point::new(0.5, 0.75));
assert_eq!(right.points().expect("2-D")[3], Point::new(1.0, 0.0));
let point = BezierSegment::from_rows(&[[1.5, -2.0]]).expect("valid");
assert_eq!(point.split(0.3), (point.clone(), point));
}
}