^d+1

d {-1,0,1,2,3}

A class Tds<Vb,Fb> that satisfies the requirements for a triangulation data structure class must provide the following types and operations.

Types

Tds<Vb,Fb>::Vertex
	Vertex
Tds<Vb,Fb>::Cell
	Cell type

Requirements for Vertex and Cell are described in Sections  and .

typedef triple<Cell*, int, int>
	Edge;	(c,i,j) is the edge of cell c whose vertices indices are i and j. (See Section .)
typedef pair<Cell*, int>
	Facet;	(c,i) is the facet of c opposite to the vertex of index i. (See Section .)

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

Tds<Vb,Fb>::Cell_iterator

Tds<Vb,Fb>::Facet_iterator

Tds<Vb,Fb>::Edge_iterator

Tds<Vb,Fb>::Vertex_iterator

The following circulators allow us to visit all the cells and facets incident to a given edge. They are bidirectional and non-mutable.

Tds<Vb,Fb>::Facet_circulator

Tds<Vb,Fb>::Cell_circulator

Creation

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

Tds<Vb,Fb>

tds = Tds tds1

Assignment. All the vertices and cells are duplicated.

The previous two methods are equivalent.

void	tds.swap ( Tds & tds1)
		Swaps tds and tds1. There is no copy of cells and vertices, thus this method runs in constant time. This method should be preferred to tds=tds1 or tds(tds1) when tds1 is deleted after that.
Vertex*	tds.copy_tds ( Tds tds1, Vertex* v = NULL)
		tds1 is copied into tds. If $$v != NULL, the vertex of tds corresponding to v is returned, otherwise NULL is returned. Precondition: The optional argument v is a vertex of tds1.
void ~	tds ()	Destructor. All vertices and cells are deleted, and tds itself is deleted.

Access Functions

int	tds.dimension ()	The dimension of the triangulated topological sphere.
int	tds.number_of_vertices ()
		The number of vertices. Note that the triangulation data structure has one more vertex than an associated geometric triangulation, if there is one, since the infinite vertex is a standard vertex and is thus also counted.

Non constant-time access functions

Setting

Queries

bool	tds.is_vertex ( Vertex* v)
		Tests whether v is a vertex of tds.
bool	tds.is_edge ( Cell* c, int i, int j)
		Tests whether (c,i,j) is an edge of tds. Answers false when dimension() $$<1 .
bool	tds.is_edge ( Vertex* u, Vertex* v, Cell* & c, int & i, int & j)
		Tests whether (u,v) is an edge of tds. If the edge is found, it computes a cell c having this edge and the indices i and j of the vertices u and v, in this order.
bool	tds.is_facet ( Cell* c, int i)
		Tests whether (c,i) is a facet of tds. Answers false when dimension() $$<2 .
bool	tds.is_facet ( Vertex* u, Vertex* v, Vertex* w, Cell* & c, int & i, int & j, int & k)
		Tests whether (u,v,w) is a facet of tds. If the facet is found, it computes a cell c having this facet and the indices i, j and k of the vertices u, v and w, in this order.
bool	tds.is_cell ( Cell* c)
		Tests whether c is a cell of tds. Answers false when dimension() $$<3 .
bool	tds.is_cell ( Vertex* u, Vertex* v, Vertex* w, Vertex* t, Cell* & c, int & i, int & j, int & k, int & l)
		Tests whether (u,v,w,t) is a cell of tds. If the cell c is found, it computes the indices i, j, k and l of the vertices u, v, w and t in c, in this order.

Flips

Two kinds of flips exist for a three-dimensional triangulation. They are reciprocal. To be flipped, an edge must be incident to three tetrahedra. During the flip, these three tetrahedra disappear and two tetrahedra appear. Figure (left) shows the edge that is flipped as bold dashed, and one of its three incident facets is shaded. On the right, the facet shared by the two new tetrahedra is dashed.

Flips are possible only if the tetrahedra to be created do not already exist.

Figure:  Flips

The following methods guarantee the validity of the resulting 3D combinatorial triangulation.

Flips for a 2d triangulation are not implemented yet

bool	tds.flip ( Edge e)
bool	tds.flip ( Cell* c, int i, int j)
		Before flipping, these methods check that edge e=(c,i,j) is flippable (which is quite expensive). They return false or true according to this test.
void	tds.flip_flippable ( Edge e)
void	tds.flip_flippable ( Cell* c, int i, int j)
		Should be preferred to the previous methods when the edge is known to be flippable. Precondition: The edge is flippable.
bool	tds.flip ( Facet f)
bool	tds.flip ( Cell* c, int i)
		Before flipping, these methods check that facet f=(c,i) is flippable (which is quite expensive). They return false or true according to this test.
void	tds.flip_flippable ( Facet f)
void	tds.flip_flippable ( Cell* c, int i)
		Should be preferred to the previous methods when the facet is known to be flippable. Precondition: The facet is flippable.

Insertions

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

Vertex *	tds.insert_in_cell ( Vertex v, Cell* c)
		Inserts vertex v in cell c. Cell c is split into four new cells, each of these cells being formed with v and a facet of c. Precondition: tds.dimension() $$=3 and c is a cell of tds.
Vertex *	tds.insert_in_facet ( Vertex v, Facet f)
		Inserts vertex v in facet f. In dimension 3, the two incident cells are split into 3 new cells; in dimension 2, the facet is split into 3 facets. Precondition: tds.dimension() $$ 2 and f is a facet of tds.
Vertex *	tds.insert_in_facet ( Vertex v, Cell* c, int i)
		Inserts v in facet i of c. Precondition: tds.dimension() $$ 2, $$i {0,1,2,3} in dimension 3, $$i=3 in dimension 2 and (c,i) is a facet of tds.
Vertex *	tds.insert_in_edge ( Vertex v, Edge e)
		Inserts vertex v in edge e. In dimension 3, all the incident cells are split into 2 new cells; in dimension 2, the 2 incident facets are split into 2 new facets; in dimension 1, the edge is split into 2 new edges. Precondition: tds.dimension() $$ 1 and e is an edge of tds.
Vertex *	tds.insert_in_edge ( Vertex v, Cell* c, int i, int j)
		Inserts v in edge $$(i,j) of c. Precondition: tds.dimension() $$ 1. $$i j, $$i,j {0,1,2,3} in dimension 3, $$i,j {0,1,2} in dimension 2, $$i,j {0,1} in dimension 1 and (c,i,j) is an edge of tds.
Vertex *	tds.insert_increase_dimension ( Vertex v, Vertex* star = NULL, bool reorient = false)
		Transforms a triangulation of the sphere $$Sd of $$ d+1 into the triangulation of the sphere $$Sd+1 of $$ d+2 by adding vertex v: v is linked to all the vertices to triangulate one of the two halfspheres of dimension $$(d+1). Vertex star is used to triangulate the second halfsphere (when there is an associated geometric triangulation, star is in fact the vertex associated with its infinite vertex). See Figure . The numbering of the cells is such that, if f was a face of maximal dimension in the initial triangulation, then (f,v) (in this order) is the corresponding face in the new triangulation. If the boolean reorient is set to true, all the faces of maximal dimension are given the opposite orientation. This method can be used to insert the first two vertices in an empty triangulation. Precondition: tds.dimension() $$= d < 3. When tds.number_of_vertices() $$>0, $$star NULL and star is a vertex of tds.

Figure:  insert_increase_dimension (1-dimensional case)

void	tds.remove_degree_dplus1 ( Vertex* v, Cell *f = NULL)
		Removes v. The incident faces of maximal dimension incident to v are replaced by a single face of the same dimension. This operation is exactly reciprocal to tds.insert_in_cell(v). Precondition: v is a vertex of degree tds.dimension()+1. not yet implemented
void	tds.clear ()	Deletes all cells and vertices. tds is reset as a triangulation data structure constructed by the default constructor.

In addition to these requirements, in order to be used as a triangulation data structure by the class Delaunay_triangulation_3<Traits,Tds>, the triangulation must offer the following method:

void	tds.star_region ( set<void*, less<void*> > & region, Vertex* v, Cell* c, int li)
		Replaces all the cells in region by the cells formed by v and the facets on the boundary of region. Precondition: tds.dimension() $$ 2. region is a non-empty set of connected cells of t (this precondition is not checked but must be satisfied). c is an element of region whose facet of index i lies on the boundary of region (this precondition is not checked but must be satisfied).

Other modifiers

void	tds.add_cell ( Cell* c)
		Adds an already constructed cell to the triangulation data structure. Precondition: c != NULL.
Cell *	tds.create_cell ()	Creates a cell and adds it to the triangulation data structure. Its vertices and neighbors are initialized to NULL. The setting functions of the cell can be used later to modify them.
Cell *	tds.create_cell ( Vertex* v0, Vertex* v1, Vertex* v2, Vertex* v3)
		Creates a cell and adds it into the triangulation data structure. Initializes the vertices of the cell, its neighbor pointers being initialized with NULL.
Cell*	tds.create_cell ( Vertex* v0, Vertex* v1, Vertex* v2, Vertex* v3, Cell* n0, Cell* n1, Cell* n2, Cell* n3)
		Creates a cell, initializes its vertices and neighbors, and adds it into the triangulation data structure.
void	tds.delete_cell ( Cell* c)
		Removes the cell from the triangulation data structure and deletes it. Precondition: The cell is a cell of tds.

Traversing the triangulation

Cell_iterator	tds.cells_begin ()	Returns cells_end() when tds.dimension() $$<3.
Cell_iterator	tds.cells_end ()
Facet_iterator	tds.facets_begin ()
		Returns facets_end() when tds.dimension() $$<2.
Facet_iterator	tds.facets_end ()
Edge_iterator	tds.edges_begin ()	Returns edges_end() when tds.dimension() $$<1.
Edge_iterator	tds.edges_end ()
Vertex_iterator	tds.vertices_begin ()
		Returns vertices_end() when tds.number_of_vertices() $$< 1.
Vertex_iterator	tds.vertices_end ()
Cell_circulator	tds.incident_cells ( Edge e)
		Starts at an arbitrary cell incident to e. Precondition: tds.dimension() $$=3
Cell_circulator	tds.incident_cells ( Cell* c, int i, int j)
		As above for edge (i,j) of c.
Cell_circulator	tds.incident_cells ( Edge e, Cell* start)
		Starts at cell start. Precondition: tds.dimension() $$=3 and start is incident to e.
Cell_circulator	tds.incident_cells ( Cell* c, int i, int j, Cell* start)
		As above for edge (i,j) of c.

The following circulators on facets are defined only in dimension 3, though facets are defined also in dimension 2: there are only two facets sharing an edge in dimension 2.

Facet_circulator	tds.incident_facets ( Edge e)
		Starts at an arbitrary facet incident to e. Precondition: tds.dimension() $$=3
Facet_circulator	tds.incident_facets ( Cell* c, int i, int j)
		As above for edge (i,j) of c.
Facet_circulator	tds.incident_facets ( Edge e, Facet start)
		Starts at facet start. Precondition: start is incident to e.
Facet_circulator	tds.incident_facets ( Edge e, Cell* start, int f)
		Starts at facet of index f in start.
Facet_circulator	tds.incident_facets ( Cell* c, int i, int j, Facet start)
		As above for edge (i,j) of c.
Facet_circulator	tds.incident_facets ( Cell* c, int i, int j, Cell* start, int f)
		As above for edge (i,j) of c and facet (start,f).

Traversal of the incident cells and the adjacent vertices of a given vertex

void	tds.incident_cells ( Vertex* v, set<Cell*, less<Cell*> > & cells, Cell* c = NULL)
		Computes the set cells of all cells incident to v. If tds.dimension() $$<3 then the set is empty. The optional argument c will be used for initializing the set. Precondition: v $$ NULL, tds.is_vertex(v) and the optional argument c is a cell having v as a vertex.
void	tds.incident_vertices ( Vertex* v, set<Vertex*, less<Vertex*> > & vertices, Cell* c = NULL)
		Computes the set vertices of all vertices incident to v. If tds.number_of_vertices() $$<2 then the set is empty. The optional argument c will be used for finding a first vertex of the set. Precondition: v $$ NULL, tds.is_vertex(v) and the optional argument c is a cell having v as a vertex.

Checking

bool	tds.is_valid ( bool verbose = false)
		Checks the combinatorial validity of the triangulation by checking the validity of all its cells and vertices. (See Section .) Moreover, the Euler relation is tested. When verbose is set to true, messages are printed to give a precise indication on the kind of invalidity encountered.

I/O

istream&	istream& is >> Tds & t
		Reads a combinatorial triangulation from is and assigns it to t
ostream&	ostream& os << Tds t
		Writes t into the stream os

The information stored in the iostream is: the dimension, the number of vertices, the number of cells, the indices of the vertices of each cell, then the indices of the neighbors of each cell, where the index corresponds to the preceding list of cells. When dimension $$< 3, the same information is stored for faces of maximal dimension instead of cells.