In addition, the class Triangulation_default_data_structure_2<Tds_gt,Vb,Fb> has a first template parameter which is a geometric traits class. This may be 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 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 data structure is implemented using 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 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 and the coordinate comparison functions compare_x(Point p0, Point p1) and compare_y(Point p0, Point p1) described in section . The point type defined by the geometric traits class of the triangulation data structure has to be the same as the point type defined by the geometric traits of the triangulation. This is achieved if the same model is used for both traits classes which is recommended but not compulsory.

#include <CGAL/Triangulation_default_data_structure_2.h>