CGAL proposes the class CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb > as a default for the triangulation data structure class of a triangulation. As required this class has two template parameters Vb anf Fb which have to be models for the Vertex-base and Face_base concepts whose requirements are described in next section .

In addition, the class CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb>has a first template parameter which is a geometric traits class. This is surprising because the triangulation data structure is supposed to deal only with the combinatorial aspect of the triangulation and not with any geometric embedding The reason for that is the following. The class CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb>does not use any additional data structure such as a list or a vector to act as a container for faces and vertices. The iterators which allows to visit all faces and vertices of the triangulation is implemented through an implicit tree structure over the faces as described by de Berg, van Oostrum, and Overmars, in Proc. 12th Annual Symp. on Comput. Geom., 1996, pages C5-C6. This tree structure is based on the planar geometric embedding the triangulation. Each face can find its parent and its children using only simple comparisons on the coordinates of the points embedding its vertices. Thus the tree structure may remain implicit and does not require any additional memory.

The requirements concerning the geometric traits Tds_gt of the triangulation data structure CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb> are very light and form a subset of the requirements needed for the geometric traits of the triangulations. Mainly This class is required to provide a type Point and the coordinate comparison functions compare_x(Point p0, Point p1) and compare_y(Point p0, Point p1) described in section . Of course, the point type defined by the geometric traits class of the triangulation has to be the same as the point type defined by the geometric traits of the triangulation, so we recommend to use the same model for both traits classes. However this is by no mean compulsory.

#include <CGAL/Triangulation_default_data_structure_2.h>