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

/// <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>
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:9 years ago
Author:albertp007
Tags: #grahamscan , #convexhull , #computationalgeometry , tryfsharp