6 people like it.

# 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: 42: ``` ``````// Based on Andrew's Monotone Chain algorithm, as described here: // http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain // Additional explanations provided here: http://www.clear-lines.com/blog/post/Convex-Hull.aspx 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

### More information

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