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.

Synopsis

# Documentation

type QEDS a = Vector (Maybe (Edge a))Source

type MQEDS s a = MVector s (Maybe (Edge a))Source

# Creation

Create an empty QEDS

# 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

spliceM :: MQEDS s a -> EdgeRef -> EdgeRef -> ST s ()Source

deleteEdgeM :: MQEDS s a -> EdgeRef -> ST s ()Source

Delete an edge while in mutate mode

# Edge queries

edges :: QEDS a -> Vector (Edge a)Source

Return all valid edges in the QEDS

Return all valid edge references in the QEDS

getEdge :: QEDS a -> EdgeRef -> Edge aSource

Look up an edge. The edge must be valid.

getAttr :: QEDS a -> EdgeRef -> aSource

Look up the attributes of an edge. The edge must be valid.

randomEdgeRef :: RandomGen g => QEDS a -> g -> (EdgeRef, g)Source

Return a random valid EdgeRef

isValid :: QEDS a -> EdgeRef -> BoolSource

Check if an EdgeRef points to an active Edge

# Edge updating

updateAttr :: QEDS a -> EdgeRef -> a -> QEDS aSource

# Alternate edge creation/deletion routines

Delete a set of edges in one pass, using mutate and deleteEdgeM

makeEdge :: QEDS a -> a -> (QEDS a, EdgeRef)Source

ring :: QEDS a -> (QEDS a -> EdgeRef -> EdgeRef) -> EdgeRef -> Stream EdgeRefSource

onext :: QEDS a -> EdgeRef -> EdgeRefSource

CCW around the origin

oprev :: QEDS a -> EdgeRef -> EdgeRefSource

CW around the origin

lnext :: QEDS a -> EdgeRef -> EdgeRefSource

CCW around the left face

lprev :: QEDS a -> EdgeRef -> EdgeRefSource

CW around the left face

rnext :: QEDS a -> EdgeRef -> EdgeRefSource

CCW around the right face

rprev :: QEDS a -> EdgeRef -> EdgeRefSource

CW around the right face

dnext :: QEDS a -> EdgeRef -> EdgeRefSource

CCW around the destination

dprev :: QEDS a -> EdgeRef -> EdgeRefSource

CW around the destination

comp :: (EdgeRef -> a) -> (b -> EdgeRef) -> QEDS d -> b -> aSource