Definition
The TriangulationDataStructure concept describes objects responsible for storing and maintaining the combinatorial part of a \( d\)-dimensional pure simplicial complex that has the topology of the \( d\)-dimensional sphere \( \mathbb{S}^d\) with \( d\in[-2,D]\). Since the simplicial \( d\)-complex is pure, all faces are sub-faces of some \( d\)-simplex. And since it has the topology of the sphere \( \mathbb{S}^d\), it is manifold, thus any \( d-1\)-face belongs to exactly two \( d\)-dimensional full cells.
The concept TriangulationDataStructure includes two sub-concepts TriangulationDataStructure::Vertex and TriangulationDataStructure::FullCell.
Possible values for the current dimension \( d\) include
- -2
- This corresponds to the non-existence of any object in the triangulation.
- -1
This corresponds to a single vertex and a single full cell, which is also the unique vertex and the unique full cell in the TriangulationDataStructure. In a geometric realization of the TriangulationDataStructure (e.g., in a CGAL::Triangulation<TriangulationTraits_, TriangulationDataStructure_> or a CGAL::Delaunay_triangulation<DelaunayTriangulationTraits_, TriangulationDataStructure_>), this vertex corresponds to the vertex at infinity.
- 0
This corresponds to two vertices, each incident to one \( 0\)-face; the two full cells being neighbors of each other. This is the unique triangulation of the \( 0\)-sphere.
- \( d>0\)
- This corresponds to a triangulation of the sphere \( \mathbb{S}^d\).
An \( i\)-simplex is a simplex with \( i+1\) vertices. An \( i\)-simplex \( \sigma\) is incident to a \( j\)-simplex \( \sigma'\), \( j<i\), if and only if \( \sigma'\) is a proper face of \( \sigma\).
We call a \( 0\)-simplex a vertex, a \( (d-1)\)-simplex a facet and a \( d\)-simplex a full cell. A face can have any dimension. Two full cells are neighbors if they share a facet. Two faces are incident if one is included in the other.
Input/Output
The information stored in the iostream is:
- the current dimension (which must be smaller than or equal to tds.maximal_dimension()),
- the number of vertices,
- for each vertex the information of that vertex,
- the number of full cells,
- for each full cell the indices of its vertices and extra information for that full cell,
- for each full cell the indices of its neighbors.
The indices of vertices and full cells correspond to the order in the file; the user cannot control it. The classes Vertex and Full_cell have to provide the relevant I/O operators (possibly empty).
- Has models
- CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_>
Concepts | |
| class | Vertex |
| The concept TriangulationDataStructure::Vertex describes the type used by a TriangulationDataStructure to store the vertices. More... | |
| class | FullCell |
| The concept TriangulationDataStructure::FullCell describes the type used by a TriangulationDataStructure to store the full cells. More... | |
Types | |
| typedef unspecified_type | Vertex |
| The vertex type, requirements for this type are described in the concept TriangulationDataStructure::Vertex. | |
| typedef unspecified_type | Full_cell |
| The full cell type, requirements for this type are described in the concept TriangulationDataStructure::FullCell. | |
| typedef unspecified_type | Full_cell_data |
| A model of the concept FullCellData. | |
| typedef unspecified_type | Facet |
| The facet type, for describing faces of the triangulation with codimension 1. | |
| typedef unspecified_type | Face |
| The face type, which must be a model of the concept TriangulationDSFace. | |
Handles | |
Vertices and full cells are manipulated via handles. Handles support the usual two dereference operators and operator->. | |
| typedef unspecified_type | Vertex_handle |
| Handle to a Vertex. | |
| typedef unspecified_type | Vertex_const_handle |
| Const handle to a Vertex. | |
| typedef unspecified_type | Full_cell_handle |
| Handle to a Full_cell. | |
| typedef unspecified_type | Full_cell_const_handle |
| Const handle to a Full_cell. | |
Iterators | |
Vertices, facets and full cells can be iterated over using iterators. Iterators support the usual two dereference operators and operator->. | |
| typedef unspecified_type | Vertex_iterator |
| Iterator over the list of vertices. | |
| typedef unspecified_type | Full_cell_iterator |
| Iterator over the list of full cells. | |
| typedef unspecified_type | Facet_iterator |
| Iterator over the facets of the complex. | |
| typedef unspecified_type | size_type |
| Size type (an unsigned integral type). | |
| typedef unspecified_type | difference_type |
| Difference type (a signed integral type). | |
Creation | |
| TriangulationDataStructure (int dim=0) | |
| Creates an instance tds of type TriangulationDataStructure. | |
Queries | |
| int | maximal_dimension () const |
| Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds. | |
| int | current_dimension () const |
| Returns the dimension of the full dimensional cells stored in the triangulation. | |
| bool | empty () const |
| Returns true if the triangulation contains nothing, returns false otherwise. | |
| size_type | number_of_vertices () const |
| Returns the number of vertices in the triangulation. | |
| size_type | number_of_full_cells () const |
| Returns the number of full cells in the triangulation. | |
| bool | is_vertex (const Vertex_handle &v) const |
| Tests whether v is a vertex of the triangulation. | |
| bool | is_full_cell (const Full_cell_handle &c) const |
| Tests whether c is a full cell of the triangulation. | |
| template<typename TraversalPredicate, typename OutputIterator> | |
| Facet | gather_full_cells (Full_cell_handle start, TraversalPredicate &tp, OutputIterator &out) const |
| This function computes (gathers) a connected set of full cells satisfying a common criterion. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_full_cells (Vertex_handle v, OutputIterator out) const |
| Inserts in out all the full cells that are incident to the vertex v, i.e., the full cells that have the Vertex v as a vertex. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_full_cells (const Face &f, OutputIterator out) const |
| Inserts in out all the full cells that are incident to the face f, i.e., the full cells that have the Face f as a subface. | |
| template<typename OutputIterator> | |
| OutputIterator | star (const Face &f, OutputIterator out) const |
| Inserts in out all the full cells that share at least one vertex with the Face f. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_faces (Vertex_handle v, const int dim, OutputIterator out) |
| Constructs all the Faces of dimension dim incident to Vertex v and inserts them in the OutputIterator out. | |
Accessing the Vertices | |
| Vertex_handle | vertex (Full_cell_handle c, const int i) const |
| Returns a handle to the i-th Vertex of the Full_cell c. | |
| int | mirror_index (Full_cell_handle c, int i) const |
| Returns the index of c as a neighbor of its i-th neighbor. | |
| Vertex_handle | mirror_vertex (Full_cell_handle c, int i) const |
| Returns the vertex of the i-th neighbor of c that is not vertex of c. | |
| Vertex_iterator | vertices_begin () |
| Iterator to the first vertex of tds. | |
| Vertex_iterator | vertices_end () |
| Iterator referring beyond the last vertex of tds. | |
Accessing the Full Cells | |
| Full_cell_handle | full_cell (Vertex_handle v) const |
| Returns a full cell incident to Vertex v. | |
| Full_cell_handle | neighbor (Full_cell_handle c, int i) const |
| Returns a Full_cell_handle pointing to the Full_cell opposite to the i-th vertex of c. | |
| Full_cell_iterator | full_cells_begin () |
| Iterator to the first full cell of tds. | |
| Full_cell_iterator | full_cells_end () |
| Iterator referring beyond the last full cell of tds. | |
Faces and Facets | |
| Facet_iterator | facets_begin () |
| Iterator to the first facet of the triangulation. | |
| Facet_iterator | facets_end () |
| Iterator referring beyond the last facet of the triangulation. | |
| Full_cell_handle | full_cell (const Facet &f) const |
| Returns a full cell containing the facet f. | |
| int | index_of_covertex (const Facet &f) const |
| Returns the index of vertex of the full cell c=tds.full_cell(f) which does not belong to f. | |
Vertex Insertion | |
| Vertex_handle | insert_in_full_cell (Full_cell_handle c) |
| Inserts a new vertex v in the full cell c and returns a handle to it. | |
| Vertex_handle | insert_in_face (const Face &f) |
| Inserts a vertex in the triangulation data structure by subdividing the Face f. | |
| Vertex_handle | insert_in_facet (const Facet &ft) |
| Inserts a vertex in the triangulation data structure by subdividing the Facet ft. | |
| template<class ForwardIterator> | |
| Vertex_handle | insert_in_hole (ForwardIterator s, ForwardIterator e, Facet f) |
| This is an advanced function. | |
| template<class ForwardIterator, class OutputIterator> | |
| Vertex_handle | insert_in_hole (ForwardIterator s, ForwardIterator e, Facet f, OutputIterator out) |
| Same as above, but handles to the new full cells are appended to the out output iterator. | |
| Vertex_handle | insert_increase_dimension (Vertex_handle star) |
| Transforms a triangulation of the sphere \( \mathbb{S}^d\) into the triangulation of the sphere \( \mathbb{S}^{d+1}\) by adding a new vertex v. | |
| Full_cell_handle | new_full_cell () |
| Adds a new full cell to tds and returns a handle to it. | |
| Vertex_handle | new_vertex () |
| Adds a new vertex to tds and returns a handle to it. | |
| void | associate_vertex_with_full_cell (Full_cell_handle c, int i, Vertex_handle v) |
| Sets the i-th vertex of c to v and, if v != Vertex_handle(), sets c as the incident full cell of v. | |
| void | set_neighbors (Full_cell_handle ci, int i, Full_cell_handle cj, int j) |
| Sets the neighbor opposite to vertex i of Full_cell ci to cj. | |
| void | set_current_dimension (int d) |
| Forces the current dimension of the complex to d. | |
Vertex Removal | |
| void | clear () |
| Reinitializes tds to the empty complex. | |
| Vertex_handle | collapse_face (const Face &f) |
| Contracts the Face f to a single vertex. | |
| void | remove_decrease_dimension (Vertex_handle v, Vertex_handle star) |
| This method does exactly the opposite of insert_increase_dimension(): v is removed, full cells not containing star are removed, full cells containing star but not v lose vertex star, full cells containing star and v lose vertex v (see Figure 52.5). | |
| void | delete_vertex (Vertex_handle v) |
| This is an advanced function. | |
| void | delete_full_cell (Full_cell_handle c) |
| This is an advanced function. | |
| template<typename ForwardIterator> | |
| void | delete_full_cells (ForwardIterator s, ForwardIterator e) |
| This is an advanced function. | |
Validity Check | |
| bool | is_valid (bool verbose=false) const |
| This is a function for debugging purpose. | |
| std::istream & | operator>> (std::istream &is, TriangulationDataStructure &tds) |
| Reads a combinatorial triangulation from is and assigns it to tds. | |
| std::ostream & | operator<< (std::ostream &os, const TriangulationDataStructure &tds) |
| Writes tds into the output stream os. | |
Member Typedef Documentation
◆ Facet
The facet type, for describing faces of the triangulation with codimension 1.
The constructor Facet(c,i) constructs a Facet representing the facet of full cell c opposite to its i-th vertex. Its dimension is current_dimension()-1.
Constructor & Destructor Documentation
◆ TriangulationDataStructure()
| TriangulationDataStructure::TriangulationDataStructure | ( | int | dim = 0 | ) |
Creates an instance tds of type TriangulationDataStructure.
The maximal dimension of its full cells is dim and tds is initialized to the empty triangulation. Thus, tds.current_dimension() equals -2. The parameter dim can be ignored by the constructor if it is already known at compile-time. Otherwise, the following precondition holds:
- Precondition
- dim>0.
Member Function Documentation
◆ collapse_face()
| Vertex_handle TriangulationDataStructure::collapse_face | ( | const Face & | f | ) |
Contracts the Face f to a single vertex.
Returns a handle to that vertex (see Figure 52.1).
- Precondition
- The boundary of the full cells incident to f is a topological sphere of dimension tds.current_dimension()-1).
◆ current_dimension()
| int TriangulationDataStructure::current_dimension | ( | ) | const |
Returns the dimension of the full dimensional cells stored in the triangulation.
It holds that tds.current_dimension()=-2 if and only if tds.empty() is true.
- Postcondition
- the returned value d satisfies \( -2\leq d \leq\)tds.maximal_dimension().
◆ delete_full_cell()
| void TriangulationDataStructure::delete_full_cell | ( | Full_cell_handle | c | ) |
This is an advanced function.
- Precondition
- c is a full cell of tds.
◆ delete_full_cells()
| void TriangulationDataStructure::delete_full_cells | ( | ForwardIterator | s, |
| ForwardIterator | e ) |
This is an advanced function.
◆ delete_vertex()
| void TriangulationDataStructure::delete_vertex | ( | Vertex_handle | v | ) |
This is an advanced function.
- Precondition
- v is a vertex of tds.
◆ full_cell()
| Full_cell_handle TriangulationDataStructure::full_cell | ( | Vertex_handle | v | ) | const |
Returns a full cell incident to Vertex v.
Note that this full cell is not unique (v is typically incident to more than one full cell).
- Precondition
- v != Vertex_handle
◆ full_cells_begin()
| Full_cell_iterator TriangulationDataStructure::full_cells_begin | ( | ) |
Iterator to the first full cell of tds.
User has no control on the order.
◆ gather_full_cells()
| Facet TriangulationDataStructure::gather_full_cells | ( | Full_cell_handle | start, |
| TraversalPredicate & | tp, | ||
| OutputIterator & | out ) const |
This function computes (gathers) a connected set of full cells satisfying a common criterion.
Call them good full cells. It is assumed that the argument start is a good full cell. The full cells are then recursively explored by examining if, from a given good full cell, its adjacent full cells are also good.
The argument tp is a predicate, i.e. a function or a functor providing operator(), that takes as argument a Facet whose Full_cell is good. The predicate must return true if the traversal of that Facet leads to a good full cell.
All the good full cells are output into the last argument out.
Returns a facet on the boundary of the set of cells.
- Precondition
- start != Full_cell_handle() and start is a good cell.
◆ incident_faces()
| OutputIterator TriangulationDataStructure::incident_faces | ( | Vertex_handle | v, |
| const int | dim, | ||
| OutputIterator | out ) |
Constructs all the Faces of dimension dim incident to Vertex v and inserts them in the OutputIterator out.
If dim >= tds.current_dimension(), then no Face is constructed.
- Precondition
- 0 < dim and v!=Vertex_handle().
◆ incident_full_cells() [1/2]
| OutputIterator TriangulationDataStructure::incident_full_cells | ( | const Face & | f, |
| OutputIterator | out ) const |
Inserts in out all the full cells that are incident to the face f, i.e., the full cells that have the Face f as a subface.
Returns the output iterator.
- Precondition
- f.full_cell()!=Full_cell_handle().
◆ incident_full_cells() [2/2]
| OutputIterator TriangulationDataStructure::incident_full_cells | ( | Vertex_handle | v, |
| OutputIterator | out ) const |
Inserts in out all the full cells that are incident to the vertex v, i.e., the full cells that have the Vertex v as a vertex.
Returns the output iterator.
- Precondition
- v!=Vertex_handle().
◆ insert_in_face()
| Vertex_handle TriangulationDataStructure::insert_in_face | ( | const Face & | f | ) |
Inserts a vertex in the triangulation data structure by subdividing the Face f.
Returns a handle to the newly created Vertex.
◆ insert_in_facet()
| Vertex_handle TriangulationDataStructure::insert_in_facet | ( | const Facet & | ft | ) |
◆ insert_in_full_cell()
| Vertex_handle TriangulationDataStructure::insert_in_full_cell | ( | Full_cell_handle | c | ) |
Inserts a new vertex v in the full cell c and returns a handle to it.
The full cell c is subdivided into tds.current_dimension()+1 full cells which share the vertex v.
- Precondition
- Current dimension is positive and c is a full cell of tds.
◆ insert_in_hole()
| Vertex_handle TriangulationDataStructure::insert_in_hole | ( | ForwardIterator | s, |
| ForwardIterator | e, | ||
| Facet | f ) |
This is an advanced function.
- Precondition
- c belongs to \( C\) and c->neighbor(i) does not, with f=(c,i). \( H\), the union of full cells in \( C\), is simply connected and its boundary \( \partial H\) is a combinatorial triangulation of the sphere \( \mathbb{S}^{d-1}\). All vertices of cells of \( C\) are on \( \partial H\).
◆ insert_increase_dimension()
| Vertex_handle TriangulationDataStructure::insert_increase_dimension | ( | Vertex_handle | star | ) |
Transforms a triangulation of the sphere \( \mathbb{S}^d\) into the triangulation of the sphere \( \mathbb{S}^{d+1}\) by adding a new vertex v.
v is used to triangulate one of the two half-spheres of \( \mathbb{S}^{d+1}\) ( \( v\) is added as \( (d+2)^{th}\) vertex to all full cells) and star is used to triangulate the other half-sphere (all full cells that do not already have star as vertex are duplicated, and star replaces v in these full cells). The indexing of the vertices in the full cell is such that, if f was a full cell of maximal dimension in the initial complex, then (f,v), in this order, is the corresponding full cell in the updated triangulation. A handle to v is returned (see Figure 52.5).
- Precondition
- If the current dimension is -2 (empty triangulation), then star can be omitted (it is ignored), otherwise the current dimension must be strictly less than the maximal dimension and star must be a vertex of tds.
◆ is_valid()
| bool TriangulationDataStructure::is_valid | ( | bool | verbose = false | ) | const |
This is a function for debugging purpose.
- check the validity of the vertices and full cells of tds by calling their respective is_valid method.
- check that each full cell has no duplicate vertices and has as many neighbors as its number of facets (current_dimension()+1).
- check that each full cell share exactly tds.current_dimension() vertices with each of its neighbor.
◆ maximal_dimension()
| int TriangulationDataStructure::maximal_dimension | ( | ) | const |
Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds.
- Postcondition
- the returned value is positive.
◆ mirror_index()
| int TriangulationDataStructure::mirror_index | ( | Full_cell_handle | c, |
| int | i ) const |
Returns the index of c as a neighbor of its i-th neighbor.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ mirror_vertex()
| Vertex_handle TriangulationDataStructure::mirror_vertex | ( | Full_cell_handle | c, |
| int | i ) const |
Returns the vertex of the i-th neighbor of c that is not vertex of c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ neighbor()
| Full_cell_handle TriangulationDataStructure::neighbor | ( | Full_cell_handle | c, |
| int | i ) const |
Returns a Full_cell_handle pointing to the Full_cell opposite to the i-th vertex of c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c != Full_cell_handle()
◆ new_full_cell()
| Full_cell_handle TriangulationDataStructure::new_full_cell | ( | ) |
Adds a new full cell to tds and returns a handle to it.
The new full cell has no vertices and no neighbors yet.
◆ new_vertex()
| Vertex_handle TriangulationDataStructure::new_vertex | ( | ) |
Adds a new vertex to tds and returns a handle to it.
The new vertex has no associated full cell nor index yet.
◆ operator>>()
| std::istream & TriangulationDataStructure::operator>> | ( | std::istream & | is, |
| TriangulationDataStructure & | tds ) |
Reads a combinatorial triangulation from is and assigns it to tds.
- Precondition
- The dimension of the input complex must be less than or equal to tds.maximal_dimension().
◆ remove_decrease_dimension()
| void TriangulationDataStructure::remove_decrease_dimension | ( | Vertex_handle | v, |
| Vertex_handle | star ) |
This method does exactly the opposite of insert_increase_dimension(): v is removed, full cells not containing star are removed, full cells containing star but not v lose vertex star, full cells containing star and v lose vertex v (see Figure 52.5).
- Precondition
- All cells contain either star or v. Edge star-v exists in the triangulation and current_dimension() != -2.
◆ set_current_dimension()
| void TriangulationDataStructure::set_current_dimension | ( | int | d | ) |
Forces the current dimension of the complex to d.
- Precondition
- \(-2 \leq d \leq \)maximal_dimension().
◆ set_neighbors()
| void TriangulationDataStructure::set_neighbors | ( | Full_cell_handle | ci, |
| int | i, | ||
| Full_cell_handle | cj, | ||
| int | j ) |
◆ star()
| OutputIterator TriangulationDataStructure::star | ( | const Face & | f, |
| OutputIterator | out ) const |
Inserts in out all the full cells that share at least one vertex with the Face f.
Returns the output iterator.
- Precondition
- f.full_cell()!=Full_cell_handle().
◆ vertex()
| Vertex_handle TriangulationDataStructure::vertex | ( | Full_cell_handle | c, |
| const int | i ) const |
Returns a handle to the i-th Vertex of the Full_cell c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ vertices_begin()
| Vertex_iterator TriangulationDataStructure::vertices_begin | ( | ) |
Iterator to the first vertex of tds.
User has no control on the order.
- Generated by
1.17.0
#include <Concepts/TriangulationDataStructure.h>
Definition
The TriangulationDataStructure concept describes objects responsible for storing and maintaining the combinatorial part of a \( d\)-dimensional pure simplicial complex that has the topology of the \( d\)-dimensional sphere \( \mathbb{S}^d\) with \( d\in[-2,D]\). Since the simplicial \( d\)-complex is pure, all faces are sub-faces of some \( d\)-simplex. And since it has the topology of the sphere \( \mathbb{S}^d\), it is manifold, thus any \( d-1\)-face belongs to exactly two \( d\)-dimensional full cells.
The concept TriangulationDataStructure includes two sub-concepts TriangulationDataStructure::Vertex and TriangulationDataStructure::FullCell.
Possible values for the current dimension \( d\) include
- -2
- This corresponds to the non-existence of any object in the triangulation.
- -1
This corresponds to a single vertex and a single full cell, which is also the unique vertex and the unique full cell in the TriangulationDataStructure. In a geometric realization of the TriangulationDataStructure (e.g., in a CGAL::Triangulation<TriangulationTraits_, TriangulationDataStructure_> or a CGAL::Delaunay_triangulation<DelaunayTriangulationTraits_, TriangulationDataStructure_>), this vertex corresponds to the vertex at infinity.
- 0
This corresponds to two vertices, each incident to one \( 0\)-face; the two full cells being neighbors of each other. This is the unique triangulation of the \( 0\)-sphere.
- \( d>0\)
- This corresponds to a triangulation of the sphere \( \mathbb{S}^d\).
An \( i\)-simplex is a simplex with \( i+1\) vertices. An \( i\)-simplex \( \sigma\) is incident to a \( j\)-simplex \( \sigma'\), \( j<i\), if and only if \( \sigma'\) is a proper face of \( \sigma\).
We call a \( 0\)-simplex a vertex, a \( (d-1)\)-simplex a facet and a \( d\)-simplex a full cell. A face can have any dimension. Two full cells are neighbors if they share a facet. Two faces are incident if one is included in the other.
Input/Output
The information stored in the iostream is:
- the current dimension (which must be smaller than or equal to tds.maximal_dimension()),
- the number of vertices,
- for each vertex the information of that vertex,
- the number of full cells,
- for each full cell the indices of its vertices and extra information for that full cell,
- for each full cell the indices of its neighbors.
The indices of vertices and full cells correspond to the order in the file; the user cannot control it. The classes Vertex and Full_cell have to provide the relevant I/O operators (possibly empty).
- Has models
- CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex_, TriangulationDSFullCell_>
Concepts | |
| class | Vertex |
| The concept TriangulationDataStructure::Vertex describes the type used by a TriangulationDataStructure to store the vertices. More... | |
| class | FullCell |
| The concept TriangulationDataStructure::FullCell describes the type used by a TriangulationDataStructure to store the full cells. More... | |
Types | |
| typedef unspecified_type | Vertex |
| The vertex type, requirements for this type are described in the concept TriangulationDataStructure::Vertex. | |
| typedef unspecified_type | Full_cell |
| The full cell type, requirements for this type are described in the concept TriangulationDataStructure::FullCell. | |
| typedef unspecified_type | Full_cell_data |
| A model of the concept FullCellData. | |
| typedef unspecified_type | Facet |
| The facet type, for describing faces of the triangulation with codimension 1. | |
| typedef unspecified_type | Face |
| The face type, which must be a model of the concept TriangulationDSFace. | |
Handles | |
Vertices and full cells are manipulated via handles. Handles support the usual two dereference operators and operator->. | |
| typedef unspecified_type | Vertex_handle |
| Handle to a Vertex. | |
| typedef unspecified_type | Vertex_const_handle |
| Const handle to a Vertex. | |
| typedef unspecified_type | Full_cell_handle |
| Handle to a Full_cell. | |
| typedef unspecified_type | Full_cell_const_handle |
| Const handle to a Full_cell. | |
Iterators | |
Vertices, facets and full cells can be iterated over using iterators. Iterators support the usual two dereference operators and operator->. | |
| typedef unspecified_type | Vertex_iterator |
| Iterator over the list of vertices. | |
| typedef unspecified_type | Full_cell_iterator |
| Iterator over the list of full cells. | |
| typedef unspecified_type | Facet_iterator |
| Iterator over the facets of the complex. | |
| typedef unspecified_type | size_type |
| Size type (an unsigned integral type). | |
| typedef unspecified_type | difference_type |
| Difference type (a signed integral type). | |
Creation | |
| TriangulationDataStructure (int dim=0) | |
| Creates an instance tds of type TriangulationDataStructure. | |
Queries | |
| int | maximal_dimension () const |
| Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds. | |
| int | current_dimension () const |
| Returns the dimension of the full dimensional cells stored in the triangulation. | |
| bool | empty () const |
| Returns true if the triangulation contains nothing, returns false otherwise. | |
| size_type | number_of_vertices () const |
| Returns the number of vertices in the triangulation. | |
| size_type | number_of_full_cells () const |
| Returns the number of full cells in the triangulation. | |
| bool | is_vertex (const Vertex_handle &v) const |
| Tests whether v is a vertex of the triangulation. | |
| bool | is_full_cell (const Full_cell_handle &c) const |
| Tests whether c is a full cell of the triangulation. | |
| template<typename TraversalPredicate, typename OutputIterator> | |
| Facet | gather_full_cells (Full_cell_handle start, TraversalPredicate &tp, OutputIterator &out) const |
| This function computes (gathers) a connected set of full cells satisfying a common criterion. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_full_cells (Vertex_handle v, OutputIterator out) const |
| Inserts in out all the full cells that are incident to the vertex v, i.e., the full cells that have the Vertex v as a vertex. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_full_cells (const Face &f, OutputIterator out) const |
| Inserts in out all the full cells that are incident to the face f, i.e., the full cells that have the Face f as a subface. | |
| template<typename OutputIterator> | |
| OutputIterator | star (const Face &f, OutputIterator out) const |
| Inserts in out all the full cells that share at least one vertex with the Face f. | |
| template<typename OutputIterator> | |
| OutputIterator | incident_faces (Vertex_handle v, const int dim, OutputIterator out) |
| Constructs all the Faces of dimension dim incident to Vertex v and inserts them in the OutputIterator out. | |
Accessing the Vertices | |
| Vertex_handle | vertex (Full_cell_handle c, const int i) const |
| Returns a handle to the i-th Vertex of the Full_cell c. | |
| int | mirror_index (Full_cell_handle c, int i) const |
| Returns the index of c as a neighbor of its i-th neighbor. | |
| Vertex_handle | mirror_vertex (Full_cell_handle c, int i) const |
| Returns the vertex of the i-th neighbor of c that is not vertex of c. | |
| Vertex_iterator | vertices_begin () |
| Iterator to the first vertex of tds. | |
| Vertex_iterator | vertices_end () |
| Iterator referring beyond the last vertex of tds. | |
Accessing the Full Cells | |
| Full_cell_handle | full_cell (Vertex_handle v) const |
| Returns a full cell incident to Vertex v. | |
| Full_cell_handle | neighbor (Full_cell_handle c, int i) const |
| Returns a Full_cell_handle pointing to the Full_cell opposite to the i-th vertex of c. | |
| Full_cell_iterator | full_cells_begin () |
| Iterator to the first full cell of tds. | |
| Full_cell_iterator | full_cells_end () |
| Iterator referring beyond the last full cell of tds. | |
Faces and Facets | |
| Facet_iterator | facets_begin () |
| Iterator to the first facet of the triangulation. | |
| Facet_iterator | facets_end () |
| Iterator referring beyond the last facet of the triangulation. | |
| Full_cell_handle | full_cell (const Facet &f) const |
| Returns a full cell containing the facet f. | |
| int | index_of_covertex (const Facet &f) const |
| Returns the index of vertex of the full cell c=tds.full_cell(f) which does not belong to f. | |
Vertex Insertion | |
| Vertex_handle | insert_in_full_cell (Full_cell_handle c) |
| Inserts a new vertex v in the full cell c and returns a handle to it. | |
| Vertex_handle | insert_in_face (const Face &f) |
| Inserts a vertex in the triangulation data structure by subdividing the Face f. | |
| Vertex_handle | insert_in_facet (const Facet &ft) |
| Inserts a vertex in the triangulation data structure by subdividing the Facet ft. | |
| template<class ForwardIterator> | |
| Vertex_handle | insert_in_hole (ForwardIterator s, ForwardIterator e, Facet f) |
| This is an advanced function. | |
| template<class ForwardIterator, class OutputIterator> | |
| Vertex_handle | insert_in_hole (ForwardIterator s, ForwardIterator e, Facet f, OutputIterator out) |
| Same as above, but handles to the new full cells are appended to the out output iterator. | |
| Vertex_handle | insert_increase_dimension (Vertex_handle star) |
| Transforms a triangulation of the sphere \( \mathbb{S}^d\) into the triangulation of the sphere \( \mathbb{S}^{d+1}\) by adding a new vertex v. | |
| Full_cell_handle | new_full_cell () |
| Adds a new full cell to tds and returns a handle to it. | |
| Vertex_handle | new_vertex () |
| Adds a new vertex to tds and returns a handle to it. | |
| void | associate_vertex_with_full_cell (Full_cell_handle c, int i, Vertex_handle v) |
| Sets the i-th vertex of c to v and, if v != Vertex_handle(), sets c as the incident full cell of v. | |
| void | set_neighbors (Full_cell_handle ci, int i, Full_cell_handle cj, int j) |
| Sets the neighbor opposite to vertex i of Full_cell ci to cj. | |
| void | set_current_dimension (int d) |
| Forces the current dimension of the complex to d. | |
Vertex Removal | |
| void | clear () |
| Reinitializes tds to the empty complex. | |
| Vertex_handle | collapse_face (const Face &f) |
| Contracts the Face f to a single vertex. | |
| void | remove_decrease_dimension (Vertex_handle v, Vertex_handle star) |
| This method does exactly the opposite of insert_increase_dimension(): v is removed, full cells not containing star are removed, full cells containing star but not v lose vertex star, full cells containing star and v lose vertex v (see Figure 52.5). | |
| void | delete_vertex (Vertex_handle v) |
| This is an advanced function. | |
| void | delete_full_cell (Full_cell_handle c) |
| This is an advanced function. | |
| template<typename ForwardIterator> | |
| void | delete_full_cells (ForwardIterator s, ForwardIterator e) |
| This is an advanced function. | |
Validity Check | |
| bool | is_valid (bool verbose=false) const |
| This is a function for debugging purpose. | |
| std::istream & | operator>> (std::istream &is, TriangulationDataStructure &tds) |
| Reads a combinatorial triangulation from is and assigns it to tds. | |
| std::ostream & | operator<< (std::ostream &os, const TriangulationDataStructure &tds) |
| Writes tds into the output stream os. | |
Member Typedef Documentation
◆ Facet
The facet type, for describing faces of the triangulation with codimension 1.
The constructor Facet(c,i) constructs a Facet representing the facet of full cell c opposite to its i-th vertex. Its dimension is current_dimension()-1.
Constructor & Destructor Documentation
◆ TriangulationDataStructure()
| TriangulationDataStructure::TriangulationDataStructure | ( | int | dim = 0 | ) |
Creates an instance tds of type TriangulationDataStructure.
The maximal dimension of its full cells is dim and tds is initialized to the empty triangulation. Thus, tds.current_dimension() equals -2. The parameter dim can be ignored by the constructor if it is already known at compile-time. Otherwise, the following precondition holds:
- Precondition
- dim>0.
Member Function Documentation
◆ collapse_face()
| Vertex_handle TriangulationDataStructure::collapse_face | ( | const Face & | f | ) |
Contracts the Face f to a single vertex.
Returns a handle to that vertex (see Figure 52.1).
- Precondition
- The boundary of the full cells incident to f is a topological sphere of dimension tds.current_dimension()-1).
◆ current_dimension()
| int TriangulationDataStructure::current_dimension | ( | ) | const |
Returns the dimension of the full dimensional cells stored in the triangulation.
It holds that tds.current_dimension()=-2 if and only if tds.empty() is true.
- Postcondition
- the returned value d satisfies \( -2\leq d \leq\)tds.maximal_dimension().
◆ delete_full_cell()
| void TriangulationDataStructure::delete_full_cell | ( | Full_cell_handle | c | ) |
This is an advanced function.
- Precondition
- c is a full cell of tds.
◆ delete_full_cells()
| void TriangulationDataStructure::delete_full_cells | ( | ForwardIterator | s, |
| ForwardIterator | e ) |
This is an advanced function.
◆ delete_vertex()
| void TriangulationDataStructure::delete_vertex | ( | Vertex_handle | v | ) |
This is an advanced function.
- Precondition
- v is a vertex of tds.
◆ full_cell()
| Full_cell_handle TriangulationDataStructure::full_cell | ( | Vertex_handle | v | ) | const |
Returns a full cell incident to Vertex v.
Note that this full cell is not unique (v is typically incident to more than one full cell).
- Precondition
- v != Vertex_handle
◆ full_cells_begin()
| Full_cell_iterator TriangulationDataStructure::full_cells_begin | ( | ) |
Iterator to the first full cell of tds.
User has no control on the order.
◆ gather_full_cells()
| Facet TriangulationDataStructure::gather_full_cells | ( | Full_cell_handle | start, |
| TraversalPredicate & | tp, | ||
| OutputIterator & | out ) const |
This function computes (gathers) a connected set of full cells satisfying a common criterion.
Call them good full cells. It is assumed that the argument start is a good full cell. The full cells are then recursively explored by examining if, from a given good full cell, its adjacent full cells are also good.
The argument tp is a predicate, i.e. a function or a functor providing operator(), that takes as argument a Facet whose Full_cell is good. The predicate must return true if the traversal of that Facet leads to a good full cell.
All the good full cells are output into the last argument out.
Returns a facet on the boundary of the set of cells.
- Precondition
- start != Full_cell_handle() and start is a good cell.
◆ incident_faces()
| OutputIterator TriangulationDataStructure::incident_faces | ( | Vertex_handle | v, |
| const int | dim, | ||
| OutputIterator | out ) |
Constructs all the Faces of dimension dim incident to Vertex v and inserts them in the OutputIterator out.
If dim >= tds.current_dimension(), then no Face is constructed.
- Precondition
- 0 < dim and v!=Vertex_handle().
◆ incident_full_cells() [1/2]
| OutputIterator TriangulationDataStructure::incident_full_cells | ( | const Face & | f, |
| OutputIterator | out ) const |
Inserts in out all the full cells that are incident to the face f, i.e., the full cells that have the Face f as a subface.
Returns the output iterator.
- Precondition
- f.full_cell()!=Full_cell_handle().
◆ incident_full_cells() [2/2]
| OutputIterator TriangulationDataStructure::incident_full_cells | ( | Vertex_handle | v, |
| OutputIterator | out ) const |
Inserts in out all the full cells that are incident to the vertex v, i.e., the full cells that have the Vertex v as a vertex.
Returns the output iterator.
- Precondition
- v!=Vertex_handle().
◆ insert_in_face()
| Vertex_handle TriangulationDataStructure::insert_in_face | ( | const Face & | f | ) |
Inserts a vertex in the triangulation data structure by subdividing the Face f.
Returns a handle to the newly created Vertex.
◆ insert_in_facet()
| Vertex_handle TriangulationDataStructure::insert_in_facet | ( | const Facet & | ft | ) |
◆ insert_in_full_cell()
| Vertex_handle TriangulationDataStructure::insert_in_full_cell | ( | Full_cell_handle | c | ) |
Inserts a new vertex v in the full cell c and returns a handle to it.
The full cell c is subdivided into tds.current_dimension()+1 full cells which share the vertex v.
- Precondition
- Current dimension is positive and c is a full cell of tds.
◆ insert_in_hole()
| Vertex_handle TriangulationDataStructure::insert_in_hole | ( | ForwardIterator | s, |
| ForwardIterator | e, | ||
| Facet | f ) |
This is an advanced function.
- Precondition
- c belongs to \( C\) and c->neighbor(i) does not, with f=(c,i). \( H\), the union of full cells in \( C\), is simply connected and its boundary \( \partial H\) is a combinatorial triangulation of the sphere \( \mathbb{S}^{d-1}\). All vertices of cells of \( C\) are on \( \partial H\).
◆ insert_increase_dimension()
| Vertex_handle TriangulationDataStructure::insert_increase_dimension | ( | Vertex_handle | star | ) |
Transforms a triangulation of the sphere \( \mathbb{S}^d\) into the triangulation of the sphere \( \mathbb{S}^{d+1}\) by adding a new vertex v.
v is used to triangulate one of the two half-spheres of \( \mathbb{S}^{d+1}\) ( \( v\) is added as \( (d+2)^{th}\) vertex to all full cells) and star is used to triangulate the other half-sphere (all full cells that do not already have star as vertex are duplicated, and star replaces v in these full cells). The indexing of the vertices in the full cell is such that, if f was a full cell of maximal dimension in the initial complex, then (f,v), in this order, is the corresponding full cell in the updated triangulation. A handle to v is returned (see Figure 52.5).
- Precondition
- If the current dimension is -2 (empty triangulation), then star can be omitted (it is ignored), otherwise the current dimension must be strictly less than the maximal dimension and star must be a vertex of tds.
◆ is_valid()
| bool TriangulationDataStructure::is_valid | ( | bool | verbose = false | ) | const |
This is a function for debugging purpose.
- check the validity of the vertices and full cells of tds by calling their respective is_valid method.
- check that each full cell has no duplicate vertices and has as many neighbors as its number of facets (current_dimension()+1).
- check that each full cell share exactly tds.current_dimension() vertices with each of its neighbor.
◆ maximal_dimension()
| int TriangulationDataStructure::maximal_dimension | ( | ) | const |
Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds.
- Postcondition
- the returned value is positive.
◆ mirror_index()
| int TriangulationDataStructure::mirror_index | ( | Full_cell_handle | c, |
| int | i ) const |
Returns the index of c as a neighbor of its i-th neighbor.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ mirror_vertex()
| Vertex_handle TriangulationDataStructure::mirror_vertex | ( | Full_cell_handle | c, |
| int | i ) const |
Returns the vertex of the i-th neighbor of c that is not vertex of c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ neighbor()
| Full_cell_handle TriangulationDataStructure::neighbor | ( | Full_cell_handle | c, |
| int | i ) const |
Returns a Full_cell_handle pointing to the Full_cell opposite to the i-th vertex of c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c != Full_cell_handle()
◆ new_full_cell()
| Full_cell_handle TriangulationDataStructure::new_full_cell | ( | ) |
Adds a new full cell to tds and returns a handle to it.
The new full cell has no vertices and no neighbors yet.
◆ new_vertex()
| Vertex_handle TriangulationDataStructure::new_vertex | ( | ) |
Adds a new vertex to tds and returns a handle to it.
The new vertex has no associated full cell nor index yet.
◆ operator>>()
| std::istream & TriangulationDataStructure::operator>> | ( | std::istream & | is, |
| TriangulationDataStructure & | tds ) |
Reads a combinatorial triangulation from is and assigns it to tds.
- Precondition
- The dimension of the input complex must be less than or equal to tds.maximal_dimension().
◆ remove_decrease_dimension()
| void TriangulationDataStructure::remove_decrease_dimension | ( | Vertex_handle | v, |
| Vertex_handle | star ) |
This method does exactly the opposite of insert_increase_dimension(): v is removed, full cells not containing star are removed, full cells containing star but not v lose vertex star, full cells containing star and v lose vertex v (see Figure 52.5).
- Precondition
- All cells contain either star or v. Edge star-v exists in the triangulation and current_dimension() != -2.
◆ set_current_dimension()
| void TriangulationDataStructure::set_current_dimension | ( | int | d | ) |
Forces the current dimension of the complex to d.
- Precondition
- \(-2 \leq d \leq \)maximal_dimension().
◆ set_neighbors()
| void TriangulationDataStructure::set_neighbors | ( | Full_cell_handle | ci, |
| int | i, | ||
| Full_cell_handle | cj, | ||
| int | j ) |
◆ star()
| OutputIterator TriangulationDataStructure::star | ( | const Face & | f, |
| OutputIterator | out ) const |
Inserts in out all the full cells that share at least one vertex with the Face f.
Returns the output iterator.
- Precondition
- f.full_cell()!=Full_cell_handle().
◆ vertex()
| Vertex_handle TriangulationDataStructure::vertex | ( | Full_cell_handle | c, |
| const int | i ) const |
Returns a handle to the i-th Vertex of the Full_cell c.
- Precondition
- \(0 \leq i \leq \)tds.current_dimension() and c!=Full_cell_handle().
◆ vertices_begin()
| Vertex_iterator TriangulationDataStructure::vertices_begin | ( | ) |
Iterator to the first vertex of tds.
User has no control on the order.