CGAL Basic Library Reference Manual: Tds<Vb,Fb>

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

To be a model of triangulation data structure the class Tds<Vb,Fb> is required to provide the following types and operations.

typedef Tds<Vb,Fb> Tds; self

typedef Vb Vertex_base; the Vertex_base

typedef Fb Face_base; the Face_base

Tds<Vb,Fb>::Vertex
requirement for this type are described in section .

Tds<Vb,Fb>::Face
requirements for this type are described in described .

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

Tds<Vb,Fb>::Face_iterator

Tds<Vb,Fb>::Edge_iterator

Tds<Vb,Fb>::Vertex_iterator

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

Tds<Vb,Fb>::Face_circulator

Tds<Vb,Fb>::Edge_circulator

Tds<Vb,Fb>::Vertex_circulator

Creation

Tds<Vb,Fb> tds;
	A default constructor.

Tds<Vb,Fb> tds ( Tds tds1);
	Copy constructor. All the vertices and faces are duplicated.

Tds<Vb,Fb> tds = tds1 Assignation. All the vertices and faces are duplicated.

void tds.swap ( Tds 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.

void ~Tds<Vb, Fb> () Destructor. All vertices and faces are deleted.

Access Functions

int	tds.dimension ()	The dimension of the triangulation.
int	tds.number_of_vertices ()
		The number of vertices in the data structure.
int	tds.number_of_faces ()
		The number of two dimensional faces in the data structure.
int	tds.number_of_edges ()
		The number of edges in the triangulation data structure.
int	tds.number_of_full_dim_faces ()
		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_number_of_vertices ( int n)
void	tds.set_dimension ( int n)

Modifiers

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

void tds.flip ( Face* 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: Flip.

Vertex* tds.insert_first ( Vertex* v)
creates the first vertex and returns a pointer to it.

Vertex* tds.insert_second ( Vertex* v)
creates the second finite vertex and returns a pointer to it.

Vertex* tds.insert_in_edge ( Vertex* v, Face* f, int i)
adds a vertex v splitting edge i of face f. Return a pointer to v.

Vertex* tds.insert_in_face ( Vertex* v, Face* 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* tds.insert_dim_up ( Vertex* 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.

void tds.remove_degree_3 ( Vertex* 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* v)
removes the before last vertex.

void tds.remove_first ( Vertex* v)
removes the last vertex.

void tds.remove_dim_down ( Vertex* 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.

Traversing the triangulation

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

Miscelleanous

int tds.ccw ( int i) returns i+1 modulo 3.
Precondition: 0 i 2.

int tds.cw ( int i) 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.

Next: Class declaration of Tds::Vertex

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

The GALIA project. Jan 18, 2000.

typedef Tds<Vb,Fb>	Tds;	self
typedef Vb	Vertex_base;	the Vertex_base
typedef Fb	Face_base;	the Face_base

Tds<Vb,Fb>::Vertex
	requirement for this type are described in section .
Tds<Vb,Fb>::Face
	requirements for this type are described in described .

Tds<Vb,Fb>::Face_iterator
Tds<Vb,Fb>::Edge_iterator
Tds<Vb,Fb>::Vertex_iterator

Tds<Vb,Fb>::Face_circulator
Tds<Vb,Fb>::Edge_circulator
Tds<Vb,Fb>::Vertex_circulator

Tds<Vb,Fb>	tds = tds1	Assignation. All the vertices and faces are duplicated.

void	tds.swap ( Tds 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.

void ~Tds<Vb,	Fb> ()	Destructor. All vertices and faces are deleted.

void	tds.flip ( Face 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).

Vertex*	tds.insert_first ( Vertex v)*
		creates the first vertex and returns a pointer to it.
Vertex*	tds.insert_second ( Vertex v)*
		creates the second finite vertex and returns a pointer to it.

Vertex*	tds.insert_in_edge ( Vertex v, Face* f, int i)*
		adds a vertex v splitting edge i of face f. Return a pointer to v.
Vertex*	tds.insert_in_face ( Vertex v, Face* 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*	tds.insert_dim_up ( Vertex 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.

void	tds.remove_degree_3 ( Vertex 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 v)*
		removes the before last vertex.
void	tds.remove_first ( Vertex v)*
		removes the last vertex.
void	tds.remove_dim_down ( Vertex 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.

int	tds.ccw ( int i)	returns i+1 modulo 3. Precondition: 0 i 2.
int	tds.cw ( int i)	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.