Concept

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

TriangulationDataStructure_2::size_type
Size type (unsigned integral type)

TriangulationDataStructure_2::difference_type
Difference type (signed integral type)


TriangulationDataStructure_2::Vertex
The vertex type. Requirements for this type are described in concept TriangulationDataStructure_2::Vertex .

TriangulationDataStructure_2::Face
The face type. Requirements for this type are described in concept TriangulationDataStructure_2::Face .

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

TriangulationDataStructure_2::Vertex_handle
Handle to a vertex

TriangulationDataStructure_2::Face_handle
Handle to a face.

template <typename Vb2>
TriangulationDataStructure_2:: struct Rebind_vertex
This nested template class allows to get the type of a triangulation data structure that only changes the vertex type. It has to define a type Other which is a rebound triangulation data structure, that is, the one whose TriangulationDSVertexBase_2 will be Vb2.

template <typename Fb2>
TriangulationDataStructure_2:: struct Rebind_face
This nested template class allows to get the type of a triangulation data structure that only changes the face type. It has to define a type Other which is a rebound triangulation data structure, that is, the one whose TriangulationDSFaceBase_2 will be Fb2.

typedef std::pair<Face_handle,int>
Edge; The edge type. The Edge(f,i) is edge common to faces f and f.neighbor(i). It is also the edge joining the vertices vertex(cw(i)) and vertex(ccw(i)) of f.

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.

TriangulationDataStructure_2::Face_iterator
TriangulationDataStructure_2::Edge_iterator
TriangulationDataStructure_2::Vertex_iterator

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.

TriangulationDataStructure_2::Face_circulator
TriangulationDataStructure_2::Edge_circulator
TriangulationDataStructure_2::Vertex_circulator

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

Creation

TriangulationDataStructure_2 tds;
default constructor.


TriangulationDataStructure_2 tds ( tds1);
Copy constructor. All the vertices and faces are duplicated.

TriangulationDataStructure_2& tds = tds1 Assignment. All the vertices and faces of tds1 are duplicated in tds . Former faces and vertices of tds , if any, are deleted

Vertex_handle tds.copy_tds ( tds1, Vertex_handle v = Vertex_handle())
tds1 is copied into tds. If v != NULL, the vertex of tds corresponding to v is returned, otherwise Vertex_handle() is returned.
Precondition: The optional argument v is a vertex of tds1.

void tds.swap ( & tds1) Swaps tds and tds1. Should be preferred to tds=tds1 or tds(tds1) when tds1 is deleted after that.

void tds.clear () Deletes all faces and all finite vertices.

Access Functions

int tds.dimension () const returns the dimension of the triangulation.
size_type tds.number_of_vertices () const returns the number of vertices in the data structure.
size_type tds.number_of_faces () const returns the number of two dimensional faces in the data structure.
size_type tds.number_of_edges () const returns the number of edges in the triangulation data structure.
size_type tds.number_of_full_dim_faces () const
returns the number of full dimensional faces, i.e. faces of dimension equal to the dimension of the triangulation. This is the actual number of faces stored in the triangulation data structure.

Setting

void tds.set_dimension ( int n) sets the dimension.

Queries

bool tds.is_vertex ( Vertex_handle v) const
returns true if v is a vertex of tds.
bool tds.is_edge ( Face_handle fh, int i) const
tests whether (fh,i) is an edge of tds. Answers false when dimension() <1 .
bool tds.is_edge ( Vertex_handle va, Vertex_handle vb) const
returns true if va vb is an edge of tds.
bool tds.is_edge ( Vertex_handle va, Vertex_handle vb, Face_handle &fr, int &i) const
as previous. In addition, if true is returned fr and i are set such that the pair (fr,i) is the description of the ordered edge va vb.
bool tds.is_face ( Face_handle fh) const
tests whether fh is a face of tds. Answers false when dimension() <2 .
bool tds.is_face ( Vertex_handle v1, Vertex_handle v2, Vertex_handle v3) const
true if there is a face having v1, v2 andv3 as vertices.
bool tds.is_face ( Vertex_handle v1, Vertex_handle v2, Vertex_handle v3, Face_handle &fr) const
as above. In addition, if true is returned, fr is a pointer to the face with v1, v2 and v3 as vertices.

Traversing the triangulation

Face_iterator tds.faces_begin () const visits all faces
Face_iterator tds.faces_end () const
Vertex_iterator tds.vertices_begin () const visits all vertices
Vertex_iterator tds.vertices_end () const
Edge_iterator tds.edges_begin () const visits all edges
Edge_iterator tds.edges_end () const

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.

Vertex_circulator tds.incident_vertices ( Vertex_handle v, Face_handle f=NULL) const
Precondition: If the face f is given, it has to be incident to be a face of tds incident to v and the circulator begins with the vertex f->vertex(ccw(i)) if i is the index of v in f.
Edge_circulator tds.incident_edges ( Vertex_handle v, Face_handle f=NULL) const
Precondition: If the face f is given, it has to be a face of tds incident to v and the circulator begins with the edge (f,cw(i)) of f if i is the index of v in f.
Face_circulator tds.incident_faces ( Vertex_handle v, Face_handle f=NULL) const
Precondition: If the face f is given, it has to be a face of tds incident to v and the circulator begins with the face f.

Vertex_handle tds.mirror_vertex ( Face_handle f, int i) const
returns vertex of f->neighbor(i).

int tds.mirror_index ( Face_handle f, int i) const
returns the index of f as a neighbor of f->neighbor(i).

Edge tds.mirror_edge ( Edge e) const returns the same edge seen from the other adjacent face.

Modifiers

The following modifier member functions guarantee the combinatorial validity of the resulting triangulation.

void tds.flip ( Face_handle f, int i) exchanges the edge incident to f and f->neighbor(i) with the other diagonal of the quadrilateral formed by f and f->neighbor(i).

Figure 38.4:  Flip.

Flip

Vertex_handle tds.insert_first () creates the first vertex and returns a pointer to it.
Vertex_handle tds.insert_second () creates the second vertex and returns a pointer to it.

Vertex_handle tds.insert_in_edge ( Face_handle f, int i)
adds a vertex v splitting edge i of face f. Return a pointer to v.
Vertex_handle tds.insert_in_face ( Face_handle f)
adds a vertex v splitting face f in three. Face f is modified, two new faces are created. Return a pointer to v
Vertex_handle tds.insert_dim_up ( Vertex_handle w, bool orient=true)
adds a vertex v, increasing by one the dimension of the triangulation. Vertex v and the existing vertex w are linked to all the vertices of the triangulation. The Boolean orient decides the final orientation of all faces. A pointer to vertex v is returned.

Insertion

void tds.remove_degree_3 ( Vertex_handle v, Face *f=NULL)
removes a vertex of degree 3. Two of the incident faces are destroyed, the third one is modified. If parameter f is specified, it has to be a face incident to v and will be the modified face.
Precondition: Vertex v is a finite vertex with degree 3 and, if specified, face f is incident to v.

void tds.remove_second ( Vertex_handle v)
removes the before last vertex.
void tds.remove_first ( Vertex_handle v)
removes the last vertex.
void tds.remove_dim_down ( Vertex_handle v)
removes vertex v incident to all other vertices and decreases by one the dimension of the triangulation.
Precondition: if the dimension is 2, the number of vertices is more than 3, if the dimension is 1, the number of vertices is 2.

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 (S 2), dim_down crushes the two-dimensional data-structure (S 2) onto the one-dimensional data structure (S 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.

From a two-dimensional data structure to a one-dimensional data structure.

The following modifiers are required for convenience of the advanced user. They do not guarantee the combinatorial validity of the resulting triangulation.

template< class EdgeIt>
Vertex_handle tds.star_hole ( EdgeIt edge_begin, EdgeIt edge_end)
creates a new vertex v and use it to star the hole whose boundary is described by the sequence of edges [edge_begin, edge_end[. Returns a pointer to the vertex.
template< class EdgeIt, class FaceIt>
Vertex_handle tds.star_hole ( EdgeIt edge_begin, EdgeIt edge_end, FaceIt face_begin, FaceIt face_end)
same as above, except that, to build the new faces, the algorithm first recycles faces in the sequence [face_begin, face_end[ and create new ones when the sequence is exhausted.
template< class EdgeIt>
void tds.star_hole ( Vertex_handle v, EdgeIt edge_begin, EdgeIt edge_end)
uses vertex v to star the hole whose boundary is described by the sequence of edges[edge_begin, edge_end[.
template< class EdgeIt, class FaceIt>
void
tds.star_hole ( Vertex_handle v,
EdgeIt edge_begin,
EdgeIt edge_end,
FaceIt face_begin,
FaceIt face_end)
same as above, recycling faces in the sequence [face_begin, face_end[ .
void tds.make_hole ( Vertex_handle v, List_edges& hole)
removes the vertex v, and store in hole the list of edges on the boundary of the hole.

Vertex_handle tds.create_vertex () adds a new vertex.
Face_handle tds.create_face ( Face_handle f1, int i1, Face_handle f2, int i2, Face_handle f3, int i3)
adds a face which is the neighbor i1 of f1, i2 of f2 and i3 of f3.
Face_handle tds.create_face ( Face_handle f1, int i1, Face_handle f2, int i2)
adds a face which is the neighbor i1 of f1, and the neighbor i2 of f2.
Face_handle tds.create_face ( Face_handle f1, int i1, Vertex_handle v)
adds a face which is the neighbor i1 of f1, and has v as vertex.
Face_handle tds.create_face ( Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)
adds a face with vertices v1, v2 and v3.
Face_handle
tds.create_face ( Vertex_handle v1,
Vertex_handle v2,
Vertex_handle v3,
Face_handle f1,
Face_handle f2,
Face_handle f3)
adds a face with vertices v1, v2 and v3, and neighbors f1, f2, f3.
Face_handle tds.create_face () adds a face whose vertices and neighbors are set to NULL.
void tds.delete_face ( Face_handle) deletes a face.
void tds.delete_vertex ( Vertex_handle)
deletes a vertex.

Miscellaneous

int tds.ccw ( int i) const returns i+1 modulo 3.
Precondition: 0 i 2.
int tds.cw ( int i) const returns i+2 modulo 3.
Precondition: 0 i 2.
bool tds.is_valid () checks the combinatorial validity of the triangulation: call the is_valid() member function for each vertex and each face, checks the number of vertices and the Euler relation between numbers of vertices, faces and edges.
size_type tds.degree ( Vertex_handle v) const
Returns the degree of v in the triangulation.

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.

void tds. file_output ( ostream& os, Vertex_handle v = Vertex_handle(), bool skip_first=false)
writes tds into the stream os. If v is not a null handle, vertex v is output first or skipped if skip_first is true.

Vertex_handle tds. file_input ( istream& is, bool skip_first=false)
inputs tds from file and returns a pointer to the first input vertex. If skip_first is true, it is assumed that the first vertex has been omitted when output.

istream& istream& is >> TriangulationDataStructure_3 & tds
reads a combinatorial triangulation from is and assigns it to tds

ostream& ostream& os << TriangulationDataStructure_3 tds
writes tds into the stream os

Has Models

CGAL::Triangulation_data_structure_2<Vb,Fb>

See Also

TriangulationDataStructure_2::Face
TriangulationDataStructure_2::Vertex
CGAL::Triangulation_2<Traits,Tds>