Monotone Chain Convex Hull Algorithm

// Based on Andrew's Monotone Chain algorithm, as described here:
// http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
// Additional explanations provided here: http://www.clear-lines.com/blog/post/Convex-Hull.aspx

type Point = { X: float; Y: float }

let clockwise (p1, p2, p3) =
   (p2.X - p1.X) * (p3.Y - p1.Y)
   - (p2.Y - p1.Y) * (p3.X - p1.X)
   <= 0.0

let rec chain (hull: Point list) (candidates: Point list) =
   match candidates with
   | [ ] -> hull
   | c :: rest ->
      match hull with
      | [ ] -> chain [ c ] rest
      | [ start ] -> chain [c ; start] rest
      | b :: a :: tail -> 
         if clockwise (a, b, c) then chain (c :: hull) rest else
         chain (a :: tail) rest

let hull (points: Point list) =
   match points with
   | [ ] -> points
   | [ _ ] -> points
   | _ ->
       let sorted = List.sort points
       let upper = chain [ ] sorted
       let lower = chain [ ] (List.rev sorted)
       List.append (List.tail upper) (List.tail lower)

// illustration

let a = { X = 0.0; Y = 0.0 }
let b = { X = 2.0; Y = 0.0 }
let c = { X = 1.0; Y = 2.0 }
let d = { X = 1.0; Y = 1.0 }
let e = { X = 1.0; Y = 0.0 }
let test = [a;b;c;d;e]

let h = hull test