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 Face s 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).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 Face
s 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 | ) |
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
.