Function segment_segment

src/model/kernel.rs:127–191

Classify how segments `a -> b` and `c -> d` relate in the XY plane. Crossing vs not is decided by exact orientation signs; crossing vs touching, and near-miss touches, by metric distance ([`XY_TOL`]).

(a: DVec2, b: DVec2, c: DVec2, d: DVec2)

    let o1 = orient2d(c, d, a);
    let o2 = orient2d(c, d, b);
    let o3 = orient2d(a, b, c);
    let o4 = orient2d(a, b, d);

    // Exact proper-crossing test: each segment's endpoints straddle the
    // other's supporting line (allowing exactly-on-line as straddling so a
    // vertex sitting exactly on the other segment still yields a point).
    let straddles = (o1 >= 0.0) != (o2 >= 0.0) || (o1 > 0.0) != (o2 > 0.0);
    let straddled = (o3 >= 0.0) != (o4 >= 0.0) || (o3 > 0.0) != (o4 > 0.0);
    if straddles && straddled {
        let r = b - a;
        let s = d - c;
        let denom = r.perp_dot(s);
        // A true crossing guarantees denom != 0; the division is
        // well-conditioned because the straddle test already bounded the
        // configuration away from parallel-and-disjoint.
        let t = ((c - a).perp_dot(s) / denom).clamp(0.0, 1.0);
        let u = ((c - a).perp_dot(r) / denom).clamp(0.0, 1.0);
        let point = a + r * t;
        let near_endpoint = point.distance(a) <= XY_TOL || point.distance(b) <= XY_TOL || point.distance(c) <= XY_TOL || point.distance(d) <= XY_TOL;
        return if near_endpoint {
            SegSeg::Touching { point, t, u }
        } else {
            SegSeg::Crossing { point, t, u }
        };
    }

    // No exact crossing: the segments may still pass within XY_TOL of each
    // other at an endpoint (a touch that drifted apart by float noise).
    let candidates = [(a, c, d, 0.0, None), (b, c, d, 1.0, None), (c, a, b, 0.0, Some(())), (d, a, b, 1.0, Some(()))];
    let mut best: Option<(f64, DVec2, f64, f64)> = None;
    for (p, s0, s1, fixed_param, swapped) in candidates {
        let (proj, param) = project_onto_segment(p, s0, s1);
        let dist = p.distance(proj);
        if dist <= XY_TOL && best.is_none_or(|(bd, ..)| dist < bd) {
            let (t, u) = if swapped.is_some() { (param, fixed_param) } else { (fixed_param, param) };
            best = Some((dist, proj, t, u));
        }
    }
    if let Some((_, point, t, u)) = best {
        return SegSeg::Touching { point, t, u };
    }
    SegSeg::Disjoint
}

/// Signed perpendicular distance in metres from `point` to the directed line
/// `a -> b`. Positive on the left of the line; sign is exact (via
/// [`orient2d`]), magnitude is approximate. Returns `0.0` for a degenerate
/// (zero-length) edge.
pub(crate) fn signed_distance_to_line(point: DVec2, a: DVec2, b: DVec2) -> f64 {
    let len = a.distance(b);
    if len == 0.0 {
        return 0.0;
    }
    orient2d(a, b, point) / len
}

/// Closest point on segment `a -> b` to `p`, with its clamped parameter.
pub(crate) fn project_onto_segment(p: DVec2, a: DVec2, b: DVec2) -> (DVec2, f64) {