839 Fundamental

Sweep Line Algorithm

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Sweep Line Algorithm" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Many geometric problems — computing area of union of rectangles, finding all intersecting segment pairs, computing Voronoi diagrams — can be solved efficiently by imagining a vertical line sweeping left-to-right through the plane. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Many geometric problems — computing area of union of rectangles, finding all intersecting segment pairs, computing Voronoi diagrams — can be solved efficiently by imagining a vertical line sweeping left-to-right through the plane. The sweep line processes "events" (start/end of intervals, segment crossings) in sorted x-order, maintaining a data structure of active elements. This reduces 2D problems to a sequence of 1D operations. The sweep line technique is the basis for computational geometry algorithms used in GIS, VLSI design, and computer graphics.

🎯 Learning Outcomes

• Model the sweep as a priority queue of events sorted by x-coordinate

• Maintain an active set of elements currently crossed by the sweep line

• Process start events (add to active set) and end events (remove from active set)

• Apply to: area of union of rectangles, all-segments intersection detection, closest pair

• Understand event-driven programming: only process significant x-positions, not every pixel

Code Example

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

(* Sweep Line Algorithm in OCaml *)

type interval = { lo: float; hi: float }

(* Event type: 0 = END (process before START at same x), 1 = START *)
type event = { x: float; kind: int; (* 0=end, 1=start *) }

let make_events (intervals : interval list) : event list =
  List.concat_map (fun iv ->
    [{ x = iv.lo; kind = 1 }; { x = iv.hi; kind = 0 }]
  ) intervals
  |> List.sort (fun a b ->
    let cx = compare a.x b.x in
    if cx <> 0 then cx else compare a.kind b.kind)  (* END before START *)

(* Maximum overlap depth: max # of intervals active at any point *)
let max_overlap (intervals : interval list) : int =
  let events = make_events intervals in
  let active = ref 0 and best = ref 0 in
  List.iter (fun ev ->
    if ev.kind = 1 then begin incr active; if !active > !best then best := !active end
    else decr active
  ) events;
  !best

(* Total length of union of intervals *)
let union_length (intervals : interval list) : float =
  let events = make_events intervals in
  let active = ref 0 and total = ref 0.0 and prev_x = ref 0.0 in
  List.iter (fun ev ->
    if !active > 0 then total := !total +. (ev.x -. !prev_x);
    prev_x := ev.x;
    if ev.kind = 1 then incr active else decr active
  ) events;
  !total

(* All points with maximum overlap — just return max value here *)
let () =
  let ivs = [
    {lo=1.0; hi=4.0};
    {lo=2.0; hi=6.0};
    {lo=3.0; hi=5.0};
    {lo=7.0; hi=9.0};
  ] in
  Printf.printf "Intervals: [1,4] [2,6] [3,5] [7,9]\n";
  Printf.printf "Max overlap depth: %d  (expected 3 at [3,4])\n" (max_overlap ivs);
  Printf.printf "Union length: %.1f  (expected 7.0: [1,6]∪[7,9])\n" (union_length ivs);

  (* Touching intervals — should not count as overlapping *)
  let touching = [{lo=0.0;hi=1.0}; {lo=1.0;hi=2.0}; {lo=2.0;hi=3.0}] in
  Printf.printf "\nTouching intervals [0,1] [1,2] [2,3]:\n";
  Printf.printf "Max overlap: %d  (expected 1)\n" (max_overlap touching);
  Printf.printf "Union length: %.1f  (expected 3.0)\n" (union_length touching)

Key Differences

Aspect	Rust	OCaml
Event type	`enum EventType`	Variant type
Event sort	`sort_by` on `Vec<Event>`	`List.sort`
Active set	`BTreeSet` for O(log n) ops	`Set.Make` balanced BST
Area accumulation	`f64` variable in loop	Mutable ref or fold
Dispatch	`match event.event_type`	`match event_type with`
Coordinate type	`f64` or `i64`	`float` or `int`

OCaml Approach

OCaml uses a variant type for events and List.sort for the event queue. The active set is a Set.Make balanced BST. OCaml's match event_type with Start -> ... | End -> ... cleanly dispatches. The area accumulation uses a mutable float ref or a fold over events. OCaml's float_of_int handles mixed int/float coordinates. The sweep function is naturally recursive over the sorted event list.

Full Source

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

(* Sweep Line Algorithm in OCaml *)

type interval = { lo: float; hi: float }

(* Event type: 0 = END (process before START at same x), 1 = START *)
type event = { x: float; kind: int; (* 0=end, 1=start *) }

let make_events (intervals : interval list) : event list =
  List.concat_map (fun iv ->
    [{ x = iv.lo; kind = 1 }; { x = iv.hi; kind = 0 }]
  ) intervals
  |> List.sort (fun a b ->
    let cx = compare a.x b.x in
    if cx <> 0 then cx else compare a.kind b.kind)  (* END before START *)

(* Maximum overlap depth: max # of intervals active at any point *)
let max_overlap (intervals : interval list) : int =
  let events = make_events intervals in
  let active = ref 0 and best = ref 0 in
  List.iter (fun ev ->
    if ev.kind = 1 then begin incr active; if !active > !best then best := !active end
    else decr active
  ) events;
  !best

(* Total length of union of intervals *)
let union_length (intervals : interval list) : float =
  let events = make_events intervals in
  let active = ref 0 and total = ref 0.0 and prev_x = ref 0.0 in
  List.iter (fun ev ->
    if !active > 0 then total := !total +. (ev.x -. !prev_x);
    prev_x := ev.x;
    if ev.kind = 1 then incr active else decr active
  ) events;
  !total

(* All points with maximum overlap — just return max value here *)
let () =
  let ivs = [
    {lo=1.0; hi=4.0};
    {lo=2.0; hi=6.0};
    {lo=3.0; hi=5.0};
    {lo=7.0; hi=9.0};
  ] in
  Printf.printf "Intervals: [1,4] [2,6] [3,5] [7,9]\n";
  Printf.printf "Max overlap depth: %d  (expected 3 at [3,4])\n" (max_overlap ivs);
  Printf.printf "Union length: %.1f  (expected 7.0: [1,6]∪[7,9])\n" (union_length ivs);

  (* Touching intervals — should not count as overlapping *)
  let touching = [{lo=0.0;hi=1.0}; {lo=1.0;hi=2.0}; {lo=2.0;hi=3.0}] in
  Printf.printf "\nTouching intervals [0,1] [1,2] [2,3]:\n";
  Printf.printf "Max overlap: %d  (expected 1)\n" (max_overlap touching);
  Printf.printf "Union length: %.1f  (expected 3.0)\n" (union_length touching)

Deep Comparison

OCaml vs Rust: Sweep Line Events

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

Implement the area of union of n rectangles using the sweep line in O(n^2) (naive active set) then O(n log^2 n) (segment tree for y-coverage).

Find all intersecting pairs among n line segments using the Bentley-Ottmann sweep line algorithm.

Implement a sweep line to compute the perimeter of the union of rectangles.

Count the maximum number of overlapping intervals at any point using a sweep line over 1D intervals.

Extend the rectangle union to 3D: volume of union of axis-aligned boxes using two nested sweeps.

Open Source Repos

functional-rust

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

Rust