836: Line Segment Intersection Detection

Difficulty: 4 Level: Advanced Determine whether two line segments intersect using cross-product orientation tests — robust, branchless, and degenerate-case aware.

The Problem This Solves

Given two line segments AB and CD in the plane, do they intersect? This elementary computational geometry primitive appears in collision detection (game physics, robotics), map overlay algorithms (GIS), circuit board routing (do two wire segments cross?), and as the inner test in sweep-line algorithms for the general line segment intersection problem. The naïve approach — compute the intersection point by solving the linear system — fails on parallel segments and requires careful handling of the collinear case. The cross-product orientation approach is cleaner: it works purely with sign tests, handles all degenerate cases naturally, and avoids division entirely (important for exact arithmetic with integer coordinates). This example implements the complete intersection test including the collinear overlap case, and also computes the intersection point when segments properly cross.

The Intuition

The orientation of three points P, Q, R is determined by the sign of the cross product (Q-P) × (R-P):

Positive: P→Q→R is counter-clockwise
Negative: clockwise
Zero: collinear

Two segments AB and CD intersect if and only if: 1. A and B have opposite orientations with respect to CD (C and D are on opposite sides of line AB), and 2. C and D have opposite orientations with respect to AB Special case: if any orientation is zero, points are collinear — check if the segment endpoint lies within the other segment's bounding box. No division, no floating-point edge cases for the orientation test itself. When you do need the intersection point, a single parameterised formula works after verifying intersection.

How It Works in Rust

#[derive(Clone, Copy, Debug)]
struct Point { x: f64, y: f64 }

// Cross product of vectors (b-a) and (c-a)
// Positive: counter-clockwise; negative: clockwise; zero: collinear
fn cross(a: Point, b: Point, c: Point) -> f64 {
 (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
}

fn on_segment(p: Point, a: Point, b: Point) -> bool {
 // Is p on segment AB, given p is collinear with A and B?
 p.x >= a.x.min(b.x) && p.x <= a.x.max(b.x) &&
 p.y >= a.y.min(b.y) && p.y <= a.y.max(b.y)
}

fn segments_intersect(a: Point, b: Point, c: Point, d: Point) -> bool {
 let d1 = cross(c, d, a); // orientation of A w.r.t. CD
 let d2 = cross(c, d, b); // orientation of B w.r.t. CD
 let d3 = cross(a, b, c); // orientation of C w.r.t. AB
 let d4 = cross(a, b, d); // orientation of D w.r.t. AB

 // Proper intersection: A and B on opposite sides of CD, and vice versa
 if d1 * d2 < 0.0 && d3 * d4 < 0.0 { return true; }

 // Degenerate: collinear cases — check if endpoint lies on other segment
 if d1 == 0.0 && on_segment(a, c, d) { return true; }
 if d2 == 0.0 && on_segment(b, c, d) { return true; }
 if d3 == 0.0 && on_segment(c, a, b) { return true; }
 if d4 == 0.0 && on_segment(d, a, b) { return true; }

 false
}

// Compute intersection point (assumes segments properly intersect)
fn intersection_point(a: Point, b: Point, c: Point, d: Point) -> Option<Point> {
 let denom = (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x);
 if denom.abs() < 1e-12 { return None; } // parallel

 let t = ((c.x - a.x) * (d.y - c.y) - (c.y - a.y) * (d.x - c.x)) / denom;
 Some(Point {
     x: a.x + t * (b.x - a.x),
     y: a.y + t * (b.y - a.y),
 })
}

`d1 d2 < 0.0` elegantly tests "opposite signs" without branching on which is positive. For integer coordinates, use `i64` cross products and `d1 d2 < 0` to avoid any floating-point error entirely. The four collinear checks handle all degenerate configurations: T-intersections, endpoint touching, and collinear overlap. Skipping them causes subtle bugs in sweep-line algorithms.

What This Unlocks

Sweep-line intersection: Shamos-Hoey and Bentley-Ottmann algorithms use this test as their O(1) inner operation.
Polygon inside test: the ray-casting algorithm fires a ray from the query point and counts segment intersections.
Collision detection: convex polygon intersection (GJK, SAT) reduces to segment intersection tests on polygon edges.

Key Differences

Concept	OCaml	Rust
Point type	Record `{ x: float; y: float }`	`#[derive(Clone, Copy)] struct Point { x: f64, y: f64 }`
Cross product	Same formula	Identical — geometry is language-agnostic
`Copy` semantics	Records copy by default	Requires explicit `#[derive(Copy)]` — opt-in, not default
Float comparison	`<> 0.0` is fine for exact cases	`== 0.0` for collinear check (exact orientation test output)
Opposite-sign test	`d1 . d2 < 0.0`	`d1 d2 < 0.0` — same, no dot notation for `f64`

/// Line Segment Intersection Detection.
///
/// Uses cross-product sign tests to determine if two segments AB and CD
/// intersect. No division until we need the actual point.

#[derive(Clone, Copy, Debug, PartialEq)]
struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn new(x: f64, y: f64) -> Self { Point { x, y } }
}

/// Cross product of vectors (b - a) and (c - a).
fn cross(a: Point, b: Point, c: Point) -> f64 {
    (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
}

fn sign(x: f64) -> i32 {
    if x > 0.0 { 1 } else if x < 0.0 { -1 } else { 0 }
}

/// Is point p on segment [a, b]? (assumes p is collinear with a, b)
fn on_segment(a: Point, b: Point, p: Point) -> bool {
    p.x >= f64::min(a.x, b.x) && p.x <= f64::max(a.x, b.x)
        && p.y >= f64::min(a.y, b.y) && p.y <= f64::max(a.y, b.y)
}

/// Do segments AB and CD intersect (including endpoint touches)?
pub fn segments_intersect(a: Point, b: Point, c: Point, d: Point) -> bool {
    let d1 = cross(c, d, a);
    let d2 = cross(c, d, b);
    let d3 = cross(a, b, c);
    let d4 = cross(a, b, d);

    // Proper intersection: each segment straddles the other's line
    if sign(d1) * sign(d2) < 0 && sign(d3) * sign(d4) < 0 {
        return true;
    }

    // Collinear/endpoint cases
    if d1 == 0.0 && on_segment(c, d, a) { return true; }
    if d2 == 0.0 && on_segment(c, d, b) { return true; }
    if d3 == 0.0 && on_segment(a, b, c) { return true; }
    if d4 == 0.0 && on_segment(a, b, d) { return true; }

    false
}

/// Compute actual intersection point (None if parallel or disjoint).
pub fn intersection_point(a: Point, b: Point, c: Point, d: Point) -> Option<Point> {
    let denom = (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x);
    if denom.abs() < 1e-12 { return None; } // Parallel

    let t = ((c.x - a.x) * (d.y - c.y) - (c.y - a.y) * (d.x - c.x)) / denom;
    let s = ((c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x)) / denom;

    if t < 0.0 || t > 1.0 || s < 0.0 || s > 1.0 {
        return None;
    }

    Some(Point::new(
        a.x + t * (b.x - a.x),
        a.y + t * (b.y - a.y),
    ))
}

fn main() {
    let cases: &[(Point, Point, Point, Point, bool)] = &[
        // X-crossing
        (Point::new(0.0, 0.0), Point::new(2.0, 2.0),
         Point::new(0.0, 2.0), Point::new(2.0, 0.0), true),
        // Parallel, same y
        (Point::new(0.0, 0.0), Point::new(1.0, 0.0),
         Point::new(2.0, 0.0), Point::new(3.0, 0.0), false),
        // T-intersection
        (Point::new(0.0, 0.0), Point::new(2.0, 0.0),
         Point::new(1.0, -1.0), Point::new(1.0, 1.0), true),
        // Near-miss
        (Point::new(0.0, 0.0), Point::new(1.0, 1.0),
         Point::new(1.0, 0.0), Point::new(2.0, 1.0), false),
    ];

    for &(a, b, c, d, expected) in cases {
        let result = segments_intersect(a, b, c, d);
        let pt = intersection_point(a, b, c, d);
        print!("({},{})-({},{}) vs ({},{})-({},{}): {} (expected {})",
            a.x, a.y, b.x, b.y, c.x, c.y, d.x, d.y, result, expected);
        if let Some(p) = pt {
            print!("  → intersection at ({:.2},{:.2})", p.x, p.y);
        }
        println!();
    }
}

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

    #[test]
    fn test_x_crossing() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(2.0, 2.0);
        let c = Point::new(0.0, 2.0);
        let d = Point::new(2.0, 0.0);
        assert!(segments_intersect(a, b, c, d));
        let p = intersection_point(a, b, c, d).unwrap();
        assert!((p.x - 1.0).abs() < 1e-9);
        assert!((p.y - 1.0).abs() < 1e-9);
    }

    #[test]
    fn test_no_intersection() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(1.0, 0.0);
        let c = Point::new(0.0, 1.0);
        let d = Point::new(1.0, 1.0);
        assert!(!segments_intersect(a, b, c, d));
    }

    #[test]
    fn test_parallel_no_overlap() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(1.0, 0.0);
        let c = Point::new(2.0, 0.0);
        let d = Point::new(3.0, 0.0);
        assert!(!segments_intersect(a, b, c, d));
    }

    #[test]
    fn test_collinear_overlap() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(2.0, 0.0);
        let c = Point::new(1.0, 0.0);
        let d = Point::new(3.0, 0.0);
        assert!(segments_intersect(a, b, c, d));
    }

    #[test]
    fn test_endpoint_touch() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(1.0, 1.0);
        let c = Point::new(1.0, 1.0);
        let d = Point::new(2.0, 0.0);
        assert!(segments_intersect(a, b, c, d));
    }

    #[test]
    fn test_t_intersection() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(2.0, 0.0);
        let c = Point::new(1.0, -1.0);
        let d = Point::new(1.0, 1.0);
        assert!(segments_intersect(a, b, c, d));
    }

    #[test]
    fn test_cross_product() {
        let a = Point::new(0.0, 0.0);
        let b = Point::new(2.0, 0.0);
        let above = Point::new(1.0, 1.0);
        let below = Point::new(1.0, -1.0);
        assert!(cross(a, b, above) > 0.0);
        assert!(cross(a, b, below) < 0.0);
    }
}

(* Line Segment Intersection in OCaml *)

type point = { x: float; y: float }

(* Cross product of vectors (b-a) and (c-a) *)
let cross a b c =
  (b.x -. a.x) *. (c.y -. a.y) -. (b.y -. a.y) *. (c.x -. a.x)

let sign x = if x > 0.0 then 1 else if x < 0.0 then -1 else 0

(* Is point p on segment [a, b]? (assuming p is collinear with a, b) *)
let on_segment a b p =
  min a.x b.x <= p.x && p.x <= max a.x b.x &&
  min a.y b.y <= p.y && p.y <= max a.y b.y

(* Do segments AB and CD intersect? *)
let segments_intersect a b c d =
  let d1 = cross c d a in
  let d2 = cross c d b in
  let d3 = cross a b c in
  let d4 = cross a b d in
  if sign d1 * sign d2 < 0 && sign d3 * sign d4 < 0 then
    true  (* Proper intersection *)
  else if d1 = 0.0 && on_segment c d a then true
  else if d2 = 0.0 && on_segment c d b then true
  else if d3 = 0.0 && on_segment a b c then true
  else if d4 = 0.0 && on_segment a b d then true
  else false

(* Find actual intersection point for non-parallel segments *)
let intersection_point a b c d =
  let denom = (b.x -. a.x) *. (d.y -. c.y) -. (b.y -. a.y) *. (d.x -. c.x) in
  if abs_float denom < 1e-12 then None  (* Parallel *)
  else
    let t = ((c.x -. a.x) *. (d.y -. c.y) -. (c.y -. a.y) *. (d.x -. c.x)) /. denom in
    if t < 0.0 || t > 1.0 then None
    else
      let s = ((c.x -. a.x) *. (b.y -. a.y) -. (c.y -. a.y) *. (b.x -. a.x)) /. denom in
      if s < 0.0 || s > 1.0 then None
      else Some { x = a.x +. t *. (b.x -. a.x); y = a.y +. t *. (b.y -. a.y) }

let () =
  let cases = [
    ({x=0.0;y=0.0}, {x=2.0;y=2.0}, {x=0.0;y=2.0}, {x=2.0;y=0.0}, true);
    ({x=0.0;y=0.0}, {x=1.0;y=0.0}, {x=2.0;y=0.0}, {x=3.0;y=0.0}, false);
    ({x=0.0;y=0.0}, {x=1.0;y=1.0}, {x=1.0;y=0.0}, {x=2.0;y=1.0}, false);
    ({x=0.0;y=0.0}, {x=2.0;y=0.0}, {x=1.0;y=-1.0}, {x=1.0;y=1.0}, true);
  ] in
  List.iter (fun (a, b, c, d, expected) ->
    let result = segments_intersect a b c d in
    Printf.printf "(%g,%g)-(%g,%g) vs (%g,%g)-(%g,%g): %b (expected %b)\n"
      a.x a.y b.x b.y c.x c.y d.x d.y result expected;
    match intersection_point a b c d with
    | Some p -> Printf.printf "  Intersection at (%g, %g)\n" p.x p.y
    | None -> ()
  ) cases