mod parallel;
mod segment;
mod split;
pub use parallel::{
Direction, Parallel, check_if_parallel, find_control_points, get_cos_sin, get_intersection,
get_normal_points, get_parallels, make_wedged_bezier2,
};
pub use segment::{BezierError, BezierSegment, real_roots_in_01};
pub use split::{
find_bezier_t_intersecting_with_closedpath, inside_circle,
split_bezier_intersecting_with_closedpath, split_path_inout,
};
use crate::Point;
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum Bezier {
Line(Point, Point),
Quad(Point, Point, Point),
Cubic(Point, Point, Point, Point),
}
impl Bezier {
pub const fn start(&self) -> Point {
match *self {
Self::Line(p0, _) | Self::Quad(p0, _, _) | Self::Cubic(p0, _, _, _) => p0,
}
}
pub const fn end(&self) -> Point {
match *self {
Self::Line(_, p1) | Self::Quad(_, _, p1) | Self::Cubic(_, _, _, p1) => p1,
}
}
pub fn control_points(&self) -> Vec<Point> {
match *self {
Self::Line(a, b) => vec![a, b],
Self::Quad(a, b, c) => vec![a, b, c],
Self::Cubic(a, b, c, d) => vec![a, b, c, d],
}
}
pub fn eval(&self, t: f64) -> Point {
match *self {
Self::Line(a, b) => a.lerp(b, t),
Self::Quad(a, b, c) => a.lerp(b, t).lerp(b.lerp(c, t), t),
Self::Cubic(a, b, c, d) => {
let ab = a.lerp(b, t);
let bc = b.lerp(c, t);
let cd = c.lerp(d, t);
ab.lerp(bc, t).lerp(bc.lerp(cd, t), t)
}
}
}
pub fn derivative(&self, t: f64) -> Point {
match *self {
Self::Line(a, b) => b - a,
Self::Quad(a, b, c) => ((b - a).lerp(c - b, t)) * 2.0,
Self::Cubic(a, b, c, d) => {
let (u, v, w) = (b - a, c - b, d - c);
u.lerp(v, t).lerp(v.lerp(w, t), t) * 3.0
}
}
}
pub fn split(&self, t: f64) -> (Self, Self) {
match *self {
Self::Line(a, b) => {
let m = a.lerp(b, t);
(Self::Line(a, m), Self::Line(m, b))
}
Self::Quad(a, b, c) => {
let ab = a.lerp(b, t);
let bc = b.lerp(c, t);
let m = ab.lerp(bc, t);
(Self::Quad(a, ab, m), Self::Quad(m, bc, c))
}
Self::Cubic(a, b, c, d) => {
let ab = a.lerp(b, t);
let bc = b.lerp(c, t);
let cd = c.lerp(d, t);
let abc = ab.lerp(bc, t);
let bcd = bc.lerp(cd, t);
let m = abc.lerp(bcd, t);
(Self::Cubic(a, ab, abc, m), Self::Cubic(m, bcd, cd, d))
}
}
}
pub fn axis_aligned_extrema(&self) -> Vec<f64> {
let mut roots = Vec::new();
match *self {
Self::Line(..) => {}
Self::Quad(a, b, c) => {
for (p0, p1, p2) in [(a.x, b.x, c.x), (a.y, b.y, c.y)] {
let denom = p0 - 2.0 * p1 + p2;
if denom != 0.0 {
roots.push((p0 - p1) / denom);
}
}
}
Self::Cubic(a, b, c, d) => {
for (p0, p1, p2, p3) in [(a.x, b.x, c.x, d.x), (a.y, b.y, c.y, d.y)] {
let qa = -p0 + 3.0 * p1 - 3.0 * p2 + p3;
let qb = 2.0 * (p0 - 2.0 * p1 + p2);
let qc = p1 - p0;
roots.extend(quadratic_roots(qa, qb, qc));
}
}
}
roots.retain(|t| *t > 0.0 && *t < 1.0);
roots.sort_by(f64::total_cmp);
roots.dedup();
roots
}
pub fn flatten_into(&self, tolerance: f64, out: &mut Vec<Point>) {
let segments = self.segments_for_tolerance(tolerance);
let step = 1.0 / segments as f64;
out.extend((1..segments).map(|i| self.eval(i as f64 * step)));
out.push(self.end());
}
fn segments_for_tolerance(&self, tolerance: f64) -> usize {
let tolerance = tolerance.max(1e-9);
let dd = match *self {
Self::Line(..) => return 1,
Self::Quad(a, b, c) => (a - b * 2.0 + c).length() * 2.0,
Self::Cubic(a, b, c, d) => {
let d1 = (a - b * 2.0 + c).length();
let d2 = (b - c * 2.0 + d).length();
d1.max(d2) * 6.0
}
};
let n = (dd / (8.0 * tolerance)).sqrt().ceil();
if n.is_finite() {
(n as usize).clamp(1, 10_000)
} else {
1
}
}
}
fn quadratic_roots(a: f64, b: f64, c: f64) -> Vec<f64> {
const EPS: f64 = 1e-12;
if a.abs() < EPS {
return if b.abs() < EPS {
Vec::new()
} else {
vec![-c / b]
};
}
let disc = b * b - 4.0 * a * c;
if disc < 0.0 {
return Vec::new();
}
let sq = disc.sqrt();
let q = -0.5 * (b + b.signum() * sq);
if q == 0.0 {
return vec![0.0];
}
vec![q / a, c / q]
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
#[test]
fn eval_endpoints_and_midpoint() {
let c = Bezier::Cubic(p(0.0, 0.0), p(0.0, 1.0), p(1.0, 1.0), p(1.0, 0.0));
assert_eq!(c.eval(0.0), p(0.0, 0.0));
assert_eq!(c.eval(1.0), p(1.0, 0.0));
assert_eq!(c.eval(0.5), p(0.5, 0.75));
}
#[test]
fn split_reconstructs_curve() {
let c = Bezier::Cubic(p(0.0, 0.0), p(1.0, 3.0), p(2.0, -1.0), p(4.0, 1.0));
let (left, right) = c.split(0.3);
for i in 0..=10 {
let t = f64::from(i) / 10.0;
assert!((left.eval(t) - c.eval(0.3 * t)).length() < 1e-12);
assert!((right.eval(t) - c.eval(0.3 + 0.7 * t)).length() < 1e-12);
}
}
#[test]
fn extrema_of_symmetric_arch() {
let c = Bezier::Cubic(p(0.0, 0.0), p(0.0, 1.0), p(1.0, 1.0), p(1.0, 0.0));
assert_eq!(c.axis_aligned_extrema(), vec![0.5]);
let q = Bezier::Quad(p(0.0, 0.0), p(1.0, 2.0), p(2.0, 0.0));
assert_eq!(q.axis_aligned_extrema(), vec![0.5]);
}
#[test]
fn derivative_matches_finite_difference() {
let c = Bezier::Cubic(p(0.0, 0.0), p(1.0, 3.0), p(2.0, -1.0), p(4.0, 1.0));
let h = 1e-6;
let numeric = (c.eval(0.4 + h) - c.eval(0.4 - h)) / (2.0 * h);
assert!((numeric - c.derivative(0.4)).length() < 1e-6);
}
#[test]
fn flattening_respects_tolerance() {
let c = Bezier::Cubic(p(0.0, 0.0), p(0.0, 100.0), p(100.0, 100.0), p(100.0, 0.0));
let mut pts = vec![c.start()];
c.flatten_into(0.1, &mut pts);
assert_eq!(*pts.last().expect("non-empty"), c.end());
let n = pts.len() - 1;
for i in 0..n {
let t = (i as f64 + 0.5) / n as f64;
let mid = pts[i].lerp(pts[i + 1], 0.5);
assert!((mid - c.eval(t)).length() < 0.25);
}
}
}