 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: 10 years ago Author: Carsten König Tags: computational geometry , convex hull , graham