\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.4 - High-dimension Triangulation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
MODIFICATIONS
Class CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >
The class Triangulation is used to store and query the full cells and vertices of a triangulationin dimension \( d\)(see the User Manual for a definition of "triangulation").
Member DelaunayTriangulationTraits::Side_of_oriented_sphere_d
Class FullCellData
The concept FullCellData describes the requirements on the type which is used to mark some full cells, during modifications of the triangulation data structure.
Group PkgTriangulations
See the User Manual for more details.
Member TriangulationDataStructure::Full_cell_data
A model of the concept FullCellData.
Class TriangulationDSFace
The dimension of a face is automatically set when TriangulationDSFace::set_index is called.
Member TriangulationDSFace::Triangulation_data_structure
The Triangulation_data_structure in which the TriangulationDSFace is defined/used.
Member TriangulationDSFullCell::operator<< (std::ostream &os, const Triangulation_ds_full_cell< TriangulationDataStructure > &c)
Writes (possibly) non-combinatorial information about full cell c to the stream os.
Member TriangulationDSFullCell::operator>> (std::istream &is, Triangulation_ds_full_cell< TriangulationDataStructure > &c)
Reads from stream is the full cell information written by operator<<.
Member TriangulationDSFullCell::Triangulation_data_structure
The Triangulation_data_structure in which the TriangulationDSFullCell is defined/used.
Member TriangulationDSVertex::operator<< (std::ostream &os, const Triangulation_ds_vertex< TriangulationDataStructure > &v)
Writes (possibly) non-combinatorial information about vertex v to the stream os.
Member TriangulationDSVertex::operator>> (std::istream &is, Triangulation_ds_vertex< TriangulationDataStructure > &v)
Reads from stream is the vertex information written by operator<<.
Member TriangulationDSVertex::Triangulation_data_structure
The Triangulation_data_structure in which the TriangulationDSVertex is defined/used.
Class TriangulationTraits
Member TriangulationTraits::Construct_flat_orientation_d
Member TriangulationTraits::Contained_in_affine_hull_d
Member TriangulationTraits::Dimension
A type representing the dimension of the Orientation_d predicate (but not necessarily the one of Point_d).
Member TriangulationTraits::Orientation_d
The operator returns the orientation of the simplex defined by the points in the range [start, end); the value can be CGAL::POSITIVE, CGAL::NEGATIVE or CGAL::COPLANAR.
page User Manual

A simplex having \( d+1 \) vertices is said of dimension \( d \). The simplicial complex is pure if all the maximal simplices have the same dimension.

In the sequel, we will call these maximal simplices full cells. A face of a simplex is a subset of it. A proper face of a simplex is a strict subset of it.

A complex has no boundaries if any proper face of a simplex is also a proper face of another simplex. A pure complex is manifold if all faces of dimension \( d-1 \) are proper faces of exactly two simplices.

The class CGAL::Triangulation<TriangulationTraits, TriangulationDataStructure> describes an embedded triangulation that has as vertices a given set of points and which fills the convex hull of these points. Methods are provided for the insertion of points in the triangulation, the traversal of various elements of the triangulation, as well as the localization of a query point inside the triangulation. The convex hull of the points is part of the triangulation, the fact that there is no boundary is ensured by adding an infinite vertex and infinite full cells to triangulate the outside of the convex hull.

See Chapter 3D Triangulations for more details about infinite vertices and cells.

A TriangulationDataStructure has a maximal dimension which is a positive integer equal to the maximum dimension a full cell can have. This maximal dimension can be chosen by the user at the creation of a TriangulationDataStructure and can then be queried using the method tds.maximal_dimension(). A TriangulationDataStructure also knows the current dimension of its full cells, which can be queried with tds.current_dimension(). In the sequel, let us denote the maximal dimension with \( D \) and the current dimension with \( d \). The inequalities \( -2 \leq d \leq D\) and \( 0 \le D\) always hold. The special meaning of negative values for \(d\) is explained below.

Possible values of \(d\) (the current dimension of the triangulation) include

Faces of dimension between 0 and \( d-1 \) can be accessed as subfaces of a full cell.

Template parameters

The default values are CGAL::Triangulation_ds_vertex<TDS> and CGAL::Triangulation_ds_full_cell<TDS> where TDS is the current class Triangulation_data_structure<Dimensionality, TriangulationDSVertex, TriangulationDSFullCell> This creates a circular dependency, which we resolve in the same way as in the CGAL Triangulation_2 and Triangulation_3 packages (see Chapters chapterTDS2, chapterTriangulation2, chapterTDS3, and chapterTriangulation3). In particular, models of the concepts TriangulationDSVertex and TriangulationDSFullCell must provide a nested template Rebind_TDS which is documented in those two concept's reference manual pages. This mechanism can be used to provide a custom vertex or full cell class. The user is encouraged to read the documentation of the CGAL Triangulation_2 or Triangulation_3 package.

The class CGAL::Triangulation<TriangulationTraits, TriangulationDataStructure> maintains a geometric triangulation in Euclidean space. More precisely, it maintains a triangulation (a partition into pairwise interior-disjoint full cells) of the convex hull of the points (the embedded vertices) of the triangulation. A special vertex at infinity is added to the convex hull facets to create infinite full cells and make the triangulation homeomorphic to a sphere of one dimension higher.

The ordering of the vertices of a full cell defines an orientation of that full cell. As long as no advanced class method is called, it is guaranteed that all finite full cells have positive orientation. The infinite full cells are oriented as if the infinite vertex have been on the the other side of the hyperplane supported by the convex hull facets that the other points.

The dimension of the predicates provided by TriangulationTraits must match the dimension of the TriangulationDataStructure.

The template parameter TriangulationDataStructure must be a model of the concept TriangulationDataStructure which provides the triangulation data structure as described in the previous section.

(include files triangulation1.cpp and triangulation2.cpp are given and commented below).

One important difference between the two examples above is that the first uses little memory but traverses all the full cells, while the second visits only the infinite full cells but stores handles to them into the potentially big array infinite_full_cells.