3D Triangulation Data Structures

The triangulation data structure must be able to represent a triangulation of a topological sphere $$S^d of $$ ^d+1, for $$d {-1,0,1,2,3}. (See .)

The vertex class of a 3D-triangulation data structure must define a number of types and operations. Some of these requirements are of geometric nature, they are optional when using the triangulation data structure class alone. They become compulsory when the triangulation data structure is used as a layer for the geometric triangulation class. (See Section .)

The cell class of a triangulation data structure stores four pointers to its four vertices and four pointers to its four neighbors The vertices are indexed 0, 1, 2, and 3 in positive order. The neighbor indexed $$i lies opposite to vertex i.

In degenerate dimensions, cells are used to store faces of maximal dimension: in dimension 2, each cell represents only one facet of index 3, and 3 edges $$(0,1), $$(1,2) and $$(2,0); in dimension 1, each cell represents one edge $$(0,1). (See Section .)

Concepts

TriangulationDataStructure_3

TriangulationDataStructure_3::Vertex
TriangulationDataStructure_3::Cell

TriangulationVertexBase_3
TriangulationCellBase_3

Classes

CGAL::Triangulation_data_structure_3<TriangulationVertexBase_3,TriangulationCellBase_3>

This class is a model for the concept of the 3D-triangulation data structure TriangulationDataStructure_3 and provides the optional geometric functionalities. It is templated by base classes for vertices and cells.

CGAL provides two base vertex classes and one base cell class:

CGAL::Triangulation_vertex_base_3<TriangulationTraits_3>
CGAL::Triangulation_vertex_base_pointer_3<TriangulationTraits_3>
CGAL::Triangulation_cell_base_3<TriangulationTraits_3>

• TriangulationDataStructure_3.

• TriangulationDataStructure_3::Cell.

• TriangulationDataStructure_3::Vertex.

• TriangulationCellBase_3.

• Triangulation_cell_base_3<TriangulationTraits_3>.

• Triangulation_data_structure_3<TriangulationVertexBase_3,TriangulationCellBase_3>.

• TriangulationVertexBase_3.

• Triangulation_vertex_base_3<TriangulationTraits_3>.

• Triangulation_vertex_base_pointer_3<TriangulationTraits_3>.