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

Safe HaskellNone




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)