3D-triangulation data structures are meant to maintain the combinatorial information for 3D-geometric triangulations.
In CGAL, a triangulation data structure is a container of cells (-faces) and vertices (-faces). Each cell gives access to its four incident vertices and to its four adjacent cells. Each vertex gives direct access to one of its incident cells, which is sufficient to retrieve all the incident cells when needed.
The four vertices of a cell are indexed with 0, 1, 2 and 3. The neighbors of a cell are also indexed with 0, 1, 2, 3 in such a way that the neighbor indexed by is opposite to the vertex with the same index (see Figure ).
Edges (-faces) and facets (-faces) are not explicitly represented: a facet is given by a cell and an index (the facet i of a cell c is the facet of c that is opposite to the vertex of index i) and an edge is given by a cell and two indices (the edge (i,j) of a cell c is the edge whose endpoints are the vertices of indices i and j of c).
As CGAL explicitly deals with all degenerate cases, a 3D-triangulation data structure in CGAL can handle the cases when the dimension of the triangulation is lower than 3 (see Section ).
Thus, a 3D-triangulation data structure can store a triangulation of a topological sphere of , for any .
The second template parameter of the basic triangulation class (see Chapter , ) Triangulation_3 is a triangulation data structure class. (See Chapter .)
To ensure all the flexibility of the class Triangulation_3, a model of a triangulation data structure must be templated by the base vertex and the base cell classes (see ): TriangulationDataStructure_3<TriangulationVertexBase_3,TriangulationCellBase_3>. The optional functionalities related to geometry are compulsory for this use as a template parameter of Triangulation_3.
A class that satisfies the requirements for a triangulation data structure class must provide the following types and operations.
| |
Vertex type
| |
| |
Cell type
| |
| |
Size type (unsigned integral type)
| |
| |
Difference type (signed integral type)
|
Vertices and cells are usually manipulated via handles, which support the two dereference operators operator* and operator->.
| |
|
Requirements for Vertex and Cell are described in TriangulationDataStructure_3::Vertex and TriangulationDataStructure_3::Cell .
| ||
| (c,i,j) is the edge of cell c whose vertices indices are i and j. (See Section .) | |
| ||
| (c,i) is the facet of c opposite to the vertex of index i. (See Section .) |
The following iterators allow one to visit all the vertices, edges, facets and cells of the triangulation data structure. They are all bidirectional, non-mutable iterators.
| |
| |
| |
|
The following circulators allow us to visit all the cells and facets incident to a given edge. They are bidirectional and non-mutable.
| |
|
Iterators and circulators are convertible to the corresponding handles, thus the user can pass them directly as arguments to the functions.
| |
Default constructor.
| |
| |
Copy constructor. All vertices and cells are duplicated.
|
| ||||
| Assignment operator. All vertices and cells are duplicated, and the former data structure of tds is deleted. | |||
|
| |||
tds1 is copied into tds. If ,
the vertex of tds corresponding to v is returned,
otherwise Vertex_handle() is returned. Precondition: The optional argument v is a vertex of tds1. | ||||
|
| |||
Swaps tds and tds1. There is no copy of cells and vertices, thus this method runs in constant time. This method should be preferred to tds=tds1 or tds(tds1) when tds1 is deleted after that. | ||||
|
| Deletes all cells and vertices. tds is reset as a triangulation data structure constructed by the default constructor. | ||
|
| |||
Destructor. All vertices and cells are deleted, and tds itself is deleted. |
|
| |
The number of facets. Returns 0 if tds.dimension(). | ||
|
| |
The number of edges. Returns 0 if tds.dimension(). |
There is a method has_vertex in the cell class. The analogous methods for facets are defined here.
|
| |||
If v is a vertex of f, then j is the index of
v in the cell f.first, and the method returns true. Precondition: tds.dimension()=3 | ||||
|
| |||
Same for facet (c,i). Computes the index j of v in c. | ||||
|
| |||
|
| |||
Same as the first two methods, but these two methods do not return the index of the vertex. |
The following three methods test whether two facets have the same vertices.
|
| |||
|
| |||
|
| |||
For these three methods: Precondition: tds.dimension()=3. |
Two kinds of flips exist for a three-dimensional triangulation. They are reciprocal. To be flipped, an edge must be incident to three tetrahedra. During the flip, these three tetrahedra disappear and two tetrahedra appear. Figure (left) shows the edge that is flipped as bold dashed, and one of its three incident facets is shaded. On the right, the facet shared by the two new tetrahedra is shaded.
The following methods guarantee the validity of the resulting 3D combinatorial triangulation.
Flips for a 2d triangulation are not implemented yet
|
|
|
|
| |
Before flipping, these methods check that edge e=(c,i,j) is flippable (which is quite expensive). They return false or true according to this test. | ||
|
| |
|
| |
Should be preferred to the previous methods when the edge is
known to be flippable. Precondition: The edge is flippable. | ||
|
| |
|
| |
Before flipping, these methods check that facet f=(c,i) is flippable (which is quite expensive). They return false or true according to this test. | ||
|
| |
|
| |
Should be preferred to the previous methods when the facet is
known to be flippable. Precondition: The facet is flippable. |
The following modifier member functions guarantee the combinatorial validity of the resulting triangulation.
|
| |||
Creates a new vertex, inserts it in cell c and returns its handle.
The cell c is split into four new cells, each of these cells being
formed by the new vertex and a facet of c. Precondition: tds.dimension() and c is a cell of tds. | ||||
|
| |||
Creates a new vertex, inserts it in facet f and returns its handle.
In dimension 3, the two incident cells are split into 3 new cells;
in dimension 2, the facet is split into 3 facets. Precondition: tds.dimension() and f is a facet of tds. | ||||
|
| |||
Creates a new vertex, inserts it in facet i of c and returns its
handle. Precondition: tds.dimension() , in dimension 3, in dimension 2 and (c,i) is a facet of tds. | ||||
|
| |||
Creates a new vertex, inserts it in edge e and returns its handle.
In dimension 3, all the
incident cells are split into 2 new cells; in dimension 2, the 2
incident facets are split into 2 new facets; in dimension 1, the edge is
split into 2 new edges. Precondition: tds.dimension() and e is an edge of tds. | ||||
|
| |||
Creates a new vertex, inserts it in edge of c and returns its
handle. Precondition: tds.dimension() . , in dimension 3, in dimension 2, in dimension 1 and (c,i,j) is an edge of tds. | ||||
|
| |||
Transforms a triangulation of the sphere of into the
triangulation of the sphere of by adding a new vertex
v:
v is linked to all the vertices to triangulate one of the two
halfspheres of dimension . Vertex star is used to
triangulate the second halfsphere (when there is an associated
geometric triangulation, star is in fact the vertex associated with
its infinite vertex).
See Figure . The numbering of the cells is such that, if f was a face of maximal dimension in the initial triangulation, then (f,v) (in this order) is the corresponding face in the new triangulation. This method can be used to insert the first two vertices in an empty triangulation. A handle to v is returned. Precondition: tds.dimension() . When tds.number_of_vertices() , and star is a vertex of tds. |
Figure: insert_increase_dimension (1-dimensional case).
| ||||
|
| |||
Creates a new vertex by starring a hole. It takes an iterator range
[cell_begin; cell_end[ of Cell_handles which specifies a set
of connected cells (resp. facets in dimension 2) describing a hole.
(begin, i) is a facet (resp. an edge) on the boundary of the hole,
that is, begin belongs to the set of cells (resp. facets) previously
described, and begin->neighbor(i) does not. Then this function deletes
all the cells (resp. facets) describing the hole, creates a new vertex
v, and for each facet (resp. edge) on the boundary of the hole, creates
a new cell (resp. facet) with v as vertex. v is returned. Precondition: tds.dimension() , the set of cells (resp. facets) is connected, and its boundary is connected. |
|
| |||
This operation is the reciprocal of insert_increase_dimension().
It transforms a triangulation of the sphere of into the
triangulation of the sphere of by removing the vertex
v. Precondition: tds.dimension() . tds.degree(v) tds.number_of_vertices() . | ||||
|
| |||
Removes v. The incident simplices of maximal dimension incident to
v are replaced by a single simplex of the same dimension. This
operation is exactly the reciprocal to tds.insert_in_cell(v) in
dimension 3, tds.insert_in_facet(v) in dimension 2, and
tds.insert_in_edge(v) in dimension 1. Precondition: tds.degree(v) tds.dimension()+1. |
advanced |
|
|
Changes the orientation of all cells of the triangulation data structure. Precondition: tds.dimension() . | ||
|
| |||
Adds a copy of the vertex v to the triangulation data structure. | ||||
|
| |||
Creates a vertex which is a copy of the one pointed to by v and adds it to the triangulation data structure. | ||||
|
| |||
Adds a copy of the cell c to the triangulation data structure. | ||||
|
| |||
Creates a cell which is a copy of the one pointed to by c and adds it to the triangulation data structure. | ||||
|
| |||
Creates a cell and adds it into the triangulation data structure. Initializes the vertices of the cell, its neighbor handles being initialized with the default constructed handle. | ||||
|
| |||
Creates a cell, initializes its vertices and neighbors, and adds it into the triangulation data structure. | ||||
|
| |||
Removes the vertex from the triangulation data structure. Precondition: The vertex is a vertex of tds. | ||||
|
| |||
Removes the cell from the triangulation data structure. Precondition: The cell is a cell of tds. | ||||
| ||||
|
| |||
Calls delete_vertex over an iterator range of value type Vertex_handle. | ||||
| ||||
|
| |||
Calls delete_cell over an iterator range of value type Cell_handle. |
advanced |
|
| Returns cells_end() when tds.dimension() . | ||
|
|
|||
|
| |||
Returns facets_end() when tds.dimension() . | ||||
|
|
|||
|
| Returns edges_end() when tds.dimension() . | ||
|
|
|||
|
| |||
|
| |||
|
| |||
Starts at an arbitrary cell incident to e. Precondition: tds.dimension() | ||||
|
| |||
As above for edge (i,j) of c. | ||||
|
| |||
Starts at cell start. Precondition: tds.dimension() and start is incident to e. | ||||
|
| |||
As above for edge (i,j) of c. |
The following circulators on facets are defined only in dimension 3, though facets are defined also in dimension 2: there are only two facets sharing an edge in dimension 2.
|
| |||
Starts at an arbitrary facet incident to e. Precondition: tds.dimension() | ||||
|
| |||
As above for edge (i,j) of c. | ||||
|
| |||
Starts at facet start. Precondition: start is incident to e. | ||||
|
| |||
Starts at facet of index f in start. | ||||
|
| |||
As above for edge (i,j) of c. | ||||
|
| |||
As above for edge (i,j) of c and facet (start,f). |
| ||||
|
| |||
Copies the Cell_handles of all cells (resp. facets in dimension 2)
incident to v to the output iterator cells.
If tds.dimension() , then do nothing.
Returns the resulting output iterator. Precondition: v Vertex_handle(), tds.is_vertex(v). | ||||
| ||||
|
| |||
Copies the Vertex_handles of all vertices incident to v to the
output iterator vertices. If tds.dimension() , then do
nothing. Returns the resulting output iterator. Precondition: v Vertex_handle(), tds.is_vertex(v). | ||||
|
| |||
Returns the degree of a vertex, that is, the number of incident vertices. Precondition: v Vertex_handle(), tds.is_vertex(v). |
advanced |
|
| |
Checks the combinatorial validity of the triangulation by checking
the validity of all its cells and vertices.
(See Section .) Moreover, the Euler relation is
tested. When verbose is set to true, messages are printed to give a precise indication on the kind of invalidity encountered. |
advanced |
|
| |
Reads a combinatorial triangulation from is and assigns it to tds | ||
|
| |
Writes tds into the stream os |
The information stored in the iostream is: the dimension, the number of vertices, the number of cells, the indices of the vertices of each cell, then the indices of the neighbors of each cell, where the index corresponds to the preceding list of cells. When dimension 3, the same information is stored for faces of maximal dimension instead of cells.
CGAL::Triangulation_data_structure_3
TriangulationDataStructure_3::Vertex
TriangulationDataStructure_3::Cell