module GrahamScan
type Point = { X : int; Y : int }
/// finds the points lying on the convex hull of the given set of points and
/// returns those points in clockwise direction, starting at the point
/// with minimum y-value
/// Remarks: it's a more or less direct implementation of the algorithm named
/// after Ronald Graham that is explained on http://en.wikipedia.org/wiki/Graham_scan
let FindConvexHull (pts : Point seq) : Point seq =
// it's nicer to work with lists so let's convert
let ptl = List.ofSeq pts
// to make something worthwhile we need at last two points
if ptl.Length <= 2 then Seq.empty
else
// this is a helperfunction (explained in the wikipedia article) in which direction
// 3 points "turn"
let ccw (a : Point) (b : Point) (c : Point) =
(b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)
// 1. Let's find the point with the minimum y-coordinate
/// this is the comparision function for this
let cmpPts (a : Point) (b : Point) =
match a.Y.CompareTo(b.Y) with
| 0 -> a.X.CompareTo(b.X)
| _ as r -> r
// and with it we can look for the mentioned point
let sortedY = ptl |> List.sortWith cmpPts
let org, rest = sortedY.Head, sortedY.Tail
// 2. we have to sort the list in increasing order of the angle
// that a point p makes with org and the x-axis
let winkelCos (p : Point) =
let dx = float (p.X - org.X)
let dy = float (p.Y - org.Y)
let l = System.Math.Sqrt(dx*dx + dy*dy)
dx / l
// and here we sort the list (we only sort the remainder without
// org and prepend it afterwards to ward of
// any issue with "division by zero"
let sortedW = org::(rest |> List.sortBy winkelCos)
// here is the actual algorithm
// it uses two lists
// lastPts: every visited point is put but might
// be removed if the "turn direction"
// 'turns' out to be wrong
// nextPts: the points left to be checked
// as the algorithm progresses those
// points are moved to lastPts
// so lastPts will contain the found points
// on the convex hull at every step, but in
// clockwise orientation (as we push in front
// of the list)
let rec scan (lastPts : Point list) (nextPts : Point list) =
// we are done if there are no points left to check
if nextPts.IsEmpty then lastPts
else
// if there are points left take the first one
let c = nextPts.Head
match lastPts with
// if there are at least 2 points b,a in the visited points
// and a,b,c is NOT a counterclockwise turn
// we have to remove b from lastPoints and continue checking
// backwards ...
| b::a::_ when ccw a b c >= 0 -> scan (lastPts.Tail) nextPts
// in every other case we can push c onto the visited
// stack and continue
| _ -> scan (c::lastPts) nextPts.Tail
// run it
sortedW |> scan [] |> Seq.ofList