|
CGAL 4.4 - High-dimension Triangulation
|
|
CGAL 4.4 - High-dimension Triangulation
|
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 \( \mathcal 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 \( \mathcal S^d\), it is manifold, thus any \( d-1\)-face belongs to exactly two \( d\)-dimensional full cells.
Possible values for the current dimension \( d\) include
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 Triangulation<TriangulationTraits, TriangulationDataStructure> or a Delaunay_triangulation<DelaunayTriangulationTraits, TriangulationDataStructure>), this vertex corresponds to the vertex at infinity.
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.
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.
The information stored in the iostream is:
<=tds.maximal_dimension()),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).
CGAL::Triangulation_data_structure<Dimensionality, TriangulationDSVertex, TriangulationDSFullCell>TriangulationDSVertex TriangulationDSFullCell TriangulationDSFace Triangulation Concepts | |
| concept | Rebind_full_cell |
| This nested template class allows to get the type of a triangulation data structure that only changes the full cell type. More... | |
| concept | Rebind_vertex |
| This nested template class allows to get the type of a triangulation data structure that only changes the vertex type. More... | |
Types | |
| typedef Hidden_type | Vertex |
| The vertex type. More... | |
| typedef Hidden_type | Full_cell |
| The full cell type. More... | |
| typedef Hidden_type | Full_cell_data |
| typedef Hidden_type | Facet |
The concept TriangulationDataStructure also defines a type for describing faces of the triangulation with codimension 1. More... | |
| typedef Hidden_type | Face |
A model of the concept TriangulationDSFace. More... | |
Handles | |
Vertices and full cells are manipulated via handles. Handles support the usual two dereference operators and | |
| typedef Hidden_type | Vertex_handle |
Handle to a Vertex. More... | |
| typedef Hidden_type | Full_cell_handle |
Handle to a Full_cell. More... | |
Iterators | |
Vertices, facets and full cells can be iterated over using iterators. Iterators support the usual two dereference operators and | |
| typedef Hidden_type | Vertex_iterator |
| Iterator over the list of vertices. More... | |
| typedef Hidden_type | Full_cell_iterator |
| Iterator over the list of full cells. More... | |
| typedef Hidden_type | Facet_iterator |
| Iterator over the facets of the complex. More... | |
| typedef Hidden_type | size_type |
| Size type (an unsigned integral type) More... | |
| typedef Hidden_type | difference_type |
| Difference type (a signed integral type) More... | |
Creation | |
| TriangulationDataStructure (int dim=0) | |
Creates an instance tds of type TriangulationDataStructure. More... | |
Queries | |
| int | maximal_dimension () const |
Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds. More... | |
| int | current_dimension () const |
| Returns the dimension of the full dimensional cells stored in the triangulation. More... | |
| bool | empty () const |
Returns true if thetriangulation contains nothing. More... | |
| size_type | number_of_vertices () const |
| Returns the number of vertices in the triangulation. More... | |
| size_type | number_of_full_cells () const |
| Returns the number of full cells in the triangulation. More... | |
| bool | is_vertex (const Vertex_handle &v) const |
Tests whether v is a vertex of the triangulation. More... | |
| bool | is_full_cell (const Full_cell_handle &c) const |
Tests whether c is a full cell of the triangulation. More... | |
| template<typename TraversalPredicate , typename OutputIterator > | |
| void | full_cells (Full_cell_handle c, TraversalPredicate &tp, OutputIterator &out) const |
| This function computes (gathers) a connected set of full cells satifying a common criterion. More... | |
| template<typename OutputIterator > | |
| OutputIterator | incident_full_cells (Vertex_handle v, OutputIterator out) const |
Insert 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. More... | |
| template<typename OutputIterator > | |
| OutputIterator | incident_full_cells (const Face &f, OutputIterator out) const |
Insert 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. More... | |
| template<typename OutputIterator > | |
| OutputIterator | star (const Face &f, OutputIterator out) const |
Insert in out all the full cells that share at least one vertex with the Face f. More... | |
| 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. More... | |
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. More... | |
| int | mirror_index (Full_cell_handle c, int i) const |
Returns the index of c as a neighbor of its i-th neighbor. More... | |
| 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. More... | |
| Vertex_iterator | vertices_begin () |
The first vertex of tds. More... | |
| Vertex_iterator | vertices_end () |
The beyond vertex of tds. More... | |
Accessing the full cells | |
| Full_cell_handle | full_cell (Vertex_handle v) const |
Returns a full cell incident to Vertex v. More... | |
| 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. More... | |
| Full_cell_iterator | full_cells_begin () |
The first full cell of tds. More... | |
| Full_cell_iterator | full_cells_end () |
The beyond full cell of tds. More... | |
Faces and Facets | |
| Facet_iterator | facets_begin () |
| Iterator to the first facet of the triangulation. More... | |
| Facet_iterator | facets_end () |
| Iterator to the beyond facet of the triangulation. More... | |
| Full_cell_handle | full_cell (const Facet &f) const |
Returns a full cell containing the facet f More... | |
| int | index_of_covertex (const Facet &f) const |
Returns the index of vertex of the full cell c=tds. More... | |
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. More... | |
| Vertex_handle | insert_in_face (const Face &f) |
Inserts a vertex in the triangulation data structure by subdividing the Face f. More... | |
| Vertex_handle | insert_in_facet (const Facet &ft) |
Inserts a vertex in the triangulation data structure by subdividing the Facet ft. More... | |
| template<class ForwardIterator > | |
| Vertex_handle | insert_in_hole (ForwardIterator start, ForwardIterator end, Facet f) |
The full cells in the range \( C=\)[start, end) are removed, thus forming a hole \( H\). More... | |
| template<class ForwardIterator , class OutputIterator > | |
| Vertex_handle | insert_in_hole (ForwardIterator start, ForwardIterator end, Facet f, OutputIterator out) |
Same as above, but handles to the new full cells are appended to the out output iterator. More... | |
| Vertex_handle | insert_increase_dimension (Vertex_handle star) |
Transforms a triangulation of the sphere \( \mathcal S^d\) into the triangulation of the sphere \( \mathcal S^{d+1}\) by adding a new vertex v. More... | |
| Full_cell_handle | new_full_cell () |
Adds a new full cell to tds and returns a handle to it. More... | |
| Vertex_handle | new_vertex () |
Adds a new vertex to tds and returns a handle to it. More... | |
| 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. More... | |
| 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. More... | |
| void | set_current_dimension (int d) |
Forces the current dimension of the complex to d. More... | |
Vertex removal | |
| void | clear () |
Reinitializes tds to the empty complex. More... | |
| Vertex_handle | collapse_face (const Face &f) |
Contracts the Face f to a single vertex. More... | |
| 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 loose vertex star, full cells containing star and v loose vertex v (see Figure Figure 40.5). More... | |
| void | delete_vertex (Vertex_handle v) |
Remove the vertex v from the triangulation. More... | |
| void | delete_full_cell (Full_cell_handle c) |
Remove the full cell c from the triangulation. More... | |
| template<typename ForwardIterator > | |
| void | delete_full_cells (ForwardIterator start, ForwardIterator end) |
Remove the full cells in the range [start,end) from the triangulation. More... | |
Validity check | |
| bool | is_valid (bool verbose=false) const |
Partially checks whether tds is indeed a triangulation. More... | |
| std::istream & | operator>> (std::istream &is, TriangulationDataStructure &tds) |
Reads a combinatorial triangulation from is and assigns it to tds. More... | |
| std::ostream & | operator<< (std::ostream &os, const TriangulationDataStructure &tds) |
Writes tds into the output stream os More... | |
| typedef Hidden_type TriangulationDataStructure::difference_type |
Difference type (a signed integral type)
| typedef Hidden_type TriangulationDataStructure::Face |
A model of the concept TriangulationDSFace.
| typedef Hidden_type TriangulationDataStructure::Facet |
The concept TriangulationDataStructure also defines a 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.
| typedef Hidden_type TriangulationDataStructure::Facet_iterator |
Iterator over the facets of the complex.
| typedef Hidden_type TriangulationDataStructure::Full_cell |
The full cell type.
A model of the concept TriangulationDSFullCell.
| typedef Hidden_type TriangulationDataStructure::Full_cell_data |
FullCellData.| typedef Hidden_type TriangulationDataStructure::Full_cell_handle |
Handle to a Full_cell.
| typedef Hidden_type TriangulationDataStructure::Full_cell_iterator |
Iterator over the list of full cells.
| typedef Hidden_type TriangulationDataStructure::size_type |
Size type (an unsigned integral type)
| typedef Hidden_type TriangulationDataStructure::Vertex |
The vertex type.
A model of the concept TriangulationDSVertex.
| typedef Hidden_type TriangulationDataStructure::Vertex_handle |
Handle to a Vertex.
| typedef Hidden_type TriangulationDataStructure::Vertex_iterator |
Iterator over the list of vertices.
| 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:
dim>0. | void TriangulationDataStructure::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 TriangulationDataStructure::clear | ( | ) |
Reinitializes tds to the empty complex.
| Vertex_handle TriangulationDataStructure::collapse_face | ( | const Face & | f | ) |
Contracts the Face f to a single vertex.
Returns a handle to that vertex (see Figure Figure 40.1).
f is a topological sphere of dimension tds.current_dimension()-1).
v is returned. | 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.
d satisfies \( -2\leq d \leq\)tds.maximal_dimension(). | void TriangulationDataStructure::delete_full_cell | ( | Full_cell_handle | c | ) |
Remove the full cell c from the triangulation.
| void TriangulationDataStructure::delete_full_cells | ( | ForwardIterator | start, |
| ForwardIterator | end | ||
| ) |
Remove the full cells in the range [start,end) from the triangulation.
| void TriangulationDataStructure::delete_vertex | ( | Vertex_handle | v | ) |
Remove the vertex v from the triangulation.
| bool TriangulationDataStructure::empty | ( | ) | const |
Returns true if thetriangulation contains nothing.
Returns false otherwise.
| Facet_iterator TriangulationDataStructure::facets_begin | ( | ) |
Iterator to the first facet of the triangulation.
| Facet_iterator TriangulationDataStructure::facets_end | ( | ) |
Iterator to the beyond facet of the triangulation.
| 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).
v != Vertex_handle | Full_cell_handle TriangulationDataStructure::full_cell | ( | const Facet & | f | ) | const |
Returns a full cell containing the facet f
| void TriangulationDataStructure::full_cells | ( | Full_cell_handle | c, |
| TraversalPredicate & | tp, | ||
| OutputIterator & | out | ||
| ) | const |
This function computes (gathers) a connected set of full cells satifying a common criterion.
Call them good full cells. It is assumed that the argument c 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.
c!=Full_cell_handle() and tp(c)==true. | Full_cell_iterator TriangulationDataStructure::full_cells_begin | ( | ) |
The first full cell of tds.
User has no control on the order.
| Full_cell_iterator TriangulationDataStructure::full_cells_end | ( | ) |
The beyond full cell of tds.
| 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.
0 < dim and v!=Vertex_handle(). | OutputIterator TriangulationDataStructure::incident_full_cells | ( | Vertex_handle | v, |
| OutputIterator | out | ||
| ) | const |
Insert 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.
v!=Vertex_handle(). | OutputIterator TriangulationDataStructure::incident_full_cells | ( | const Face & | f, |
| OutputIterator | out | ||
| ) | const |
Insert 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.
f.full_cell()!=Full_cell_handle(). | int TriangulationDataStructure::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 c.
| 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.
| Vertex_handle TriangulationDataStructure::insert_in_facet | ( | const Facet & | ft | ) |
Inserts a vertex in the triangulation data structure by subdividing the Facet ft.
Returns a handle to the newly created Vertex.
| 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.
c is a full cell of tds. | Vertex_handle TriangulationDataStructure::insert_in_hole | ( | ForwardIterator | start, |
| ForwardIterator | end, | ||
| Facet | f | ||
| ) |
The full cells in the range \( C=\)[start, end) are removed, thus forming a hole \( H\).
A Vertex is inserted and connected to the boundary of the hole in order to ``fill it''. A Vertex_handle to the new Vertex is returned.
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 \( \mathcal S^{d-1}\). All vertices of cells of \( C\) are on \( \partial H\).
| Vertex_handle TriangulationDataStructure::insert_in_hole | ( | ForwardIterator | start, |
| ForwardIterator | end, | ||
| Facet | f, | ||
| OutputIterator | out | ||
| ) |
Same as above, but handles to the new full cells are appended to the out output iterator.
| Vertex_handle TriangulationDataStructure::insert_increase_dimension | ( | Vertex_handle | star | ) |
Transforms a triangulation of the sphere \( \mathcal S^d\) into the triangulation of the sphere \( \mathcal S^{d+1}\) by adding a new vertex v.
v is used to triangulate one of the two half-spheres of \( \mathcal 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 Figure 40.5).
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.
| bool TriangulationDataStructure::is_full_cell | ( | const Full_cell_handle & | c | ) | const |
Tests whether c is a full cell of the triangulation.
| bool TriangulationDataStructure::is_valid | ( | bool | verbose = false | ) | const |
Partially checks whether tds is indeed a triangulation.
It must at least
tds by calling their respective is_valid method. current_dimension()+1). tds.current_dimension() vertices with each of its neighbor. When verbose is set to true, messages are printed to give a precise indication on the kind of invalidity encountered.
Returns true if all the tests pass, false if any test fails. See the documentation for the models of this concept to see the additionnal (if any) validity checks that they implement.
| bool TriangulationDataStructure::is_vertex | ( | const Vertex_handle & | v | ) | const |
Tests whether v is a vertex of the triangulation.
| int TriangulationDataStructure::maximal_dimension | ( | ) | const |
Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation tds.
| int TriangulationDataStructure::mirror_index | ( | Full_cell_handle | c, |
| int | i | ||
| ) | const |
Returns the index of c as a neighbor of its i-th neighbor.
tds.current_dimension()and c!=Full_cell_handle().
| 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.
tds.current_dimension()and c!=Full_cell_handle().
| 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.
tds.current_dimension()and c != Full_cell_handle()
| 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.
| 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.
| size_type TriangulationDataStructure::number_of_full_cells | ( | ) | const |
Returns the number of full cells in the triangulation.
| size_type TriangulationDataStructure::number_of_vertices | ( | ) | const |
Returns the number of vertices in the triangulation.
| std::ostream& TriangulationDataStructure::operator<< | ( | std::ostream & | os, |
| const TriangulationDataStructure & | tds | ||
| ) |
Writes tds into the output stream os
| std::istream& TriangulationDataStructure::operator>> | ( | std::istream & | is, |
| TriangulationDataStructure & | tds | ||
| ) |
Reads a combinatorial triangulation from is and assigns it to tds.
tds.maximal_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 loose vertex star, full cells containing star and v loose vertex v (see Figure Figure 40.5).
star or v. Edge star-v exists in the triangulation and current_dimension()!=2. | void TriangulationDataStructure::set_current_dimension | ( | int | d | ) |
Forces the current dimension of the complex to d.
maximal_dimension(). | void TriangulationDataStructure::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.
Sets the neighbor opposite to vertex j of Full_cell cj to ci.
| OutputIterator TriangulationDataStructure::star | ( | const Face & | f, |
| OutputIterator | out | ||
| ) | const |
Insert in out all the full cells that share at least one vertex with the Face f.
Returns the output iterator.
f.full_cell()!=Full_cell_handle(). | 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.
tds.current_dimension() and c!=Full_cell_handle(). | Vertex_iterator TriangulationDataStructure::vertices_begin | ( | ) |
The first vertex of tds.
User has no control on the order.
| Vertex_iterator TriangulationDataStructure::vertices_end | ( | ) |
The beyond vertex of tds.
1.8.5