hgeometry-combinatorial-0.9.0.0: Data structures, and Data types.

Data.PlanarGraph.Dual

Description

Data type for representing connected planar graphs. This module contains everything that has to do with the dual graph (i.e. computing it/ operations on faces etc.)

Synopsis

# Documentation

>>> :{
let dart i s = Dart (Arc i) (read s)
(aA:aB:aC:aD:aE:aG:_) = take 6 [Arc 0..]
myGraph :: PlanarGraph () Primal () String ()
myGraph = planarGraph [ [ (Dart aA Negative, "a-")
, (Dart aC Positive, "c+")
, (Dart aB Positive, "b+")
, (Dart aA Positive, "a+")
]
, [ (Dart aE Negative, "e-")
, (Dart aB Negative, "b-")
, (Dart aG Positive, "g+")
]
, [ (Dart aE Positive, "e+")
, (Dart aC Negative, "c-")
]
, [ (Dart aG Negative, "g-")
]
]
:}


This represents the following graph. Note that the graph is undirected, the arrows are just to indicate what the Positive direction of the darts is. faces' :: PlanarGraph s w v e f -> Vector (FaceId s w) Source #

Enumerate all faces in the planar graph

faces :: PlanarGraph s w v e f -> Vector (FaceId s w, f) Source #

All faces with their face data.

leftFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w Source #

The face to the left of the dart

>>> leftFace (dart 1 "+1") myGraph
FaceId 1
>>> leftFace (dart 1 "-1") myGraph
FaceId 2
>>> leftFace (dart 2 "+1") myGraph
FaceId 2
>>> leftFace (dart 0 "+1") myGraph
FaceId 0


running time: $$O(1)$$.

rightFace :: Dart s -> PlanarGraph s w v e f -> FaceId s w Source #

The face to the right of the dart

>>> rightFace (dart 1 "+1") myGraph
FaceId 2
>>> rightFace (dart 1 "-1") myGraph
FaceId 1
>>> rightFace (dart 2 "+1") myGraph
FaceId 1
>>> rightFace (dart 0 "+1") myGraph
FaceId 1


running time: $$O(1)$$.

nextEdge :: Dart s -> PlanarGraph s w v e f -> Dart s Source #

Get the next edge along the face

running time: $$O(1)$$.

prevEdge :: Dart s -> PlanarGraph s w v e f -> Dart s Source #

Get the previous edge along the face

running time: $$O(1)$$.

boundaryDart :: FaceId s w -> PlanarGraph s w v e f -> Dart s Source #

Gets a dart bounding this face. I.e. a dart d such that the face lies to the right of the dart.

boundary :: FaceId s w -> PlanarGraph s w v e f -> Vector (Dart s) Source #

The darts bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: $$O(k)$$, where $$k$$ is the output size.

boundary' :: Dart s -> PlanarGraph s w v e f -> Vector (Dart s) Source #

Generates the darts incident to a face, starting with the given dart.

$$O(k)$$, where $$k$$ is the number of darts reported

boundaryVertices :: FaceId s w -> PlanarGraph s w v e f -> Vector (VertexId s w) Source #

The vertices bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.

running time: $$O(k)$$, where $$k$$ is the output size.