835 Intermediate

Point-in-Polygon Test

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Point-in-Polygon Test" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Determining whether a point lies inside a polygon is fundamental to GIS applications, game collision detection, map interfaces (is this GPS coordinate inside this region?), and computational geometry. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Determining whether a point lies inside a polygon is fundamental to GIS applications, game collision detection, map interfaces (is this GPS coordinate inside this region?), and computational geometry. The ray casting algorithm casts a horizontal ray from the query point rightward and counts crossings with polygon edges — an odd count means inside, even means outside. The winding number algorithm counts how many times the polygon winds around the point, handling non-convex and self-intersecting polygons correctly. These tests appear in every GIS library, game physics engine, and graphics renderer.

🎯 Learning Outcomes

• Implement the ray casting algorithm: count horizontal ray crossings with polygon edges

• Handle edge cases: point exactly on edge, ray passing through vertex, horizontal edges

• Implement the winding number algorithm for non-convex and self-intersecting polygons

• Understand when each algorithm is appropriate: ray casting for simple polygons, winding number for complex

• Apply to batch queries: preprocess polygon for O(log n) per query vs O(n) per query

Code Example

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

(* Point-in-Polygon: Ray Casting in OCaml *)

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

(* Ray casting: count how many times the +x ray from P crosses polygon edges *)
(* Returns `Inside`, `Outside`, or `OnBoundary` *)
type location = Inside | Outside | OnBoundary

let point_in_polygon (p : point) (polygon : point array) : location =
  let n = Array.length polygon in
  if n = 0 then Outside
  else begin
    let crossings = ref 0 in
    let on_boundary = ref false in
    for i = 0 to n - 1 do
      let a = polygon.(i) in
      let b = polygon.((i + 1) mod n) in
      (* Check if P is on the segment AB *)
      let cross = (b.x -. a.x) *. (p.y -. a.y) -. (b.y -. a.y) *. (p.x -. a.x) in
      let min_x = min a.x b.x and max_x = max a.x b.x in
      let min_y = min a.y b.y and max_y = max a.y b.y in
      if abs_float cross < 1e-12
         && p.x >= min_x && p.x <= max_x
         && p.y >= min_y && p.y <= max_y then
        on_boundary := true;
      (* Ray crossing test *)
      if (a.y <= p.y && b.y > p.y) || (b.y <= p.y && a.y > p.y) then begin
        let x_cross = a.x +. (p.y -. a.y) /. (b.y -. a.y) *. (b.x -. a.x) in
        if p.x < x_cross then incr crossings
      end
    done;
    if !on_boundary then OnBoundary
    else if !crossings mod 2 = 1 then Inside
    else Outside
  end

let string_of_location = function
  | Inside -> "Inside" | Outside -> "Outside" | OnBoundary -> "OnBoundary"

let () =
  (* Square [0,2]×[0,2] *)
  let square = [| {x=0.0;y=0.0}; {x=2.0;y=0.0};
                  {x=2.0;y=2.0}; {x=0.0;y=2.0} |] in
  let tests = [
    ({x=1.0;y=1.0}, "centre");
    ({x=3.0;y=1.0}, "right outside");
    ({x=0.0;y=0.0}, "corner");
    ({x=1.0;y=0.0}, "edge");
    ({x=1.0;y=2.5}, "above");
  ] in
  Printf.printf "Square [0,2]×[0,2]:\n";
  List.iter (fun (p, label) ->
    Printf.printf "  (%g,%g) [%s]: %s\n" p.x p.y label
      (string_of_location (point_in_polygon p square))
  ) tests;

  (* L-shaped polygon *)
  let l_shape = [| {x=0.0;y=0.0}; {x=2.0;y=0.0}; {x=2.0;y=1.0};
                   {x=1.0;y=1.0}; {x=1.0;y=2.0}; {x=0.0;y=2.0} |] in
  Printf.printf "\nL-shape polygon:\n";
  List.iter (fun (p, label) ->
    Printf.printf "  (%g,%g) [%s]: %s\n" p.x p.y label
      (string_of_location (point_in_polygon p l_shape))
  ) [({x=0.5;y=0.5}, "bottom-left leg"); ({x=1.5;y=1.5}, "top-right — outside")]

Key Differences

Aspect	Rust	OCaml
Mutation	`inside = !inside` (bool flip)	`inside := not !inside`
Edge iteration	`for i in 0..n` with `j = i`	`for` loop or `fold_left`
Previous vertex	Separate `j` variable	Same or pair in fold state
Float comparison	`!=` for `f64` (works here)	`<>` for float
Winding number	Separate function	Same approach
Batch queries	`fn contains_batch`	`List.map (point_in_polygon poly)`

OCaml Approach

OCaml implements point-in-polygon with a List.fold_left over edge pairs or a for loop with Array. The condition is identical floating-point arithmetic. OCaml's ref for the mutable inside flag: let inside = ref false in ... inside := not !inside. The functional version threads the crossing count and previous vertex through fold. OCaml's List.filteri can pre-filter edges that could possibly cross the query point's y-coordinate for batch optimization.

Full Source

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

(* Point-in-Polygon: Ray Casting in OCaml *)

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

(* Ray casting: count how many times the +x ray from P crosses polygon edges *)
(* Returns `Inside`, `Outside`, or `OnBoundary` *)
type location = Inside | Outside | OnBoundary

let point_in_polygon (p : point) (polygon : point array) : location =
  let n = Array.length polygon in
  if n = 0 then Outside
  else begin
    let crossings = ref 0 in
    let on_boundary = ref false in
    for i = 0 to n - 1 do
      let a = polygon.(i) in
      let b = polygon.((i + 1) mod n) in
      (* Check if P is on the segment AB *)
      let cross = (b.x -. a.x) *. (p.y -. a.y) -. (b.y -. a.y) *. (p.x -. a.x) in
      let min_x = min a.x b.x and max_x = max a.x b.x in
      let min_y = min a.y b.y and max_y = max a.y b.y in
      if abs_float cross < 1e-12
         && p.x >= min_x && p.x <= max_x
         && p.y >= min_y && p.y <= max_y then
        on_boundary := true;
      (* Ray crossing test *)
      if (a.y <= p.y && b.y > p.y) || (b.y <= p.y && a.y > p.y) then begin
        let x_cross = a.x +. (p.y -. a.y) /. (b.y -. a.y) *. (b.x -. a.x) in
        if p.x < x_cross then incr crossings
      end
    done;
    if !on_boundary then OnBoundary
    else if !crossings mod 2 = 1 then Inside
    else Outside
  end

let string_of_location = function
  | Inside -> "Inside" | Outside -> "Outside" | OnBoundary -> "OnBoundary"

let () =
  (* Square [0,2]×[0,2] *)
  let square = [| {x=0.0;y=0.0}; {x=2.0;y=0.0};
                  {x=2.0;y=2.0}; {x=0.0;y=2.0} |] in
  let tests = [
    ({x=1.0;y=1.0}, "centre");
    ({x=3.0;y=1.0}, "right outside");
    ({x=0.0;y=0.0}, "corner");
    ({x=1.0;y=0.0}, "edge");
    ({x=1.0;y=2.5}, "above");
  ] in
  Printf.printf "Square [0,2]×[0,2]:\n";
  List.iter (fun (p, label) ->
    Printf.printf "  (%g,%g) [%s]: %s\n" p.x p.y label
      (string_of_location (point_in_polygon p square))
  ) tests;

  (* L-shaped polygon *)
  let l_shape = [| {x=0.0;y=0.0}; {x=2.0;y=0.0}; {x=2.0;y=1.0};
                   {x=1.0;y=1.0}; {x=1.0;y=2.0}; {x=0.0;y=2.0} |] in
  Printf.printf "\nL-shape polygon:\n";
  List.iter (fun (p, label) ->
    Printf.printf "  (%g,%g) [%s]: %s\n" p.x p.y label
      (string_of_location (point_in_polygon p l_shape))
  ) [({x=0.5;y=0.5}, "bottom-left leg"); ({x=1.5;y=1.5}, "top-right — outside")]

Deep Comparison

OCaml vs Rust: Point In Polygon

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 winding number algorithm and verify it handles self-intersecting polygons correctly where ray casting fails.

Add a point_on_edge test and handle the "on boundary" case by returning an enum Inside/Outside/OnBoundary.

Preprocess a convex polygon for O(log n) point-in-polygon using binary search on edge angles.

Batch test 10,000 random points against a complex polygon and measure the performance of ray casting vs. winding number.

Implement polygon union/intersection using multiple point-in-polygon tests (Sutherland-Hodgman algorithm).

Open Source Repos

functional-rust

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

Rust