|
An instance D of the data type Topological_explorer is a decorator for interfacing the topological structure of a plane map P (read-only).
A plane map P consists of a triple (V, E, F) of vertices, edges, and faces. We collectively call them objects. An edge e is a pair of vertices (v,w) with incidence operations v = source(e), w = target(e). The list of all edges with source v is called the adjacency list A(v).
Edges are paired into twins. For each edge e = (v,w) there's an edge twin(e) = (w,v) and twin(twin(e)) == e1.
An edge e = (v,w) knows two adjacent edges en = next(e) and ep = previous(e) where source(en) = w, previous(en) = e and target(ep) = v and next(ep) = e. By this symmetric previous-next relationship all edges are partitioned into face cycles. Two edges e and e' are in the same face cycle if e = next*(e'). All edges e in the same face cycle have the same incident face f = face(e). The cyclic order on the adjacency list of a vertex v = source(e) is given by cyclic_adj_succ(e) = twin(previous(e)) and cyclic_adj_pred(e) = next(twin(e)).
A vertex v is embedded via coordinates point(v). By the embedding of its source and target an edge corresponds to a segment. P has the property that the embedding is always order-preserving. This means a ray fixed in point(v) of a vertex v and swept around counterclockwise meets the embeddings of target(e) (e ∈ A(v)) in the cyclic order defined by the list order of A.
The embedded face cycles partition the plane into maximal connected subsets of points. Each such set corresponds to a face. A face is bounded by its incident face cycles. For all the edges in the non-trivial face cycles it holds that the face is left of the edges. There can also be trivial face cycles in form of isolated vertices in the interior of a face. Each such vertex v knows its surrounding face f = face(v).
Plane maps are attributed, for each object u ∈ V ∪ E ∪ F we attribute an information mark(u) of type Mark. Mark fits the concepts assignable, default-constructible, and equal-comparable.
Local types are handles, iterators and circulators of the following kind: Vertex_const_handle, Vertex_const_iterator, Halfedge_const_handle, Halfedge_const_iterator, Face_const_handle, Face_const_iterator. Additionally the following circulators are defined.
| Vertex_const_iterator | D.vertices_begin () | iterator over vertices of the map. |
| Vertex_const_iterator | D.vertices_end () | past-the-end iterator for vertices. |
| Halfedge_const_iterator | D.halfedges_begin () | iterator over halfedges of the map. |
| Halfedge_const_iterator | D.halfedges_end () | past-the-end iterator for halfedges. |
| Face_const_iterator | D.faces_begin () | iterator over faces of the map. |
| Face_const_iterator | D.faces_end () | past-the-end iterator for faces |
| Halfedge_around_vertex_const_circulator | ||
| D.out_edges ( Vertex_const_handle v) | ||
| returns a circulator for the cyclic adjacency list of v. | ||
| Halfedge_around_face_const_circulator | ||
| D.face_cycle ( Face_const_handle f) | ||
| returns a circulator for the outer face cycle of f. | ||
| Hole_const_iterator | D.holes_begin ( Face_const_handle f) | |
| returns an iterator for all holes in the interior of f. A Hole_iterator can be assigned to a Halfedge_around_face_const_circulator. | ||
| Hole_const_iterator | D.holes_end ( Face_const_handle f) | |
| returns the past-the-end iterator of f. | ||
| Isolated_vertex_const_iterator | D.isolated_vertices_begin ( Face_const_handle f) | |
| returns an iterator for all isolated vertices in the interior of f. | ||
| Isolated_vertex_const_iterator | D.isolated_vertices_end ( Face_const_handle f) | |
| returns the past the end iterator of f. | ||
| Point | D.point ( Vertex_const_handle v) | returns the embedding of v. |
| Mark | D.mark ( Vertex_const_handle v) | returns the mark of v. |
| Mark | D.mark ( Halfedge_const_handle e) | |
| returns the mark of e. | ||
| Mark | D.mark ( Face_const_handle f) | returns the mark of f. |
| Size_type | D.number_of_vertices () | returns the number of vertices. |
| Size_type | D.number_of_halfedges () | returns the number of halfedges. |
| Size_type | D.number_of_edges () | returns the number of halfedge pairs. |
| Size_type | D.number_of_faces () | returns the number of faces. |
| Size_type | D.number_of_face_cycles () | returns the number of face cycles. |
| Size_type | D.number_of_connected_components () | |
| calculates the number of connected components of P. | ||
| void | D.print_statistics ( std::ostream& os = std::cout) | |
| print the statistics of P: the number of vertices, edges, and faces. | ||
| void | D.check_integrity_and_topological_planarity ( bool faces=true) | |
| checks the link structure and the genus of P. | ||
| 1 | The existence of the edge pairs makes P a bidirected graph, the twin links make P a map. |