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 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:9 years ago
Author:albertpang
Tags: computational geometry graham scan , tryfsharp