Function line_intersection

nodedb-spatial/src/predicates/intersection.rs:174–187

Compute the intersection point of two line segments (as infinite lines).

(a1: [f64; 2], a2: [f64; 2], b1: [f64; 2], b2: [f64; 2])

/// Compute the intersection point of two line segments (as infinite lines).
fn line_intersection(a1: [f64; 2], a2: [f64; 2], b1: [f64; 2], b2: [f64; 2]) -> Option<[f64; 2]> {
    let dx_a = a2[0] - a1[0];
    let dy_a = a2[1] - a1[1];
    let dx_b = b2[0] - b1[0];
    let dy_b = b2[1] - b1[1];

    let denom = dx_a * dy_b - dy_a * dx_b;
    if denom.abs() < 1e-15 {
        return None; // Parallel lines.
    }

    let t = ((b1[0] - a1[0]) * dy_b - (b1[1] - a1[1]) * dx_b) / denom;
    Some([a1[0] + t * dx_a, a1[1] + t * dy_a])
}

/// Strip the closing vertex from a ring if present.
fn strip_closing(ring: &[[f64; 2]]) -> Vec<[f64; 2]> {