Algorithms.Geometry.DelaunayTriangulation.Naive

Documentation

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

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)

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]

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)]

Given a list of faces, construct a list of edges

isDelaunay :: (Fractional r, Ord r) => Mapping p r -> VertexID -> VertexID -> VertexID -> Bool

\( O(n) \) Test if the given three points form a triangle in the delaunay triangulation.