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

Data.PlaneGraph.Core

Description

Data type for planar graphs embedded in $$\mathbb{R}^2$$. For functions that export faces and edges etc, we assume the graph has a (planar) straight line embedding.

Synopsis

# Documentation

>>> import Data.Proxy
>>> import Data.PlaneGraph.AdjRep(Gr(Gr),Face(Face),Vtx(Vtx))
>>> import Data.PlaneGraph.IO(fromAdjRep)
>>> import Data.PlanarGraph.Dart(Dart(..),Arc(..))
>>> :{
let dart i s = Dart (Arc i) (read s)
small :: Gr (Vtx Int String Int) (Face String)
small = Gr [ Vtx 0 (Point2 0 0) [ (2,"0->2")
, (1,"0->1")
, (3,"0->3")
] 0
, Vtx 1 (Point2 2 2) [ (0,"1->0")
, (2,"1->2")
, (3,"1->3")
] 1
, Vtx 2 (Point2 2 0) [ (0,"2->0")
, (1,"2->1")
] 2
, Vtx 3 (Point2 (-1) 4) [ (0,"3->0")
, (1,"3->1")
] 3
]
[ Face (2,1) "OuterFace"
, Face (0,1) "A"
, Face (1,0) "B"
]
smallG = fromAdjRep (Proxy :: Proxy ()) small
:}


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. newtype PlaneGraph s v e f r Source #

Embedded, *connected*, planar graph

Constructors

 PlaneGraph (PlanarGraph s Primal (VertexData r v) e f)
Instances
 Functor (PlaneGraph s v e f) Source # Instance detailsDefined in Data.PlaneGraph.Core Methodsfmap :: (a -> b) -> PlaneGraph s v e f a -> PlaneGraph s v e f b #(<$) :: a -> PlaneGraph s v e f b -> PlaneGraph s v e f a # (Eq r, Eq v, Eq e, Eq f) => Eq (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core Methods(==) :: PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool #(/=) :: PlaneGraph s v e f r -> PlaneGraph s v e f r -> Bool # (Show r, Show v, Show e, Show f) => Show (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core MethodsshowsPrec :: Int -> PlaneGraph s v e f r -> ShowS #show :: PlaneGraph s v e f r -> String #showList :: [PlaneGraph s v e f r] -> ShowS # Generic (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype Rep (PlaneGraph s v e f r) :: Type -> Type # Methodsfrom :: PlaneGraph s v e f r -> Rep (PlaneGraph s v e f r) x #to :: Rep (PlaneGraph s v e f r) x -> PlaneGraph s v e f r # (ToJSON v, ToJSON e, ToJSON f, ToJSON r) => ToJSON (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.IO MethodstoJSON :: PlaneGraph s v e f r -> Value #toEncoding :: PlaneGraph s v e f r -> Encoding #toJSONList :: [PlaneGraph s v e f r] -> Value #toEncodingList :: [PlaneGraph s v e f r] -> Encoding # (FromJSON v, FromJSON e, FromJSON f, FromJSON r) => FromJSON (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.IO MethodsparseJSON :: Value -> Parser (PlaneGraph s v e f r) #parseJSONList :: Value -> Parser [PlaneGraph s v e f r] # IsBoxable (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core MethodsboundingBox :: PlaneGraph s v e f r -> Box (Dimension (PlaneGraph s v e f r)) () (NumType (PlaneGraph s v e f r)) Source # HasDataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (FaceId' s) :: Type # MethodsdataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s)) # HasDataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s)) # HasDataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (VertexId' s) :: Type # MethodsdataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s)) # type Rep (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core type Rep (PlaneGraph s v e f r) = D1 (MetaData "PlaneGraph" "Data.PlaneGraph.Core" "hgeometry-0.11.0.0-5Q7X7STHtn33ZJbJEL0QVy" True) (C1 (MetaCons "PlaneGraph" PrefixI True) (S1 (MetaSel (Just "_graph") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (PlanarGraph s Primal (VertexData r v) e f)))) type NumType (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core type NumType (PlaneGraph s v e f r) = r type Dimension (PlaneGraph s v e f r) Source # Instance detailsDefined in Data.PlaneGraph.Core type Dimension (PlaneGraph s v e f r) = 2 type DataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (FaceId' s) = f type DataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (Dart s) = e type DataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (VertexId' s) = v graph :: forall s v e f r s v e f r. Iso (PlaneGraph s v e f r) (PlaneGraph s v e f r) (PlanarGraph s Primal (VertexData r v) e f) (PlanarGraph s Primal (VertexData r v) e f) Source # data PlanarGraph (s :: k) (w :: World) v e f :: forall k. k -> World -> Type -> Type -> Type -> Type # A *connected* Planar graph with bidirected edges. I.e. the edges (darts) are directed, however, for every directed edge, the edge in the oposite direction is also in the graph. The types v, e, and f are the are the types of the data associated with the vertices, edges, and faces, respectively. The orbits in the embedding are assumed to be in counterclockwise order. Therefore, every dart directly bounds the face to its right. Instances  (Eq v, Eq e, Eq f) => Eq (PlanarGraph s w v e f) Instance detailsDefined in Data.PlanarGraph.Core Methods(==) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool #(/=) :: PlanarGraph s w v e f -> PlanarGraph s w v e f -> Bool # (Show v, Show e, Show f) => Show (PlanarGraph s w v e f) Instance detailsDefined in Data.PlanarGraph.Core MethodsshowsPrec :: Int -> PlanarGraph s w v e f -> ShowS #show :: PlanarGraph s w v e f -> String #showList :: [PlanarGraph s w v e f] -> ShowS # Generic (PlanarGraph s w v e f) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype Rep (PlanarGraph s w v e f) :: Type -> Type # Methodsfrom :: PlanarGraph s w v e f -> Rep (PlanarGraph s w v e f) x #to :: Rep (PlanarGraph s w v e f) x -> PlanarGraph s w v e f # HasDataOf (PlanarGraph s w v e f) (Dart s) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: Type # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: Type # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) # type Rep (PlanarGraph s w v e f) Instance detailsDefined in Data.PlanarGraph.Core type Rep (PlanarGraph s w v e f) = D1 (MetaData "PlanarGraph" "Data.PlanarGraph.Core" "hgeometry-combinatorial-0.11.0.0-Cktt0ZWYuCrAhHfx7XTJDd" False) (C1 (MetaCons "PlanarGraph" PrefixI True) ((S1 (MetaSel (Just "_embedding") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Permutation (Dart s))) :*: S1 (MetaSel (Just "_vertexData") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Vector v))) :*: (S1 (MetaSel (Just "_rawDartData") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Vector e)) :*: (S1 (MetaSel (Just "_faceData") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Vector f)) :*: S1 (MetaSel (Just "_dual") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (PlanarGraph s (DualOf w) f e v)))))) type DataOf (PlanarGraph s w v e f) (Dart s) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (Dart s) = e type DataOf (PlanarGraph s w v e f) (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (VertexId s w) = v type DataOf (PlanarGraph s w v e f) (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (FaceId s w) = f data VertexData r v Source # Note that the functor instance is in v Constructors  VertexData !(Point 2 r) !v Instances  Source # Instance detailsDefined in Data.PlaneGraph.Core Methodsbimap :: (a -> b) -> (c -> d) -> VertexData a c -> VertexData b d #first :: (a -> b) -> VertexData a c -> VertexData b c #second :: (b -> c) -> VertexData a b -> VertexData a c # Source # Instance detailsDefined in Data.PlaneGraph.Core Methodsfmap :: (a -> b) -> VertexData r a -> VertexData r b #(<$) :: a -> VertexData r b -> VertexData r a # Source # Instance detailsDefined in Data.PlaneGraph.Core Methodsfold :: Monoid m => VertexData r m -> m #foldMap :: Monoid m => (a -> m) -> VertexData r a -> m #foldr :: (a -> b -> b) -> b -> VertexData r a -> b #foldr' :: (a -> b -> b) -> b -> VertexData r a -> b #foldl :: (b -> a -> b) -> b -> VertexData r a -> b #foldl' :: (b -> a -> b) -> b -> VertexData r a -> b #foldr1 :: (a -> a -> a) -> VertexData r a -> a #foldl1 :: (a -> a -> a) -> VertexData r a -> a #toList :: VertexData r a -> [a] #null :: VertexData r a -> Bool #length :: VertexData r a -> Int #elem :: Eq a => a -> VertexData r a -> Bool #maximum :: Ord a => VertexData r a -> a #minimum :: Ord a => VertexData r a -> a #sum :: Num a => VertexData r a -> a #product :: Num a => VertexData r a -> a # Source # Instance detailsDefined in Data.PlaneGraph.Core Methodstraverse :: Applicative f => (a -> f b) -> VertexData r a -> f (VertexData r b) #sequenceA :: Applicative f => VertexData r (f a) -> f (VertexData r a) #mapM :: Monad m => (a -> m b) -> VertexData r a -> m (VertexData r b) #sequence :: Monad m => VertexData r (m a) -> m (VertexData r a) # (Eq r, Eq v) => Eq (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core Methods(==) :: VertexData r v -> VertexData r v -> Bool #(/=) :: VertexData r v -> VertexData r v -> Bool # (Ord r, Ord v) => Ord (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core Methodscompare :: VertexData r v -> VertexData r v -> Ordering #(<) :: VertexData r v -> VertexData r v -> Bool #(<=) :: VertexData r v -> VertexData r v -> Bool #(>) :: VertexData r v -> VertexData r v -> Bool #(>=) :: VertexData r v -> VertexData r v -> Bool #max :: VertexData r v -> VertexData r v -> VertexData r v #min :: VertexData r v -> VertexData r v -> VertexData r v # (Show r, Show v) => Show (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core MethodsshowsPrec :: Int -> VertexData r v -> ShowS #show :: VertexData r v -> String #showList :: [VertexData r v] -> ShowS # Generic (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype Rep (VertexData r v) :: Type -> Type # Methodsfrom :: VertexData r v -> Rep (VertexData r v) x #to :: Rep (VertexData r v) x -> VertexData r v # (ToJSON r, ToJSON v) => ToJSON (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core MethodstoJSON :: VertexData r v -> Value #toEncoding :: VertexData r v -> Encoding #toJSONList :: [VertexData r v] -> Value #toEncodingList :: [VertexData r v] -> Encoding # (FromJSON r, FromJSON v) => FromJSON (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core MethodsparseJSON :: Value -> Parser (VertexData r v) #parseJSONList :: Value -> Parser [VertexData r v] # type Rep (VertexData r v) Source # Instance detailsDefined in Data.PlaneGraph.Core type Rep (VertexData r v) = D1 (MetaData "VertexData" "Data.PlaneGraph.Core" "hgeometry-0.11.0.0-5Q7X7STHtn33ZJbJEL0QVy" False) (C1 (MetaCons "VertexData" PrefixI True) (S1 (MetaSel (Just "_location") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Point 2 r)) :*: S1 (MetaSel (Just "_vData") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 v)))

vData :: forall r v v. Lens (VertexData r v) (VertexData r v) v v Source #

location :: forall r v r. Lens (VertexData r v) (VertexData r v) (Point 2 r) (Point 2 r) Source #

Arguments

 :: proxy s -> SimplePolygon p r -> f data inside -> f data outside the polygon -> PlaneGraph s p () f r

Construct a plane graph from a simple polygon. It is assumed that the polygon is given in counterclockwise order.

the interior of the polygon will have faceId 0

pre: the input polygon is given in counterclockwise order running time: $$O(n)$$.

fromConnectedSegments :: (Foldable f, Ord r, Num r) => proxy s -> f (LineSegment 2 p r :+ e) -> PlaneGraph s (NonEmpty p) e () r Source #

Constructs a connected plane graph

pre: The segments form a single connected component

running time: $$O(n\log n)$$

fromAdjacencyLists :: (Foldable h, Functor h) => [(VertexId s w, h (VertexId s w))] -> PlanarGraph s w () () () #

Construct a planar graph from a adjacency matrix. For every vertex, all vertices should be given in counter-clockwise order.

pre: No self-loops, and no multi-edges

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

numVertices :: PlaneGraph s v e f r -> Int Source #

Get the number of vertices

>>> numVertices smallG
4


numEdges :: PlaneGraph s v e f r -> Int Source #

Get the number of Edges

>>> numEdges smallG
5


numFaces :: PlaneGraph s v e f r -> Int Source #

Get the number of faces

>>> numFaces smallG
3


numDarts :: PlaneGraph s v e f r -> Int Source #

Get the number of Darts

>>> numDarts smallG
10


dual :: Getter (PlanarGraph s w v e f) (PlanarGraph s (DualOf w) f e v) #

Get the dual graph of this graph.

vertices' :: PlaneGraph s v e f r -> Vector (VertexId' s) Source #

Enumerate all vertices

>>> vertices' smallG
[VertexId 0,VertexId 1,VertexId 2,VertexId 3]


vertices :: PlaneGraph s v e f r -> Vector (VertexId' s, VertexData r v) Source #

Enumerate all vertices, together with their vertex data

>>> mapM_ print $vertices smallG (VertexId 0,VertexData {_location = Point2 [0,0], _vData = 0}) (VertexId 1,VertexData {_location = Point2 [2,2], _vData = 1}) (VertexId 2,VertexData {_location = Point2 [2,0], _vData = 2}) (VertexId 3,VertexData {_location = Point2 [-1,4], _vData = 3})  edges' :: PlaneGraph s v e f r -> Vector (Dart s) Source # Enumerate all edges. We report only the Positive darts edges :: PlaneGraph s v e f r -> Vector (Dart s, e) Source # Enumerate all edges with their edge data. We report only the Positive darts. >>> mapM_ print$ edges smallG
(Dart (Arc 0) +1,"0->2")
(Dart (Arc 1) +1,"0->1")
(Dart (Arc 2) +1,"0->3")
(Dart (Arc 4) +1,"1->2")
(Dart (Arc 3) +1,"1->3")


faces' :: PlaneGraph s v e f r -> Vector (FaceId' s) Source #

Enumerate all faces in the plane graph

faces :: PlaneGraph s v e f r -> Vector (FaceId' s, f) Source #

All faces with their face data.

>>> mapM_ print $faces smallG (FaceId 0,"OuterFace") (FaceId 1,"A") (FaceId 2,"B")  internalFaces :: (Ord r, Fractional r) => PlaneGraph s v e f r -> Vector (FaceId' s, f) Source # Reports all internal faces. running time: $$O(n)$$ faces'' :: (Ord r, Fractional r) => PlaneGraph s v e f r -> ((FaceId' s, f), Vector (FaceId' s, f)) Source # Reports the outerface and all internal faces separately. running time: $$O(n)$$ darts' :: PlaneGraph s v e f r -> Vector (Dart s) Source # Enumerate all darts darts :: PlaneGraph s v e f r -> Vector (Dart s, e) Source # Get all darts together with their data traverseVertices :: Applicative m => (VertexId' s -> v -> m v') -> PlaneGraph s v e f r -> m (PlaneGraph s v' e f r) Source # Traverse the vertices (^.vertexData)$ traverseVertices (i x -> Just (i,x)) smallG Just [(VertexId 0,0),(VertexId 1,1),(VertexId 2,2),(VertexId 3,3)] >>> traverseVertices (i x -> print (i,x)) smallG >> pure () (VertexId 0,0) (VertexId 1,1) (VertexId 2,2) (VertexId 3,3)

traverseDarts :: Applicative m => (Dart s -> e -> m e') -> PlaneGraph s v e f r -> m (PlaneGraph s v e' f r) Source #

Traverses the darts

>>> traverseDarts (\d x -> print (d,x)) smallG >> pure ()
(Dart (Arc 0) +1,"0->2")
(Dart (Arc 0) -1,"2->0")
(Dart (Arc 1) +1,"0->1")
(Dart (Arc 1) -1,"1->0")
(Dart (Arc 2) +1,"0->3")
(Dart (Arc 2) -1,"3->0")
(Dart (Arc 3) +1,"1->3")
(Dart (Arc 3) -1,"3->1")
(Dart (Arc 4) +1,"1->2")
(Dart (Arc 4) -1,"2->1")


traverseFaces :: Applicative m => (FaceId' s -> f -> m f') -> PlaneGraph s v e f r -> m (PlaneGraph s v e f' r) Source #

Traverses the faces

>>> traverseFaces (\i x -> print (i,x)) smallG >> pure ()
(FaceId 0,"OuterFace")
(FaceId 1,"A")
(FaceId 2,"B")


headOf :: Dart s -> PlaneGraph s v e f r -> VertexId' s Source #

The vertex this dart is heading in to

running time: $$O(1)$$

>>> headOf (dart 0 "+1") smallG
VertexId 2


tailOf :: Dart s -> PlaneGraph s v e f r -> VertexId' s Source #

The tail of a dart, i.e. the vertex this dart is leaving from

running time: $$O(1)$$

>>> tailOf (dart 0 "+1") smallG
VertexId 0


twin :: Dart s -> Dart s #

Get the twin of this dart (edge)

>>> twin (dart 0 "+1")
Dart (Arc 0) -1
>>> twin (dart 0 "-1")
Dart (Arc 0) +1


endPoints :: Dart s -> PlaneGraph s v e f r -> (VertexId' s, VertexId' s) Source #

endPoints d g = (tailOf d g, headOf d g)

running time: $$O(1)$$

>>> endPoints (dart 0 "+1") smallG
(VertexId 0,VertexId 2)


incidentEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s) Source #

All edges incident to vertex v, in counterclockwise order around v.

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

>>> incidentEdges (VertexId 1) smallG
[Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]


incomingEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s) Source #

All edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v.

running time: $$O(k)$$, where (k) is the total number of incident edges of v

>>> incomingEdges (VertexId 1) smallG
[Dart (Arc 1) +1,Dart (Arc 4) -1,Dart (Arc 3) -1]


outgoingEdges :: VertexId' s -> PlaneGraph s v e f r -> Vector (Dart s) Source #

All edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v.

running time: $$O(k)$$, where (k) is the total number of incident edges of v

>>> outgoingEdges (VertexId 1) smallG
[Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]


neighboursOf :: VertexId' s -> PlaneGraph s v e f r -> Vector (VertexId' s) Source #

Gets the neighbours of a particular vertex, in counterclockwise order around the vertex.

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

>>> neighboursOf (VertexId 1) smallG
[VertexId 0,VertexId 2,VertexId 3]


nextIncidentEdge :: Dart s -> PlaneGraph s v e f r -> Dart s Source #

Given a dart d that points into some vertex v, report the next dart in the cyclic order around v in clockwise direction.

running time: $$O(1)$$

>>> nextIncidentEdge (dart 1 "+1") smallG
Dart (Arc 2) +1


prevIncidentEdge :: Dart s -> PlaneGraph s v e f r -> Dart s Source #

Given a dart d that points into some vertex v, report the next dart in the cyclic order around v (in clockwise order)

running time: $$O(1)$$

>>> prevIncidentEdge (dart 1 "+1") smallG
Dart (Arc 0) +1


leftFace :: Dart s -> PlaneGraph s v e f r -> FaceId' s Source #

The face to the left of the dart

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

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


rightFace :: Dart s -> PlaneGraph s v e f r -> FaceId' s Source #

The face to the right of the dart

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

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


nextEdge :: Dart s -> PlaneGraph s v e f r -> Dart s Source #

Get the next edge along the face

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

>>> nextEdge (dart 1 "+1") smallG
Dart (Arc 4) +1


prevEdge :: Dart s -> PlaneGraph s v e f r -> Dart s Source #

Get the previous edge along the face

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

>>> prevEdge (dart 1 "+1") smallG
Dart (Arc 0) -1


boundary :: FaceId' s -> PlaneGraph s v e f r -> 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 -> PlaneGraph s v e f r -> 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

boundaryDart :: FaceId' s -> PlaneGraph s v e f r -> 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.

boundaryVertices :: FaceId' s -> PlaneGraph s v e f r -> Vector (VertexId' s) 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.

outerFaceId :: (Ord r, Fractional r) => PlaneGraph s v e f r -> FaceId' s Source #

gets the id of the outer face

running time: $$O(n)$$

outerFaceDart :: (Ord r, Fractional r) => PlaneGraph s v e f r -> Dart s Source #

gets a dart incident to the outer face (in particular, that has the outerface on its left)

running time: $$O(n)$$

locationOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (Point 2 r) Source #

class HasDataOf g i where #

Associated Types

type DataOf g i :: Type #

Methods

dataOf :: i -> Lens' g (DataOf g i) #

get the data associated with the value i.

running time: $$O(1)$$ to read the data, $$O(n)$$ to write it.

Instances
 HasDataOf (PlanarGraph s w v e f) (Dart s) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) # HasDataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (FaceId' s) :: Type # MethodsdataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s)) # HasDataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s)) # HasDataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (VertexId' s) :: Type # MethodsdataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s)) # HasDataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: Type # MethodsdataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s)) # HasDataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s)) # HasDataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: Type # MethodsdataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s)) # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: Type # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: Type # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) #

endPointsOf :: Dart s -> Getter (PlaneGraph s v e f r) (VertexData r v, VertexData r v) Source #

Getter for the data at the endpoints of a dart

running time: $$O(1)$$

endPointData :: Dart s -> PlaneGraph s v e f r -> (VertexData r v, VertexData r v) Source #

Data corresponding to the endpoints of the dart

running time: $$O(1)$$

vertexData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v' e f r) (Vector v) (Vector v') Source #

faceData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v e f' r) (Vector f) (Vector f') Source #

Lens to access face data

dartData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v e' f r) (Vector (Dart s, e)) (Vector (Dart s, e')) Source #

lens to access the Dart Data

rawDartData :: Lens (PlaneGraph s v e f r) (PlaneGraph s v e' f r) (Vector e) (Vector e') Source #

Lens to access the raw dart data, use at your own risk

edgeSegment :: Dart s -> PlaneGraph s v e f r -> LineSegment 2 v r :+ e Source #

Given a dart and the graph constructs the line segment representing the dart. The segment $$\overline{uv})$$ is has $$u$$ as its tail and $$v$$ as its head.

$$O(1)$$

edgeSegments :: PlaneGraph s v e f r -> Vector (Dart s, LineSegment 2 v r :+ e) Source #

Reports all edges as line segments

>>> mapM_ print \$ edgeSegments smallG
(Dart (Arc 0) +1,LineSegment (Closed (Point2 [0,0] :+ 0)) (Closed (Point2 [2,0] :+ 2)) :+ "0->2")
(Dart (Arc 1) +1,LineSegment (Closed (Point2 [0,0] :+ 0)) (Closed (Point2 [2,2] :+ 1)) :+ "0->1")
(Dart (Arc 2) +1,LineSegment (Closed (Point2 [0,0] :+ 0)) (Closed (Point2 [-1,4] :+ 3)) :+ "0->3")
(Dart (Arc 4) +1,LineSegment (Closed (Point2 [2,2] :+ 1)) (Closed (Point2 [2,0] :+ 2)) :+ "1->2")
(Dart (Arc 3) +1,LineSegment (Closed (Point2 [2,2] :+ 1)) (Closed (Point2 [-1,4] :+ 3)) :+ "1->3")


rawFacePolygon :: FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f Source #

Alias for rawFace Boundary

runningtime: $$O(k)$$, where $$k$$ is the size of the face.

rawFaceBoundary :: FaceId' s -> PlaneGraph s v e f r -> SimplePolygon v r :+ f Source #

The polygon describing the face

runningtime: $$O(k)$$, where $$k$$ is the size of the face.

rawFacePolygons :: PlaneGraph s v e f r -> Vector (FaceId' s, SimplePolygon v r :+ f) Source #

Lists all faces of the plane graph.

newtype VertexId (s :: k) (w :: World) :: forall k. k -> World -> Type #

A vertex in a planar graph. A vertex is tied to a particular planar graph by the phantom type s, and to a particular world w.

Constructors

 VertexId Fields_unVertexId :: Int
Instances
 Enum (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Methodssucc :: VertexId s w -> VertexId s w #pred :: VertexId s w -> VertexId s w #toEnum :: Int -> VertexId s w #fromEnum :: VertexId s w -> Int #enumFrom :: VertexId s w -> [VertexId s w] #enumFromThen :: VertexId s w -> VertexId s w -> [VertexId s w] #enumFromTo :: VertexId s w -> VertexId s w -> [VertexId s w] #enumFromThenTo :: VertexId s w -> VertexId s w -> VertexId s w -> [VertexId s w] # Eq (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Methods(==) :: VertexId s w -> VertexId s w -> Bool #(/=) :: VertexId s w -> VertexId s w -> Bool # Ord (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Methodscompare :: VertexId s w -> VertexId s w -> Ordering #(<) :: VertexId s w -> VertexId s w -> Bool #(<=) :: VertexId s w -> VertexId s w -> Bool #(>) :: VertexId s w -> VertexId s w -> Bool #(>=) :: VertexId s w -> VertexId s w -> Bool #max :: VertexId s w -> VertexId s w -> VertexId s w #min :: VertexId s w -> VertexId s w -> VertexId s w # Show (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodsshowsPrec :: Int -> VertexId s w -> ShowS #show :: VertexId s w -> String #showList :: [VertexId s w] -> ShowS # Generic (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype Rep (VertexId s w) :: Type -> Type # Methodsfrom :: VertexId s w -> Rep (VertexId s w) x #to :: Rep (VertexId s w) x -> VertexId s w # ToJSON (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodstoJSON :: VertexId s w -> Value #toEncoding :: VertexId s w -> Encoding #toJSONList :: [VertexId s w] -> Value #toEncodingList :: [VertexId s w] -> Encoding # FromJSON (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodsparseJSON :: Value -> Parser (VertexId s w) #parseJSONList :: Value -> Parser [VertexId s w] # NFData (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Methodsrnf :: VertexId s w -> () # HasDataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (VertexId' s) :: Type # MethodsdataOf :: VertexId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (VertexId' s)) # HasDataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (VertexId' s) :: Type # MethodsdataOf :: VertexId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (VertexId' s)) # HasDataOf (PlanarGraph s w v e f) (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (VertexId s w) :: Type # MethodsdataOf :: VertexId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (VertexId s w)) # type Rep (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core type Rep (VertexId s w) = D1 (MetaData "VertexId" "Data.PlanarGraph.Core" "hgeometry-combinatorial-0.11.0.0-Cktt0ZWYuCrAhHfx7XTJDd" True) (C1 (MetaCons "VertexId" PrefixI True) (S1 (MetaSel (Just "_unVertexId") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 Int))) type DataOf (PlaneGraph s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (VertexId' s) = v type DataOf (PlanarSubdivision s v e f r) (VertexId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (VertexId' s) = v type DataOf (PlanarGraph s w v e f) (VertexId s w) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (VertexId s w) = v

newtype FaceId (s :: k) (w :: World) :: forall k. k -> World -> Type #

The type to reprsent FaceId's

Constructors

 FaceId Fields_unFaceId :: VertexId s (DualOf w)
Instances
 Enum (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Methodssucc :: FaceId s w -> FaceId s w #pred :: FaceId s w -> FaceId s w #toEnum :: Int -> FaceId s w #fromEnum :: FaceId s w -> Int #enumFrom :: FaceId s w -> [FaceId s w] #enumFromThen :: FaceId s w -> FaceId s w -> [FaceId s w] #enumFromTo :: FaceId s w -> FaceId s w -> [FaceId s w] #enumFromThenTo :: FaceId s w -> FaceId s w -> FaceId s w -> [FaceId s w] # Eq (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Methods(==) :: FaceId s w -> FaceId s w -> Bool #(/=) :: FaceId s w -> FaceId s w -> Bool # Ord (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Methodscompare :: FaceId s w -> FaceId s w -> Ordering #(<) :: FaceId s w -> FaceId s w -> Bool #(<=) :: FaceId s w -> FaceId s w -> Bool #(>) :: FaceId s w -> FaceId s w -> Bool #(>=) :: FaceId s w -> FaceId s w -> Bool #max :: FaceId s w -> FaceId s w -> FaceId s w #min :: FaceId s w -> FaceId s w -> FaceId s w # Show (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodsshowsPrec :: Int -> FaceId s w -> ShowS #show :: FaceId s w -> String #showList :: [FaceId s w] -> ShowS # ToJSON (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodstoJSON :: FaceId s w -> Value #toEncoding :: FaceId s w -> Encoding #toJSONList :: [FaceId s w] -> Value #toEncodingList :: [FaceId s w] -> Encoding # FromJSON (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core MethodsparseJSON :: Value -> Parser (FaceId s w) #parseJSONList :: Value -> Parser [FaceId s w] # HasDataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (FaceId' s) :: Type # MethodsdataOf :: FaceId' s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (FaceId' s)) # HasDataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (FaceId' s) :: Type # MethodsdataOf :: FaceId' s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (FaceId' s)) # HasDataOf (PlanarGraph s w v e f) (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (FaceId s w) :: Type # MethodsdataOf :: FaceId s w -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (FaceId s w)) # type DataOf (PlaneGraph s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (FaceId' s) = f type DataOf (PlanarSubdivision s v e f r) (FaceId' s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (FaceId' s) = f type DataOf (PlanarGraph s w v e f) (FaceId s w) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (FaceId s w) = f

data Dart (s :: k) :: forall k. k -> Type #

A dart represents a bi-directed edge. I.e. a dart has a direction, however the dart of the oposite direction is always present in the planar graph as well.

Instances
 Enum (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart Methodssucc :: Dart s -> Dart s #pred :: Dart s -> Dart s #toEnum :: Int -> Dart s #fromEnum :: Dart s -> Int #enumFrom :: Dart s -> [Dart s] #enumFromThen :: Dart s -> Dart s -> [Dart s] #enumFromTo :: Dart s -> Dart s -> [Dart s] #enumFromThenTo :: Dart s -> Dart s -> Dart s -> [Dart s] # Eq (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart Methods(==) :: Dart s -> Dart s -> Bool #(/=) :: Dart s -> Dart s -> Bool # Ord (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart Methodscompare :: Dart s -> Dart s -> Ordering #(<) :: Dart s -> Dart s -> Bool #(<=) :: Dart s -> Dart s -> Bool #(>) :: Dart s -> Dart s -> Bool #(>=) :: Dart s -> Dart s -> Bool #max :: Dart s -> Dart s -> Dart s #min :: Dart s -> Dart s -> Dart s # Show (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart MethodsshowsPrec :: Int -> Dart s -> ShowS #show :: Dart s -> String #showList :: [Dart s] -> ShowS # Generic (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart Associated Typestype Rep (Dart s) :: Type -> Type # Methodsfrom :: Dart s -> Rep (Dart s) x #to :: Rep (Dart s) x -> Dart s # Instance detailsDefined in Data.PlanarGraph.Dart Methodsarbitrary :: Gen (Dart s) #shrink :: Dart s -> [Dart s] # NFData (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart Methodsrnf :: Dart s -> () # HasDataOf (PlanarGraph s w v e f) (Dart s) Instance detailsDefined in Data.PlanarGraph.Core Associated Typestype DataOf (PlanarGraph s w v e f) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlanarGraph s w v e f) (DataOf (PlanarGraph s w v e f) (Dart s)) # HasDataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph.Core Associated Typestype DataOf (PlaneGraph s v e f r) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlaneGraph s v e f r) (DataOf (PlaneGraph s v e f r) (Dart s)) # HasDataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic Associated Typestype DataOf (PlanarSubdivision s v e f r) (Dart s) :: Type # MethodsdataOf :: Dart s -> Lens' (PlanarSubdivision s v e f r) (DataOf (PlanarSubdivision s v e f r) (Dart s)) # type Rep (Dart s) Instance detailsDefined in Data.PlanarGraph.Dart type Rep (Dart s) = D1 (MetaData "Dart" "Data.PlanarGraph.Dart" "hgeometry-combinatorial-0.11.0.0-Cktt0ZWYuCrAhHfx7XTJDd" False) (C1 (MetaCons "Dart" PrefixI True) (S1 (MetaSel (Just "_arc") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 (Arc s)) :*: S1 (MetaSel (Just "_direction") NoSourceUnpackedness SourceStrict DecidedStrict) (Rec0 Direction))) type DataOf (PlanarGraph s w v e f) (Dart s) Instance detailsDefined in Data.PlanarGraph.Core type DataOf (PlanarGraph s w v e f) (Dart s) = e type DataOf (PlaneGraph s v e f r) (Dart s) Source # Instance detailsDefined in Data.PlaneGraph.Core type DataOf (PlaneGraph s v e f r) (Dart s) = e type DataOf (PlanarSubdivision s v e f r) (Dart s) Source # Instance detailsDefined in Data.Geometry.PlanarSubdivision.Basic type DataOf (PlanarSubdivision s v e f r) (Dart s) = e

data World #

The world in which the graph lives

Constructors

 Primal Dual
Instances
 Instance detailsDefined in Data.PlanarGraph.Core Methods(==) :: World -> World -> Bool #(/=) :: World -> World -> Bool # Instance detailsDefined in Data.PlanarGraph.Core MethodsshowsPrec :: Int -> World -> ShowS #show :: World -> String #showList :: [World] -> ShowS #

type VertexId' (s :: k) = VertexId s Primal #

Shorthand for vertices in the primal.

type FaceId' (s :: k) = FaceId s Primal #

Shorthand for FaceId's in the primal.

withEdgeDistances :: (Point 2 r -> Point 2 r -> a) -> PlaneGraph s p e f r -> PlaneGraph s p (a :+ e) f r Source #

Labels the edges of a plane graph with their distances, as specified by the distance function.