CGAL::Topological_explorer
Definition
An instance D of the data type Topological_explorer is a
decorator for interfacing the topological structure of a plane map
P (readonly).
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)) == e^{1}.
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 previousnext 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
orderpreserving. 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
nontrivial 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, defaultconstructible, and
equalcomparable.
Types
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.
Topological_explorer::Halfedge_around_vertex_const_circulator


circulating the outgoing halfedges in $$A(v).


Topological_explorer::Halfedge_around_face_const_circulator


circulating the halfedges in the face cycle of a face f.


Topological_explorer::Hole_const_iterator


iterating all holes of a face f. The type is
convertible to Halfedge_const_handle.


Topological_explorer::Isolated_vertex_const_iterator


iterating all isolated vertices of a face f.
The type generalizes Vertex_const_handle.

Operations
Vertex_const_handle


D.source ( Halfedge_const_handle e)

 
returns the source of e.


Vertex_const_handle


D.target ( Halfedge_const_handle e)

 
returns the target of e.


Halfedge_const_handle


D.twin ( Halfedge_const_handle e)

 
returns the twin of e.


bool

D.is_isolated ( Vertex_const_handle v)

 
returns true iff $$A(v) = .


Halfedge_const_handle


D.first_out_edge ( Vertex_const_handle v)

 
returns one halfedge with source v. It's the starting point for
the circular iteration over the halfedges with source v.
Precondition: !is_isolated(v).


Halfedge_const_handle


D.last_out_edge ( Vertex_const_handle v)

 
returns the halfedge with source v that is the last
in the circular iteration before encountering first_out_edge(v)
again.
Precondition: !is_isolated(v).


Halfedge_const_handle


D.cyclic_adj_succ ( Halfedge_const_handle e)

 
returns the edge after e in the cyclic ordered adjacency list of
source(e).


Halfedge_const_handle


D.cyclic_adj_pred ( Halfedge_const_handle e)

 
returns the edge before e in the cyclic ordered adjacency list of
source(e).


Halfedge_const_handle


D.next ( Halfedge_const_handle e)

 
returns the next edge in the face cycle containing e.


Halfedge_const_handle


D.previous ( Halfedge_const_handle e)

 
returns the previous edge in the face cycle containing e.


Face_const_handle

D.face ( Halfedge_const_handle e)

 
returns the face incident to e.


Face_const_handle

D.face ( Vertex_const_handle v)

 
returns the face incident to v.
Precondition: is_isolated(v).


Halfedge_const_handle


D.halfedge ( Face_const_handle f)

 
returns a halfedge in the bounding face cycle of f
(Halfedge_const_handle() if there is no bounding face cycle).

Iteration
Vertex_const_iterator


D.vertices_begin ()

 
iterator over vertices of the map.


Vertex_const_iterator


D.vertices_end ()

pasttheend iterator for vertices.


Halfedge_const_iterator


D.halfedges_begin ()

 
iterator over halfedges of the map.


Halfedge_const_iterator


D.halfedges_end ()

pasttheend iterator for halfedges.


Face_const_iterator


D.faces_begin ()

iterator over faces of the map.


Face_const_iterator


D.faces_end ()

pasttheend 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 pasttheend 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.

Associated Information
The type Mark is the general attribute of an object.
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.

Statistics and Integrity
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.

Footnotes

^{1} 
The
existence of the edge pairs makes P a bidirected graph, the
twin links make P a map.
