a770fa5a5e5f
curves.rs
//! Snap points on ellipses, elliptical arcs and splines: the midpoint by length, and the
//! perpendicular feet and tangent points from a base point. Splines (and perpendiculars on
//! ellipses) are solved numerically: the parameter range is sampled, each sign change of the
//! condition is narrowed by bisection, and every loop has a fixed bound.
use cadcraft_geom::{Circle, Ellipse, Spline, Vec2, angle_in_sweep};
/// Parameter samples along a curve (sign changes and length).
const SAMPLES: usize = 512;
/// Bisection steps per root (the bracket shrinks to 2⁻⁶⁰ of a sample step).
const BISECT: usize = 60;
/// The most solutions one curve offers.
const MAX_ROOTS: usize = 16;
/// A curve given by a parameter range, its points and its derivative.
struct Param<'a> {
lo: f64,
hi: f64,
at: &'a dyn Fn(f64) -> Vec2,
d: &'a dyn Fn(f64) -> Vec2,
}
impl Param<'_> {
fn ellipse(e: &Ellipse, f: impl FnOnce(&Param) -> Vec<Vec2>) -> Vec<Vec2> {
let (u, v) = (e.major, e.minor());
let lo = e.start;
let hi = e.start + e.sweep();
f(&Param { lo, hi, at: &|t| e.at_param(t), d: &|t| v * t.cos() - u * t.sin() })
}
fn spline(s: &Spline, f: impl FnOnce(&Param) -> Vec<Vec2>) -> Vec<Vec2> {
let (lo, hi) = s.domain();
if !(s.is_valid() && lo.is_finite() && hi.is_finite() && hi > lo) {
return Vec::new();
}
let h = (hi - lo) * 1e-7;
let d = |t: f64| {
let (a, b) = ((t - h).max(lo), (t + h).min(hi));
if b > a { (s.eval(b) - s.eval(a)) / (b - a) } else { Vec2::ZERO }
};
f(&Param { lo, hi, at: &|t| s.eval(t), d: &d })
}
fn param(&self, i: usize) -> f64 {
self.lo + (self.hi - self.lo) * i as f64 / SAMPLES as f64
}
/// The point halfway along the curve's length.
fn mid(&self) -> Option<Vec2> {
let pts: Vec<Vec2> = (0..=SAMPLES).map(|i| (self.at)(self.param(i))).collect();
let lens: Vec<f64> = pts.windows(2).map(|w| if let [a, b] = w { a.dist(*b) } else { 0.0 }).collect();
let total: f64 = lens.iter().sum();
if !(total.is_finite() && total > 0.0) {
return None;
}
let mut run = 0.0;
for (i, l) in lens.iter().enumerate() {
if run + l >= total / 2.0 && *l > 0.0 {
let k = (total / 2.0 - run) / l;
let t = self.param(i) + (self.param(i + 1) - self.param(i)) * k;
return Some((self.at)(t)).filter(|p| p.is_finite());
}
run += l;
}
None
}
/// The points where `cond(point − base, derivative)` is zero: sign changes of the samples,
/// narrowed by bisection; kept when the normalised condition is (nearly) zero there, so a
/// sign flip at a kink or a pole is not taken for a solution.
fn solve(&self, base: Vec2, cond: fn(Vec2, Vec2) -> f64) -> Vec<Vec2> {
let g = |t: f64| cond((self.at)(t) - base, (self.d)(t));
let samples: Vec<(Vec2, Vec2)> = (0..=SAMPLES).map(|i| ((self.at)(self.param(i)) - base, (self.d)(self.param(i)))).collect();
let vals: Vec<f64> = samples.iter().map(|(r, d)| cond(*r, *d)).collect();
// A curve on which every point qualifies (a circle seen from its centre) has no
// particular solution.
let scale = samples.iter().map(|(r, d)| r.len() * d.len()).fold(0.0, f64::max);
if !(scale.is_finite() && scale > 0.0) || vals.iter().all(|v| v.abs() <= scale * 1e-12) {
return Vec::new();
}
let mut out: Vec<Vec2> = Vec::new();
for i in 0..SAMPLES {
let (Some(&ga), Some(&gb)) = (vals.get(i), vals.get(i + 1)) else { break };
if !(ga.is_finite() && gb.is_finite()) || (ga > 0.0) == (gb > 0.0) && ga != 0.0 {
continue;
}
let (mut a, mut b, mut fa) = (self.param(i), self.param(i + 1), ga);
for _ in 0..BISECT {
let m = 0.5 * (a + b);
let fm = g(m);
if fm == 0.0 {
(a, b) = (m, m);
break;
}
if (fm > 0.0) == (fa > 0.0) {
(a, fa) = (m, fm);
} else {
b = m;
}
}
let t = 0.5 * (a + b);
let (p, dv) = ((self.at)(t), (self.d)(t));
let (r, dl) = ((p - base).len(), dv.len());
if !(p.is_finite() && r > 1e-12 && dl > 0.0) || cond(p - base, dv).abs() > 1e-6 * r * dl {
continue;
}
if !out.iter().any(|q| q.near(p, 1e-9 * (1.0 + r))) {
out.push(p);
if out.len() >= MAX_ROOTS {
break;
}
}
}
out
}
}
fn perpendicular(r: Vec2, d: Vec2) -> f64 {
r.dot(d)
}
fn tangent(r: Vec2, d: Vec2) -> f64 {
r.cross(d)
}
/// The midpoint (by length) of an elliptical arc; none for a full ellipse.
pub(super) fn ellipse_mid(e: &Ellipse) -> Option<Vec2> {
if e.is_full() {
return None;
}
Param::ellipse(e, |c| c.mid().into_iter().collect()).first().copied()
}
/// The feet of the perpendiculars from `base` to an ellipse or elliptical arc.
pub(super) fn ellipse_perpendiculars(e: &Ellipse, base: Vec2) -> Vec<Vec2> {
Param::ellipse(e, |c| c.solve(base, perpendicular))
}
/// The points where lines from `base` touch an ellipse or elliptical arc: exact, by mapping the
/// ellipse onto the unit circle (an affine map keeps tangency).
pub(super) fn ellipse_tangents(e: &Ellipse, base: Vec2) -> Vec<Vec2> {
let (u, v) = (e.major, e.minor());
let (a, b) = (u.len(), v.len());
if !(a > 0.0 && b > 0.0 && a.is_finite() && b.is_finite()) {
return Vec::new();
}
let r = base - e.center;
let local = Vec2::new(r.dot(u) / (a * a), r.dot(v) / (b * b));
Circle::new(Vec2::ZERO, 1.0)
.tangent_points(local)
.into_iter()
.map(|q| q.angle())
.filter(|t| t.is_finite() && angle_in_sweep(*t, e.start, e.end))
.map(|t| e.at_param(t))
.collect()
}
/// The midpoint (by length) of an open spline.
pub(super) fn spline_mid(s: &Spline) -> Option<Vec2> {
if s.closed {
return None;
}
Param::spline(s, |c| c.mid().into_iter().collect()).first().copied()
}
/// The feet of the perpendiculars from `base` to a spline.
pub(super) fn spline_perpendiculars(s: &Spline, base: Vec2) -> Vec<Vec2> {
Param::spline(s, |c| c.solve(base, perpendicular))
}
/// The points where lines from `base` touch a spline.
pub(super) fn spline_tangents(s: &Spline, base: Vec2) -> Vec<Vec2> {
Param::spline(s, |c| c.solve(base, tangent))
}
#[cfg(test)]
mod tests {
use super::*;
use cadcraft_geom::PI;
fn length(f: impl Fn(f64) -> Vec2, lo: f64, hi: f64) -> f64 {
let n = 20_000;
(0..n).map(|i| f(lo + (hi - lo) * i as f64 / n as f64).dist(f(lo + (hi - lo) * (i + 1) as f64 / n as f64))).sum()
}
#[test]
fn ellipse_mid_halves_the_length() {
let e = Ellipse { center: Vec2::new(1.0, 2.0), major: Vec2::new(4.0, 0.0), ratio: 0.5, start: 0.0, end: PI / 2.0 };
let m = ellipse_mid(&e).unwrap();
let t = e.param_of(m);
let (l1, l2) = (length(|t| e.at_param(t), 0.0, t), length(|t| e.at_param(t), t, PI / 2.0));
assert!((l1 - l2).abs() < 1e-4, "{l1} vs {l2}");
assert!(ellipse_mid(&Ellipse::full(Vec2::ZERO, Vec2::X, 0.5)).is_none());
}
#[test]
fn ellipse_tangents_touch_and_stay_on_the_arc() {
let full = Ellipse::full(Vec2::ZERO, Vec2::new(4.0, 0.0), 0.5);
let base = Vec2::new(0.0, 5.0);
let ts = ellipse_tangents(&full, base);
assert_eq!(ts.len(), 2);
for p in &ts {
// On the ellipse, and the line from the base touches it: (x/a)² + (y/b)² = 1 and
// the gradient is perpendicular to the line.
assert!(((p.x / 4.0).powi(2) + (p.y / 2.0).powi(2) - 1.0).abs() < 1e-9);
let grad = Vec2::new(p.x / 16.0, p.y / 4.0);
assert!(grad.dot(*p - base).abs() < 1e-9);
}
// Only the right half of the upper arc: one tangent point.
let arc = Ellipse { start: 0.0, end: PI / 2.0, ..full };
assert_eq!(ellipse_tangents(&arc, base).len(), 1);
// From inside: none.
assert!(ellipse_tangents(&full, Vec2::new(1.0, 0.5)).is_empty());
}
#[test]
fn ellipse_perpendiculars_are_normals() {
let e = Ellipse::full(Vec2::ZERO, Vec2::new(4.0, 0.0), 0.5);
let base = Vec2::new(1.0, 0.5);
let ps = ellipse_perpendiculars(&e, base);
// From a point inside near the centre: the four normals of an ellipse.
assert_eq!(ps.len(), 4, "{ps:?}");
for p in &ps {
let tan = Vec2::new(-p.y * 4.0 / 2.0, p.x * 2.0 / 4.0);
assert!(tan.dot(*p - base).abs() < 1e-6, "{p:?}");
}
// A circle seen from its centre has no particular perpendicular.
assert!(ellipse_perpendiculars(&Ellipse::full(Vec2::ZERO, Vec2::X, 1.0), Vec2::ZERO).is_empty());
}
#[test]
fn spline_snaps() {
let s = Spline::from_control(vec![Vec2::new(0.0, 0.0), Vec2::new(1.0, 3.0), Vec2::new(3.0, 3.0), Vec2::new(4.0, 0.0)], 3);
// Symmetric about x = 2: the midpoint is on the axis, so is the perpendicular from
// straight below, and the tangents from far above are symmetric.
let m = spline_mid(&s).unwrap();
assert!((m.x - 2.0).abs() < 1e-6 && (m.y - 2.25).abs() < 1e-6, "{m:?}");
let ps = spline_perpendiculars(&s, Vec2::new(2.0, -5.0));
assert!(ps.iter().any(|p| p.near(m, 1e-6)), "{ps:?}");
// Every tangent of the arch passes x = 2 between y = 2.25 and 6: none from (2, 10) or
// from below the arch, two from (2, 4).
assert!(spline_tangents(&s, Vec2::new(2.0, 10.0)).is_empty());
assert!(spline_tangents(&s, Vec2::new(2.0, -1.0)).is_empty());
let ts = spline_tangents(&s, Vec2::new(2.0, 4.0));
assert_eq!(ts.len(), 2, "{ts:?}");
assert!((ts[0].x - 2.0 + ts[1].x - 2.0).abs() < 1e-6 && (ts[0].y - ts[1].y).abs() < 1e-6, "{ts:?}");
}
}
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.