GitCorner

Code

ossartcraftcadcraft🌐
a770fa5a5e5f
//! Shared curve geometry for the M1/M2 draw and modify commands: arc constructions, tangent
//! circles (TTR/TTT), length parametrisation of curves, spline splitting and picking helpers.

use cadcraft_doc::{Entity, EntityKind, Handle, Prim};
use cadcraft_geom::{Arc, Circle, EPS, Line, PolyVertex, Polyline, Segment, Spline, TAU, Vec2, circle_circle, line_circle, line_line_infinite};

use crate::{EngineError, Result, Session};

/// Hard cap on generated vertices/points from user-sized inputs.
pub const MAX_GEN: usize = 20_000;

/// A keyword-only prompt: spaces separate inputs (like Enter), as at AutoCAD's option prompts.
pub const KW: crate::Accept = crate::Accept { point: false, number: false, text: false, select: false, enter: true };

// ---------------- picking ----------------

pub fn pick_aperture(s: &Session) -> f64 {
    s.pixel_size() * s.settings.pickbox.max(1.0) * 1.5
}

/// The object under `p` in the current space (or the one named for `p`: [`Session::pick_object`]).
pub fn pick_at(s: &Session, p: Vec2) -> Option<Handle> {
    s.pick_object(&s.space(), p, pick_aperture(s)).ok().flatten()
}

pub fn entity(s: &Session, h: Handle) -> Result<Entity> {
    s.doc()?.entity(h).map(|e| (**e).clone()).ok_or_else(|| EngineError::Other("no such object".into()))
}

pub fn handle_value(v: &serde_json::Value) -> Option<Handle> {
    v.as_str().and_then(Handle::parse_hex).or_else(|| v.as_u64().map(Handle))
}

pub fn handle_param(p: &serde_json::Value, key: &str) -> Option<Handle> {
    p.get(key).and_then(handle_value)
}

/// Is the entity on a locked layer, or outside the working set while a block reference is edited in place (REFEDIT)?
pub fn is_locked(s: &Session, h: Handle) -> bool {
    s.doc().ok().is_some_and(|d| d.entity(h).and_then(|e| d.layer(&e.common.layer)).is_some_and(|l| l.locked) || super::blocks::refedit::locked(d, h))
}

// ---------------- arc constructions ----------------

pub(crate) fn finite_arc(a: Arc) -> Option<Arc> {
    (a.center.is_finite() && a.radius.is_finite() && a.radius > EPS && a.start.is_finite() && a.end.is_finite()).then_some(a)
}

/// Arc from start, center and a signed included angle (CCW positive).
pub fn arc_sca(st: Vec2, c: Vec2, angle: f64) -> Option<Arc> {
    let r = st.dist(c);
    if !angle.is_finite() || angle.abs() < 1e-12 {
        return None;
    }
    let a0 = c.angle_to(st);
    let a = angle.clamp(-TAU, TAU);
    finite_arc(if a > 0.0 { Arc::new(c, r, a0, a0 + a) } else { Arc::new(c, r, a0 + a, a0) })
}

/// Arc from start, center and chord length (positive: CCW minor arc, negative: CCW major arc).
pub fn arc_scl(st: Vec2, c: Vec2, chord: f64) -> Option<Arc> {
    let r = st.dist(c);
    if r <= EPS || !chord.is_finite() || chord.abs() < 1e-12 || chord.abs() > 2.0 * r + 1e-9 {
        return None;
    }
    let theta = 2.0 * (chord.abs() / (2.0 * r)).clamp(-1.0, 1.0).asin();
    let sweep = if chord > 0.0 { theta } else { TAU - theta };
    arc_sca(st, c, sweep)
}

/// Arc from start and end points with a signed included angle (CCW positive).
pub fn arc_sea(st: Vec2, en: Vec2, angle: f64) -> Option<Arc> {
    if !angle.is_finite() || angle.abs() < 1e-9 || angle.abs() >= TAU - 1e-9 || st.near(en, EPS) {
        return None;
    }
    let (a, b, th) = if angle > 0.0 { (st, en, angle) } else { (en, st, -angle) };
    let chord = a.dist(b);
    let r = chord / (2.0 * (th / 2.0).sin());
    let h = (chord / 2.0) / (th / 2.0).tan();
    let c = a.mid(b) + (b - a).normalized().perp() * h;
    finite_arc(Arc::new(c, r.abs(), c.angle_to(a), c.angle_to(b)))
}

/// Arc from start and end points with the tangent direction at the start.
pub fn arc_sed(st: Vec2, en: Vec2, dir: Vec2) -> Option<Arc> {
    let d = dir.normalized();
    if d == Vec2::ZERO || st.near(en, EPS) {
        return None;
    }
    let n = d.perp();
    let v = en - st;
    let den = 2.0 * n.dot(v);
    if den.abs() < 1e-12 * v.len().max(1.0) {
        return None;
    }
    let t = v.len2() / den;
    let c = st + n * t;
    let r = c.dist(st);
    finite_arc(if t > 0.0 { Arc::new(c, r, c.angle_to(st), c.angle_to(en)) } else { Arc::new(c, r, c.angle_to(en), c.angle_to(st)) })
}

/// Arc from start and end points with a radius (CCW; negative radius gives the major arc).
pub fn arc_ser(st: Vec2, en: Vec2, radius: f64) -> Option<Arc> {
    let r = radius.abs();
    let chord = st.dist(en);
    if !radius.is_finite() || chord < EPS || r < chord / 2.0 - 1e-9 {
        return None;
    }
    let h = (r * r - chord * chord / 4.0).max(0.0).sqrt();
    let left = (en - st).normalized().perp();
    let c = if radius > 0.0 { st.mid(en) + left * h } else { st.mid(en) - left * h };
    finite_arc(Arc::new(c, r, c.angle_to(st), c.angle_to(en)))
}

/// End point and outgoing unit tangent of the last line/arc/open polyline in the current space
/// (ARC "Continue" and LINE continuation).
pub fn last_curve_end(s: &Session) -> Option<(Vec2, Vec2)> {
    let d = s.doc().ok()?;
    let space = s.space();
    let store = d.space(&space)?;
    for e in store.iter().collect::<Vec<_>>().into_iter().rev() {
        match &e.kind {
            EntityKind::Line(l) => {
                let dir = (l.b.xy() - l.a.xy()).normalized();
                if dir != Vec2::ZERO {
                    return Some((l.b.xy(), dir));
                }
            }
            EntityKind::Arc(a) => {
                let g = Arc::new(a.center.xy(), a.radius, a.start, a.end);
                // Arcs are stored CCW: one drawn clockwise ended on its start point, so continue
                // from the last picked point (LASTPOINT), leaving it in the drawing direction.
                let tol = 1e-9 * g.radius.max(1.0);
                if g.start_point().near(s.last_point, tol) && !g.end_point().near(s.last_point, tol) {
                    return Some((g.start_point(), -Vec2::from_angle(g.start).perp()));
                }
                return Some((g.end_point(), Vec2::from_angle(g.end).perp()));
            }
            EntityKind::LwPolyline(p) if !p.closed => {
                let segs = Polyline { vertices: p.vertices.clone(), closed: false }.segments();
                if let Some(sg) = segs.last() {
                    return Some((sg.end(), sg.tangent(1.0)));
                }
            }
            _ => {}
        }
    }
    None
}

/// Signed bulge of the arc from `a` through `m` to `b` (0 when collinear).
pub fn bulge_through(a: Vec2, m: Vec2, b: Vec2) -> f64 {
    let Some(arc) = Arc::from_3_points(a, m, b) else { return 0.0 };
    let sw = arc.sweep();
    if arc.start_point().near(a, 1e-6 * arc.radius.max(1.0)) { cadcraft_geom::arc_to_bulge(sw) } else { cadcraft_geom::arc_to_bulge(-sw) }
}

/// Bulge of the arc from `a` to `b` leaving `a` along `tangent`.
pub fn bulge_from_tangent(a: Vec2, b: Vec2, tangent: Vec2) -> f64 {
    let c = b - a;
    let t = tangent.normalized();
    if c.len() < EPS || t == Vec2::ZERO {
        return 0.0;
    }
    let alpha = t.cross(c).atan2(t.dot(c));
    cadcraft_geom::arc_to_bulge(2.0 * alpha)
}

// ---------------- tangent circles ----------------

/// A tangency target: an infinite line or a full circle.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum TanObj {
    Line(Line),
    Circle(Circle),
}

impl TanObj {
    /// From an entity and the pick point (polylines use the picked segment).
    pub fn from_kind(k: &EntityKind, pick: Vec2) -> Option<TanObj> {
        match k {
            EntityKind::Line(l) => {
                let ln = Line::new(l.a.xy(), l.b.xy());
                (ln.len() > EPS).then_some(TanObj::Line(ln))
            }
            EntityKind::Circle(c) => Some(TanObj::Circle(Circle::new(c.center.xy(), c.radius))),
            EntityKind::Arc(a) => Some(TanObj::Circle(Circle::new(a.center.xy(), a.radius))),
            EntityKind::Ray(r) | EntityKind::XLine(r) => Some(TanObj::Line(Line::new(r.base.xy(), r.base.xy() + r.dir.xy()))),
            EntityKind::LwPolyline(p) => {
                let segs = Polyline { vertices: p.vertices.clone(), closed: p.closed }.segments();
                let sg = segs.iter().min_by(|a, b| a.closest(pick).dist(pick).total_cmp(&b.closest(pick).dist(pick)))?;
                Some(match sg {
                    Segment::Line(l) => TanObj::Line(*l),
                    Segment::Arc { arc, .. } => TanObj::Circle(Circle::new(arc.center, arc.radius)),
                })
            }
            _ => None,
        }
    }
    /// The point where a circle `c` tangent to this object touches it.
    pub fn touch(&self, c: &Circle) -> Vec2 {
        match self {
            TanObj::Line(l) => l.project(c.center),
            TanObj::Circle(k) => {
                let d = (c.center - k.center).normalized();
                let d = if d == Vec2::ZERO { Vec2::X } else { d };
                let p1 = k.center + d * k.radius;
                let p2 = k.center - d * k.radius;
                if (p1.dist(c.center) - c.radius).abs() <= (p2.dist(c.center) - c.radius).abs() { p1 } else { p2 }
            }
        }
    }
    /// Tangency residual of circle `(c, r)`: zero when tangent.
    fn residual(&self, c: Vec2, r: f64) -> f64 {
        match self {
            TanObj::Line(l) => l.dist_inf(c) - r,
            TanObj::Circle(k) => {
                let d = c.dist(k.center);
                (d - (k.radius + r)).abs().min((d - (k.radius - r).abs()).abs())
            }
        }
    }
    fn offsets(&self, r: f64) -> Vec<TanObj> {
        match self {
            TanObj::Line(l) => vec![TanObj::Line(l.offset(r)), TanObj::Line(l.offset(-r))],
            TanObj::Circle(k) => {
                let mut v = vec![TanObj::Circle(Circle::new(k.center, k.radius + r))];
                if (k.radius - r).abs() > EPS {
                    v.push(TanObj::Circle(Circle::new(k.center, (k.radius - r).abs())));
                }
                v
            }
        }
    }
}

trait InfDist {
    fn dist_inf(&self, p: Vec2) -> f64;
}
impl InfDist for Line {
    fn dist_inf(&self, p: Vec2) -> f64 {
        self.project(p).dist(p)
    }
}

fn intersect_tan(a: &TanObj, b: &TanObj) -> Vec<Vec2> {
    match (a, b) {
        (TanObj::Line(x), TanObj::Line(y)) => line_line_infinite(x.a, x.b, y.a, y.b).map(|r| vec![r.0]).unwrap_or_default(),
        (TanObj::Line(l), TanObj::Circle(c)) | (TanObj::Circle(c), TanObj::Line(l)) => line_circle(l, c).into_iter().map(|x| x.0).collect(),
        (TanObj::Circle(x), TanObj::Circle(y)) => circle_circle(x, y),
    }
}

/// Score a candidate: how far its tangent points are from the picks.
fn score(c: &Circle, objs: &[(TanObj, Vec2)]) -> f64 {
    objs.iter().map(|(o, p)| o.touch(c).dist(*p)).sum()
}

/// Circle of radius `r` tangent to two objects, nearest the pick points.
pub fn ttr(o1: TanObj, p1: Vec2, o2: TanObj, p2: Vec2, r: f64) -> Option<Circle> {
    if !(r.is_finite() && r > EPS) {
        return None;
    }
    let objs = [(o1, p1), (o2, p2)];
    let mut best: Option<(f64, Circle)> = None;
    for a in o1.offsets(r) {
        for b in o2.offsets(r) {
            for c in intersect_tan(&a, &b) {
                let ci = Circle::new(c, r);
                if !c.is_finite() || o1.residual(c, r).abs() > 1e-6 * r.max(1.0) || o2.residual(c, r).abs() > 1e-6 * r.max(1.0) {
                    continue;
                }
                let sc = score(&ci, &objs);
                if best.is_none_or(|(b, _)| sc < b) {
                    best = Some((sc, ci));
                }
            }
        }
    }
    best.map(|(_, c)| c)
}

/// Solve a 3×3 linear system (Cramer's rule).
fn solve3(m: [[f64; 3]; 3], b: [f64; 3]) -> Option<[f64; 3]> {
    let det = |m: &[[f64; 3]; 3]| {
        m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1]) - m[0][1] * (m[1][0] * m[2][2] - m[1][2] * m[2][0])
            + m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0])
    };
    let d = det(&m);
    if !d.is_finite() || d.abs() < 1e-14 {
        return None;
    }
    let mut out = [0.0; 3];
    for (k, o) in out.iter_mut().enumerate() {
        let mut mk = m;
        for (row, bv) in mk.iter_mut().zip(b.iter()) {
            row[k] = *bv;
        }
        *o = det(&mk) / d;
    }
    Some(out)
}

/// A signed tangency equation f(x, y, r) = 0 with its gradient.
#[derive(Clone, Copy)]
enum Eq3 {
    /// n·p + c = s r (unit normal n).
    Line { n: Vec2, c: f64, s: f64 },
    /// |p − k| = R + s r (s = ±1), or r − R when `enclose`.
    Circle { k: Vec2, rr: f64, s: f64, enclose: bool },
}

impl Eq3 {
    fn eval(&self, x: [f64; 3]) -> (f64, [f64; 3]) {
        let p = Vec2::new(x[0], x[1]);
        let r = x[2];
        match *self {
            Eq3::Line { n, c, s } => (n.dot(p) + c - s * r, [n.x, n.y, -s]),
            Eq3::Circle { k, rr, s, enclose } => {
                let d = p - k;
                let l = d.len().max(1e-12);
                let g = [d.x / l, d.y / l];
                if enclose { (l - (r - rr), [g[0], g[1], -1.0]) } else { (l - (rr + s * r), [g[0], g[1], -s]) }
            }
        }
    }
}

fn eq_variants(o: &TanObj) -> Vec<Eq3> {
    match o {
        TanObj::Line(l) => {
            let n = (l.b - l.a).normalized().perp();
            let c = -n.dot(l.a);
            vec![Eq3::Line { n, c, s: 1.0 }, Eq3::Line { n, c, s: -1.0 }]
        }
        TanObj::Circle(k) => vec![
            Eq3::Circle { k: k.center, rr: k.radius, s: 1.0, enclose: false },
            Eq3::Circle { k: k.center, rr: k.radius, s: -1.0, enclose: false },
            Eq3::Circle { k: k.center, rr: k.radius, s: 0.0, enclose: true },
        ],
    }
}

/// Circle tangent to three objects, nearest the pick points (Newton on all sign combinations).
pub fn ttt(objs: [(TanObj, Vec2); 3]) -> Option<Circle> {
    let [(o1, p1), (o2, p2), (o3, p3)] = objs;
    let mut starts: Vec<[f64; 3]> = Vec::new();
    let cen = (p1 + p2 + p3) / 3.0;
    let rad = (cen.dist(p1) + cen.dist(p2) + cen.dist(p3)) / 3.0;
    starts.push([cen.x, cen.y, rad.max(1e-3)]);
    if let Some(c) = Circle::from_3_points(p1, p2, p3) {
        starts.push([c.center.x, c.center.y, c.radius]);
    }
    let mut best: Option<(f64, Circle)> = None;
    let scale = rad.max(p1.dist(p2)).max(1e-6);
    for e1 in eq_variants(&o1) {
        for e2 in eq_variants(&o2) {
            for e3 in eq_variants(&o3) {
                for st in &starts {
                    let mut x = *st;
                    let mut converged = false;
                    for _ in 0..60 {
                        let (f1, g1) = e1.eval(x);
                        let (f2, g2) = e2.eval(x);
                        let (f3, g3) = e3.eval(x);
                        if f1.abs().max(f2.abs()).max(f3.abs()) < 1e-11 * scale {
                            converged = true;
                            break;
                        }
                        let Some(dx) = solve3([g1, g2, g3], [-f1, -f2, -f3]) else { break };
                        for (xi, di) in x.iter_mut().zip(dx) {
                            *xi += di;
                        }
                        if !x.iter().all(|v| v.is_finite()) {
                            break;
                        }
                    }
                    if !converged || x[2] <= 1e-9 * scale || x[2] > 1e6 * scale {
                        continue;
                    }
                    let c = Circle::new(Vec2::new(x[0], x[1]), x[2]);
                    let sc = score(&c, &objs);
                    if best.is_none_or(|(b, _)| sc < b - 1e-12) {
                        best = Some((sc, c));
                    }
                }
            }
        }
    }
    best.map(|(_, c)| c)
}

// ---------------- curves as segment chains ----------------

/// A curve flattened to lines/arcs (exact for lines, arcs, circles and polylines; tessellated for
/// ellipses, splines and 3D polylines).
#[derive(Clone, Debug, Default)]
pub struct Chain {
    pub segs: Vec<Segment>,
    pub closed: bool,
}

impl Chain {
    pub fn of(k: &EntityKind) -> Option<Chain> {
        let tess = |pts: Vec<Vec2>, closed: bool| Chain {
            segs: pts.windows(2).filter_map(|w| Some(Segment::Line(Line::new(*w.first()?, *w.get(1)?)))).filter(|s| s.len() > 1e-15).collect(),
            closed,
        };
        let c = match k {
            EntityKind::Line(l) => Chain { segs: vec![Segment::Line(Line::new(l.a.xy(), l.b.xy()))], closed: false },
            EntityKind::Arc(a) => {
                Chain { segs: vec![Segment::Arc { arc: Arc::new(a.center.xy(), a.radius, a.start, a.end), ccw: true }], closed: false }
            }
            EntityKind::Circle(c) => {
                let o = c.center.xy();
                Chain {
                    segs: vec![
                        Segment::Arc { arc: Arc::new(o, c.radius, 0.0, std::f64::consts::PI), ccw: true },
                        Segment::Arc { arc: Arc::new(o, c.radius, std::f64::consts::PI, TAU), ccw: true },
                    ],
                    closed: true,
                }
            }
            EntityKind::LwPolyline(p) => Chain { segs: Polyline { vertices: p.vertices.clone(), closed: p.closed }.segments(), closed: p.closed },
            EntityKind::Polyline3d(p) => {
                let mut pts: Vec<Vec2> = p.points.iter().map(|q| q.xy()).collect();
                if p.closed
                    && let Some(f) = pts.first().copied()
                {
                    pts.push(f);
                }
                tess(pts, p.closed)
            }
            EntityKind::Ellipse(e) => {
                let ge = cadcraft_geom::Ellipse { center: e.center.xy(), major: e.major.xy(), ratio: e.ratio, start: e.start, end: e.end };
                let mut pts = Vec::new();
                ge.tessellate(e.major.xy().len() * 1e-4, &mut pts);
                tess(pts, ge.is_full())
            }
            EntityKind::Spline(sp) => tess(sp.tessellate(1e-4), sp.closed),
            _ => return None,
        };
        (!c.segs.is_empty()).then_some(c)
    }
    pub fn len(&self) -> f64 {
        self.segs.iter().map(Segment::len).sum()
    }
    pub fn start(&self) -> Option<Vec2> {
        self.segs.first().map(Segment::start)
    }
    pub fn end(&self) -> Option<Vec2> {
        self.segs.last().map(Segment::end)
    }
    /// Point and unit tangent at arc length `d` from the start (clamped).
    pub fn at_length(&self, d: f64) -> Option<(Vec2, Vec2)> {
        self.at_length_in(&self.end_lengths(), d)
    }
    /// The arc length from the chain's start to the end of each segment, for [`Self::at_length_in`].
    pub fn end_lengths(&self) -> Vec<f64> {
        self.segs
            .iter()
            .scan(0.0, |acc, s| {
                *acc += s.len();
                Some(*acc)
            })
            .collect()
    }
    /// [`Self::at_length`] with the segment end lengths computed once (`ends` from
    /// [`Self::end_lengths`]), so many samples along one chain each cost a binary search.
    pub fn at_length_in(&self, ends: &[f64], d: f64) -> Option<(Vec2, Vec2)> {
        let first = ends.partition_point(|e| d > e + 1e-12);
        // A segment of no length can't hold the point; the next one that has length does.
        // `ends` never decreases, so the first segment past `first` with length is found by search
        // (a run of zero-length segments can be long) instead of a scan.
        let base = first.checked_sub(1).and_then(|p| ends.get(p)).copied().unwrap_or(0.0);
        let i = first + ends.get(first..).unwrap_or_default().partition_point(|e| *e <= base);
        let i = (i < self.segs.len()).then_some(i);
        if let Some(s) = i.and_then(|i| self.segs.get(i)) {
            let start = i.and_then(|i| i.checked_sub(1)).and_then(|p| ends.get(p)).copied().unwrap_or(0.0);
            let t = ((d - start) / s.len()).clamp(0.0, 1.0);
            return Some((s.at(t), s.tangent(t)));
        }
        self.segs.last().map(|s| (s.end(), s.tangent(1.0)))
    }
    /// Arc length of the point on the chain nearest `p`.
    pub fn length_of(&self, p: Vec2) -> f64 {
        let mut acc = 0.0;
        let mut best = (f64::INFINITY, 0.0);
        for s in &self.segs {
            let c = s.closest(p);
            let dd = c.dist(p);
            if dd < best.0 {
                best = (dd, acc + seg_param(s, c) * s.len());
            }
            acc += s.len();
        }
        best.1
    }
    /// The curve parameter of the point on the chain nearest `p`: the index of its segment plus
    /// the fraction along it (AutoCAD's polyline parameter; 0..1 along a line or an arc).
    pub fn param_of(&self, p: Vec2) -> f64 {
        let mut best = (f64::INFINITY, 0.0);
        for (i, s) in self.segs.iter().enumerate() {
            let c = s.closest(p);
            let dd = c.dist(p);
            if dd < best.0 {
                best = (dd, i as f64 + seg_param(s, c));
            }
        }
        best.1
    }
    /// Reversed copy.
    pub fn reversed(&self) -> Chain {
        Chain { segs: self.segs.iter().rev().map(Segment::reversed).collect(), closed: self.closed }
    }
    /// Polyline vertices for the chain.
    pub fn vertices(&self) -> Vec<PolyVertex> {
        let mut vs: Vec<PolyVertex> = self
            .segs
            .iter()
            .map(|s| PolyVertex {
                p: s.start(),
                bulge: match s {
                    Segment::Line(_) => 0.0,
                    Segment::Arc { arc, ccw } => cadcraft_geom::arc_to_bulge(if *ccw { arc.sweep() } else { -arc.sweep() }),
                },
                ..Default::default()
            })
            .collect();
        if !self.closed
            && let Some(e) = self.end()
        {
            vs.push(PolyVertex::new(e));
        }
        vs
    }
}

/// The polyline parameter of the point nearest `p` on spans `(start, end, bulge)` taken from the
/// source vertices: the span's index plus the fraction along it. Unlike [`Chain::param_of`] it
/// counts zero-length spans, which a polyline's parameter range includes (one per vertex) but its
/// chain drops.
pub fn vertex_param_of(spans: &[(Vec2, Vec2, f64)], p: Vec2) -> f64 {
    let mut best = (f64::INFINITY, 0.0);
    for (i, &(a, b, bulge)) in spans.iter().enumerate() {
        if a.near(b, EPS) {
            continue;
        }
        let seg = match cadcraft_geom::bulge_to_arc(a, b, bulge) {
            Some((arc, ccw)) => Segment::Arc { arc, ccw },
            None => Segment::Line(Line::new(a, b)),
        };
        let c = seg.closest(p);
        let dd = c.dist(p);
        if dd < best.0 {
            best = (dd, i as f64 + seg_param(&seg, c));
        }
    }
    best.1
}

/// Parameter (0..1 along travel) of a point on a segment.
pub fn seg_param(s: &Segment, p: Vec2) -> f64 {
    match s {
        Segment::Line(l) => l.param_of(p).clamp(0.0, 1.0),
        Segment::Arc { arc, ccw } => {
            let t = (cadcraft_geom::norm_angle(arc.center.angle_to(p) - arc.start) / arc.sweep().max(1e-15)).clamp(0.0, 1.0);
            if *ccw { t } else { 1.0 - t }
        }
    }
}

/// Distance from `p` to an entity's geometry (prims; text and blocks by insertion point).
pub fn kind_distance(k: &EntityKind, p: Vec2) -> f64 {
    k.prims()
        .iter()
        .map(|pr| match pr {
            Prim::Seg(s) => s.closest(p).dist(p),
            Prim::Circle(c) => c.closest(p).dist(p),
            Prim::Ellipse(e) => e.closest(p).dist(p),
            Prim::Spline(sp) => {
                let pts = sp.tessellate(1e-3);
                pts.windows(2).filter_map(|w| Some(Line::new(*w.first()?, *w.get(1)?).closest(p).dist(p))).fold(f64::INFINITY, f64::min)
            }
            Prim::Point(q) => q.dist(p),
            Prim::Infinite { base, dir, .. } => Line::new(*base, *base + *dir).project(p).dist(p),
            Prim::Fill(f) => {
                let n = f.len();
                (0..n).filter_map(|i| Some(Line::new(*f.get(i)?, *f.get((i + 1) % n)?).closest(p).dist(p))).fold(f64::INFINITY, f64::min)
            }
        })
        .fold(f64::INFINITY, f64::min)
}

// ---------------- splines ----------------

/// Split a spline at parameter `t` into (left, right). `None` at the ends.
pub fn split_spline(sp: &Spline, t: f64) -> Option<(Spline, Spline)> {
    sp.split_at(t)
}

/// The part of a spline between parameters `a < b`.
pub fn sub_spline(sp: &Spline, a: f64, b: f64) -> Option<Spline> {
    sp.sub_between(a, b)
}

/// Parameter of the point on the spline nearest `p`.
pub fn spline_param_of(sp: &Spline, p: Vec2) -> f64 {
    let (lo, hi) = sp.domain();
    let n = 400;
    let mut best = (f64::INFINITY, lo);
    for i in 0..=n {
        let t = lo + (hi - lo) * i as f64 / n as f64;
        let d = sp.eval(t).dist(p);
        if d < best.0 {
            best = (d, t);
        }
    }
    let step = (hi - lo) / n as f64;
    let (mut a, mut b) = ((best.1 - step).max(lo), (best.1 + step).min(hi));
    for _ in 0..60 {
        let m1 = a + (b - a) / 3.0;
        let m2 = b - (b - a) / 3.0;
        if sp.eval(m1).dist(p) < sp.eval(m2).dist(p) {
            b = m2;
        } else {
            a = m1;
        }
    }
    (a + b) / 2.0
}

/// Reverse a spline's direction (control, weights, fit points and knots).
pub fn reverse_spline(sp: &Spline) -> Spline {
    sp.reversed()
}

/// Reverse an LWPOLYLINE's vertex order, keeping its shape (bulges and widths move with segments).
pub fn reverse_vertices(vs: &[PolyVertex], closed: bool) -> Vec<PolyVertex> {
    let n = vs.len();
    if n < 2 {
        return vs.to_vec();
    }
    (0..n)
        .map(|k| {
            let p = vs.get(n - 1 - k).map(|v| v.p).unwrap_or_default();
            let seg = (2 * n - 2 - k) % n; // old segment index reversed into new segment k
            let has_seg = closed || k + 1 < n;
            match (has_seg, vs.get(seg)) {
                (true, Some(o)) => PolyVertex { p, bulge: -o.bulge, start_width: o.end_width, end_width: o.start_width },
                _ => PolyVertex::new(p),
            }
        })
        .collect()
}

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

    /// The indexed lookup gives the point and tangent a scan from the start gives, also past the
    /// ends and over a segment of no length.
    #[test]
    fn at_length_in_matches_a_scan() {
        let l = |a: (f64, f64), b: (f64, f64)| Segment::Line(Line::new(Vec2::new(a.0, a.1), Vec2::new(b.0, b.1)));
        let c = Chain {
            segs: vec![l((0.0, 0.0), (0.0, 0.0)), l((0.0, 0.0), (4.0, 0.0)), l((4.0, 0.0), (4.0, 0.0)), l((4.0, 0.0), (4.0, 3.0))],
            closed: false,
        };
        let ends = c.end_lengths();
        for d in [-1.0, 0.0, 1.5, 4.0, 4.0 + 1e-13, 5.0, 7.0, 9.0] {
            // The scan this replaced.
            let mut acc = 0.0;
            let mut want = c.segs.last().map(|s| (s.end(), s.tangent(1.0)));
            for s in &c.segs {
                let len = s.len();
                if d <= acc + len + 1e-12 && len > 0.0 {
                    let t = ((d - acc) / len).clamp(0.0, 1.0);
                    want = Some((s.at(t), s.tangent(t)));
                    break;
                }
                acc += len;
            }
            assert_eq!(c.at_length_in(&ends, d), want, "d = {d}");
            assert_eq!(c.at_length(d), want);
        }
    }

    #[test]
    fn arc_builders() {
        let a = arc_sca(Vec2::new(1.0, 0.0), Vec2::ZERO, std::f64::consts::FRAC_PI_2).unwrap();
        assert!(a.end_point().near(Vec2::new(0.0, 1.0), 1e-9));
        let b = arc_sea(Vec2::new(1.0, 0.0), Vec2::new(-1.0, 0.0), std::f64::consts::PI).unwrap();
        assert!(b.center.near(Vec2::ZERO, 1e-9));
        assert!(b.mid_point().near(Vec2::new(0.0, 1.0), 1e-9));
        let c = arc_sed(Vec2::new(1.0, 0.0), Vec2::new(-1.0, 0.0), Vec2::Y).unwrap();
        assert!(c.mid_point().near(Vec2::new(0.0, 1.0), 1e-9));
        let d = arc_ser(Vec2::new(1.0, 0.0), Vec2::new(-1.0, 0.0), 1.0).unwrap();
        assert!(d.center.near(Vec2::ZERO, 1e-9));
        let e = arc_scl(Vec2::new(1.0, 0.0), Vec2::ZERO, 2f64.sqrt()).unwrap();
        assert!(e.end_point().near(Vec2::new(0.0, 1.0), 1e-9));
        assert!(arc_scl(Vec2::new(1.0, 0.0), Vec2::ZERO, 5.0).is_none());
        assert!((bulge_through(Vec2::new(1.0, 0.0), Vec2::new(0.0, 1.0), Vec2::new(-1.0, 0.0)) - 1.0).abs() < 1e-9);
        assert!((bulge_through(Vec2::new(-1.0, 0.0), Vec2::new(0.0, 1.0), Vec2::new(1.0, 0.0)) + 1.0).abs() < 1e-9);
    }

    #[test]
    fn tangent_circles() {
        let l1 = TanObj::Line(Line::new(Vec2::ZERO, Vec2::new(10.0, 0.0)));
        let l2 = TanObj::Line(Line::new(Vec2::ZERO, Vec2::new(0.0, 10.0)));
        let c = ttr(l1, Vec2::new(3.0, 0.0), l2, Vec2::new(0.0, 3.0), 1.0).unwrap();
        assert!(c.center.near(Vec2::new(1.0, 1.0), 1e-9));
        let l3 = TanObj::Line(Line::new(Vec2::new(4.0, 0.0), Vec2::new(0.0, 3.0)));
        let inc = ttt([(l1, Vec2::new(2.0, 0.0)), (l2, Vec2::new(0.0, 1.0)), (l3, Vec2::new(2.0, 1.5))]).unwrap();
        assert!(inc.center.near(Vec2::new(1.0, 1.0), 1e-6), "{inc:?}");
        assert!((inc.radius - 1.0).abs() < 1e-6);
        let k = TanObj::Circle(Circle::new(Vec2::new(5.0, 0.0), 2.0));
        let c2 = ttr(l2, Vec2::new(0.0, 0.0), k, Vec2::new(3.0, 0.0), 1.5).unwrap();
        assert!((c2.center.x - 1.5).abs() < 1e-9);
    }

    #[test]
    fn spline_split_and_reverse() {
        let sp = Spline::from_control(vec![Vec2::ZERO, Vec2::new(1.0, 2.0), Vec2::new(3.0, 2.0), Vec2::new(4.0, 0.0)], 3);
        let (lo, hi) = sp.domain();
        let t = lo + (hi - lo) * 0.3;
        let (l, r) = split_spline(&sp, t).unwrap();
        let p = sp.eval(t);
        assert!(l.eval(l.domain().1).near(p, 1e-9));
        assert!(r.eval(r.domain().0).near(p, 1e-9));
        assert!(r.eval(r.domain().1).near(Vec2::new(4.0, 0.0), 1e-9));
        let mid = sp.eval(lo + (hi - lo) * 0.6);
        assert!(r.eval(r.domain().0 + (r.domain().1 - r.domain().0) * (0.3 / 0.7)).near(mid, 1e-9));
        let rv = reverse_spline(&sp);
        assert!(rv.eval(rv.domain().0).near(Vec2::new(4.0, 0.0), 1e-9));
        assert!((spline_param_of(&sp, p) - t).abs() < 1e-6);
        let sub = sub_spline(&sp, lo + 0.2 * (hi - lo), lo + 0.8 * (hi - lo)).unwrap();
        assert!(sub.eval(sub.domain().0).near(sp.eval(lo + 0.2 * (hi - lo)), 1e-9));
    }

    #[test]
    fn reverse_polyline_vertices() {
        let vs = vec![PolyVertex::with_bulge(Vec2::ZERO, 0.5), PolyVertex::new(Vec2::new(1.0, 0.0)), PolyVertex::new(Vec2::new(1.0, 1.0))];
        let r = reverse_vertices(&vs, false);
        assert!(r[0].p.near(Vec2::new(1.0, 1.0), 0.0));
        assert_eq!(r[0].bulge, 0.0);
        assert!((r[1].bulge + 0.5).abs() < 1e-12);
        assert_eq!(r[2].bulge, 0.0);
        let r2 = reverse_vertices(&r, false);
        assert_eq!(r2, vs);
    }
}