| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.DelaunayTriangulation.DivideAndConquer
Description
Synopsis
- delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r
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)