// 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