Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

52.6 KB
Raw Blame
//! The geometry of planar profiles ([`Seg2`], [`Loop2`], [`Region2`]: plain data in the
//! record): evaluation, derivatives, lengths, areas, containment, polylines and triangles.
//! Sketches produce profiles; the kernel turns them into faces.

use std::f64::consts::TAU;

use solidcore_record::{Loop2, MAX_BEZIER_CTRL, MAX_BEZIER_DEGREE, Region2, Seg2, Vec2};

use crate::prelude::*;
use crate::{Aabb2, Ring};

/// Highest derivative order [`Seg2Geom::derivatives`] hands out, and therefore the highest
/// continuity order a blend curve can be built for (4 = G4).
pub const MAX_DERIVATIVE_ORDER: usize = 4;

/// A similarity of the plane: a point is scaled by `scale` (above 0) about the origin, turned
/// `angle` radians counter-clockwise, then moved by `shift`. It keeps shapes and the direction
/// curves turn in, so an arc stays an arc ([`Seg2Geom::similar`]).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Similarity2 {
    scale: f64,
    angle: f64,
    shift: Vec2,
    /// The angle's cosine and sine times the scale, worked out once rather than per point.
    cos: f64,
    sin: f64,
}

impl Similarity2 {
    /// `None` unless `scale` is finite and above 0 and `angle` and `shift` are finite.
    pub fn new(scale: f64, angle: f64, shift: Vec2) -> Option<Similarity2> {
        if !(scale.is_finite() && scale > 0.0 && angle.is_finite() && shift.is_finite()) {
            return None;
        }
        let (sin, cos) = angle.sin_cos();
        Some(Similarity2 { scale, angle, shift, cos: cos * scale, sin: sin * scale })
    }

    pub fn scale(&self) -> f64 {
        self.scale
    }

    pub fn angle(&self) -> f64 {
        self.angle
    }

    pub fn apply(&self, p: Vec2) -> Vec2 {
        Vec2::new(self.cos * p.x - self.sin * p.y, self.sin * p.x + self.cos * p.y) + self.shift
    }
}

/// A Bézier segment over `pts` (2…[`MAX_BEZIER_CTRL`] points): a line, a cubic or a higher-degree
/// piece. A quadratic becomes a conic of weight 1.
pub fn bezier(pts: &[Vec2]) -> Option<Seg2> {
    Some(match *pts {
        [a, b] => Seg2::Line { a, b },
        [a, apex, b] => Seg2::Conic { a, apex, b, w: 1.0 },
        [p0, p1, p2, p3] => Seg2::Cubic { p0, p1, p2, p3 },
        _ if (2..=MAX_BEZIER_CTRL).contains(&pts.len()) => {
            let mut p = [Vec2::ZERO; MAX_BEZIER_CTRL];
            for (d, s) in p.iter_mut().zip(pts) {
                *d = *s;
            }
            Seg2::Bezier { n: (pts.len() - 1) as u8, p }
        }
        _ => return None,
    })
}

/// Smallest radius, conic weight and absolute arc sweep [`Seg2Geom::check`] accepts.
const MIN_POSITIVE: f64 = 1e-12;
/// Largest conic weight [`Seg2Geom::check`] accepts.
const MAX_WEIGHT: f64 = 1e12;
/// Largest arc start angle either way, in radians, [`Seg2Geom::check`] accepts.
const MAX_START_ANGLE: f64 = 1e6;

fn require(condition: bool, message: &'static str) -> Result<(), &'static str> {
    if condition { Ok(()) } else { Err(message) }
}

/// Every value finite and at most `max_abs` in size: [`Seg2Geom::check`]'s rule for coordinates, which
/// `section` applies to its planes and contacts too.
pub(crate) fn coordinates(values: impl IntoIterator<Item = f64>, max_abs: f64) -> Result<(), &'static str> {
    require(values.into_iter().all(|v| v.is_finite() && v.abs() <= max_abs), "non-finite or excessive coordinate")
}

fn controls(points: &[Vec2], max_abs: f64) -> Result<(), &'static str> {
    coordinates(points.iter().flat_map(|p| [p.x, p.y]), max_abs)?;
    let Some((first, rest)) = points.split_first() else { return Err("empty controls") };
    require(rest.iter().any(|p| p != first), "collapsed curve")
}

/// de Casteljau: the point at `t` and the two halves' control points.
fn casteljau(c: &[Vec2], t: f64) -> (Vec2, Vec<Vec2>, Vec<Vec2>) {
    let mut w = c.to_vec();
    let mut left = Vec::with_capacity(c.len());
    let mut right = Vec::with_capacity(c.len());
    while let Some(first) = w.first().copied() {
        left.push(first);
        if let Some(last) = w.last().copied() {
            right.push(last);
        }
        if w.len() == 1 {
            break;
        }
        w = w.windows(2).map(|x| x[0].lerp(x[1], t)).collect();
    }
    right.reverse();
    (left.last().copied().unwrap_or(Vec2::ZERO), left, right)
}

/// Binomial coefficient `C(n, k)` for the small orders the derivative rules need (0 when
/// `k > n`).
pub(crate) fn binom(n: usize, k: usize) -> f64 {
    if k > n {
        return 0.0;
    }
    (0..k.min(n - k)).fold(1.0, |v, i| v * (n - i) as f64 / (i + 1) as f64)
}

/// Derivatives 1…`order` of the Bézier over `c` (degree `c.len() - 1`) at `t`: the j-th forward
/// difference of the control polygon, scaled by `n!/(n − j)!` and evaluated by de Casteljau.
/// Exact in exact arithmetic, zero above the degree, `None` for non-finite input.
fn bezier_derivatives(c: &[Vec2], t: f64, order: usize) -> Option<Vec<Vec2>> {
    if !t.is_finite() || c.is_empty() || c.iter().any(|p| !p.is_finite()) {
        return None;
    }
    let n = c.len() - 1;
    let mut diffs = c.to_vec();
    let mut scale = 1.0;
    let mut out = Vec::with_capacity(order);
    for j in 1..=order {
        if diffs.len() < 2 {
            out.push(Vec2::ZERO);
            continue;
        }
        diffs = diffs.windows(2).map(|w| w[1] - w[0]).collect();
        scale *= (n + 1 - j) as f64;
        out.push(casteljau(&diffs, t).0 * scale);
    }
    Some(out)
}

/// Gauss–Legendre nodes and weights on [0, 1] (5 points).
const GL5: [(f64, f64); 5] = [
    (0.046_910_077_030_668, 0.118_463_442_528_095),
    (0.230_765_344_947_158, 0.239_314_335_249_683),
    (0.5, 0.284_444_444_444_444),
    (0.769_234_655_052_842, 0.239_314_335_249_683),
    (0.953_089_922_969_332, 0.118_463_442_528_095),
];

/// The largest distance from a point inside `loops` (even-odd) to their sides, by a grid search
/// over their box refined around the best point. Zero for an empty or degenerate outline.
fn max_clearance(loops: &[Ring<Vec2>]) -> f64 {
    let sides: Vec<(Vec2, Vec2)> = loops.iter().flat_map(|pl| pl.edges().map(|(a, b)| (*a, *b))).filter(|(a, b)| a.dist(*b) > 0.0).collect();
    let corners: Aabb2 = sides.iter().map(|s| s.0).collect();
    if corners.is_empty() {
        return 0.0;
    }
    let Aabb2 { min: lo, max: hi } = corners;
    let inside = |p: Vec2| {
        let mut odd = false;
        for (a, b) in &sides {
            if (a.y > p.y) != (b.y > p.y) && p.x < a.x + (p.y - a.y) / (b.y - a.y) * (b.x - a.x) {
                odd = !odd;
            }
        }
        odd
    };
    let clearance = |p: Vec2| -> f64 {
        if !inside(p) {
            return 0.0;
        }
        sides
            .iter()
            .map(|(a, b)| {
                let ab = *b - *a;
                let t = ((p - *a).dot(ab) / ab.len2()).clamp(0.0, 1.0);
                p.dist(*a + ab * t)
            })
            .fold(f64::INFINITY, f64::min)
    };
    const N: usize = 32;
    let size = hi - lo;
    let mut best = (0.0, (lo + hi) * 0.5);
    for i in 0..=N {
        for j in 0..=N {
            let p = Vec2::new(lo.x + size.x * i as f64 / N as f64, lo.y + size.y * j as f64 / N as f64);
            let c = clearance(p);
            if c > best.0 {
                best = (c, p);
            }
        }
    }
    // Refine: try the eight neighbours, halving the step whenever none is better.
    let mut step = size.x.max(size.y) / N as f64;
    for _ in 0..60 {
        if step < size.x.max(size.y) * 1e-9 {
            break;
        }
        let around = [(1.0, 0.0), (-1.0, 0.0), (0.0, 1.0), (0.0, -1.0), (1.0, 1.0), (1.0, -1.0), (-1.0, 1.0), (-1.0, -1.0)];
        match around.iter().map(|(dx, dy)| best.1 + Vec2::new(dx * step, dy * step)).map(|p| (clearance(p), p)).max_by(|a, b| a.0.total_cmp(&b.0)) {
            Some(n) if n.0 > best.0 => best = n,
            _ => step *= 0.5,
        }
    }
    best.0
}

/// Most boundary segment pairs [`regions_apart`] compares before it gives up (and says no).
const APART_BUDGET: usize = 50_000_000;

/// Whether no two of the regions meet or come within `gap` of each other (their boundaries
/// are farther apart than `gap` and none lies inside another; one inside another's hole is
/// apart). Tools made from them alike (extruded over one interval) are then apart too, and
/// can be cut as one. False when unsure (a degenerate region, too much to compare).
pub fn regions_apart(regions: &[Region2], gap: f64) -> bool {
    if !(gap.is_finite() && gap > 0.0) || regions.len() > 10_000 {
        return false;
    }
    // The polylines lie within `tol` of the curves: boundaries this much farther than the gap
    // apart are apart.
    let tol = gap / 4.0;
    let reach = gap + 2.0 * tol;
    struct Outline {
        loops: Vec<Ring<Vec2>>,
        bounds: Aabb2,
        inside: Vec2,
    }
    let mut outlines = Vec::with_capacity(regions.len());
    for r in regions {
        let loops: Vec<Ring<Vec2>> = std::iter::once(&r.outer).chain(&r.holes).map(|l| l.polyline(tol)).collect();
        let Some(outer) = loops.first().filter(|l| l.len() >= 2) else { return false };
        if outer.iter().any(|p| !p.is_finite()) {
            return false;
        }
        let bounds = outer.bounds();
        let Some(inside) = outer.first().copied() else { return false };
        outlines.push(Outline { loops, bounds, inside });
    }
    let mut order: Vec<usize> = (0..outlines.len()).collect();
    order.sort_by(|&i, &j| {
        let x = |k: usize| outlines.get(k).map(|o| o.bounds.min.x).unwrap_or(0.0);
        x(i).total_cmp(&x(j))
    });
    let mut work = 0usize;
    for (k, &i) in order.iter().enumerate() {
        let Some(a) = outlines.get(i) else { return false };
        for &j in order.iter().skip(k + 1) {
            let Some(b) = outlines.get(j) else { return false };
            let (a_box, b_box) = (a.bounds, b.bounds);
            if b_box.min.x > a_box.max.x + reach {
                break;
            }
            if b_box.min.y > a_box.max.y + reach || a_box.min.y > b_box.max.y + reach {
                continue;
            }
            // A boundary point of one inside the other: one holds the other (boundaries that do
            // not come near each other do not cross).
            let (Some(ra), Some(rb)) = (regions.get(i), regions.get(j)) else { return false };
            if ra.contains(b.inside) || rb.contains(a.inside) {
                return false;
            }
            for la in &a.loops {
                for lb in &b.loops {
                    work = work.saturating_add(la.len().saturating_mul(lb.len()));
                    if work > APART_BUDGET {
                        return false;
                    }
                    // (Each loop closed: its last point back to its first.)
                    for (p, q) in la.iter().zip(la.iter().skip(1).chain(la.first())) {
                        for (r, s) in lb.iter().zip(lb.iter().skip(1).chain(lb.first())) {
                            if segment_distance(*p, *q, *r, *s) <= reach {
                                return false;
                            }
                        }
                    }
                }
            }
        }
    }
    true
}

/// The distance between segments `ab` and `cd` (0 where they cross).
fn segment_distance(a: Vec2, b: Vec2, c: Vec2, d: Vec2) -> f64 {
    let side = |p: Vec2, q: Vec2, r: Vec2| (q - p).cross(r - p);
    let (d1, d2, d3, d4) = (side(c, d, a), side(c, d, b), side(a, b, c), side(a, b, d));
    if ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0)) && ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0)) {
        return 0.0;
    }
    let to = |p: Vec2, s: Vec2, e: Vec2| {
        let v = e - s;
        let len2 = v.dot(v);
        let t = if len2 > 0.0 { ((p - s).dot(v) / len2).clamp(0.0, 1.0) } else { 0.0 };
        p.dist(s + v * t)
    };
    to(a, c, d).min(to(b, c, d)).min(to(c, a, b)).min(to(d, a, b))
}

/// The geometry of a profile segment ([`Seg2`]): evaluation, derivatives, lengths, splits and
/// closest points.
pub trait Seg2Geom {
    /// Checks a segment read from outside before anything evaluates it: every stored coordinate
    /// finite and at most `max_abs` in size (a Bézier's unused slots too, as they are serialized),
    /// a radius in 1e-12..=`max_abs`, an arc's start within ±1e6 radians and its absolute sweep
    /// 1e-12 to one turn (with 1e-12 radians of allowance), a conic weight in 1e-12..=1e12, a
    /// Bézier degree of 4 to [`MAX_BEZIER_DEGREE`], controls not all at one point, and finite
    /// ends. The limits keep evaluation finite; they promise no accuracy. The caller wraps the
    /// message in its own error.
    fn check(&self, max_abs: f64) -> Result<(), &'static str>;
    /// Derivative with respect to the parameter at `t` (Béziers and conics; lines and arcs too).
    fn derivative(&self, t: f64) -> Vec2;
    /// Derivatives 1…`order` with respect to the segment's own parameter at `t`, exactly: a line
    /// and an arc from their analytic form (an arc's are the circular-motion recurrence, zero
    /// curvature terms included), a cubic and a higher-degree piece from the forward differences
    /// of their controls, a conic through the quotient rule of its rational form. A blend curve
    /// reads a reference curve's derivatives here to build a Hermite interpolation, so this is
    /// exact at both ends (`t` = 0 and 1) and `None` — never a wrong number — when `order` is
    /// above [`MAX_DERIVATIVE_ORDER`], `t` is not finite or a value is not finite, as with a
    /// degenerate rational piece.
    fn derivatives(&self, t: f64, order: usize) -> Option<Vec<Vec2>>;
    fn start(&self) -> Vec2;
    fn end(&self) -> Vec2;
    fn point_at(&self, t: f64) -> Vec2;
    fn mid(&self) -> Vec2;
    /// Unit tangent at the start (direction of travel).
    fn start_tangent(&self) -> Vec2;
    /// Unit tangent at the end (direction of travel).
    fn end_tangent(&self) -> Vec2;
    fn reversed(&self) -> Seg2;
    /// The segment with each control point mapped by `f`: exact for any affine map of lines,
    /// Béziers and conics. An arc is returned as it is: only a similarity keeps it an arc
    /// ([`Seg2Geom::similar`]), and callers that mirror one handle it themselves.
    fn map_controls(&self, f: impl Fn(Vec2) -> Vec2) -> Seg2;
    /// The segment moved by the similarity `m`, exactly: an arc's centre maps, its radius scales
    /// and its start turns; every other kind maps its control points.
    fn similar(&self, m: &Similarity2) -> Seg2;
    fn length(&self) -> f64;
    /// The segment split at parameter `t` in (0, 1) (same kind, exact; conic halves are
    /// re-normalised so their end weights stay 1).
    fn split_at(&self, t: f64) -> (Seg2, Seg2);
    /// Parameter of the closest point: exact projection for lines,
    /// sampling followed by Newton for the remaining curves.
    fn closest_param(&self, p: Vec2) -> f64;
    /// The two halves of the segment (same kind, exact).
    fn split_half(&self) -> (Seg2, Seg2);
    /// Contribution to the loop's signed area (shoelace integral ½∮(x dy − y dx)).
    fn area_term(&self) -> f64;
    /// Polyline approximation (including both end points) with at most `tol` chord error.
    fn polyline(&self, tol: f64) -> Vec<Vec2>;
}

impl Seg2Geom for Seg2 {
    fn check(&self, max_abs: f64) -> Result<(), &'static str> {
        match *self {
            Seg2::Line { a, b } => controls(&[a, b], max_abs)?,
            Seg2::Arc { center, radius, start, sweep } => {
                coordinates([center.x, center.y], max_abs)?;
                require(radius.is_finite() && (MIN_POSITIVE..=max_abs).contains(&radius), "arc radius")?;
                require(start.is_finite() && start.abs() <= MAX_START_ANGLE, "arc start angle")?;
                require(sweep.is_finite() && (MIN_POSITIVE..=TAU + 1e-12).contains(&sweep.abs()), "arc sweep")?;
            }
            Seg2::Cubic { p0, p1, p2, p3 } => controls(&[p0, p1, p2, p3], max_abs)?,
            Seg2::Conic { a, apex, b, w } => {
                controls(&[a, apex, b], max_abs)?;
                require(w.is_finite() && (MIN_POSITIVE..=MAX_WEIGHT).contains(&w), "conic weight")?;
            }
            Seg2::Bezier { n, ref p } => {
                require((4..=MAX_BEZIER_DEGREE).contains(&usize::from(n)), "Bezier degree")?;
                // The unused slots are serialized too: reject hidden non-finite/excessive values.
                coordinates(p.iter().flat_map(|q| [q.x, q.y]), max_abs)?;
                controls(p.get(..=usize::from(n)).ok_or("Bezier degree")?, max_abs)?;
            }
        }
        require(self.start().is_finite() && self.end().is_finite(), "non-finite curve endpoint")
    }
    fn derivative(&self, t: f64) -> Vec2 {
        match *self {
            Seg2::Line { a, b } => b - a,
            Seg2::Arc { radius, start, sweep, .. } => Vec2::from_angle(start + sweep * t).perp() * (radius * sweep),
            Seg2::Cubic { p0, p1, p2, p3 } => {
                let u = 1.0 - t;
                (p1 - p0) * (3.0 * u * u) + (p2 - p1) * (6.0 * u * t) + (p3 - p2) * (3.0 * t * t)
            }
            Seg2::Conic { a, apex, b, w } => {
                let u = 1.0 - t;
                let (n, d) = (a * (u * u) + apex * (2.0 * w * u * t) + b * (t * t), u * u + 2.0 * w * u * t + t * t);
                let (dn, dd) = (a * (-2.0 * u) + apex * (2.0 * w * (1.0 - 2.0 * t)) + b * (2.0 * t), -2.0 * u + 2.0 * w * (1.0 - 2.0 * t) + 2.0 * t);
                (dn * d - n * dd) / (d * d).max(1e-300)
            }
            Seg2::Bezier { n, ref p } => {
                let c = bez(n, p);
                let diffs: Vec<Vec2> = c.windows(2).map(|w| (w[1] - w[0]) * (c.len() - 1) as f64).collect();
                casteljau(&diffs, t).0
            }
        }
    }
    fn derivatives(&self, t: f64, order: usize) -> Option<Vec<Vec2>> {
        if !t.is_finite() || order > MAX_DERIVATIVE_ORDER {
            return None;
        }
        let mut d = match *self {
            Seg2::Line { a, b } => {
                if !a.is_finite() || !b.is_finite() {
                    return None;
                }
                let mut d = vec![b - a];
                d.resize(MAX_DERIVATIVE_ORDER, Vec2::ZERO);
                d
            }
            Seg2::Arc { center, radius, start, sweep } => {
                if !center.is_finite() || !radius.is_finite() || !start.is_finite() || !sweep.is_finite() {
                    return None;
                }
                // Differentiating the radial direction twice returns its negative, so the
                // directions of the successive derivatives are tangential, radial, tangential…
                // with alternating signs, each order picking up one more factor of the sweep.
                let mut v = Vec2::from_angle(start + sweep * t).perp();
                let mut d = Vec::with_capacity(MAX_DERIVATIVE_ORDER);
                for j in 1..=MAX_DERIVATIVE_ORDER {
                    d.push(v * (radius * sweep.powi(j as i32)));
                    v = v.perp();
                }
                d
            }
            Seg2::Cubic { p0, p1, p2, p3 } => bezier_derivatives(&[p0, p1, p2, p3], t, MAX_DERIVATIVE_ORDER)?,
            Seg2::Bezier { n, ref p } => bezier_derivatives(bez(n, p), t, MAX_DERIVATIVE_ORDER)?,
            Seg2::Conic { a, apex, b, w } => {
                if !a.is_finite() || !apex.is_finite() || !b.is_finite() || !w.is_finite() {
                    return None;
                }
                // The conic is `N(t) / d(t)` with `N` the quadratic through `a`, `w·apex`, `b` and
                // `d` its weight polynomial; both are evaluated here in the power basis (at the
                // ends `d` = 1, so a join is never singular). The quotient rule in its
                // derivative-of-a-product form gives the higher derivatives: the numerator of
                // `x⁽ʲ⁾` is `N⁽ʲ⁾` minus the terms that already use `d` and a lower `x`.
                let (n0, n1, n2) = (a, apex * (2.0 * w) - a * 2.0, a - apex * (2.0 * w) + b);
                let (e1, e2) = (2.0 * (w - 1.0), 2.0 * (1.0 - w));
                let quotient = |j: usize| match j {
                    0 => n0 + n1 * t + n2 * (t * t),
                    1 => n1 + n2 * (2.0 * t),
                    2 => n2 * 2.0,
                    _ => Vec2::ZERO,
                };
                let weight = |j: usize| match j {
                    0 => 1.0 + e1 * t + e2 * (t * t),
                    1 => e1 + e2 * (2.0 * t),
                    2 => e2 * 2.0,
                    _ => 0.0,
                };
                let den = weight(0);
                if !(den.abs() > 1e-300) {
                    return None;
                }
                let mut x = vec![quotient(0) / den];
                for j in 1..=MAX_DERIVATIVE_ORDER {
                    let mut v = quotient(j);
                    for i in 1..=j {
                        v -= x[j - i] * (weight(i) * binom(j, i));
                    }
                    x.push(v / den);
                }
                x.remove(0);
                x
            }
        };
        d.truncate(order);
        d.iter().all(|q| q.is_finite()).then_some(d)
    }
    fn start(&self) -> Vec2 {
        match *self {
            Seg2::Line { a, .. } | Seg2::Conic { a, .. } => a,
            Seg2::Cubic { p0, .. } => p0,
            Seg2::Bezier { p, .. } => p[0],
            Seg2::Arc { center, radius, start, .. } => center + Vec2::from_angle(start) * radius,
        }
    }
    fn end(&self) -> Vec2 {
        match *self {
            Seg2::Line { b, .. } | Seg2::Conic { b, .. } => b,
            Seg2::Cubic { p3, .. } => p3,
            Seg2::Bezier { n, ref p } => bez(n, p).last().copied().unwrap_or(p[0]),
            Seg2::Arc { center, radius, start, sweep } => center + Vec2::from_angle(start + sweep) * radius,
        }
    }
    fn point_at(&self, t: f64) -> Vec2 {
        match *self {
            Seg2::Line { a, b } => a.lerp(b, t),
            Seg2::Arc { center, radius, start, sweep } => center + Vec2::from_angle(start + sweep * t) * radius,
            Seg2::Cubic { p0, p1, p2, p3 } => {
                let u = 1.0 - t;
                p0 * (u * u * u) + p1 * (3.0 * u * u * t) + p2 * (3.0 * u * t * t) + p3 * (t * t * t)
            }
            Seg2::Conic { a, apex, b, w } => {
                let u = 1.0 - t;
                let d = u * u + 2.0 * w * u * t + t * t;
                (a * (u * u) + apex * (2.0 * w * u * t) + b * (t * t)) / d.max(1e-300)
            }
            Seg2::Bezier { n, ref p } => casteljau(bez(n, p), t).0,
        }
    }
    fn mid(&self) -> Vec2 {
        self.point_at(0.5)
    }
    fn start_tangent(&self) -> Vec2 {
        match *self {
            Seg2::Line { a, b } => (b - a).normalized().unwrap_or(Vec2::X),
            Seg2::Arc { start, sweep, .. } => Vec2::from_angle(start).perp() * sweep.signum(),
            Seg2::Cubic { p0, p1, p2, .. } => (p1 - p0).normalized().or_else(|| (p2 - p0).normalized()).unwrap_or(Vec2::X),
            Seg2::Conic { a, apex, b, .. } => (apex - a).normalized().or_else(|| (b - a).normalized()).unwrap_or(Vec2::X),
            Seg2::Bezier { n, ref p } => {
                let c = bez(n, p);
                c.iter().skip(1).find_map(|q| (*q - c[0]).normalized()).unwrap_or(Vec2::X)
            }
        }
    }
    fn end_tangent(&self) -> Vec2 {
        match *self {
            Seg2::Line { a, b } => (b - a).normalized().unwrap_or(Vec2::X),
            Seg2::Arc { start, sweep, .. } => Vec2::from_angle(start + sweep).perp() * sweep.signum(),
            Seg2::Cubic { p1, p2, p3, .. } => (p3 - p2).normalized().or_else(|| (p3 - p1).normalized()).unwrap_or(Vec2::X),
            Seg2::Conic { a, apex, b, .. } => (b - apex).normalized().or_else(|| (b - a).normalized()).unwrap_or(Vec2::X),
            Seg2::Bezier { n, ref p } => {
                let c = bez(n, p);
                let last = c.last().copied().unwrap_or(p[0]);
                c.iter().rev().skip(1).find_map(|q| (last - *q).normalized()).unwrap_or(Vec2::X)
            }
        }
    }
    fn reversed(&self) -> Seg2 {
        match *self {
            Seg2::Line { a, b } => Seg2::Line { a: b, b: a },
            Seg2::Arc { center, radius, start, sweep } => Seg2::Arc { center, radius, start: start + sweep, sweep: -sweep },
            Seg2::Cubic { p0, p1, p2, p3 } => Seg2::Cubic { p0: p3, p1: p2, p2: p1, p3: p0 },
            Seg2::Conic { a, apex, b, w } => Seg2::Conic { a: b, apex, b: a, w },
            Seg2::Bezier { n, ref p } => {
                let mut q = *p;
                let k = (n as usize).clamp(1, MAX_BEZIER_DEGREE);
                q[..=k].reverse();
                Seg2::Bezier { n, p: q }
            }
        }
    }
    fn map_controls(&self, f: impl Fn(Vec2) -> Vec2) -> Seg2 {
        match *self {
            Seg2::Line { a, b } => Seg2::Line { a: f(a), b: f(b) },
            Seg2::Cubic { p0, p1, p2, p3 } => Seg2::Cubic { p0: f(p0), p1: f(p1), p2: f(p2), p3: f(p3) },
            Seg2::Conic { a, apex, b, w } => Seg2::Conic { a: f(a), apex: f(apex), b: f(b), w },
            Seg2::Bezier { n, mut p } => {
                p.iter_mut().take(usize::from(n) + 1).for_each(|q| *q = f(*q));
                Seg2::Bezier { n, p }
            }
            arc @ Seg2::Arc { .. } => arc,
        }
    }
    fn similar(&self, m: &Similarity2) -> Seg2 {
        match *self {
            Seg2::Arc { center, radius, start, sweep } => {
                Seg2::Arc { center: m.apply(center), radius: radius * m.scale(), start: start + m.angle(), sweep }
            }
            _ => self.map_controls(|p| m.apply(p)),
        }
    }
    fn length(&self) -> f64 {
        match *self {
            Seg2::Line { a, b } => a.dist(b),
            Seg2::Arc { radius, sweep, .. } => (radius * sweep).abs(),
            Seg2::Cubic { .. } | Seg2::Conic { .. } | Seg2::Bezier { .. } => integrate(self, |s, t| s.derivative(t).len()),
        }
    }
    fn split_at(&self, t: f64) -> (Seg2, Seg2) {
        let t = t.clamp(1e-9, 1.0 - 1e-9);
        match *self {
            Seg2::Line { a, b } => {
                let m = a.lerp(b, t);
                (Seg2::Line { a, b: m }, Seg2::Line { a: m, b })
            }
            Seg2::Arc { center, radius, start, sweep } => (
                Seg2::Arc { center, radius, start, sweep: sweep * t },
                Seg2::Arc { center, radius, start: start + sweep * t, sweep: sweep * (1.0 - t) },
            ),
            Seg2::Cubic { p0, p1, p2, p3 } => {
                let (a, b, c) = (p0.lerp(p1, t), p1.lerp(p2, t), p2.lerp(p3, t));
                let (d, e) = (a.lerp(b, t), b.lerp(c, t));
                let m = d.lerp(e, t);
                (Seg2::Cubic { p0, p1: a, p2: d, p3: m }, Seg2::Cubic { p0: m, p1: e, p2: c, p3 })
            }
            Seg2::Conic { a, apex, b, w } => {
                // Homogeneous de Casteljau: (a, 1), (w·apex, w), (b, 1).
                let h = |p: Vec2, wt: f64| (p * wt, wt);
                let lerp = |x: (Vec2, f64), y: (Vec2, f64)| (x.0 * (1.0 - t) + y.0 * t, x.1 * (1.0 - t) + y.1 * t);
                let (p0, p1, p2) = (h(a, 1.0), h(apex, w), h(b, 1.0));
                let (q0, q1) = (lerp(p0, p1), lerp(p1, p2));
                let r = lerp(q0, q1);
                let pt = |x: (Vec2, f64)| x.0 / x.1.max(1e-300);
                let m = pt(r);
                (
                    Seg2::Conic { a, apex: pt(q0), b: m, w: q0.1 / r.1.max(1e-300).sqrt() },
                    Seg2::Conic { a: m, apex: pt(q1), b, w: q1.1 / r.1.max(1e-300).sqrt() },
                )
            }
            Seg2::Bezier { n, ref p } => {
                let (_, l, r) = casteljau(bez(n, p), t);
                let mk = |c: &[Vec2]| bezier(c).unwrap_or(*self);
                (mk(&l), mk(&r))
            }
        }
    }
    fn closest_param(&self, p: Vec2) -> f64 {
        let finite = |p: Vec2| p.x.is_finite() && p.y.is_finite();
        match *self {
            Seg2::Line { a, b } if finite(a) && finite(b) && finite(p) => {
                let d = b - a;
                if a == b {
                    return 0.0;
                }
                let denominator = d.len2();
                let t = (p - a).dot(d) / denominator;
                if denominator > 0.0 && denominator.is_finite() && t.is_finite() {
                    return t.clamp(0.0, 1.0);
                }
            }
            _ => {}
        }
        let n = 64;
        let t = (0..=n).map(|i| i as f64 / n as f64).min_by(|x, y| self.point_at(*x).dist(p).total_cmp(&self.point_at(*y).dist(p))).unwrap_or(0.0);
        let t = newton_closest(self, p, t);
        // A closed segment (a full circle) starts where it ends: a point just before its start is
        // nearest just before its end, which Newton from the start (held there by the clamp)
        // never reaches. Try from the other end too.
        let (a, b) = (self.point_at(0.0), self.point_at(1.0));
        if (t == 0.0 || t == 1.0) && a.dist(b) <= 1e-12 * (1.0 + a.len()) {
            let other = newton_closest(self, p, 1.0 - t);
            if self.point_at(other).dist(p) < self.point_at(t).dist(p) {
                return other;
            }
        }
        t
    }
    fn split_half(&self) -> (Seg2, Seg2) {
        match *self {
            Seg2::Line { a, b } => {
                let m = a.lerp(b, 0.5);
                (Seg2::Line { a, b: m }, Seg2::Line { a: m, b })
            }
            Seg2::Arc { center, radius, start, sweep } => (
                Seg2::Arc { center, radius, start, sweep: sweep / 2.0 },
                Seg2::Arc { center, radius, start: start + sweep / 2.0, sweep: sweep / 2.0 },
            ),
            Seg2::Cubic { p0, p1, p2, p3 } => {
                let (a, b, c) = (p0.lerp(p1, 0.5), p1.lerp(p2, 0.5), p2.lerp(p3, 0.5));
                let (d, e) = (a.lerp(b, 0.5), b.lerp(c, 0.5));
                let m = d.lerp(e, 0.5);
                (Seg2::Cubic { p0, p1: a, p2: d, p3: m }, Seg2::Cubic { p0: m, p1: e, p2: c, p3 })
            }
            Seg2::Conic { a, apex, b, w } => {
                // Rational de Casteljau at the middle, weights normalised to 1 at the ends.
                let m = self.point_at(0.5);
                let w2 = ((1.0 + w) / 2.0).max(0.0).sqrt();
                let (l, r) = ((a + apex * w) / (1.0 + w), (apex * w + b) / (1.0 + w));
                (Seg2::Conic { a, apex: l, b: m, w: w2 }, Seg2::Conic { a: m, apex: r, b, w: w2 })
            }
            Seg2::Bezier { .. } => self.split_at(0.5),
        }
    }
    fn area_term(&self) -> f64 {
        match *self {
            Seg2::Line { a, b } => 0.5 * a.cross(b),
            Seg2::Arc { radius, sweep, .. } => {
                let (a, b) = (self.start(), self.end());
                // Chord term plus the circular segment between chord and arc.
                0.5 * a.cross(b) + 0.5 * radius * radius * (sweep - sweep.sin())
            }
            Seg2::Cubic { .. } | Seg2::Conic { .. } | Seg2::Bezier { .. } => integrate(self, |s, t| 0.5 * s.point_at(t).cross(s.derivative(t))),
        }
    }
    fn polyline(&self, tol: f64) -> Vec<Vec2> {
        match *self {
            Seg2::Line { a, b } => vec![a, b],
            Seg2::Arc { radius, sweep, .. } => {
                let tol = tol.max(radius.abs() * 1e-6).max(1e-9);
                let step = if tol < radius { 2.0 * (1.0 - tol / radius).clamp(-1.0, 1.0).acos() } else { TAU / 8.0 };
                let n = ((sweep.abs() / step.max(1e-6)).ceil() as usize).clamp(2, 4096);
                (0..=n).map(|i| self.point_at(i as f64 / n as f64)).collect()
            }
            Seg2::Cubic { p0, p1, p2, p3 } => {
                // Chord error of n pieces ≈ max second difference / (8 n²).
                let bow = (p0 - p1 * 2.0 + p2).len().max((p1 - p2 * 2.0 + p3).len()) * 6.0;
                let n = ((bow / (8.0 * tol.max(1e-9))).sqrt().ceil() as usize).clamp(2, 4096);
                (0..=n).map(|i| self.point_at(i as f64 / n as f64)).collect()
            }
            Seg2::Conic { a, apex, b, w } => {
                let bow = (a - apex * 2.0 + b).len() * 2.0 * w.max(1.0);
                let n = ((bow / (8.0 * tol.max(1e-9))).sqrt().ceil() as usize).clamp(2, 4096);
                (0..=n).map(|i| self.point_at(i as f64 / n as f64)).collect()
            }
            Seg2::Bezier { n, ref p } => {
                // Second derivative ≤ n(n−1) × the largest second difference of the controls.
                let c = bez(n, p);
                let d2 = c.windows(3).map(|w| (w[0] - w[1] * 2.0 + w[2]).len()).fold(0.0, f64::max) * (n as f64) * (n as f64 - 1.0);
                let k = ((d2 / (8.0 * tol.max(1e-9))).sqrt().ceil() as usize).clamp(2, 4096);
                (0..=k).map(|i| self.point_at(i as f64 / k as f64)).collect()
            }
        }
    }
}

/// The geometry of a profile loop ([`Loop2`]): area, orientation, containment and polylines.
pub trait Loop2Geom {
    /// The radius of the largest circle inside the loop, to about `tol` ([`Region2Geom::inradius`]).
    fn inradius(&self, tol: f64) -> f64;
    /// Signed area: positive when counter-clockwise.
    fn signed_area(&self) -> f64;
    fn reversed(&self) -> Loop2;
    /// Whether the loop runs counter-clockwise ([`Loop2::ccw`] keeps it as it is).
    fn is_ccw(&self) -> bool;
    /// Counter-clockwise copy.
    fn ccw(&self) -> Loop2;
    /// Each segment with the next and the last with the first: the loop's joints, where one
    /// segment should end on the start of the next.
    fn joints(&self) -> impl Iterator<Item = (&Seg2, &Seg2)> + Clone;
    /// The loop as a polyline within `tol`: each segment's points but its last, which the next
    /// segment starts on.
    fn polyline(&self, tol: f64) -> Ring<Vec2>;
    /// Even-odd point containment against the polyline approximation.
    fn contains(&self, p: Vec2) -> bool;
    /// Area-weighted centroid (of the polyline approximation).
    fn centroid(&self) -> Vec2;
    /// Closed within `tol`?
    fn is_closed(&self, tol: f64) -> bool;
}

impl Loop2Geom for Loop2 {
    fn inradius(&self, tol: f64) -> f64 {
        max_clearance(&[self.polyline(tol)])
    }
    fn signed_area(&self) -> f64 {
        self.segs.iter().map(Seg2::area_term).sum()
    }
    fn reversed(&self) -> Loop2 {
        Loop2 { segs: self.segs.iter().rev().map(Seg2::reversed).collect() }
    }
    fn is_ccw(&self) -> bool {
        self.signed_area() >= 0.0
    }
    fn ccw(&self) -> Loop2 {
        if self.is_ccw() { self.clone() } else { self.reversed() }
    }
    fn joints(&self) -> impl Iterator<Item = (&Seg2, &Seg2)> + Clone {
        crate::chain::around(&self.segs)
    }
    fn polyline(&self, tol: f64) -> Ring<Vec2> {
        self.segs
            .iter()
            .flat_map(|s| {
                let p = s.polyline(tol);
                let n = p.len().saturating_sub(1);
                p.into_iter().take(n)
            })
            .collect()
    }
    fn contains(&self, p: Vec2) -> bool {
        self.polyline(1e-3).contains(p)
    }
    fn centroid(&self) -> Vec2 {
        let poly = self.polyline(1e-3);
        let n = poly.len();
        let (mut a2, mut c) = (0.0, Vec2::ZERO);
        for i in 0..n {
            let (Some(p), Some(q)) = (poly.get(i), poly.get((i + 1) % n)) else { continue };
            let k = p.cross(*q);
            a2 += k;
            c += (*p + *q) * k;
        }
        if a2.abs() < 1e-15 { poly.first().copied().unwrap_or_default() } else { c / (3.0 * a2) }
    }
    fn is_closed(&self, tol: f64) -> bool {
        let n = self.segs.len();
        n > 0
            && (0..n).all(|i| match (self.segs.get(i), self.segs.get((i + 1) % n)) {
                (Some(a), Some(b)) => a.end().dist(b.start()) <= tol,
                _ => false,
            })
    }
}

/// The geometry of a profile region ([`Region2`]): area, containment, inradius and triangles.
pub trait Region2Geom {
    fn area(&self) -> f64;
    /// A point strictly inside the region (for picking and labels).
    fn interior_point(&self) -> Vec2;
    fn contains(&self, p: Vec2) -> bool;
    /// The radius of the largest circle inside the region: how far its sides can move inwards
    /// before they meet (a taper going in closes it there). Found by a grid search refined
    /// around the best point, to about `tol`.
    fn inradius(&self, tol: f64) -> f64;
    /// Triangles covering the region (for filled display), by slabs between the vertex
    /// heights: inside each slab the boundary edges don't cross, so consecutive crossings pair
    /// up into trapezoids.
    fn triangulate(&self, tol: f64) -> Vec<[Vec2; 3]>;
    fn centroid(&self) -> Vec2;
}

impl Region2Geom for Region2 {
    fn area(&self) -> f64 {
        self.outer.signed_area().abs() - self.holes.iter().map(|h| h.signed_area().abs()).sum::<f64>()
    }
    fn interior_point(&self) -> Vec2 {
        let c = self.centroid();
        if self.contains(c) {
            return c;
        }
        // Scan a few horizontal lines for the midpoint of the widest inside span.
        let poly = self.outer.polyline(1e-2);
        let (mut y0, mut y1) = (f64::INFINITY, f64::NEG_INFINITY);
        for p in &poly {
            y0 = y0.min(p.y);
            y1 = y1.max(p.y);
        }
        for k in 1..16 {
            let y = y0 + (y1 - y0) * k as f64 / 16.0;
            let mut xs: Vec<f64> = Vec::new();
            for l in std::iter::once(&self.outer).chain(&self.holes) {
                let pl = l.polyline(1e-2);
                let n = pl.len();
                for i in 0..n {
                    let (Some(a), Some(b)) = (pl.get(i), pl.get((i + 1) % n)) else { continue };
                    if (a.y > y) != (b.y > y) {
                        xs.push(a.x + (y - a.y) / (b.y - a.y) * (b.x - a.x));
                    }
                }
            }
            xs.sort_by(f64::total_cmp);
            for w in xs.chunks(2) {
                if let [a, b] = w {
                    let p = Vec2::new((a + b) * 0.5, y);
                    if self.contains(p) {
                        return p;
                    }
                }
            }
        }
        c
    }
    fn contains(&self, p: Vec2) -> bool {
        self.outer.contains(p) && !self.holes.iter().any(|h| h.contains(p))
    }
    fn inradius(&self, tol: f64) -> f64 {
        let loops: Vec<Ring<Vec2>> = std::iter::once(&self.outer).chain(&self.holes).map(|l| l.polyline(tol)).collect();
        max_clearance(&loops)
    }
    fn triangulate(&self, tol: f64) -> Vec<[Vec2; 3]> {
        let mut edges: Vec<(Vec2, Vec2)> = Vec::new();
        for l in std::iter::once(&self.outer).chain(&self.holes) {
            let pl = l.polyline(tol);
            let n = pl.len();
            for i in 0..n {
                let (Some(a), Some(b)) = (pl.get(i), pl.get((i + 1) % n)) else { continue };
                if (a.y - b.y).abs() > 1e-12 {
                    edges.push(if a.y < b.y { (*a, *b) } else { (*b, *a) });
                }
            }
        }
        if edges.len() > 20_000 {
            return Vec::new();
        }
        let mut ys: Vec<f64> = edges.iter().flat_map(|(a, b)| [a.y, b.y]).collect();
        ys.sort_by(f64::total_cmp);
        ys.dedup_by(|a, b| (*a - *b).abs() < 1e-12);
        let x_at = |e: &(Vec2, Vec2), y: f64| e.0.x + (y - e.0.y) / (e.1.y - e.0.y) * (e.1.x - e.0.x);
        // Sweep upward: an edge joins the slabs once its lower end is passed and leaves after
        // its upper end, so each slab sorts only the edges crossing it (a finely sampled ring
        // has hundreds of slabs and edges, but four edges in each slab).
        edges.sort_by(|a, b| a.0.y.total_cmp(&b.0.y));
        let mut next = 0;
        let mut span: Vec<&(Vec2, Vec2)> = Vec::new();
        let mut out = Vec::new();
        for w in ys.windows(2) {
            let (y0, y1) = (w[0], w[1]);
            let ym = (y0 + y1) * 0.5;
            while let Some(e) = edges.get(next)
                && e.0.y <= ym
            {
                span.push(e);
                next += 1;
            }
            span.retain(|e| e.1.y >= ym);
            span.sort_by(|a, b| x_at(a, ym).total_cmp(&x_at(b, ym)));
            for pair in span.chunks(2) {
                let [l, r] = pair else { continue };
                let (a, b) = (Vec2::new(x_at(l, y0), y0), Vec2::new(x_at(r, y0), y0));
                let (c, d) = (Vec2::new(x_at(r, y1), y1), Vec2::new(x_at(l, y1), y1));
                out.push([a, b, c]);
                out.push([a, c, d]);
            }
        }
        out
    }
    fn centroid(&self) -> Vec2 {
        let ao = self.outer.signed_area().abs();
        let mut c = self.outer.centroid() * ao;
        let mut a = ao;
        for h in &self.holes {
            let ah = h.signed_area().abs();
            c -= h.centroid() * ah;
            a -= ah;
        }
        if a.abs() < 1e-15 { self.outer.centroid() } else { c / a }
    }
}

// Helpers of Seg2Geom.
fn bez(n: u8, p: &[Vec2; MAX_BEZIER_CTRL]) -> &[Vec2] {
    &p[..(n as usize).clamp(1, MAX_BEZIER_DEGREE) + 1]
}
/// Newton's method for the parameter of the point nearest `p`, from `t`, within [0, 1].
fn newton_closest(seg: &Seg2, p: Vec2, mut t: f64) -> f64 {
    for _ in 0..30 {
        let (q, d) = (seg.point_at(t), seg.derivative(t));
        let (d2, h) = ((seg.derivative((t + 1e-6).min(1.0)) - seg.derivative((t - 1e-6).max(0.0))) / 2e-6, q - p);
        let f = h.dot(d);
        let df = d.dot(d) + h.dot(d2);
        if df.abs() < 1e-300 {
            break;
        }
        let nt = (t - f / df).clamp(0.0, 1.0);
        if (nt - t).abs() < 1e-14 {
            t = nt;
            break;
        }
        t = nt;
    }
    t
}
/// ∫₀¹ f(t) dt by composite Gauss–Legendre (16 pieces of 5 points).
fn integrate(seg: &Seg2, f: impl Fn(&Seg2, f64) -> f64) -> f64 {
    let n = 16;
    let mut sum = 0.0;
    for k in 0..n {
        let (t0, h) = (k as f64 / n as f64, 1.0 / n as f64);
        for (x, w) in GL5 {
            sum += w * h * f(seg, t0 + x * h);
        }
    }
    sum
}

#[cfg(test)]
mod tests {
    use super::*;

    fn square(x: f64, y: f64, size: f64) -> Loop2 {
        Loop2::polygon(&[Vec2::new(x, y), Vec2::new(x + size, y), Vec2::new(x + size, y + size), Vec2::new(x, y + size)])
    }

    fn solid(l: Loop2) -> Region2 {
        Region2 { outer: l, holes: Vec::new() }
    }

    /// #1602: the largest circle inside a region, which bounds how far a taper can go.
    #[test]
    fn inradius_of_rectangles_circles_and_rings() {
        let close = |a: f64, b: f64| (a - b).abs() < 1e-3 * b.max(1.0);
        let rect = Loop2::polygon(&[Vec2::new(0.0, 0.0), Vec2::new(10.0, 0.0), Vec2::new(10.0, 4.0), Vec2::new(0.0, 4.0)]);
        assert!(close(solid(rect.clone()).inradius(1e-3), 2.0), "{}", solid(rect.clone()).inradius(1e-3));
        assert!(close(rect.inradius(1e-3), 2.0));
        let disc = Loop2::circle(Vec2::new(3.0, -2.0), 5.0);
        assert!(close(solid(disc.clone()).inradius(1e-4), 5.0), "{}", solid(disc).inradius(1e-4));
        // A ring 10 to 6: the material is 4 wide (radius 2); the hole alone has radius 6.
        let ring = Region2 { outer: Loop2::circle(Vec2::ZERO, 10.0), holes: vec![Loop2::circle(Vec2::ZERO, 6.0).reversed()] };
        assert!(close(ring.inradius(1e-4), 2.0), "{}", ring.inradius(1e-4));
        assert!(close(ring.holes[0].inradius(1e-4), 6.0));
        assert_eq!(Region2::default().inradius(1e-3), 0.0);
    }

    #[test]
    fn regions_are_apart_only_when_nothing_meets_or_holds_another() {
        let gap = 1e-3;
        // Side by side, a millimetre apart.
        assert!(regions_apart(&[solid(square(0.0, 0.0, 5.0)), solid(square(6.0, 0.0, 5.0))], gap));
        // Touching along a side, or at a corner, or closer than the gap: not apart.
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 5.0)), solid(square(5.0, 0.0, 5.0))], gap));
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 5.0)), solid(square(5.0, 5.0, 5.0))], gap));
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 5.0)), solid(square(5.0005, 0.0, 5.0))], gap));
        // Overlapping, or one inside another: not apart.
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 5.0)), solid(square(3.0, 3.0, 5.0))], gap));
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 10.0)), solid(square(2.0, 2.0, 2.0))], gap));
        // Inside another's hole, clear of its edge: apart (a letter in the middle of an O).
        let ring = Region2 { outer: square(0.0, 0.0, 10.0), holes: vec![square(2.0, 2.0, 6.0).reversed()] };
        assert!(regions_apart(&[ring.clone(), solid(square(4.0, 4.0, 2.0))], gap));
        // Filling the hole: its edge is the hole's.
        assert!(!regions_apart(&[ring, solid(square(2.0, 2.0, 6.0))], gap));
        // Curved boundaries: two circles a little apart, then touching.
        assert!(regions_apart(&[solid(Loop2::circle(Vec2::ZERO, 1.0)), solid(Loop2::circle(Vec2::new(2.01, 0.0), 1.0))], gap));
        assert!(!regions_apart(&[solid(Loop2::circle(Vec2::ZERO, 1.0)), solid(Loop2::circle(Vec2::new(2.0, 0.0), 1.0))], gap));
        // Nothing to compare, and nonsense gaps.
        assert!(regions_apart(&[], gap) && regions_apart(&[solid(square(0.0, 0.0, 1.0))], gap));
        assert!(!regions_apart(&[solid(square(0.0, 0.0, 1.0)), solid(square(5.0, 0.0, 1.0))], f64::NAN));
    }

    #[test]
    fn closest_line_projection_and_degeneracy() {
        let line = Seg2::Line { a: Vec2::new(-3.0, 4.0), b: Vec2::new(7.0, 4.0) };
        for (p, t) in [(Vec2::new(-9.0, 20.0), 0.0), (Vec2::new(2.0, -5.0), 0.5), (Vec2::new(15.0, 4.0), 1.0)] {
            assert_eq!(line.closest_param(p), t);
            assert_eq!(line.reversed().closest_param(p), 1.0 - t);
        }
        let a = Vec2::new(1e100, -1e100);
        let b = a + Vec2::new(1e90, 2e90);
        let large = Seg2::Line { a, b };
        assert!((large.closest_param(a.lerp(b, 0.5)) - 0.5).abs() < 1e-6);
        assert_eq!(Seg2::Line { a, b: a }.closest_param(Vec2::ZERO), 0.0);
        let tiny = Seg2::Line { a: Vec2::ZERO, b: Vec2::new(1e-12, 0.0) };
        assert_eq!(tiny.closest_param(Vec2::new(0.5e-12, 1.0)), 0.5);
        for line in [line, line.reversed(), tiny] {
            for k in 0..53 {
                let p = Vec2::new((k * 17 % 37) as f64 - 18.0, (k * 31 % 29) as f64 - 14.0);
                let closest = line.point_at(line.closest_param(p)).dist(p);
                let dense = (0..=8192).map(|i| line.point_at(i as f64 / 8192.0).dist(p)).fold(f64::INFINITY, f64::min);
                assert!(closest <= dense + 1e-12);
            }
        }
    }

    fn sampled_closest(s: &Seg2, p: Vec2) -> f64 {
        let mut t = (0..=64).map(|i| i as f64 / 64.0).min_by(|x, y| s.point_at(*x).dist(p).total_cmp(&s.point_at(*y).dist(p))).unwrap_or(0.0);
        for _ in 0..30 {
            let (q, d) = (s.point_at(t), s.derivative(t));
            let (d2, h) = ((s.derivative((t + 1e-6).min(1.0)) - s.derivative((t - 1e-6).max(0.0))) / 2e-6, q - p);
            let df = d.dot(d) + h.dot(d2);
            if df.abs() < 1e-300 {
                break;
            }
            let nt = (t - h.dot(d) / df).clamp(0.0, 1.0);
            if (nt - t).abs() < 1e-14 {
                t = nt;
                break;
            }
            t = nt;
        }
        t
    }

    #[test]
    fn closest_projection_preserves_clearance_tolerance_and_generic_fallback() {
        use std::f64::consts::TAU;
        let curves = [
            Seg2::Line { a: Vec2::new(-4.0, 7.0), b: Vec2::new(3.0, -2.0) },
            Seg2::Arc { center: Vec2::new(3.0, -2.0), radius: 6.0, start: 5.9, sweep: 1.3 },
            Seg2::Arc { center: Vec2::ZERO, radius: 2.0, start: 0.2, sweep: -TAU },
            Seg2::Arc { center: Vec2::ZERO, radius: 2.0, start: 0.0, sweep: TAU },
            Seg2::Arc { center: Vec2::ZERO, radius: 2.0, start: 0.0, sweep: 0.0 },
            Seg2::Arc { center: Vec2::ZERO, radius: 2.0, start: 0.0, sweep: 1e-12 },
            Seg2::Cubic { p0: Vec2::ZERO, p1: Vec2::new(2.0, 7.0), p2: Vec2::new(6.0, -3.0), p3: Vec2::new(8.0, 4.0) },
        ];
        for (i, s) in curves.iter().enumerate() {
            for k in 0..101 {
                let p = Vec2::new((k * 17 % 37) as f64 - 18.0, (k * 31 % 29) as f64 - 14.0);
                let old = sampled_closest(s, p);
                let new = s.closest_param(p);
                if i > 0 {
                    assert_eq!(new.to_bits(), old.to_bits());
                }
                assert!(s.point_at(new).dist(p) <= s.point_at(old).dist(p) + 1e-10);
                let on_curve = s.point_at(k as f64 / 100.0);
                assert!(s.point_at(s.closest_param(on_curve)).dist(on_curve) < 1e-9);
            }
        }
        // A full circle's points just before its start, either way round: nearest just before
        // its end, not at its start (Newton from the start stays held there).
        for sweep in [TAU, -TAU] {
            let circle = Seg2::Arc { center: Vec2::new(1.0, 2.0), radius: 5.0, start: 0.6131, sweep };
            for delta in [1e-4, 0.01, 0.04] {
                let before = 0.6131 - delta * sweep.signum();
                let p = Vec2::new(1.0, 2.0) + Vec2::from_angle(before) * 4.99;
                assert!((circle.point_at(circle.closest_param(p)).dist(p) - 0.01).abs() < 1e-9, "sweep {sweep}, {delta}");
            }
        }
    }

    /// The sweep visits only the edges crossing each slab; it must give the triangles that
    /// testing every edge against every slab gives, for a finely sampled ring too (#164).
    #[test]
    fn triangulation_sweep_matches_every_edge_against_every_slab() {
        fn every_edge(r: &Region2, tol: f64) -> Vec<[Vec2; 3]> {
            let mut edges = Vec::new();
            for l in std::iter::once(&r.outer).chain(&r.holes) {
                let pl = l.polyline(tol);
                for i in 0..pl.len() {
                    let (a, b) = (pl[i], pl[(i + 1) % pl.len()]);
                    if (a.y - b.y).abs() > 1e-12 {
                        edges.push(if a.y < b.y { (a, b) } else { (b, a) });
                    }
                }
            }
            let mut ys: Vec<f64> = edges.iter().flat_map(|(a, b): &(Vec2, Vec2)| [a.y, b.y]).collect();
            ys.sort_by(f64::total_cmp);
            ys.dedup_by(|a, b| (*a - *b).abs() < 1e-12);
            let x_at = |e: &(Vec2, Vec2), y: f64| e.0.x + (y - e.0.y) / (e.1.y - e.0.y) * (e.1.x - e.0.x);
            let mut out = Vec::new();
            for w in ys.windows(2) {
                let ym = (w[0] + w[1]) * 0.5;
                let mut span: Vec<_> = edges.iter().filter(|e| e.0.y <= ym && e.1.y >= ym).collect();
                span.sort_by(|a, b| x_at(a, ym).total_cmp(&x_at(b, ym)));
                for pair in span.chunks(2) {
                    let [l, r] = pair else { continue };
                    let (a, b) = (Vec2::new(x_at(l, w[0]), w[0]), Vec2::new(x_at(r, w[0]), w[0]));
                    let (c, d) = (Vec2::new(x_at(r, w[1]), w[1]), Vec2::new(x_at(l, w[1]), w[1]));
                    out.extend([[a, b, c], [a, c, d]]);
                }
            }
            out
        }
        let comb = Loop2::polygon(&[
            Vec2::new(0.0, 0.0),
            Vec2::new(9.0, 0.0),
            Vec2::new(9.0, 6.0),
            Vec2::new(7.0, 2.0),
            Vec2::new(5.0, 7.0),
            Vec2::new(3.0, 2.5),
            Vec2::new(1.0, 6.0),
        ]);
        let ring = Region2 { outer: Loop2::circle(Vec2::ZERO, 45.0), holes: vec![Loop2::circle(Vec2::ZERO, 40.0).reversed()] };
        let regions = [Region2 { outer: comb, holes: vec![Loop2::circle(Vec2::new(4.5, 1.2), 0.6).reversed()] }, ring];
        for (r, tol) in regions.iter().zip([1e-3, 1e-4]) {
            let tris = r.triangulate(tol);
            assert!(tris.len() > 100);
            assert_eq!(tris, every_edge(r, tol));
        }
    }

    #[test]
    fn triangulated_area() {
        let sq = Loop2::polygon(&[Vec2::new(0.0, 0.0), Vec2::new(10.0, 0.0), Vec2::new(10.0, 8.0), Vec2::new(5.0, 3.0), Vec2::new(0.0, 8.0)]);
        let r = Region2 { outer: sq, holes: vec![Loop2::circle(Vec2::new(3.0, 1.5), 1.0).reversed()] };
        let tris = r.triangulate(1e-3);
        let a: f64 = tris.iter().map(|[a, b, c]| (*b - *a).cross(*c - *a).abs() * 0.5).sum();
        // The circle is a polyline within the tolerance, so the areas agree to about that.
        assert!((a - r.area()).abs() < 1e-3 * r.area(), "{a} vs {}", r.area());
        for [a, b, c] in &tris {
            let m = (*a + *b + *c) / 3.0;
            assert!((*b - *a).cross(*c - *a).abs() < 1e-12 || r.contains(m), "{m:?}");
        }
    }

    #[test]
    fn areas() {
        let sq = Loop2::polygon(&[Vec2::new(0.0, 0.0), Vec2::new(4.0, 0.0), Vec2::new(4.0, 3.0), Vec2::new(0.0, 3.0)]);
        assert!((sq.signed_area() - 12.0).abs() < 1e-12);
        assert!((sq.reversed().signed_area() + 12.0).abs() < 1e-12);
        let c = Loop2::circle(Vec2::new(5.0, 5.0), 2.0);
        assert!((c.signed_area() - std::f64::consts::PI * 4.0).abs() < 1e-9);
        assert!(c.is_closed(1e-9));
        let r = Region2 { outer: Loop2::circle(Vec2::ZERO, 10.0), holes: vec![Loop2::circle(Vec2::ZERO, 5.0).reversed()] };
        assert!((r.area() - std::f64::consts::PI * 75.0).abs() < 1e-9);
        let ip = r.interior_point();
        assert!(r.contains(ip), "{ip:?}");
        assert!(sq.contains(Vec2::new(1.0, 1.0)) && !sq.contains(Vec2::new(5.0, 1.0)));
        assert!(sq.centroid().dist(Vec2::new(2.0, 1.5)) < 1e-9);
    }
}