type Turn = Left | Right | Straight /// Perform the graham scan algorithm to search for the convex hull /// of a given set of 2D points /// list of pair of floats representing 2D points /// /// list of pairs of floats representing the set of 2D points /// that forms the convex hull of the input points let grahamScan points= let findTurn (x1, y1) (x2, y2) (x3, y3) = let x = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1) match sign(x) with | (-1) -> Right | 0 -> Straight | 1 -> Left | _ -> failwith "Funny result from sign()" let rec scan acc points = match points with | [] -> List.rev acc // points pushed into accumulator in rev order | p1::ps -> match acc with | h1::h2::hs -> // if accumulator has two or more elements in it let t = findTurn h2 h1 p1 // acc has elements in rev order match t with | Right -> scan (h2::hs) (p1::ps) // get rid of mid point h1 | _ -> scan (p1::h1::h2::hs) ps // push p1 into acc | _ -> scan (p1::acc) ps // push into acc if it has <2 points let translate ((ox:float), (oy:float)) (x, y) = (x-ox, y-oy) let atan2' ((x:double), y) = atan2 y x let origin = List.minBy (fun (x, y) -> (y, x)) points points |> List.sortBy(translate(origin) >> atan2') |> scan []