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: 
// 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