0 people like it.

# GrahamScan.fsx

graham scan algorithm for finding the convex hull of a set of 2-dimensional points

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: ``` ``````type Turn = Left | Right | Straight 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 let rec scan = function | (p1::p2::p3::points) -> let t = findTurn p1 p2 p3 match t with | Right -> (p1::(scan (p3::points))) | _ -> (p1::(scan (p2::p3::points))) | points -> points let translate ((ox:double), (oy:double)) (x, y) = (x-ox, y-oy) let atan2' ((x:double), y) = atan2 y x let origin = List.minBy (fun (x, y) -> (y, x)) points scan (List.sortBy (translate(origin) >> atan2') points) ``````
union case Turn.Left: Turn
union case Turn.Right: Turn
union case Turn.Straight: Turn
val grahamScan : points:(double * double) list -> (double * double) list

Full name: Script.grahamScan
val points : (double * double) list
val findTurn : (double * double -> double * double -> double * double -> Turn)
val x1 : double
val y1 : double
val x2 : double
val y2 : double
val x3 : double
val y3 : double
val x : double
val sign : value:'T -> int (requires member get_Sign)

Full name: Microsoft.FSharp.Core.Operators.sign
val scan : ((double * double) list -> (double * double) list)
val p1 : double * double
val p2 : double * double
val p3 : double * double
val t : Turn
val translate : (double * double -> double * double -> double * double)
val ox : double
Multiple items
val double : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.double

--------------------
type double = System.Double

Full name: Microsoft.FSharp.Core.double
val oy : double
val y : double
val atan2' : (double * double -> double)
val atan2 : y:'T1 -> x:'T1 -> 'T2 (requires member Atan2)

Full name: Microsoft.FSharp.Core.Operators.atan2
val origin : double * double
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val minBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.minBy
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy