hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.DelaunayTriangulation.DivideAndConquer

Description

Synopsis

# Divide & Conqueror Delaunay Triangulation

delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r Source #

Computes the delaunay triangulation of a set of points.

Running time: $$O(n \log n)$$ (note: We use an IntMap in the implementation. So maybe actually $$O(n \log^2 n)$$)

pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)