Documentation

Embedded, *connected*, planar graph

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.

Note that the functor instance is in v

Convert to an Ext

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)\).

Constructs a connected plane graph

pre: The segments form a single connected component

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

Transforms the plane graph into adjacency lists. For every vertex, the adjacent vertices are given in counter clockwise order.

See toAdjacencyLists for notes on how we handle self-loops.

running time: \(O(n)\)

Given the AdjacencyList representation of a plane graph, construct the plane graph representing it. All the adjacencylists should be in counter clockwise order.

running time: \(O(n)\)

Get the number of vertices

>>> numVertices smallG
4
>>> numVertices myPlaneGraph
15

Get the number of Edges

>>> numEdges smallG
5

Get the number of faces

>>> numFaces smallG
3
>>> numFaces myPlaneGraph
7

Get the number of Darts

>>> numDarts smallG
10

Get the dual graph of this graph.

Enumerate all vertices

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

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})

Enumerate all edges. We report only the Positive darts

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")

Enumerate all faces in the plane graph

All faces with their face data.

>>> mapM_ print $ faces smallG
(FaceId 0,"OuterFace")
(FaceId 1,"A")
(FaceId 2,"B")
>>> mapM_ print $ faces myPlaneGraph
(FaceId 0,"OuterFace")
(FaceId 1,"A")
(FaceId 2,"B")
(FaceId 3,"C")
(FaceId 4,"E")
(FaceId 5,"F")
(FaceId 6,"D")

Reports all internal faces. running time: \(O(n)\)

Reports the outerface and all internal faces separately. running time: \(O(n)\)

Enumerate all darts

Get all darts together with their data

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)

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")

Traverses the faces

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

The vertex this dart is heading in to

running time: \(O(1)\)

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

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

Get the twin of this dart (edge)

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

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

running time: \(O(1)\)

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

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]
>>> mapM_ print $ incidentEdges (VertexId 5) myPlaneGraph
Dart (Arc 1) -1
Dart (Arc 7) +1
Dart (Arc 10) +1
Dart (Arc 4) -1

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]

All edges incident to vertex v in outgoing direction (i.e. pointing out of 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]

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]
>>> neighboursOf (VertexId 5) myPlaneGraph
[VertexId 0,VertexId 6,VertexId 8,VertexId 1]

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

running time: \(O(1)\)

>>> nextIncidentEdge (dart 1 "+1") smallG
Dart (Arc 4) +1
>>> nextIncidentEdge (dart 1 "+1") myPlaneGraph
Dart (Arc 7) +1
>>> nextIncidentEdge (dart 17 "-1") myPlaneGraph
Dart (Arc 15) -1

Given a dart d that points into some vertex v, report the previous dart in the cyclic (counterclockwise) order around v.

running time: \(O(1)\)

>>> prevIncidentEdge (dart 1 "+1") smallG
Dart (Arc 3) +1
>>> prevIncidentEdge (dart 1 "+1") myPlaneGraph
Dart (Arc 4) -1
>>> prevIncidentEdge (dart 7 "-1") myPlaneGraph
Dart (Arc 1) -1

Given a dart d that points away from some vertex v, report the next dart in the cyclic (counterclockwise) order around v.

running time: \(O(1)\)

>>> nextIncidentEdgeFrom (dart 1 "+1") smallG
Dart (Arc 2) +1
>>> nextIncidentEdgeFrom (dart 1 "+1") myPlaneGraph
Dart (Arc 2) +1
>>> nextIncidentEdgeFrom (dart 4 "+1") myPlaneGraph
Dart (Arc 15) +1

Given a dart d that points into away from vertex v, report the previous dart in the cyclic (counterclockwise) order around v.

running time: \(O(1)\)

>>> prevIncidentEdgeFrom (dart 1 "+1") smallG
Dart (Arc 0) +1
>>> prevIncidentEdgeFrom (dart 4 "+1") myPlaneGraph
Dart (Arc 2) -1

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

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

Get the next edge along the face

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

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

Get the previous edge along the face

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

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

The darts bounding this face. The darts are reported in order along the face. This means that for internal faces the darts are reported in *clockwise* order along the boundary, whereas for the outer face the darts are reported in counter clockwise order.

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

>>> boundary (FaceId $ VertexId 2) smallG -- around face B
[Dart (Arc 2) +1,Dart (Arc 3) -1,Dart (Arc 1) -1]
>>> boundary (FaceId $ VertexId 0) smallG -- around outer face
[Dart (Arc 0) +1,Dart (Arc 4) -1,Dart (Arc 3) +1,Dart (Arc 2) -1]

Given a dart d, generates the darts bounding the face that is to the right of the given dart. The darts are reported in order along the face. This means that for internal faces the darts are reported in *clockwise* order along the boundary, whereas for the outer face the darts are reported in counter clockwise order.

running time: \(O(k)\), where \(k\) is the number of darts reported

>>> boundary' (dart 2 "+1") smallG -- around face B
[Dart (Arc 2) +1,Dart (Arc 3) -1,Dart (Arc 1) -1]
>>> boundary' (dart 0 "+1") smallG -- around outer face
[Dart (Arc 0) +1,Dart (Arc 4) -1,Dart (Arc 3) +1,Dart (Arc 2) -1]

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

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.

>>> boundaryVertices (FaceId $ VertexId 2) smallG -- around B
[VertexId 0,VertexId 3,VertexId 1]
>>> boundaryVertices (FaceId $ VertexId 0) smallG -- around outerface
[VertexId 0,VertexId 2,VertexId 1,VertexId 3]
>>> mapM_ print $ boundaryVertices (FaceId $ VertexId 0) myPlaneGraph
VertexId 0
VertexId 9
VertexId 10
VertexId 11
VertexId 7
VertexId 8
VertexId 12
VertexId 13
VertexId 4
VertexId 3
VertexId 2

gets the id of the outer face

running time: \(O(n)\)

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

running time: \(O(n)\)

Lens to access the vertex data

Note that using the setting part of this lens may be very expensive!! (O(n))

Get the location of a vertex in the plane graph

Note that the setting part of this lens may be very expensive! Moreover, use with care (as this may destroy planarity etc.)

General interface to accessing vertex data, dart data, and face data.

Getter for the data at the endpoints of a dart

running time: \(O(1)\)

Data corresponding to the endpoints of the dart

running time: \(O(1)\)

Lens to access face data

lens to access the Dart Data

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

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)\)

Reports all edges as line segments

>>> mapM_ print $ edgeSegments smallG
(Dart (Arc 0) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 0 :+ 2) :+ "0->2")
(Dart (Arc 1) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 2 :+ 1) :+ "0->1")
(Dart (Arc 2) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 (-1) 4 :+ 3) :+ "0->3")
(Dart (Arc 4) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 2 0 :+ 2) :+ "1->2")
(Dart (Arc 3) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 (-1) 4 :+ 3) :+ "1->3")
>>> mapM_ print $ edgeSegments myPlaneGraph
(Dart (Arc 0) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 8 (-5) :+ 9) :+ ())
(Dart (Arc 1) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 8 1 :+ 5) :+ ())
(Dart (Arc 2) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 4 4 :+ 1) :+ ())
(Dart (Arc 3) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 3 7 :+ 2) :+ ())
(Dart (Arc 4) +1,ClosedLineSegment (Point2 4 4 :+ 1) (Point2 8 1 :+ 5) :+ ())
(Dart (Arc 15) +1,ClosedLineSegment (Point2 4 4 :+ 1) (Point2 10 4 :+ 12) :+ ())
(Dart (Arc 5) +1,ClosedLineSegment (Point2 3 7 :+ 2) (Point2 0 5 :+ 3) :+ ())
(Dart (Arc 6) +1,ClosedLineSegment (Point2 0 5 :+ 3) (Point2 3 8 :+ 4) :+ ())
(Dart (Arc 18) +1,ClosedLineSegment (Point2 3 8 :+ 4) (Point2 9 6 :+ 13) :+ ())
(Dart (Arc 7) +1,ClosedLineSegment (Point2 8 1 :+ 5) (Point2 6 (-1) :+ 6) :+ ())
(Dart (Arc 10) +1,ClosedLineSegment (Point2 8 1 :+ 5) (Point2 12 1 :+ 8) :+ ())
(Dart (Arc 12) +1,ClosedLineSegment (Point2 6 (-1) :+ 6) (Point2 8 (-5) :+ 9) :+ ())
(Dart (Arc 8) +1,ClosedLineSegment (Point2 9 (-1) :+ 7) (Point2 12 1 :+ 8) :+ ())
(Dart (Arc 14) +1,ClosedLineSegment (Point2 9 (-1) :+ 7) (Point2 14 (-1) :+ 11) :+ ())
(Dart (Arc 9) +1,ClosedLineSegment (Point2 12 1 :+ 8) (Point2 10 4 :+ 12) :+ ())
(Dart (Arc 11) +1,ClosedLineSegment (Point2 8 (-5) :+ 9) (Point2 12 (-3) :+ 10) :+ ())
(Dart (Arc 13) +1,ClosedLineSegment (Point2 12 (-3) :+ 10) (Point2 14 (-1) :+ 11) :+ ())
(Dart (Arc 16) +1,ClosedLineSegment (Point2 10 4 :+ 12) (Point2 9 6 :+ 13) :+ ())
(Dart (Arc 17) +1,ClosedLineSegment (Point2 10 4 :+ 12) (Point2 8 5 :+ 14) :+ ())
(Dart (Arc 19) +1,ClosedLineSegment (Point2 9 6 :+ 13) (Point2 8 5 :+ 14) :+ ())

The boundary of the face as a simple polygon. For internal faces the polygon that is reported has its vertices stored in CCW order (as expected).

pre: FaceId refers to an internal face.

For the other face this prodcuces a polygon in CW order (this may lead to unexpected results.)

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

The boundary of the face as a simple polygon. For internal faces the polygon that is reported has its vertices stored in CCW order (as expected).

pre: FaceId refers to an internal face.

For the other face this prodcuces a polygon in CW order (this may lead to unexpected results.)

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

Given the outerFaceId and the graph, construct a sufficiently large rectangular multipolygon ith a hole containing the boundary of the outer face.

Given the outerface id, and a sufficiently large outer boundary, draw the outerface as a polygon with a hole.

Given the outerFace Id, construct polygons for all faces. We construct a polygon with a hole for the outer face.

Given the outerFace Id, lists all internal faces of the plane graph with their boundaries.

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.

The type to represent FaceId's

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.

The world in which the graph lives

Shorthand for vertices in the primal.

Shorthand for FaceId's in the primal.

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

Writes a plane graph to a bytestring

Reads a plane graph from a bytestring