4 people like it.

# GrahamScan.fsx

Function to perform the Graham scan algorithm which looks for the set of points forming the convex hull of the input points

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: ``` ``````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 [] ``````
union case Turn.Left: Turn
union case Turn.Right: Turn
union case Turn.Straight: Turn
val grahamScan : points:(float * float) list -> (float * float) list

Full name: Script.grahamScan

<summary>Perform the graham scan algorithm to search for the convex hull
of a given set of 2D points</summary>
<param name="points">list of pair of floats representing 2D points
</param>
<returns>list of pairs of floats representing the set of 2D points
that forms the convex hull of the input points</returns>
val points : (float * float) list
val findTurn : (float * float -> float * float -> float * float -> Turn)
val x1 : float
val y1 : float
val x2 : float
val y2 : float
val x3 : float
val y3 : float
val x : float
val sign : value:'T -> int (requires member get_Sign)

Full name: Microsoft.FSharp.Core.Operators.sign
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val scan : ((float * float) list -> (float * float) list -> (float * float) list)
val acc : (float * float) list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : '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 rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val p1 : float * float
val ps : (float * float) list
val h1 : float * float
val h2 : float * float
val hs : (float * float) list
val t : Turn
val translate : (float * float -> float * float -> float * float)
val ox : float
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = System.Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
val oy : float
val y : float
val atan2' : (double * double -> double)
val x : 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 y : double
val atan2 : y:'T1 -> x:'T1 -> 'T2 (requires member Atan2)

Full name: Microsoft.FSharp.Core.Operators.atan2
val origin : float * float
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

### More information

 Link: http://fssnip.net/sb Posted: 7 years ago Author: albertp007 Tags: #grahamscan , #convexhull , #computationalgeometry , tryfsharp