836 Fundamental

Line Segment Intersection

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Line Segment Intersection" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Testing whether two line segments intersect is a building block of computational geometry: polygon union/intersection, road network analysis, PCB trace routing, robot obstacle detection, and sweep line algorithms all reduce to repeated segment intersection tests. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Testing whether two line segments intersect is a building block of computational geometry: polygon union/intersection, road network analysis, PCB trace routing, robot obstacle detection, and sweep line algorithms all reduce to repeated segment intersection tests. The cross product orientation test determines which side of a directed line a point lies on; two segments intersect if and only if each segment's endpoints straddle the other segment's line. Degenerate cases (collinear segments, touching at endpoints) require careful handling. This is one of the most error-prone geometric primitives due to floating-point precision issues.

🎯 Learning Outcomes

• Implement the orientation test using cross products: left turn, right turn, or collinear

• Test segment intersection: two segments AB and CD intersect iff orientations disagree properly

• Handle the collinear overlap case: segments lie on the same line and may share a range

• Understand the "straddle" test: A and B on opposite sides of line CD, AND C and D on opposite sides of line AB

• Compute the actual intersection point using parametric line equations when intersection is confirmed

Code Example

#![allow(clippy::all)]
//! Placeholder

(* 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

Key Differences

Aspect	Rust	OCaml
Point representation	`struct Point` or `(f64, f64)`	Record or tuple
Orientation return	`i32` (0,1,2 or -1,0,1)	`int`
Epsilon handling	`val.abs() < f64::EPSILON`	Same
Collinear check	Separate `on_segment` function	Same
Integer coords	`i64` for exact arithmetic	`int` for exact
Production library	`geo` crate	`Gg` library

OCaml Approach

OCaml uses the same cross-product orientation test with float arithmetic. The compare function on floats respects IEEE 754. OCaml's polymorphic comparison works on (float * float) point tuples directly. The on_segment collinear check uses min/max range tests. OCaml's pipe operator |> chains the four orientation computations readably. The Gg library provides production-quality 2D geometry primitives.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* 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

Deep Comparison

OCaml vs Rust: Line Segment Intersection

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Compute the exact intersection point (as Option<Point>) when two segments do intersect.

Implement the sweep line algorithm using segment intersection tests to find all intersections among n segments in O((n + k) log n).

Handle collinear overlapping segments by returning the overlap interval as Option<(Point, Point)>.

Implement with integer coordinates and compare robustness vs. floating-point on near-collinear cases.

Use your segment intersection test to implement a simple polygon clip against a rectangular window (Cohen-Sutherland).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust