The second template parameter of a 2D triangulation class
has to be instanciated with a model
of TriangulationDataStructure_2.
This model is decribed in section 
.
CGAL provides two classes which are models for this concept.
These models are described in section .
Section described the base
vertex and face classes of a triangulation.
At last, section shows
how the user can plug in the triangulation
data structure his own vertex or face base class.
The triangulation data structure is required to provide :
The triangulation data structure is responsible for the creation and removal of faces and vertices (memory management). It provides function that gives the number of faces, edges and vertices of the triangulation.
The triangulation data structure provides member functions
to perform the following combinatorial transformation of the triangulation:
flip of two adjacent faces,
addition of a new vertex splitting a given face,
addition of a new vertex splitting a given edge,
addition of a new vertex raising by one the dimension of a degenerate
lower dimensional triangulation,
removal of a vertex incident to three faces,
removal of a vertex lowering the dimension of the triangulation.
CGAL currently offers two models of triangulation data structures. The first one, called Triangulation_default_data_structure_2<Tds_gt,Vb,Fb > is very economic with respect to memory space but its use is restricted to planar embedded triangulations. The second one, called Triangulation_data_structure_using_list_2<Vb,Fb> can be used for the representation of any orientable triangulations.
,
the models of triangulation data structure
offered by CGAL
are themselves template classes,
parametrized by the base classes for vertices and faces.
The concepts of TriangulationVertexBase_2 and
TriangulationFaceBase_2 are described
in next section .
The triangulation data structure
derives from thoses base classes its own
vertex and face classes.
This design allows the user to plug in the
triangulation data structure
his own base classes tuned for his application.
The requirements concerning the geometric traits TdsGt of Triangulation_default_data_structure_2 are very light and form a subset of the requirements needed for the geometric traits of the triangulations. This class is required to provide a type Point_2 and coordinate comparison predicates. The point type defined by the geometric traits class of the triangulation data structure and the point type defined by the geometric traits of the triangulation have to be the same. This is automatically achieved if the same model is used for both traits classes which is recommended but not compulsory.
At the bottom layer, a vertex is required to provide access to the embedding point and to one of its incident face through a void * pointer.
At the bottom layer, a face provides access to its three vertices and to its three neighboring faces through void * pointers. The vertices and neighbors are indexed 0,1 and 2 in counterclockwise order around the face. The neighbor indexed i lies opposite to vertex with the same index.
These default base classes can be used directly or can serve as a base to derive other base classes with some additional attribute (a color for example) tuned for a specific application.
The following example derives a new base face class from the default one and adds a color to the faces of the triangulation. The face of the triangulation data structure and the face of the triangulation will inherit the new data member and its functionality. Any kind of additional functionality can thus be added to faces or vertices of a triangulation as long as this functionality does not involve additional pointers to vertices or faces (because the base classes use only void* pointer and have no knowledge of the vertex or face types.).
// file : examples/Triangulation_2/colored_face.C
#include <CGAL/Cartesian.h>
#include <CGAL/IO/Color.h>
#include <CGAL/Triangulation_2.h>
/* A facet with a color member variable. */
template < class Gt >
class My_face_base : public CGAL::Triangulation_face_base_2<Gt>
{
public:
CGAL::Color color;
My_face_base() :
CGAL::Triangulation_face_base_2<Gt>() {}
My_face_base(void* v0, void* v1, void* v2) :
CGAL::Triangulation_face_base_2<Gt>(v0,v1,v2) {}
My_face_base(void* v0, void* v1, void* v2, void* n0, void* n1, void* n2) :
CGAL::Triangulation_face_base_2<Gt>(v0,v1,v2,n0,n1,n2) {}
};
typedef CGAL::Cartesian<double> Gt;
typedef CGAL::Triangulation_vertex_base_2<Gt> Vb;
typedef My_face_base<Gt> Fb;
typedef CGAL::Triangulation_data_structure_using_list_2<Vb,Fb > Tds;
typedef CGAL::Triangulation_2<Gt,Tds> Triangulation;
typedef Triangulation::Face_handle Face_handle;
typedef Triangulation::Face_iterator Face_iterator;
typedef Gt::Point_2 Point;
int main() {
Triangulation t;
t.insert(Point(0,1));
t.insert(Point(0,0));
t.insert(Point(2,0));
t.insert(Point(2,2));
Face_iterator fc = t.faces_begin();
for( ; fc != t.faces_end(); ++fc) fc->color = CGAL::BLUE;
Point p(0.5,0.5);
Face_handle fh = t.locate(p);
fh->color = CGAL::RED;
return 0;
}