Delaunay

#

module type CCC = sig

Delaunay triangulation is available for any CCC system in the sense of Knuth's ``Axioms and Hulls''

#

type point

#

val ccw : point -> point -> point -> bool

The counterclockwise relation ccw p q r states that the circle through points (p,q,r) is traversed counterclockwise when we encounter the points in cyclic order p,q,r,p,... *

#

val in_circle : point -> point -> point -> point -> bool

The relation in_circle p q r s states that s lies inside the circle (p,q,r) if ccw p q r is true, or outside that circle if ccw p q r is false.

end

#

module type Triangulation = sig

The result of triangulation is an abstract value of type triangulation. Then one can iterate over all edges of the triangulation.

#

module S : CCC

#

type triangulation

#

val triangulate : S.point array -> triangulation

triangulate a computes the Delaunay triangulation of a set of points, given as an array a. If N is the number of points (that is Array.length a), then the running time is $O(N \log N)$ on the average and $O(N^2)$ on the worst-case. The space used is always $O(N)$.

#

val iter : (S.point -> S.point -> unit) -> triangulation -> unit

iter f t iterates over all edges of the triangulation t. f u v is called once for each undirected edge (u,v).

#

val fold : (S.point -> S.point -> 'a -> 'a) -> triangulation -> 'a -> 'a

#

val iter_triangles : (S.point -> S.point -> S.point -> unit) -> triangulation -> unit

end

#

module Make : functor (S : CCC) -> Triangulation with module S = S

Generic Delaunay triangulation

#

module IntPoints : CCC with type point = int * int

Points with integer coordinates

#

module Int : Triangulation with module S = IntPoints

Delaunay triangulation with integer coordinates

#

module FloatPoints : CCC with type point = float * float

Points with floating point coordinates

#

module Float : Triangulation with module S = FloatPoints

Delaunay triangulation with floating point coordinates

module Delaunay