CGAL 6.1.1 - dD Triangulations

Loading...
Searching...
No Matches
List of all members
CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ > Class Template Reference
Reference Manual » Triangulation Classes

`#include <CGAL/Regular_triangulation.h>`

## Inherits from

CGAL::Triangulation< Regular_triangulation_traits_adapter< RegularTriangulationTraits_ >, TriangulationDataStructure_ >.

## Definition

template<typename RegularTriangulationTraits_, typename TriangulationDataStructure_>
class CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >

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

The maximal 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.

Warning
  The removal of points is not supported yet.

Template Parameters

  RegularTriangulationTraits_ | is the geometric traits class that provides the geometric types and predicates needed by regular triangulations. `RegularTriangulationTraits_` must be a model of the concept `RegularTriangulationTraits`.
  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: `RegularTriangulationTraits_::Dimension` `Triangulation_vertex<CGAL::Regular_triangulation_traits_adapter<RegularTriangulationTraits_> >` `Triangulation_full_cell<CGAL::Regular_triangulation_traits_adapter<RegularTriangulationTraits_> >`.

`Regular_triangulation` can be defined by specifying only the first parameter, or by using the tag `CGAL::Default` as the second parameter.

See also
  `Delaunay_triangulation`
  `Triangulation_data_structure`
  `Regular_triangulation_traits_adapter`

Examples
  regular_triangulation.cpp.

## Types
typedef RegularTriangulationTraits_::Weighted_point_d | Weighted_point
| A point in Euclidean space with an associated weight.

## Creation
| Regular_triangulation (int dim, const Geom_traits &gt=Geom_traits())
| Instantiates a regular triangulation with one vertex (the vertex at infinity).

## Point Insertion
Vertex_handle | insert (const Weighted_point &p, Full_cell_handle hint=Full_cell_handle())
| Inserts weighted point `p` in the triangulation and returns the corresponding vertex.
Vertex_handle | insert (const Weighted_point &p, Vertex_handle hint)
| Same as above but uses a vertex as starting place for the search.
Vertex_handle | insert (const Weighted_point &p, Locate_type lt, const Face &f, const Facet &ft, Full_cell_handle c)
| Inserts weighted point `p` in the triangulation.
template<typename ForwardIterator >
std::ptrdiff_t | insert (ForwardIterator s, ForwardIterator e)
| Inserts the weighted points found in range `[s,e)` in the regular triangulation.
Vertex_handle | insert_if_in_star (const Weighted_point &p, Vertex_handle star_center, Full_cell_handle start=Full_cell_handle())
| inserts the weighted point `p` in the triangulation on the condition that the vertex `star_center` appears in the conflict zone of `p` (that is, `p` would appear in the star of `star_center` after the insertion).
Vertex_handle | insert_if_in_star (const Weighted_point &p, Vertex_handle star_center, Vertex_handle hint)
| Same as the above `insert_if_in_star()`, but uses a vertex as starting place for the search.
Vertex_handle | insert_if_in_star (const Weighted_point &p, Vertex_handle star_center, Locate_type lt, const Face &f, const Facet &ft, Full_cell_handle s)
| inserts the weighted point `p` in the triangulation.

## Queries
bool | is_in_conflict (const Weighted_point &p, Full_cell_const_handle c) const
| Returns `true` if and only if the point `p` is in conflict with full cell `c` (A weighted point `p` is said to be in conflict with a cell `c` if it has a negative power distance to the power sphere of `c`.)
template<typename OutputIterator >
Facet | compute_conflict_zone (const Weighted_point &p, Full_cell_handle c, OutputIterator out) const
| Outputs handles to the full cells in conflict with point `p` into the `OutputIterator out`.

## Access Functions
size_type | number_of_vertices () const
| Returns the number of finite vertices that are not hidden.
size_type | number_of_hidden_vertices () const
| Returns the number of hidden vertices.

## Additional Inherited Members
Public Types inherited from CGAL::Triangulation< Regular_triangulation_traits_adapter< RegularTriangulationTraits_ >, TriangulationDataStructure_ >
enum | Locate_type
| Used by `Triangulation` to specify 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 Regular_triangulation_traits_adapter< RegularTriangulationTraits_ > | Geom_traits
| Type for the model of the `TriangulationTraits_` concept.
typedef TriangulationTraits_::Point_d | Point
| A point in Euclidean space.
typedef TriangulationTraits_::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`).
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< Regular_triangulation_traits_adapter< RegularTriangulationTraits_ >, TriangulationDataStructure_ >
| Triangulation (int dim, const Geom_traits &gt=Geom_traits())
| Instantiates a triangulation with one vertex (the vertex at infinity).
| Triangulation (const Triangulation &t2)
| The copy constructor.
const Triangulation_ds & | tds () const
| Returns a const reference to the underlying triangulation data structure.
Triangulation_ds & | tds ()
| This is an advanced function.
const Geom_traits & | geom_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.
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 (Vertex_handle v) const
| Returns `true` if and only if the vertex `v` is the infinite vertex.
bool | is_infinite (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_const_handle hint=Full_cell_handle()) const
| The optional argument `hint` is used as a starting place for the search.
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.
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.
Vertex_handle | collapse_face (const Point &p, const Face &f)
| Contracts the `Face f` to a single vertex at position `p`.
size_type | insert (ForwardIterator s, ForwardIterator e)
| Inserts the points found in range `[s,e)` in the triangulation.
Vertex_handle | insert (const Point &p, Full_cell_handle hint=Full_cell_handle())
| Inserts point `p` in the triangulation.
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)
| Inserts point `p` into the triangulation and returns a handle to the `Vertex` at that position.
Vertex_handle | insert_in_hole (const Point &p, ForwardIterator s, ForwardIterator e, const Facet &ft, OutputIterator out)
| 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`.
Vertex_handle | insert_in_hole (const Point &p, ForwardIterator s, ForwardIterator e, const Facet &ft)
| Same as above, but the newly created full cells are not retrieved.
Vertex_handle | insert_in_face (const Point &p, const Face &f)
| Inserts point `p` in the triangulation.
Vertex_handle | insert_in_facet (const Point &p, const Facet &ft)
| Inserts point `p` in the triangulation.
Vertex_handle | insert_in_full_cell (const Point &p, Full_cell_handle c)
| Inserts point `p` in the triangulation.
Vertex_handle | insert_outside_convex_hull (const Point &, Full_cell_handle c)
| Inserts point `p` in the triangulation.
Vertex_handle | insert_outside_affine_hull (const Point &)
| Inserts point `p` in the triangulation.
bool | is_valid (bool verbose=false) const
| This is a function for debugging purpose.
bool | are_incident_full_cells_valid (Vertex_const_handle v, bool verbose=false) const
| This is a function for debugging purpose.
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.
std::ostream & | operator<< (std::ostream &os, const Triangulation &t)
| Writes the triangulation `t` into `os`.

## Constructor & Destructor Documentation

## ◆ Regular_triangulation()

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >

CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::Regular_triangulation | ( | int | dim,
|  | const Geom_traits & | gt = `Geom_traits()`
| ) |  |

Instantiates a regular 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 triangulation stores a copy of the geometric traits `gt`.

## Member Function Documentation

## ◆ compute_conflict_zone()

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >
template<typename OutputIterator >

Facet CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::compute_conflict_zone | ( | const Weighted_point & | p,
|  | Full_cell_handle | c,
|  | OutputIterator | out
| ) |  | const

Outputs handles to the full cells in conflict 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` and `rt`.`current_dimension()` \( \geq 1\).

## ◆ insert() [1/3]

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >

Vertex_handle CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::insert | ( | const Weighted_point & | p,
|  | Full_cell_handle | hint = `Full_cell_handle()`
| ) |  |

Inserts weighted point `p` in the triangulation and returns the corresponding vertex.

If this insertion creates a vertex, this vertex is returned.

If `p` coincides with an existing vertex and has a greater weight, then the existing weighted point becomes hidden and `p` replaces it as vertex of the triangulation.

If `p` coincides with an already existing vertex (both point and weights being equal), then this vertex is returned and the triangulation remains unchanged.

Otherwise if `p` does not appear as a vertex of the triangulation, then it is stored as a hidden point and this method returns the default constructed handle.

Prior to the actual insertion, `p` is located in the triangulation; `hint` is used as a starting place for locating `p`.

## ◆ insert() [2/3]

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >

Vertex_handle CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::insert | ( | const Weighted_point & | p,
|  | Locate_type | lt,
|  | const Face & | f,
|  | const Facet & | ft,
|  | Full_cell_handle | c
| ) |  |

Inserts weighted point `p` in the triangulation.

Similar to the above `insert()` function, but takes as additional parameter the return values of a previous location query. See description of `Triangulation::locate()`.

## ◆ insert() [3/3]

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >
template<typename ForwardIterator >

std::ptrdiff_t CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::insert | ( | ForwardIterator | s,
|  | ForwardIterator | e
| ) |  |

Inserts the weighted points found in range `[s,e)` in the regular triangulation.

Returns the difference between the number of vertices after and before the insertions (it may be negative due to hidden points). Note that this function is not guaranteed to insert the points following the order of `ForwardIterator` because `spatial_sort()` is used to improve efficiency.

Template Parameters

  ForwardIterator | must be an input iterator with the value type `Weighted_point`.

## ◆ insert_if_in_star() [1/2]

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >

Vertex_handle CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::insert_if_in_star | ( | const Weighted_point & | p,
|  | Vertex_handle | star_center,
|  | Full_cell_handle | start = `Full_cell_handle()`
| ) |  |

inserts the weighted point `p` in the triangulation on the condition that the vertex `star_center` appears in the conflict zone of `p` (that is, `p` would appear in the star of `star_center` after the insertion).

If the insertion of `p` creates a new vertex, this vertex is returned. Otherwise, a default constructed handle is returned.

If the dimension of the triangulation is `0` and if `p` coincides with an existing vertex and has a greater weight, then `p` replaces it as vertex of the triangulation and this vertex is returned.

If `p` coincides with an already existing vertex, with both point and weights being equal, then this vertex is returned and the triangulation remains unchanged.

By convention, if the insertion of `p` would increase the dimension of the triangulation, it is inserted.

Prior to the actual insertion, `p` is located in the triangulation; `start` is used as a starting place for locating `p`.

See also
  `Regular_triangulation::compute_conflict_zone()`

## ◆ insert_if_in_star() [2/2]

template<typename RegularTriangulationTraits_ , typename TriangulationDataStructure_ >

Vertex_handle CGAL::Regular_triangulation< RegularTriangulationTraits_, TriangulationDataStructure_ >::insert_if_in_star | ( | const Weighted_point & | p,
|  | Vertex_handle | star_center,
|  | Locate_type | lt,
|  | const Face & | f,
|  | const Facet & | ft,
|  | Full_cell_handle | s
| ) |  |

inserts the weighted point `p` in the triangulation.

This function is similar to the above `insert_if_in_star()` function, but takes as additional parameters the return values of the location query of `p`.

See also
  `Triangulation::locate()`.