834 Advanced

Convex Hull — Graham Scan

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Convex Hull — Graham Scan" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. The convex hull of a point set is the smallest convex polygon containing all points — the shape you'd get by stretching a rubber band around the points. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The convex hull of a point set is the smallest convex polygon containing all points — the shape you'd get by stretching a rubber band around the points. It's the foundation of computational geometry: collision detection in game engines, GIS boundary computation, robot motion planning (collision-free paths), image processing (object outline detection), and clustering algorithms all use convex hull. Graham scan computes the convex hull in O(n log n) dominated by sorting — the actual hull construction is O(n) after the sort. Understanding convex hull also introduces the cross product test for point orientation, a building block for many geometric algorithms.

🎯 Learning Outcomes

• Implement the cross product (orientation test) for three points: positive = left turn, negative = right turn, zero = collinear

• Sort points by polar angle from the lowest-leftmost point as pivot

• Implement the Graham scan loop: maintain a stack, pop while right turns occur, push each new point

• Handle degenerate cases: collinear points, duplicate points, all points collinear

• Recognize O(n log n) dominated by sorting; hull construction itself is linear

Code Example

#![allow(clippy::all)]
//! # Convex Hull (Graham Scan)
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Point {
    pub x: f64,
    pub y: f64,
}

fn cross(o: Point, a: Point, b: Point) -> f64 {
    (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
}

pub fn convex_hull(mut points: Vec<Point>) -> Vec<Point> {
    if points.len() < 3 {
        return points;
    }
    points.sort_by(|a, b| {
        a.x.partial_cmp(&b.x)
            .unwrap()
            .then(a.y.partial_cmp(&b.y).unwrap())
    });
    let mut lower = vec![];
    for &p in &points {
        while lower.len() >= 2 && cross(lower[lower.len() - 2], lower[lower.len() - 1], p) <= 0.0 {
            lower.pop();
        }
        lower.push(p);
    }
    let mut upper = vec![];
    for &p in points.iter().rev() {
        while upper.len() >= 2 && cross(upper[upper.len() - 2], upper[upper.len() - 1], p) <= 0.0 {
            upper.pop();
        }
        upper.push(p);
    }
    lower.pop();
    upper.pop();
    lower.extend(upper);
    lower
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_hull() {
        let pts = vec![
            Point { x: 0.0, y: 0.0 },
            Point { x: 1.0, y: 0.0 },
            Point { x: 0.5, y: 0.5 },
            Point { x: 0.0, y: 1.0 },
            Point { x: 1.0, y: 1.0 },
        ];
        assert_eq!(convex_hull(pts).len(), 4);
    }
}

(* Convex Hull: Graham Scan in OCaml *)

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

let dist2 a b =
  let dx = a.x -. b.x and dy = a.y -. b.y in
  dx *. dx +. dy *. dy

(* Cross product of vectors (b-a) and (c-a) *)
(* > 0: CCW (left turn), < 0: CW (right turn), = 0: collinear *)
let cross a b c =
  (b.x -. a.x) *. (c.y -. a.y) -. (b.y -. a.y) *. (c.x -. a.x)

(* Graham scan: returns convex hull in CCW order *)
let convex_hull (points : point list) : point list =
  let n = List.length points in
  if n <= 1 then points
  else begin
    let pts = Array.of_list points in
    (* Find bottom-most (then left-most) point as pivot *)
    let pivot = Array.fold_left (fun best p ->
      if p.y < best.y || (p.y = best.y && p.x < best.x) then p else best
    ) pts.(0) pts in
    (* Sort by polar angle with respect to pivot *)
    let sorted = Array.copy pts in
    Array.sort (fun a b ->
      if a = pivot then -1
      else if b = pivot then 1
      else
        let c = cross pivot a b in
        if c > 0.0 then -1
        else if c < 0.0 then 1
        else compare (dist2 pivot a) (dist2 pivot b)
    ) sorted;
    (* Stack-based Graham scan *)
    let stack = Array.make n {x=0.0; y=0.0} in
    let top = ref (-1) in
    Array.iter (fun p ->
      while !top >= 1 && cross stack.(!top - 1) stack.(!top) p <= 0.0 do
        decr top
      done;
      incr top;
      stack.(!top) <- p
    ) sorted;
    Array.to_list (Array.sub stack 0 (!top + 1))
  end

let () =
  let points = [
    {x=0.0;y=0.0}; {x=1.0;y=1.0}; {x=2.0;y=2.0};
    {x=0.0;y=2.0}; {x=2.0;y=0.0}; {x=1.0;y=0.0};
  ] in
  let hull = convex_hull points in
  Printf.printf "Hull (%d points):\n" (List.length hull);
  List.iter (fun p -> Printf.printf "  (%.1f, %.1f)\n" p.x p.y) hull;

  let square = [
    {x=0.0;y=0.0}; {x=1.0;y=0.0}; {x=1.0;y=1.0}; {x=0.0;y=1.0};
    {x=0.5;y=0.5}  (* interior point *)
  ] in
  let h2 = convex_hull square in
  Printf.printf "\nSquare hull (%d points, interior excluded):\n" (List.length h2);
  List.iter (fun p -> Printf.printf "  (%.1f, %.1f)\n" p.x p.y) h2

Key Differences

Aspect	Rust	OCaml
Point type	`struct Point { x: f64, y: f64 }`	Record `{ x: float; y: float }`
Float sort	`partial_cmp().unwrap()` or `total_cmp`	`compare` (handles NaN differently)
Stack	`Vec<Point>` with `pop`/`push`	`list` used as stack or `Stack.t`
Cross product	Returns `f64`	Returns `float`
Collinear handling	`<= 0.0` in condition	Same
Exact arithmetic	`i64` coordinates or `Ratio` crate	`Zarith.q` rationals

OCaml Approach

OCaml represents points as { x: float; y: float } or (float * float). The cross function is a pure floating-point computation. Sorting uses List.sort with a comparison function. OCaml's Stack module or a list used as a stack implements the hull construction. List.rev reverses for the upper hull pass. OCaml's compare function handles float comparison with NaN semantics differing from IEEE. For exact arithmetic, OCaml uses Zarith with rational coordinates.

Full Source

#![allow(clippy::all)]
//! # Convex Hull (Graham Scan)
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Point {
    pub x: f64,
    pub y: f64,
}

fn cross(o: Point, a: Point, b: Point) -> f64 {
    (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
}

pub fn convex_hull(mut points: Vec<Point>) -> Vec<Point> {
    if points.len() < 3 {
        return points;
    }
    points.sort_by(|a, b| {
        a.x.partial_cmp(&b.x)
            .unwrap()
            .then(a.y.partial_cmp(&b.y).unwrap())
    });
    let mut lower = vec![];
    for &p in &points {
        while lower.len() >= 2 && cross(lower[lower.len() - 2], lower[lower.len() - 1], p) <= 0.0 {
            lower.pop();
        }
        lower.push(p);
    }
    let mut upper = vec![];
    for &p in points.iter().rev() {
        while upper.len() >= 2 && cross(upper[upper.len() - 2], upper[upper.len() - 1], p) <= 0.0 {
            upper.pop();
        }
        upper.push(p);
    }
    lower.pop();
    upper.pop();
    lower.extend(upper);
    lower
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_hull() {
        let pts = vec![
            Point { x: 0.0, y: 0.0 },
            Point { x: 1.0, y: 0.0 },
            Point { x: 0.5, y: 0.5 },
            Point { x: 0.0, y: 1.0 },
            Point { x: 1.0, y: 1.0 },
        ];
        assert_eq!(convex_hull(pts).len(), 4);
    }
}

(* Convex Hull: Graham Scan in OCaml *)

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

let dist2 a b =
  let dx = a.x -. b.x and dy = a.y -. b.y in
  dx *. dx +. dy *. dy

(* Cross product of vectors (b-a) and (c-a) *)
(* > 0: CCW (left turn), < 0: CW (right turn), = 0: collinear *)
let cross a b c =
  (b.x -. a.x) *. (c.y -. a.y) -. (b.y -. a.y) *. (c.x -. a.x)

(* Graham scan: returns convex hull in CCW order *)
let convex_hull (points : point list) : point list =
  let n = List.length points in
  if n <= 1 then points
  else begin
    let pts = Array.of_list points in
    (* Find bottom-most (then left-most) point as pivot *)
    let pivot = Array.fold_left (fun best p ->
      if p.y < best.y || (p.y = best.y && p.x < best.x) then p else best
    ) pts.(0) pts in
    (* Sort by polar angle with respect to pivot *)
    let sorted = Array.copy pts in
    Array.sort (fun a b ->
      if a = pivot then -1
      else if b = pivot then 1
      else
        let c = cross pivot a b in
        if c > 0.0 then -1
        else if c < 0.0 then 1
        else compare (dist2 pivot a) (dist2 pivot b)
    ) sorted;
    (* Stack-based Graham scan *)
    let stack = Array.make n {x=0.0; y=0.0} in
    let top = ref (-1) in
    Array.iter (fun p ->
      while !top >= 1 && cross stack.(!top - 1) stack.(!top) p <= 0.0 do
        decr top
      done;
      incr top;
      stack.(!top) <- p
    ) sorted;
    Array.to_list (Array.sub stack 0 (!top + 1))
  end

let () =
  let points = [
    {x=0.0;y=0.0}; {x=1.0;y=1.0}; {x=2.0;y=2.0};
    {x=0.0;y=2.0}; {x=2.0;y=0.0}; {x=1.0;y=0.0};
  ] in
  let hull = convex_hull points in
  Printf.printf "Hull (%d points):\n" (List.length hull);
  List.iter (fun p -> Printf.printf "  (%.1f, %.1f)\n" p.x p.y) hull;

  let square = [
    {x=0.0;y=0.0}; {x=1.0;y=0.0}; {x=1.0;y=1.0}; {x=0.0;y=1.0};
    {x=0.5;y=0.5}  (* interior point *)
  ] in
  let h2 = convex_hull square in
  Printf.printf "\nSquare hull (%d points, interior excluded):\n" (List.length h2);
  List.iter (fun p -> Printf.printf "  (%.1f, %.1f)\n" p.x p.y) h2

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_hull() {
        let pts = vec![
            Point { x: 0.0, y: 0.0 },
            Point { x: 1.0, y: 0.0 },
            Point { x: 0.5, y: 0.5 },
            Point { x: 0.0, y: 1.0 },
            Point { x: 1.0, y: 1.0 },
        ];
        assert_eq!(convex_hull(pts).len(), 4);
    }
}

Deep Comparison

OCaml vs Rust: Convex Hull Graham

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 integer coordinate convex hull to avoid all floating-point precision issues.

Add a point_in_convex_hull function using binary search on the hull angles in O(log n).

Compute the perimeter and area of the convex hull using the shoelace formula.

Find the diameter of the point set (farthest pair) using rotating calipers on the convex hull in O(n).

Handle the degenerate case where all input points are collinear and the hull degenerates to a line segment.

Open Source Repos

functional-rust

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

Rust