Definition
A parameterized planar map M is a planar map whose nodes, edges and
faces contain additional (user defined) data. Every node contains
an element of a data type vtype, called the node type of M,every edge
contains an element of a data type etype, called the edge type of M, and
every face contains an element of a data type ftype called the face type of
M. All operations of the data type
planar
map are also defined for
instances of any parameterized planar_map type. For parameterized
planar maps there are additional operations to access or update
the node and face entries.
#include < LEDA/planar _map.h >
Creation
| PLANAR_MAP<vtype,etype,ftype> | M(GRAPH<vtype,etype> G) | creates an instance M of type PLANAR_MAP<vtype,etype,ftype> and initializes it to
the planar map represented by the parameterized directed graph G.
The node and edge entries of G are copied into the corresponding
nodes and edges of M. Every face f of M is assigned the default
value of type ftype.
Precondition: G represents a planar map. |
Operations
| vtype | M.inf(node v) | returns the information of node v. |
| etype | M.inf(edge e) | returns the information of node v. |
| ftype | M.inf(face f) | returns the information of face f. |
| vtype& | M[node v] | returns a reference to the information of node v. |
| etype& | M[edge e] | returns a reference to the information of edge e. |
| ftype& | M[face f] | returns a reference to the information of face f. |
| void | M.assign(node v, vtype x) | makes x the information of node v. |
| void | M.assign(edge e, etype x) | makes x the information of node v. |
| void | M.assign(face f, ftype x) | makes x the information of face f. |
| edge | M.new_edge(edge e1, edge e2, ftype y) | |
| inserts the edge
e = (source(e1), source(e2))
and its reversal edge e' into M.
Precondition: e1 and e2 are bounding the same face F. The operation splits F into two new faces f, adjacent to edge e, and f', adjacent to edge e', with inf(f) = inf (F) and inf(f') = y. |
||
| edge | M.split_edge(edge e, vtype x) | |
| splits edge e = (v, w) and its reversal r = (w, v) into edges (v, u), (u, w), (w, u), and (u, v). Assigns information x to the created node u and returns the edge (u, w). | ||
| node | M.new_node(list<edge>& el, vtype x) | |
| splits the face bounded by the edges in el by
inserting a new node u and connecting it to all
source nodes of edges in el. Assigns information x
to u and returns u.
Precondition: all edges in el bound the same face. |
||
| node | M.new_node(face f, vtype x) | |
| splits face f into triangles by inserting a new node u with information x and connecting it to all nodes of f. Returns u. | ||
Implementation
Parameterized planar maps are derived from planar maps. All additional operations for manipulating the node and edge contents take constant time.