#include <CGAL/Triangulation.h>

Definition

Modifications:: The class Triangulation is used to store and query the full cells and vertices of a triangulationin dimension \( d\)(see the User Manual for a definition of "triangulation").

A special vertex, named infinite vertex, is used to triangulate the outside of the convex hull of the points in so called infinite cells.

Parameters

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

TriangulationDataStructure_ is the class used to store the underlying triangulation data structure. TriangulationDataStructure_ must be a model of the concept TriangulationDataStructure. The class template 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<TriangulationTraits_::Dimension, Triangulation_vertex<TriangulationTraits_>, Triangulation_full_cell<TriangulationTraits_> >.

Input/Output

The information in the iostream is: the current dimension, the number of finite vertices, the non-combinatorial information about vertices (point, etc.), the number of full cells, the indices of the vertices of each full cell, plus the non-combinatorial information about each full cell, then the indices of the neighbors of each full cell, where the index corresponds to the preceding list of full cells.

See Also: Triangulation_data_structure<Dimensionality, TriangulationDSVertex, TriangulationDSFullCell>; Delaunay_triangulation<DelaunayTriangulationTraits, TriangulationDataStructure>

Examples:: triangulation.cpp.

Types
typedef TriangulationTraits	Geom_traits
	Type for the model of the `TriangulationTraits` concept. More...

typedef TriangulationTraits::Point_d	Point
	A point in Euclidean space. More...

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`). More...

typedef TriangulationDataStructure	Triangulation_ds
	The second template parameter. More...

typedef TriangulationDataStructure::Vertex	Vertex
	A model of the concept `TriangulationVertex`. More...

typedef TriangulationDataStructure::Full_cell	Full_cell
	A model of the concept `TriangulationFullCell`. More...

typedef TriangulationDataStructure::Facet	Facet
	The facet class. More...

typedef TriangulationDataStructure::Face	Face
	A model of the concept `TriangulationDSFace`. More...

Handles, Iterators and Circulators
The vertices and full cells of triangulations are accessed through handles, iterators and circulators. A handle is a model of the `Handle` concept, and supports the two dereference operators and `operator->`. A circulator is a model of the concept `Circulator`. Iterators and circulators are bidirectional and non-mutable. Iterators and circulators are convertible to the corresponding handles, thus the user can pass them directly as arguments to the functions.
enum	Locate_type { ON_VERTEX, IN_FACE, IN_FACET, IN_FULL_CELL, OUTSIDE_CONVEX_HULL, OUTSIDE_AFFINE_HULL }
	The enum `Locate_type` is defined by the class `Triangulation` to specify in what kind of face a point has been located in a triangulation. More...

typedef TriangulationDataStructure::Vertex_handle	Vertex_handle
	handle to a a vertex More...

typedef TriangulationDataStructure::Vertex_iterator	Vertex_iterator
	iterator over all vertices (including the infinite one) More...

typedef TriangulationDataStructure::Full_cell_iterator	Full_cell_iterator
	iterator over all full cells (including the infinite ones) More...

typedef TriangulationDataStructure::difference_type	difference_type
	Difference type (a signed integral type). More...

cgalModifBegin typedef unspecified_type	Finite_vertex_iterator
	iterator over finite vertices More...

cgalModifEnd typedef TriangulationDataStructure::Full_cell_handle	Full_cell_handle
	handle to a full cell More...

cgalModifBegin typedef unspecified_type	Finite_full_cell_iterator
	iterator over finite full cells More...

cgalModifEnd typedef TriangulationDataStructure::Facet_iterator	Facet_iterator
	iterator over all facets (including the infinite ones) More...

cgalModifBegin typedef unspecified_type	Finite_facet_iterator
	iterator over finite facets More...

cgalModifEnd typedef TriangulationDataStructure::size_type	size_type
	Size type (an unsigned integral type). More...

Creation
	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. More...

Access functions
const Triangulation_ds &	tds () const
	Advanced Returns a const reference to the underlying triangulation data structure. More...

Triangulation_ds &	tds ()
	Returns a non-const reference to the underlying triangulation data structure. More...

const Geom_traits &	geom_traits () const
	Returns a const reference to the geometric traits instance. More...

int	maximal_dimension () const
	Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation. More...

int	current_dimension () const
	Returns the dimension of the triangulation (as an embedded manifold). More...

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. More...

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). More...

Vertex_handle	infinite_vertex () const
	Returns a handle to the vertex at infinity. More...

Full_cell_handle	infinite_full_cell () const
	Returns a handle to some full cell incident to the vertex at infinity. More...

Non-constant-time access functions
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. More...

Tests for finite and infinite elements
bool	is_infinite (const Vertex_handle v) const
	Returns `true` if and only if the vertex `v` is the infinite vertex. More...

bool	is_infinite (const Full_cell_handle c) const
	Returns `true` if and only if `c` is incident to the infinite vertex. More...

bool	is_infinite (const Facet &ft) const
	Returns `true` if and only if facet `ft` is incident to the infinite vertex. More...

bool	is_infinite (const Face &f) const
	Returns `true` if and only if the face `f` is incident to the infinite vertex. More...

Faces and Facets
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 the vertex of the full cell `c=tr.full_cell(f)` which does not belong to `c`. More...

Triangulation traversal
Vertex_iterator	vertices_begin ()
	The first vertex of `tr`. More...

Vertex_iterator	vertices_end ()
	The beyond vertex of `tr`. More...

Finite_vertex_iterator	finite_vertices_begin ()
	The first finite vertex of `tr`. More...

Finite_vertex_iterator	finite_vertices_end ()
	The beyond finite vertex of `tr`. More...

Full_cell_iterator	full_cells_begin ()
	The first full cell of `tr`. More...

Full_cell_iterator	full_cells_end ()
	The beyond full cell of `tr`. More...

Finite_full_cell_iterator	finite_full_cells_begin ()
	The first finite full cell of `tr`. More...

Finite_full_cell_iterator	finite_full_cells_end ()
	The beyond finite full cell of `tr`. More...

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

Finite_facet_iterator	finite_facets_begin ()
	Iterator to the first finite facet of the triangulation. More...

Finite_facet_iterator	finite_facets_end ()
	Iterator to the beyond finite facet of the triangulation. More...

Point location
The class `Triangulation` provides methods to locate a query point with respect to 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. More...

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

Removal
Vertex_handle	collapse_face (const Point &p, const Face &f)
	Advanced Contracts the `Face f` to a single vertex at position `p`. More...

Point insertion
The class `Triangulation` provides functions to insert a given point in the triangulation:
template<typename ForwardIterator >
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. More...

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

template<typename ForwardIterator , typename OutputIterator >
Vertex_handle	insert_in_hole (const Point &p, ForwardIterator s, ForwardIterator e, const Facet &ft, OutputIterator out)
	Advanced The full cells in the range \( C=\)`[s, e)` are removed, thus forming a hole. More...

template<typename ForwardIterator >
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...

Validity check
bool	is_valid (bool verbose=false) const
	Partially checks whether `tr` is a triangulation. More...

bool	are_incident_full_cells_valid (Vertex_const_handle v, bool verbose=false) const
	Returns `true` if and only if all finite full cells incident to `v` have positive orientation. 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`. More...

Member Typedef Documentation

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::difference_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::difference_type

Difference type (a signed integral type).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Face CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Face

A model of the concept TriangulationDSFace.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Facet CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Facet

The facet class.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Full_cell CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Full_cell

A model of the concept TriangulationFullCell.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Full_cell_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Full_cell_iterator

iterator over all full cells (including the infinite ones)

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationTraits CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Geom_traits

Type for the model of the TriangulationTraits concept.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationTraits::Dimension CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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).

In the latter case, the dim parameter passed to the class's constructor is used.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationTraits::Point_d CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Point

A point in Euclidean space.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Triangulation_ds

The second template parameter.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Vertex CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Vertex

A model of the concept TriangulationVertex.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Vertex_handle

handle to a a vertex

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

typedef TriangulationDataStructure::Vertex_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Vertex_iterator

iterator over all vertices (including the infinite one)

Member Enumeration Documentation

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

enum CGAL::Triangulation::Locate_type

The enum Locate_type is defined by the class Triangulation to specify in what kind of face a point has been located in a triangulation.

Enumerator
ON_VERTEX
IN_FACE
IN_FACET
IN_FULL_CELL
OUTSIDE_CONVEX_HULL
OUTSIDE_AFFINE_HULL

Constructor & Destructor Documentation

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Triangulation	(	const int	dim,
		const Geom_traits &	gt = `Geom_traits()`
	)

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

See the description of the nested type Maximal_dimension above for an explanation of the use of the parameter dim. The triangulation stores a copy of the geometric traits gt.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Triangulation ( const Triangulation< TriangulationTraits_, TriangulationDataStructure_ > & t2 )

The copy constructor.

Member Function Documentation

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::are_incident_full_cells_valid	(	Vertex_const_handle	v,
		bool	verbose = `false`
	)		const

Returns true if and only if all finite full cells incident to v have positive orientation.

The verbose parameter is not used.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::collapse_face	(	const Point &	p,
		const Face &	f
	)

Advanced

Contracts the Face f to a single vertex at position p.

Returns a handle to that vertex.

Precondition: The boundary of the union of full cells incident to f must be a triangulation of a sphere of dimension tr.current_dimension()).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

int CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::current_dimension ( ) const

Returns the dimension of the triangulation (as an embedded manifold).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::empty ( ) const

Returns true if the triangulation has no finite vertex.

Returns false otherwise.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Facet_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::facets_begin ( )

Iterator to the first facet of the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Facet_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::facets_end ( )

Iterator to the beyond facet of the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_facet_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_facets_begin ( )

Iterator to the first finite facet of the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_facet_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_facets_end ( )

Iterator to the beyond finite facet of the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_full_cell_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_full_cells_begin ( )

The first finite full cell of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_full_cell_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_full_cells_end ( )

The beyond finite full cell of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_vertex_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_vertices_begin ( )

The first finite vertex of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Finite_vertex_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::finite_vertices_end ( )

The beyond finite vertex of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::full_cell ( const Facet & f ) const

Returns a full cell containing the facet f

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::full_cells_begin ( )

The first full cell of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::full_cells_end ( )

The beyond full cell of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

const Geom_traits& CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::geom_traits ( ) const

Returns a const reference to the geometric traits instance.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

int CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::infinite_full_cell ( ) const

Returns a handle to some full cell incident to the vertex at infinity.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::infinite_vertex ( ) const

Returns a handle to the vertex at infinity.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

template<typename ForwardIterator >

size_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert	(	ForwardIterator	s,
		ForwardIterator	e
	)

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

Returns the number of vertices actually inserted. (If several vertices share the same position in space, only the vertex that was actually inserted is counted.)

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert	(	const Point	p,
		Full_cell_handle	hint = `Full_cell_handle()`
	)

Inserts point p in the triangulation.

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 TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert	(	const Point	p,
		Vertex_handle	hint
	)

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

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

The action taken depends on the value of loc_type:

ON_VERTEX: The point of the pVertex described by f is set to p.
IN_FACE: The point p is inserted in the Face f.
IN_FACET: The point p is inserted in the Facet ft.
Anything else: The point p is inserted in the triangulation according to the value of loc_type, using the full cell c.

This method is used internally by the other insert() methods.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_in_face	(	const Point &	p,
		const Face &	f
	)

Advanced

Inserts point p in the triangulation.

Precondition: p must lie in the relative interior of f.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_in_facet	(	const Point &	p,
		const Facet &	ft
	)

Advanced

Inserts point p in the triangulation.

Precondition: p must lie in the relative interior of ft.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_in_full_cell	(	const Point &	p,
		Full_cell_handle	c
	)

Advanced

Inserts point p in the triangulation.

Precondition: p must lie in the interior of c.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

template<typename ForwardIterator , typename OutputIterator >

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_in_hole	(	const Point &	p,
		ForwardIterator	s,
		ForwardIterator	e,
		const Facet &	ft,
		OutputIterator	out
	)

Advanced

The full cells in the range \( C=\)[s, e) are removed, thus forming a hole.

A Vertex is inserted at position p and connected to the boundary of the hole in order to ``fill it''. A Vertex_handle to the new Vertex is returned. The facet ft must lie on the boundary of \( C\) and its defining full cell, tr.full_cell(ft) must lie inside \( C\). Handles to the newly created full cells are output in the out output iterator.

Precondition: \(C\) must be a (geometric) ball, must contain p in its interior and not contain any vertex all of whose incident full cells are in \(C\) . (This implies that t.current_dimension() \( \geq 2\) if \(|C|>1\) .) The boundary of \(C\) must be a triangulation of the sphere \( \mathcal S ^d-1\).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

template<typename ForwardIterator >

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_outside_affine_hull ( const Point & )

Advanced

Inserts point p in the triangulation.

Precondition: p must lie outside the affine hull of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::insert_outside_convex_hull	(	const Point &	,
		Full_cell_handle	c
	)

Advanced

Inserts point p in the triangulation.

Precondition: p must lie outside the convex hull of tr. The half-space defined by the infinite full cell c must contain p.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::is_infinite ( const Vertex_handle v ) const

Returns true if and only if the vertex v is the infinite vertex.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::is_infinite ( const Full_cell_handle c ) const

Returns true if and only if c is incident to the infinite vertex.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::is_infinite ( const Facet & ft ) const

Returns true if and only if facet ft is incident to the infinite vertex.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::is_infinite ( const Face & f ) const

Returns true if and only if the face f is incident to the infinite vertex.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

bool CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::is_valid ( bool verbose = false ) const

Partially checks whether tr is a triangulation.

This function returns true if the combinatorial triangulation data structure's is_valid() test returns true and if some geometric tests are passed with success: It is checked that the orientation of each finite full cell is positive and that the orientation of each infinite full cell is consistent with their finite adjacent full cells. The verbose parameter is not used.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

If the query point lies outside the affine hull of the points (which can happen when tr.current_dimension() < tr.maximal_dimension()) or if there is no finite vertex yet in the triangulation, then locate returns a default constructed Full_cell_handle().

If the point query lies in the interior of a bounded (finite) full cell of tr, the latter full cell is returned.

If query lies on the boundary of some finite full cells, one of the cells is returned.

Let \( d=\)tr.current_dimension(). If the point query lies outside the convex hull of the points, an infinite full cell with vertices \( \{ p_1, p_2, \ldots, p_d, \infty\}\) is returned such that the full cell \( (p_1, p_2, \ldots, p_d, query)\) is positively oriented (the rest of the triangulation lies on the other side of facet \( (p_1, p_2, \ldots, p_d)\)).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::locate	(	const Point &	query,
		Vertex_handle	hint
	)		const

Same as above but hint is a vertex and not a full cell.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

If the query point lies outside the affine hull of the points (which can happen when tr.current_dimension() < tr.maximal_dimension()) or if there is no finite vertex yet in the triangulation, then loc_type is set to OUTSIDE_AFFINE_HULL, and locate returns Full_cell_handle(). If the query point lies inside the affine hull of the points, the function finds the \( k\)-face that contains query in its relative interior (if the \( k\)-face is finite, it is unique) and the result is returned as follows:

\( k=0\): loc_type is set to ON_VERTEX, f is set to the vertex v the query lies on and a full cell having v as a vertex is returned.
\( 0<k<\)c.current_dimension()-1: loc_type is set to IN_FACE, f is set to the unique finite face containing the query point. A full cell having f on its boundary is returned.
\( k=\)c.current_dimension()-1: loc_type is set to IN_FACET, ft is set to one of the two representation of the finite facet containing the query point. The full cell of ft is returned.
\( k=\)c.current_dimension(): If the query point lies outside the convex hull of the points in the triangulation, then loc_type is set to OUTSIDE_CONVEX_HULL and a full cell is returned as in the locate method above. If the query point lies inside the convex hull of the points in the triangulation, then loc_type is set to IN_FULL_CELL and the unique full cell containing the query point is returned.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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.

The parameter hint is ignored if it is a default constructed Vertex_handle().

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

int CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::maximal_dimension ( ) const

Returns the maximal dimension of the full dimensional cells that can be stored in the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

size_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::number_of_finite_full_cells ( ) const

Returns the number of full cells of maximal dimension that are not incident to the vertex at infinity.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

size_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::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).

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

size_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::number_of_vertices ( ) const

Returns the number of finite vertices in the triangulation.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

std::ostream& CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::operator<<	(	std::ostream &	os,
		const Triangulation< TriangulationTraits_, TriangulationDataStructure_ > &	t
	)

Writes the triangulation t into os.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

std::istream& CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::operator>>	(	std::istream &	is,
		Triangulation< TriangulationTraits_, TriangulationDataStructure_ > &	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.

Assigns the resulting triangulation to t.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

const Triangulation_ds& CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::tds ( ) const

Advanced

Returns a const reference to the underlying triangulation data structure.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Triangulation_ds& CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::tds ( )

Returns a non-const reference to the underlying triangulation data structure.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::vertices_begin ( )

The first vertex of tr.

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

Vertex_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::vertices_end ( )

The beyond vertex of tr.

Member Data Documentation

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifEnd typedef TriangulationDataStructure::Facet_iterator CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Facet_iterator

iterator over all facets (including the infinite ones)

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifBegin typedef unspecified_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Finite_facet_iterator

iterator over finite facets

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifBegin typedef unspecified_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Finite_full_cell_iterator

iterator over finite full cells

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifBegin typedef unspecified_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Finite_vertex_iterator

iterator over finite vertices

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifEnd typedef TriangulationDataStructure::Full_cell_handle CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::Full_cell_handle

handle to a full cell

template<typename TriangulationTraits_, typename TriangulationDataStructure_>

cgalModifEnd typedef TriangulationDataStructure::size_type CGAL::Triangulation< TriangulationTraits_, TriangulationDataStructure_ >::size_type

Size type (an unsigned integral type).

Definition

Parameters

Input/Output

Types

Handles, Iterators and Circulators

Creation

Access functions

Non-constant-time access functions

Tests for finite and infinite elements

Faces and Facets

Triangulation traversal

Point location

Removal

Point insertion

Validity check

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation