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

Raw view Test code New version

More information

Link:	http://fssnip.net/oL
Posted:	10 years ago
Author:	albertpang
Tags:	computational geometry graham scan , tryfsharp