\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.6.1 - dD Triangulations
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure > Class Template Reference

#include <CGAL/Delaunay_triangulation.h>

Inherits from

CGAL::Triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >.

Definition

This class is used to maintain the Delaunay triangulation of a set of points in \( \mathbb{R}^D \).

It permits point insertion and removal. The dimension \( D\) can be specified at compile-time or run-time. It should be kept reasonably small, see the performance section in the user manual for what reasonable means.

In a Delaunay triangulation, each face has the so-called Delaunay or empty-ball property: there exists a circumscribing ball whose interior does not contain any vertex of the triangulation. A circumscribing ball of a simplex is a ball having all vertices of the simplex on its boundary.

Parameters

DelaunayTriangulationTraits is the geometric traits class that provides the geometric types and predicates needed by Delaunay triangulations. DelaunayTriangulationTraits must be a model of the concept DelaunayTriangulationTraits.

The parameter TriangulationDataStructure must be a model of the concept TriangulationDataStructure. This model is used to store the faces of the triangulation. The parameter TriangulationDataStructure defaults to Triangulation_data_structure whose template parameters are instantiated as follows:

The class template Delaunay_triangulation can be defined by specifying only the first parameter, or by using the tag CGAL::Default as the second parameter.

The class Delaunay_triangulation<DelaunayTriangulationTraits, TriangulationDataStructure> inherits all the types defined in the base class Triangulation<DelaunayTriangulationTraits, TriangulationDataStructure>. Additionally, it defines or overloads the following methods:

See Also
Triangulation_data_structure<Dimensionality, TriangulationDSVertex, TriangulationDSFullCell>
Examples:
delaunay_triangulation.cpp.

Creation

 Delaunay_triangulation (const int dim, const Geom_traits gt=Geom_traits())
 Instantiates a Delaunay triangulation with one vertex (the vertex at infinity). More...
 

Point removal

Full_cell_handle remove (Vertex_handle v)
 Remove the vertex v from the Delaunay triangulation. More...
 
template<typename ForwardIterator >
void remove (ForwardIterator start, ForwardIterator end)
 Remove the vertices pointed by the vertex handles in the range [start, end). More...
 

Point insertion

template<typename ForwardIterator >
size_type insert (ForwardIterator s, ForwardIterator e)
 Inserts the points found in range [s,e) in the Delaunay triangulation and ensures that the empty-ball property is preserved. More...
 
Vertex_handle insert (const Point &p, Full_cell_handle hint=Full_cell_handle())
 Inserts point p in the Delaunay triangulation and ensures that the empty-ball property is preserved. More...
 
Vertex_handle insert (const Point &p, Vertex_handle hint)
 Same as above but uses a vertex as starting place for the search.
 
Vertex_handle insert (const Point &p, const Locate_type lt, const Face &f, const Facet &ft, const Full_cell_handle c)
 
Advanced
Inserts the point p in the Delaunay triangulation and ensures that the empty-ball property is preserved. More...
 
Vertex_handle insert_outside_affine_hull (const Point &p)
 
Advanced
Inserts the point p in the Delaunay triangulation. More...
 
Vertex_handle insert_in_conflicting_cell (const Point &p, const Full_cell_handle c)
 
Advanced
Inserts the point p in the Delaunay triangulation. More...
 

Queries

bool is_in_conflict (const Point &p, Full_cell_const_handle c) const
 Returns true if and only if the point p is in (Delaunay) conflict with full cell c (i.e., the circumscribing ball of \( c\) contains \( p\) in its interior).
 
template<typename OutputIterator >
Facet compute_conflict_zone (const Point &p, const Full_cell_handle c, OutputIterator out) const
 
Advanced
Outputs handles to the full cells in confict with point p into the OutputIterator out. More...
 

Additional Inherited Members

- Public Types inherited from CGAL::Triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >
enum  Locate_type
 specifies which case occurs when locating a point in the triangulation.
 
typedef
TriangulationDataStructure::Vertex_handle 
Vertex_handle
 handle to a a vertex
 
typedef
TriangulationDataStructure::Vertex_const_handle 
Vertex_const_handle
 const handle to a a vertex
 
typedef
TriangulationDataStructure::Vertex_iterator 
Vertex_iterator
 iterator over all vertices (including the infinite one)
 
typedef
TriangulationDataStructure::Vertex_const_iterator 
Vertex_const_iterator
 const iterator over all vertices (including the infinite one)
 
typedef unspecified_type Finite_vertex_iterator
 iterator over finite vertices
 
typedef unspecified_type Finite_vertex_const_iterator
 const iterator over finite vertices
 
typedef
TriangulationDataStructure::Full_cell_handle 
Full_cell_handle
 handle to a full cell
 
typedef
TriangulationDataStructure::Full_cell_const_handle 
Full_cell_const_handle
 const handle to a full cell
 
typedef
TriangulationDataStructure::Full_cell_iterator 
Full_cell_iterator
 iterator over all full cells (including the infinite ones)
 
typedef
TriangulationDataStructure::Full_cell_const_iterator 
Full_cell_const_iterator
 const iterator over all full cells (including the infinite ones)
 
typedef unspecified_type Finite_full_cell_iterator
 iterator over finite full cells
 
typedef unspecified_type Finite_full_cell_const_iterator
 const iterator over finite full cells
 
typedef
TriangulationDataStructure::Facet_iterator 
Facet_iterator
 iterator over all facets (including the infinite ones)
 
typedef unspecified_type Finite_facet_iterator
 iterator over finite facets
 
typedef
TriangulationDataStructure::size_type 
size_type
 Size type (an unsigned integral type).
 
typedef
TriangulationDataStructure::difference_type 
difference_type
 Difference type (a signed integral type).
 
typedef DelaunayTriangulationTraits Geom_traits
 Type for the model of the TriangulationTraits concept.
 
typedef
DelaunayTriangulationTraits::Point_d 
Point
 A point in Euclidean space.
 
typedef
DelaunayTriangulationTraits::Dimension 
Maximal_dimension
 This indicates whether the maximal dimension is static (i.e. if the type of Maximal_dimension is CGAL::Dimension_tag<int dim>) or dynamic (i.e. if the type of Maximal_dimension is CGAL::Dynamic_dimension_tag). More...
 
typedef TriangulationDataStructure Triangulation_ds
 The second template parameter: the triangulation data structure.
 
typedef
TriangulationDataStructure::Vertex 
Vertex
 A model of the concept TriangulationVertex.
 
typedef
TriangulationDataStructure::Full_cell 
Full_cell
 A model of the concept TriangulationFullCell.
 
typedef
TriangulationDataStructure::Facet 
Facet
 The facet class.
 
typedef
TriangulationDataStructure::Face 
Face
 A model of the concept TriangulationDSFace.
 
- Public Member Functions inherited from CGAL::Triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >
 Triangulation (const int dim, const Geom_traits &gt=Geom_traits())
 Instantiates a triangulation with one vertex (the vertex at infinity). More...
 
 Triangulation (const Triangulation &t2)
 The copy constructor.
 
const Triangulation_dstds () const
 
Advanced
Returns a const reference to the underlying triangulation data structure. More...
 
Triangulation_dstds ()
 Returns a non-const reference to the underlying triangulation data structure.
 
const Geom_traitsgeom_traits () const
 Returns a const reference to the geometric traits instance.
 
int maximal_dimension () const
 Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation.
 
int current_dimension () const
 Returns the dimension of the triangulation (as an embedded manifold).
 
bool empty () const
 Returns true if the triangulation has no finite vertex. More...
 
size_type number_of_vertices () const
 Returns the number of finite vertices in the triangulation.
 
size_type number_of_full_cells () const
 Returns the number of full cells of maximal dimension in the triangulation (full cells incident to the vertex at infinity are counted).
 
Vertex_handle infinite_vertex () const
 Returns a handle to the vertex at infinity.
 
Full_cell_handle infinite_full_cell () const
 Returns a handle to some full cell incident to the vertex at infinity.
 
size_type number_of_finite_full_cells () const
 Returns the number of full cells of maximal dimension that are not incident to the vertex at infinity.
 
bool is_infinite (const Vertex_handle v) const
 Returns true if and only if the vertex v is the infinite vertex.
 
bool is_infinite (const Full_cell_handle c) const
 Returns true if and only if c is incident to the infinite vertex.
 
bool is_infinite (const Facet &ft) const
 Returns true if and only if facet ft is incident to the infinite vertex.
 
bool is_infinite (const Face &f) const
 Returns true if and only if the face f is incident to the infinite vertex.
 
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 the vertex of the full cell c=tr.full_cell(f) which does not belong to c.
 
Vertex_iterator vertices_begin ()
 The first vertex of tr.
 
Vertex_iterator vertices_end ()
 The beyond vertex of tr.
 
Finite_vertex_iterator finite_vertices_begin ()
 The first finite vertex of tr.
 
Finite_vertex_iterator finite_vertices_end ()
 The beyond finite vertex of tr.
 
Full_cell_iterator full_cells_begin ()
 The first full cell of tr.
 
Full_cell_iterator full_cells_end ()
 The beyond full cell of tr.
 
Finite_full_cell_iterator finite_full_cells_begin ()
 The first finite full cell of tr.
 
Finite_full_cell_iterator finite_full_cells_end ()
 The beyond finite full cell of tr.
 
Facet_iterator facets_begin ()
 Iterator to the first facet of the triangulation.
 
Facet_iterator facets_end ()
 Iterator to the beyond facet of the triangulation.
 
Finite_facet_iterator finite_facets_begin ()
 Iterator to the first finite facet of the triangulation.
 
Finite_facet_iterator finite_facets_end ()
 Iterator to the beyond finite facet of the triangulation.
 
Full_cell_handle locate (const Point &query, Full_cell_handle hint=Full_cell_handle()) const
 The optional argument hint is used as a starting place for the search. More...
 
Full_cell_handle locate (const Point &query, Vertex_handle hint) const
 Same as above but hint is a vertex and not a full cell.
 
Full_cell_handle locate (const Point &query, Locate_type &loc_type, Face &f, Facet &ft, Full_cell_handle hint=Full_cell_handle()) const
 The optional argument hint is used as a starting place for the search. More...
 
Full_cell_handle locate (const Point &query, Locate_type &loc_type, Face &f, Vertex_handle hint) const
 Same as above but hint, the starting place for the search, is a vertex. More...
 
Vertex_handle collapse_face (const Point &p, const Face &f)
 
Advanced
Contracts the Face f to a single vertex at position p. More...
 
size_type insert (ForwardIterator s, ForwardIterator e)
 Inserts the points found in range [s,e) in the triangulation. More...
 
Vertex_handle insert (const Point p, Full_cell_handle hint=Full_cell_handle())
 Inserts point p in the triangulation. More...
 
Vertex_handle insert (const Point p, Vertex_handle hint)
 Same as above but uses a vertex hint as the starting place for the search.
 
Vertex_handle insert (const Point p, Locate_type loc_type, Face &f, Facet &ft, Full_cell_handle c)
 
Advanced
Inserts point p into the triangulation and returns a handle to the Vertex at that position. More...
 
Vertex_handle insert_in_hole (const Point &p, ForwardIterator s, ForwardIterator e, const Facet &ft, OutputIterator out)
 
Advanced
Removes the full cells in the range \( C=\)[s, e), inserts a vertex at position p and fills the hole by connecting each face of the boundary to p. More...
 
Vertex_handle insert_in_hole (const Point &p, ForwardIterator s, ForwardIterator e, const Facet &ft)
 
Advanced
Same as above, but the newly created full cells are not retrieved. More...
 
Vertex_handle insert_in_face (const Point &p, const Face &f)
 
Advanced
Inserts point p in the triangulation. More...
 
Vertex_handle insert_in_facet (const Point &p, const Facet &ft)
 
Advanced
Inserts point p in the triangulation. More...
 
Vertex_handle insert_in_full_cell (const Point &p, Full_cell_handle c)
 
Advanced
Inserts point p in the triangulation. More...
 
Vertex_handle insert_outside_convex_hull (const Point &, Full_cell_handle c)
 
Advanced
Inserts point p in the triangulation. More...
 
Vertex_handle insert_outside_affine_hull (const Point &)
 
Advanced
Inserts point p in the triangulation. More...
 
bool is_valid (bool verbose=false) const
 This is a function for debugging purpose. More...
 
bool are_incident_full_cells_valid (Vertex_const_handle v, bool verbose=false) const
 This is a function for debugging purpose. More...
 
std::istream & operator>> (std::istream &is, Triangulation &t)
 Reads the underlying combinatorial triangulation from is by calling the corresponding input operator of the triangulation data structure class (note that the infinite vertex is numbered 0), and the non-combinatorial information by calling the corresponding input operators of the vertex and the full cell classes (such as point coordinates), which are provided by overloading the stream operators of the vertex and full cell types. More...
 
std::ostream & operator<< (std::ostream &os, const Triangulation &t)
 Writes the triangulation t into os.
 

Constructor & Destructor Documentation

template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::Delaunay_triangulation ( const int  dim,
const Geom_traits  gt = Geom_traits() 
)

Instantiates a Delaunay triangulation with one vertex (the vertex at infinity).

See the description of the inherited nested type Triangulation::Maximal_dimension for an explanation of the use of the parameter dim. The complex stores a copy of the geometric traits gt.

Member Function Documentation

template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
template<typename OutputIterator >
Facet CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::compute_conflict_zone ( const Point p,
const Full_cell_handle  c,
OutputIterator  out 
) const

Advanced
Outputs handles to the full cells in confict with point p into the OutputIterator out.

The full cell c is used as a starting point for gathering the full cells in conflict with p. A facet (cc,i) on the boundary of the conflict zone with cc in conflict is returned.

Precondition
c is in conflict with p. dt.current_dimension() \( \geq2\).
template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
template<typename ForwardIterator >
size_type CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::insert ( ForwardIterator  s,
ForwardIterator  e 
)

Inserts the points found in range [s,e) in the Delaunay triangulation and ensures that the empty-ball property is preserved.

Returns the number of vertices actually inserted. (If more than one vertex share the same position in space, only one insertion is counted.)

Template Parameters
ForwardIteratormust be an input iterator with the value type Point.
template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
Vertex_handle CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::insert ( const Point p,
Full_cell_handle  hint = Full_cell_handle() 
)

Inserts point p in the Delaunay triangulation and ensures that the empty-ball property is preserved.

Returns a Vertex_handle to the vertex of the triangulation with position p. Prior to the actual insertion, p is located in the triangulation; hint is used as a starting place for locating p.

template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
Vertex_handle CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::insert ( const Point p,
const Locate_type  lt,
const Face f,
const Facet ft,
const Full_cell_handle  c 
)

Advanced
Inserts the point p in the Delaunay triangulation and ensures that the empty-ball property is preserved.

Returns a handle to the (possibly newly created) vertex at that position. The behavior depends on the value of lt:

OUTSIDE_AFFINE_HULL
Point p is inserted so as to increase the current dimension of the Delaunay triangulation. The method dt.insert_outside_affine_hull() is called.
ON_VERTEX
The position of the vertex v described by f is set to p. v is returned.
Anything else
The point p is inserted. the full cell c is assumed to be in conflict with p. (Roughly speaking, the method dt.insert_in_conflicting_cell() is called.)

The parameters lt, f, ft and c must be consistent with the localization of point p in the Delaunay triangulation e.g. by a call to c = locate(p, lt, f, ft).

template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
Vertex_handle CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::insert_in_conflicting_cell ( const Point p,
const Full_cell_handle  c 
)

Advanced
Inserts the point p in the Delaunay triangulation.

Returns a handle to the (possibly newly created) vertex at that position.

Precondition
The point p must be in conflict with the full cell c.
template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
Vertex_handle CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::insert_outside_affine_hull ( const Point p)

Advanced
Inserts the point p in the Delaunay triangulation.

Returns a handle to the (possibly newly created) vertex at that position.

Precondition
The point p must lie outside the affine hull of the Delaunay triangulation. This implies that dt.current_dimension() must be less that dt.maximal_dimension().
template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
Full_cell_handle CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::remove ( Vertex_handle  v)

Remove the vertex v from the Delaunay triangulation.

If the current dimension of the triangulation has not changed after the removal, then the returned full cell c geometrically contains the removed vertex v (c can be finite or infinite). Otherwise, the default-constructed Full_cell_handle is returned.

Precondition
v is a vertex of the triangulation, different from the infinite_vertex().
template<typename DelaunayTriangulationTraits , typename TriangulationDataStructure >
template<typename ForwardIterator >
void CGAL::Delaunay_triangulation< DelaunayTriangulationTraits, TriangulationDataStructure >::remove ( ForwardIterator  start,
ForwardIterator  end 
)

Remove the vertices pointed by the vertex handles in the range [start, end).

Template Parameters
ForwardIteratormust be an input iterator with the value type Vertex_handle.