39 people like it.

Graham scal algorithm for finding the convex hull of a sequence of 2D points

finds the points lying on the convex hull of the given set of points and returns those points in clockwise direction, starting at the point with minimum y-value Remarks: it's a more or less direct implementation of the algorithm named after Ronald Graham that is explained on http://en.wikipedia.org/wiki/Graham_scan you can switch the definition Point for a proper type of your liking - e.g. System.Drawing.Point

 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: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
module GrahamScan

type Point = { X : int; Y : int }

/// finds the points lying on the convex hull of the given set of points and 
/// returns those points in clockwise direction, starting at the point
/// with minimum y-value
/// Remarks: it's a more or less direct implementation of the algorithm named
/// after Ronald Graham that is explained on http://en.wikipedia.org/wiki/Graham_scan
let FindConvexHull (pts : Point seq) : Point seq =

    // it's nicer to work with lists so let's convert
    let ptl = List.ofSeq pts

    // to make something worthwhile we need at last two points
    if ptl.Length <= 2 then Seq.empty
    else

    // this is a helperfunction (explained in the wikipedia article) in which direction
    // 3 points "turn"
    let ccw (a : Point) (b : Point) (c : Point) =
        (b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)

    // 1. Let's find the point with the minimum y-coordinate
    /// this is the comparision function for this
    let cmpPts (a : Point) (b : Point) =
        match a.Y.CompareTo(b.Y) with
        | 0 -> a.X.CompareTo(b.X)
        | _ as r -> r
    // and with it we can look for the mentioned point
    let sortedY = ptl |> List.sortWith cmpPts
    let org, rest = sortedY.Head, sortedY.Tail

    // 2. we have to sort the list in increasing order of the angle
    // that a point p makes with org and the x-axis
    let winkelCos (p : Point) =
        let dx = float (p.X - org.X)
        let dy = float (p.Y - org.Y)
        let l = System.Math.Sqrt(dx*dx + dy*dy)
        dx / l
    // and here we sort the list (we only sort the remainder without
    // org and prepend it afterwards to ward of 
    // any issue with "division by zero"
    let sortedW = org::(rest |> List.sortBy winkelCos)

    // here is the actual algorithm
    // it uses two lists
    // lastPts: every visited point is put but might
    //          be removed if the "turn direction"
    //          'turns' out to be wrong
    // nextPts: the points left to be checked
    //          as the algorithm progresses those
    //          points are moved to lastPts
    // so lastPts will contain the found points
    // on the convex hull at every step, but in
    // clockwise orientation (as we push in front
    // of the list)
    let rec scan (lastPts : Point list) (nextPts : Point list) =
        // we are done if there are no points left to check
        if nextPts.IsEmpty then lastPts
        else

        // if there are points left take the first one
        let c = nextPts.Head

        match lastPts with
        // if there are at least 2 points b,a in the visited points
        // and a,b,c is NOT a counterclockwise turn
        // we have to remove b from lastPoints and continue checking
        // backwards ...
        | b::a::_ when ccw a b c >= 0 -> scan (lastPts.Tail) nextPts
        // in every other case we can push c onto the visited
        // stack and continue
        | _ -> scan (c::lastPts) nextPts.Tail

    // run it
    sortedW |> scan [] |> Seq.ofList
module GrahamScan
type Point =
  {X: int;
   Y: int;}

Full name: GrahamScan.Point
Point.X: int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
Point.Y: int
val FindConvexHull : pts:seq<Point> -> seq<Point>

Full name: GrahamScan.FindConvexHull


 finds the points lying on the convex hull of the given set of points and
 returns those points in clockwise direction, starting at the point
 with minimum y-value
 Remarks: it's a more or less direct implementation of the algorithm named
 after Ronald Graham that is explained on http://en.wikipedia.org/wiki/Graham_scan
val pts : seq<Point>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val ptl : Point 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 ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
property List.Length: int
module Seq

from Microsoft.FSharp.Collections
val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty
val ccw : (Point -> Point -> Point -> int)
val a : Point
val b : Point
val c : Point
val cmpPts : (Point -> Point -> int)


 this is the comparision function for this
System.Int32.CompareTo(value: int) : int
System.Int32.CompareTo(value: obj) : int
val r : int
val sortedY : Point list
val sortWith : comparer:('T -> 'T -> int) -> list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.sortWith
val org : Point
val rest : Point list
property List.Head: Point
property List.Tail: Point list
val winkelCos : (Point -> float)
val p : Point
val dx : 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 dy : float
val l : float
namespace System
type Math =
  static val PI : float
  static val E : float
  static member Abs : value:sbyte -> sbyte + 6 overloads
  static member Acos : d:float -> float
  static member Asin : d:float -> float
  static member Atan : d:float -> float
  static member Atan2 : y:float * x:float -> float
  static member BigMul : a:int * b:int -> int64
  static member Ceiling : d:decimal -> decimal + 1 overload
  static member Cos : d:float -> float
  ...

Full name: System.Math
System.Math.Sqrt(d: float) : float
val sortedW : Point list
val sortBy : projection:('T -> 'Key) -> list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sortBy
val scan : (Point list -> Point list -> Point list)
val lastPts : Point list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val nextPts : Point list
property List.IsEmpty: bool
val ofList : source:'T list -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.ofList

More information

Link:http://fssnip.net/3j
Posted:13 years ago
Author:Carsten König
Tags: computational geometry , convex hull , graham