|
CGAL 4.4 - High-dimension Triangulation
|
|
CGAL 4.4 - High-dimension Triangulation
|
Triangulation provides classes for manipulating triangulations (pure simplicial complexes) in Euclidean spaces whose dimension can be specified at compile-time or at run-time. Specifically, it provides a combinatorial Triangulation data structure, which is extended into geometric triangulation and Delaunay triangulation classes. Point location and point insertion are supported. The Delaunay triangulation also supports point removal.
A triangulation is a pure manifold simplicial complex which is connected and has no boundaries. Its faces are such that two of them either do not intersect or share a common face.
The basic triangulation class of CGAL is primarily designed to represent the triangulations of a set of points \( A\) in \( \mathbb{R}^d\). It can be viewed as a partition of the convex hull of \( A\) into simplices whose vertices are the points of \( A\). Together with the unbounded full cells having the convex hull boundary as its frontier, the triangulation forms a partition of \( \mathbb{R}^d\).
In order to deal only with full dimensional simplices (full cells), which is convenient for many applications, the space outside the convex hull is subdivided into full cells by considering that each convex hull facet is incident to an infinite full cell having as vertex an auxiliary vertex called the infinite vertex. In that way, each facet is incident to exactly two full cells and special cases at the boundary of the convex hull are simple to deal with.
A triangulation is a collection of vertices and full cells that are linked together through incidence and adjacency relations. Each full cell gives access to its incident vertices and to its adjacent full cells. Each vertex gives access to one of its incident full cells.
The vertices of a full cell are indexed in positive orientation, the positive orientation being defined by the orientation of the underlying Euclidean space \( \mathbb{R}^d\). The neighbors of a full cell are also indexed in such a way that the neighbor indexed by \( i\) is opposite to the vertex with the same index.
The above concept defines three types, Vertex, Full_cell and Face, that must respectively fulfill the following concepts:
The latter two concepts are also abbreviated respectively as TrVertex and TrFullCell.
CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex, TriangulationDSFullCell>CGAL::Triangulation_ds_vertex<TriangulationDataStructure>CGAL::Triangulation_ds_full_cell<TriangulationDataStructure, TDSFullCellStoragePolicy>CGAL::Triangulation_face<TriangulationDataStructure>CGAL::Triangulation<TriangulationTraits, TriangulationDataStructure>CGAL::Delaunay_triangulation<DelaunayTriangulationTraits, TriangulationDataStructure>CGAL::Triangulation_vertex<TriangulationTraits, Data, TriangulationDSVertex>CGAL::Triangulation_full_cell<TriangulationTraits, Data, TriangulationDSFullCell>Modules | |
| Concepts | |
1.8.5