TriangulationDataStructure_2

Definition

The concept TriangulationDataStructure_2 describes the requirements for the second template parameter of the basic triangulation class Triangulation_2<Traits,Tds> and of all other 2D triangulation classes.

The concept can be seen as a container for the faces and vertices of the triangulation. The concept TriangulationDataStructure_2 includes two sub-concepts TriangulationDataStructure_2::Vertex and TriangulationDataStructure_2::Face.

The TriangulationDataStructure_2 maintains incidence and adjacency relations among vertices and faces.

Each triangular face gives access to its three incident vertices and to its three adjacent faces. Each vertex gives access to one of its incident faces and through that face to the circular list of its incident faces.

The three vertices of a face are indexed with 0, 1 and 2. The neighbors of a face are also indexed with 0,1,2 in such a way that the neighbor indexed by i is opposite to the vertex with the same index.

Each edge has two implicit representations : the edge of a face f which is opposed to the vertex indexed i, can be represented as well as an edge of the neighbor(i) of f. See Figure 37.2

The triangulation data structure is responsible for the combinatorial integrity of the triangulation. This means that the triangulation data structure allows to perform some combinatorial operations on the triangulation and guarantees the maintenance on proper incidence and adjacency relations among the vertices and faces. The term combinatorial operations means that those operations are purely topological and do not depend on the geometric embedding. Insertion of a new vertex in a given face, or in a given edge, suppression of a vertex of degree three, flip of two edges are examples of combinatorial operations.

Types

Vertices and faces are accessed via Vertex_handle and Face_handle. These types are models of the concept Handles which basically supports the two dereference operators * and ->.

The following iterators allow one to visit all the vertices, edges and faces of a triangulation data structure. They are all bidirectional, non-mutable iterators.

The following circulators allow to visit all the edges or faces incident to a given vertex and all the vertices adjacent to a given vertex. They are all bidirectional and non mutable.

Iterators and circulators are convertible to the corresponding handles, thus they can be passed directly as argument to the functions expecting a handle.

Creation

Access Functions

Queries

Traversing the triangulation

Three circulator classes allow to traverse the edges or faces incident to a vertex or the vertices adjacent to this vertex.. A face circulator is invalidated by any modification of the face it points to. An edge circulator is invalidated by any modification of anyone of the two faces incident to the edge pointed to. A vertex circulator that turns around vertex v and that has as value a pointer to vertex w, is invalidated by any modification of anyone of the two faces incident to v and w.

Modifiers

Figure 38.4:  Flip.

The following operation, dim_down, is necessary when the displacement of a vertex decreases the dimension of the triangulation.

void	tds.dim_down ( Face_handle f, int i)
		The link of a vertex v is formed by the edges disjoint from v that are included in the faces incident to v. When the link of v = f->vertex(i) contains all the other vertices of the two-dimensional triangulation data-structure ( 2), dim_down crushes the two-dimensional data-structure ( 2) onto the one-dimensional data structure ( 1) formed by the link of v augmented with the vertex v itself; this one is placed on the edge (f, i). (see Fig. 38.5). Precondition:  dimension() must be equal to 2, the degree of f->vertex(i) must be equal to the total number of vertices minus 1.

Figure 38.5:  From a two-dimensional data structure to a one-dimensional data structure.

Miscellaneous

I/O

The information output in the iostream is: the dimension, the number of (finite) vertices, the number of (finite) faces. Then comes for each vertex, the non combinatorial information stored in that vertex if any. Then comes for each faces, the indices of its vertices and the non combinatorial information (if any) stored in this face. Then comes for each face again the indices of the neighboring faces. The index of an item (vertex of face) the rank of this item in the output order. When dimension < 2, the same information is output for faces of maximal dimension instead of faces.

Has Models

See Also