Data.QuadEdge
Contents
Description
The quad-edge data structure is commonly used in computational geometry for representing triangulations. It represents simultaneously both the map, its dual and mirror image.
The fundamental idea behind the quad-edge structure is the recognition that a single edge, in a closed polygonal mesh topology, sits between exactly two faces and exactly two vertices. Thus, it can represent a dual of the graph simply by reversing the convention on what is a vertex and what is a face.
The quad-edge data structure is described in the paper by Leonidas J. Guibas and Jorge Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75-123.
This implementation is based on Stream Fusion and seems to yield similar performance to mutable implementations in the ST monad.
- type QEDS a = Vector (Maybe (Edge a))
- type MQEDS s a = MVector s (Maybe (Edge a))
- new :: QEDS a
- mutate :: QEDS a -> (forall s. MQEDS s a -> ST s ()) -> QEDS a
- mutateNEs :: QEDS a -> [a] -> ([EdgeRef] -> forall s. MQEDS s a -> ST s ()) -> (QEDS a, [EdgeRef])
- mutateNE :: QEDS a -> a -> (EdgeRef -> forall s. MQEDS s a -> ST s ()) -> (QEDS a, EdgeRef)
- spliceM :: MQEDS s a -> EdgeRef -> EdgeRef -> ST s ()
- deleteEdgeM :: MQEDS s a -> EdgeRef -> ST s ()
- edges :: QEDS a -> Vector (Edge a)
- edgerefs :: QEDS a -> Vector EdgeRef
- getEdge :: QEDS a -> EdgeRef -> Edge a
- getAttr :: QEDS a -> EdgeRef -> a
- randomEdgeRef :: RandomGen g => QEDS a -> g -> (EdgeRef, g)
- isValid :: QEDS a -> EdgeRef -> Bool
- updateEdge :: QEDS a -> EdgeRef -> Edge a -> QEDS a
- updateAttr :: QEDS a -> EdgeRef -> a -> QEDS a
- deleteEdges :: QEDS a -> Stream EdgeRef -> QEDS a
- makeEdges :: QEDS a -> Stream a -> (QEDS a, Stream EdgeRef)
- makeEdge :: QEDS a -> a -> (QEDS a, EdgeRef)
- ring :: QEDS a -> (QEDS a -> EdgeRef -> EdgeRef) -> EdgeRef -> Stream EdgeRef
- onext :: QEDS a -> EdgeRef -> EdgeRef
- oprev :: QEDS a -> EdgeRef -> EdgeRef
- lnext :: QEDS a -> EdgeRef -> EdgeRef
- lprev :: QEDS a -> EdgeRef -> EdgeRef
- rnext :: QEDS a -> EdgeRef -> EdgeRef
- rprev :: QEDS a -> EdgeRef -> EdgeRef
- dnext :: QEDS a -> EdgeRef -> EdgeRef
- dprev :: QEDS a -> EdgeRef -> EdgeRef
- comp :: (EdgeRef -> a) -> (b -> EdgeRef) -> QEDS d -> b -> a
- oprevM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- lnextM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- lprevM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- rnextM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- rprevM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- dnextM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- dprevM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- onextM :: MQEDS s a -> EdgeRef -> ST s EdgeRef
- compM :: (EdgeRef -> b) -> (t -> EdgeRef) -> MQEDS s a -> t -> ST s b
- module Data.QuadEdge.Base
Documentation
Creation
Topological modification
mutate :: QEDS a -> (forall s. MQEDS s a -> ST s ()) -> QEDS aSource
Opens up the QEDS for in-place toplogical modification
mutateNEs :: QEDS a -> [a] -> ([EdgeRef] -> forall s. MQEDS s a -> ST s ()) -> (QEDS a, [EdgeRef])Source
Create a group of new edges and open up the QEDS
mutateNE :: QEDS a -> a -> (EdgeRef -> forall s. MQEDS s a -> ST s ()) -> (QEDS a, EdgeRef)Source
Create a new edge and open up the QEDS
Edge queries
randomEdgeRef :: RandomGen g => QEDS a -> g -> (EdgeRef, g)Source
Return a random valid EdgeRef
Edge updating
updateAttr :: QEDS a -> EdgeRef -> a -> QEDS aSource
Alternate edge creation/deletion routines
deleteEdges :: QEDS a -> Stream EdgeRef -> QEDS aSource
Delete a set of edges in one pass, using mutate and deleteEdgeM
Adjacency Rings
ring :: QEDS a -> (QEDS a -> EdgeRef -> EdgeRef) -> EdgeRef -> Stream EdgeRefSource
Returns a stream of adjacent edges using the given Adjacency Operator
Adjacency Operators
Adjacency Operators (ST)
module Data.QuadEdge.Base