hgeometry-combinatorial-0.12.0.1: Data structures, and Data types.
Safe HaskellNone
LanguageHaskell2010

Data.PlanarGraph.Mutable

Synopsis

Planar graphs

data PlanarGraph s Source #

Instances

Instances details
Eq (PlanarGraph s) Source # 
Instance details

Defined in Data.PlanarGraph.Internal

pgFromFaces :: [[VertexId]] -> ST s (PlanarGraph s) Source #

\( O(n \log n) \)

Examples:

Expand
pgFromFaces [[0,1,2]]

pgFromFaces [[0,1,2,3]]

pgClone :: PlanarGraph s -> ST s (PlanarGraph s) Source #

\( O(n) \)

Elements

Vertices

data Vertex s Source #

Instances

Instances details
Eq (Vertex s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Vertex s -> Vertex s -> Bool #

(/=) :: Vertex s -> Vertex s -> Bool #

Show (Vertex s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> Vertex s -> ShowS #

show :: Vertex s -> String #

showList :: [Vertex s] -> ShowS #

Hashable (Vertex s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

hashWithSalt :: Int -> Vertex s -> Int #

hash :: Vertex s -> Int #

vertexToId :: Vertex s -> VertexId Source #

\( O(1) \)

vertexHalfEdge :: Vertex s -> ST s (HalfEdge s) Source #

\( O(1) \)

vertexIsBoundary :: Vertex s -> ST s Bool Source #

\( O(1) \)

vertexWithOutgoingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s () Source #

O(k), more efficient than vertexOutgoingHalfEdges.

vertexWithIncomingHalfEdges :: Vertex s -> (HalfEdge s -> ST s ()) -> ST s () Source #

O(k)

Edges

data Edge s Source #

Instances

Instances details
Eq (Edge s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Edge s -> Edge s -> Bool #

(/=) :: Edge s -> Edge s -> Bool #

Half-edges

data HalfEdge s Source #

Instances

Instances details
Eq (HalfEdge s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: HalfEdge s -> HalfEdge s -> Bool #

(/=) :: HalfEdge s -> HalfEdge s -> Bool #

Show (HalfEdge s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> HalfEdge s -> ShowS #

show :: HalfEdge s -> String #

showList :: [HalfEdge s] -> ShowS #

Hashable (HalfEdge s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

hashWithSalt :: Int -> HalfEdge s -> Int #

hash :: HalfEdge s -> Int #

halfEdgeNextOutgoing :: HalfEdge s -> ST s (HalfEdge s) Source #

O(1) Next half-edge with the same vertex.

halfEdgeNextIncoming :: HalfEdge s -> ST s (HalfEdge s) Source #

O(1) Next half-edge with the same vertex.

halfEdgeTailVertex :: HalfEdge s -> ST s (Vertex s) Source #

O(1) Tail vertex. IE. the vertex of the twin edge.

halfEdgeTipVertex :: HalfEdge s -> ST s (Vertex s) Source #

O(1) Synonym of halfEdgeVertex.

halfEdgeFace :: HalfEdge s -> ST s (Face s) Source #

\( O(1) \)

Examples:

Expand
pgFromFaces [[0,1,2]]

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 0 pg)
"Face 0"
>>> runST $ do pg <- pgFromFaces [[0,1,2]]; show <$> halfEdgeFace (halfEdgeFromId 1 pg)
"Boundary 0"

halfEdgeIsInterior :: HalfEdge s -> ST s Bool Source #

\( O(1) \) Check if a half-edge's face is interior or exterior.

Examples:

Expand
pgFromFaces [[0,1,2]]

>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 0 pg)
True
>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 1 pg)
False
>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 2 pg)
True
>>> runST $ do pg <- pgFromFaces [[0,1,2]]; halfEdgeIsInterior (halfEdgeFromId 3 pg)
False

Faces

data Face s Source #

Instances

Instances details
Eq (Face s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

(==) :: Face s -> Face s -> Bool #

(/=) :: Face s -> Face s -> Bool #

Show (Face s) Source # 
Instance details

Defined in Data.PlanarGraph.Mutable

Methods

showsPrec :: Int -> Face s -> ShowS #

show :: Face s -> String #

showList :: [Face s] -> ShowS #

type FaceId = Int Source #

Numerical face identifier. Negative numbers indicate boundaries, non-negative numbers are internal faces.

faceHalfEdge :: Face s -> ST s (HalfEdge s) Source #

O(1)

faceHalfEdges :: Face s -> ST s (CircularVector (HalfEdge s)) Source #

O(k) Counterclockwise vector of edges.

Mutation

pgConnectVertices :: HalfEdge s -> HalfEdge s -> ST s (Edge s) Source #

O(k) where k is the number of edges in new face.

The two half-edges must be different, must have the same face, and may not be consecutive. The first half-edge will stay in the original face. The second half-edge will be in the newly created face.

Examples:

Expand
pgFromFaces [[0,1,2,3]]

do pg <- pgFromFaces [[0,1,2,3]]
   let he0 = halfEdgeFromId 0 pg'
       he4 = halfEdgeFromId 4 pg'
   pgConnectVertices he0 he4

Misc