\( \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.4 - High-dimension Triangulation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Delaunay_triangulation< DelaunayTriangulationTraits_, TriangulationDataStructure_ > Class Template Reference
Triangulations

#include <CGAL/Delaunay_triangulation.h>

Inherits from

CGAL::Triangulation< DelaunayTriangulationTraits_, TriangulationDataStructure_ >.

Definition

The class Delaunay_triangulation is used to maintain the full cells and vertices of a Delaunay triangulation in \( \mathcal R^D\).

It permits point insertion and removal. The dimension \( D\) should be kept reasonably small, see the performance section in the user manual for what reasonable means.

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.

TriangulationDataStructure_ is the class used to store the underlying triangulation data structure. TriangulationDataStructure_ must be a model of the concept TriangulationDataStructure. 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. In both cases, TriangulationDataStructure_ defaults to Triangulation_data_structure<DelaunayTriangulationTraits_::Dimension, Triangulation_vertex<DelaunayTriangulationTraits_>, Triangulation_full_cell<DelaunayTriangulationTraits_> >.

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.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 points or the vertices (through their Vertex_handle) 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. More...
 
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). More...
 
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...
 

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<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,
Vertex_handle  hint 
)

Same as above but uses a vertex as starting place for the search.

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_ >
bool CGAL::Delaunay_triangulation< DelaunayTriangulationTraits_, TriangulationDataStructure_ >::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 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 points or the vertices (through their Vertex_handle) in the range [start, end).

ForwardIterator::value_type must be Vertex_handle.