6 people like it.
Like the snippet!

Monotone Chain Convex Hull Algorithm

Andrew's Monotone Chain Convex Hull algorithm: given points in 2 dimensions, determine their convex hull by constructing the upper and lower hull.

 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:

// Based on Andrew's Monotone Chain algorithm, as described here:
// http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

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

let clockwise (p1, p2, p3) =
   (p2.X - p1.X) * (p3.Y - p1.Y)
   - (p2.Y - p1.Y) * (p3.X - p1.X)
   <= 0.0

let rec chain (hull: Point list) (candidates: Point list) =
   match candidates with
   | [ ] -> hull
   | c :: rest ->
      match hull with
      | [ ] -> chain [ c ] rest
      | [ start ] -> chain [c ; start] rest
      | b :: a :: tail -> 
         if clockwise (a, b, c) then chain (c :: hull) rest else
         chain (a :: tail) rest

let hull (points: Point list) =
   match points with
   | [ ] -> points
   | [ _ ] -> points
   | _ ->
       let sorted = List.sort points
       let upper = chain [ ] sorted
       let lower = chain [ ] (List.rev sorted)
       List.append (List.tail upper) (List.tail lower)

// illustration

let a = { X = 0.0; Y = 0.0 }
let b = { X = 2.0; Y = 0.0 }
let c = { X = 1.0; Y = 2.0 }
let d = { X = 1.0; Y = 1.0 }
let e = { X = 1.0; Y = 0.0 }
let test = [a;b;c;d;e]

let h = hull test

Point.X: 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<_>

Point.Y: float

val clockwise : p1:Point * p2:Point * p3:Point -> bool

Full name: Script.clockwise

val p1 : Point

val p2 : Point

val p3 : Point

val chain : hull:Point list -> candidates:Point list -> Point list

Full name: Script.chain

val hull : Point list

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

Full name: Script.Point

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val candidates : Point list

val c : Point

val rest : Point list

val start : Point

val b : Point

val a : Point

val tail : Point list

val hull : points:Point list -> Point list

Full name: Script.hull

val points : Point list

val sorted : 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 sort : list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sort

val upper : Point list

val lower : Point list

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

val append : list1:'T list -> list2:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.append

val tail : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.tail

val a : Point

Full name: Script.a

val b : Point

Full name: Script.b

val c : Point

Full name: Script.c

val d : Point

Full name: Script.d

val e : Point

Full name: Script.e

val test : Point list

Full name: Script.test

val h : Point list

Full name: Script.h

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/bt
Posted:	12 years ago
Author:	Mathias Brandewinder
Tags:	geometry , math , algorithms