| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Algorithms.Geometry.DelaunayTriangulation.Naive
- delaunayTriangulation :: (Ord r, Fractional r, Show r, Show p) => NonEmpty (Point 2 r :+ p) -> Triangulation p r
- toAdjLists :: (Num r, Ord r) => Mapping p r -> [(VertexID, VertexID)] -> Vector (CList VertexID)
- sortAround' :: (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, Show r, Show p) => 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.
sortAround' :: (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
Test if the given three points form a triangle in the delaunay triangulation. running time: O(n)