| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.DelaunayTriangulation.Naive
Description
Synopsis
- delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r
- toAdjLists :: (Num r, Ord r) => Mapping p r -> [(VertexID, VertexID)] -> Vector (CList VertexID)
- sortAroundMapping :: (Num r, Ord r) => Mapping p r -> VertexID -> [VertexID] -> [VertexID]
- extractEdges :: [(VertexID, VertexID, VertexID)] -> [(VertexID, VertexID)]
- isDelaunay :: (Fractional r, Ord r) => Mapping p r -> VertexID -> VertexID -> VertexID -> Bool
Documentation
delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r Source #
Naive \( O(n^4) \) time implementation of the delaunay triangulation. Simply tries each triple (p,q,r) and tests if it is delaunay, i.e. if there are no other points in the circle defined by p, q, and r.
pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)
toAdjLists :: (Num r, Ord r) => Mapping p r -> [(VertexID, VertexID)] -> Vector (CList VertexID) Source #
Given a list of edges, as vertexId pairs, construct a vector with the adjacency lists, each in CW sorted order.
sortAroundMapping :: (Num r, Ord r) => Mapping p r -> VertexID -> [VertexID] -> [VertexID] Source #
Given a particular point u and a list of points vs, sort the points vs in CW order around u. running time: \( O(m log m) \), where m=|vs| is the number of vertices to sort.
extractEdges :: [(VertexID, VertexID, VertexID)] -> [(VertexID, VertexID)] Source #
Given a list of faces, construct a list of edges
isDelaunay :: (Fractional r, Ord r) => Mapping p r -> VertexID -> VertexID -> VertexID -> Bool Source #
\( O(n) \) Test if the given three points form a triangle in the delaunay triangulation.