#include <CGAL/Constrained_triangulation_plus_2.h>

Inherits from

Tr.

Definition

The class Constrained_triangulation_plus_2 implements a constrained triangulation with an additional data structure called the constraint hierarchy that keeps track of the input constraints and of their refinement in the triangulation.

The class Constrained_triangulation_plus_2<Tr> inherits from its template parameter Tr, which has to be instantiated by a constrained or constrained Delaunay triangulation.

According to its intersection tag, the base class will support intersecting input constraints or not. When intersections of input constraints are supported, the base class constructs a triangulation of the arrangement of the constraints, introducing new vertices at each proper intersection point and refining the input constraints into sub-constraints which are edges (more precisely constrained edges) of the triangulation. In this context, the constraint hierarchy keeps track of the input constraints and of their refinement in the triangulation. This data structure maintains for each input constraints the sequence of intersection vertices added on this constraint. The constraint hierarchy also allows the user to retrieve the set of constrained edges of the triangulation, and for each constrained edge, the set of input constraints that overlap it.

Template Parameters

Tr	must be either a CGAL::Constrained_triangulation_2 or a CGAL::Constrained_Delaunay_triangulation_2

See Also: CGAL::Constrained_triangulation_2<Traits,Tds>; CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds>; ConstrainedTriangulationTraits_2; ConstrainedDelaunayTriangulationTraits_2

Examples:: Triangulation_2/constrained_hierarchy_plus.cpp, and Triangulation_2/constrained_plus.cpp.

Types
typedef Tr	Triangulation
	The triangulation base class.

typedef Itag	Intersection_tag
	The intersection tag.

typedef unspecified_type	Constraint_iterator
	An iterator to visit all the input constraints. More...

typedef unspecified_type	Subconstraint_iterator
	An iterator to visit all the sub-constraints of the triangulation. More...

typedef unspecified_type	Vertices_in_constraint_iterator
	An iterator on the vertices of the chain of triangulation edges representing a constraint. More...

typedef	Context
	This type is intended to describe a constraint enclosing a sub-constraint and the position of the sub-constraint in this constraint. More...

typedef	Context_iterator
	An iterator on constraints enclosing a given sub-constraint. More...

Creation
	Constrained_triangulation_plus_2 (const Geom_traits &gt=Geom_traits())
	Introduces an empty triangulation.

	Constrained_triangulation_plus_2 (const Constrained_triangulation_plus_2 &ct)
	Copy constructor.

	Constrained_triangulation_plus_2 (std::list< Constraint > &lc, const Geom_traits &t=Geom_traits())
	Introduces a constrained triangulation from the list of constraints `lc`.

template<class InputIterator >
	Constrained_triangulation_plus_2 (InputIterator first, InputIterator last, const Geom_traits &gt=Geom_traits())
	Introduces a constrained triangulation from the constraints in the range `[first,last)`. More...

Assignment
Constrained_triangulation_plus_2	operator= (const Constrained_triangulation_plus_2 &tr)
	Assignment. More...

void	swap (Constrained_triangulation_plus_2 tr)
	The triangulations `tr` and this triangulation are swapped. More...

Insertion and Removal
The class `Constrained_triangulation_plus_2` overwrites the following insertion and removal member functions for points and constraints.
Vertex_handle	insert (const Point &p, Face_handle start=Face_handle())
	Inserts point `p` as a vertex of the triangulation.

Vertex_handle	insert (const Point &p, Locate_type lt, Face_handle loc, int li)
	Inserts point `p` in the triangulation at the location given by `(lt,loc,i)`. More...

Vertex_handle	push_back (const Point &p)
	Equivalent to `insert(p)`.

template<class InputIterator >
size_type	insert (InputIterator first, InputIterator last)
	Inserts the points in the range `[first,last)`. More...

void	insert_constraint (Point a, Point b)
	Inserts the constraint segment `ab` in the triangulation.

void	push_back (const Constraint &c)
	Inserts the constraint `c`.

void	insert_constraint (Vertex_handle va, Vertex_handle vb)
	Inserts a constraint whose endpoints are the vertices pointed by `va` and `vb` in the triangulation.

void	remove_constraint (Vertex_handle va, Vertex_handle vb)
	Removes the constraint joining the vertices pointed by `va` and `vb`. More...

Queries
Constraint_iterator	constraints_begin () const
	Returns a `Constraint_iterator` pointing on the first constraint.

Constraint_iterator	constraints_end () const
	Returns a `Constraint_iterator` pointing past the last constraint.

Subconstraint_iterator	subconstraints_begin () const
	Returns a `Subconstraint_iterator` pointing on the first sub-constraint.

Subconstraint_iterator	subconstraints_end () const
	Returns a `Subconstraint_iterator` pointing past the last sub-constraint.

int	number_of_enclosing_constraints (Vertex_handle va, Vertex_handle vb)
	Returns the number of constraints enclosing the sub-constraint `(va,vb)`. More...

Context	context (Vertex_handle va, Vertex_handle vb)
	Returns the `Context` relative to one of the constraints enclosing the sub-constraint `(va,vb)`. More...

Context_iterator	contexts_begin (Vertex_handle va, Vertex_handle vb)
	Returns an iterator pointing on the first `Context` of the sequence of `Contexts` corresponding to the constraints enclosing the sub-constraint`(va,vb)`. More...

Context_iterator	contexts_end (Vertex_handle va, Vertex_handle vb)
	Returns an iterator past the last `Context` of the sequence of `Contexts` corresponding to the constraints enclosing the `(va,vb)`. More...

Vertices_in_constraint_iterator	vertices_in_constraint_begin (Vertex_handle va, Vertex_handle vb)
	Returns an iterator on the first vertex on the constraint `(va,vb)`. More...

Vertices_in_constraint_iterator	vertices_in_constraint_end (Vertex_handle va, Vertex_handle vb)
	Returns an iterator past the last vertex on the constraint `(va,vb)`. More...

Member Typedef Documentation

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Constraint_iterator

An iterator to visit all the input constraints.

The order of visit is arbitrary. The value type of this iterator is a pair std::pair<Vertex_handle, Vertex_handle> corresponding to the endpoints of the constraint.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Subconstraint_iterator

An iterator to visit all the sub-constraints of the triangulation.

The order of visit is arbitrary. The value type of this iterator is a pair std::pair<Vertex_handle, Vertex_handle> corresponding to the vertices of the sub-constraint.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Vertices_in_constraint_iterator

An iterator on the vertices of the chain of triangulation edges representing a constraint.

The value type of this iterator is Vertex_handle.

Constructor & Destructor Documentation

template<typename Tr >

template<class InputIterator >

CGAL::Constrained_triangulation_plus_2< Tr >::Constrained_triangulation_plus_2	(	InputIterator	first,
		InputIterator	last,
		const Geom_traits &	gt = `Geom_traits()`
	)

Introduces a constrained triangulation from the constraints in the range [first,last).

Template Parameters

InputIterator must be an input iterator with the value type Constraint.

Member Function Documentation

template<typename Tr >

Context CGAL::Constrained_triangulation_plus_2< Tr >::context	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns the Context relative to one of the constraints enclosing the sub-constraint (va,vb).

Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Context_iterator CGAL::Constrained_triangulation_plus_2< Tr >::contexts_begin	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns an iterator pointing on the first Context of the sequence of Contexts corresponding to the constraints enclosing the sub-constraint(va,vb).

Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Context_iterator CGAL::Constrained_triangulation_plus_2< Tr >::contexts_end	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns an iterator past the last Context of the sequence of Contexts corresponding to the constraints enclosing the (va,vb).

Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Vertex_handle CGAL::Constrained_triangulation_plus_2< Tr >::insert	(	const Point &	p,
		Locate_type	lt,
		Face_handle	loc,
		int	li
	)

Inserts point p in the triangulation at the location given by (lt,loc,i).

See Also: Triangulation_2::locate()

template<typename Tr >

template<class InputIterator >

size_type CGAL::Constrained_triangulation_plus_2< Tr >::insert	(	InputIterator	first,
		InputIterator	last
	)

Inserts the points in the range [first,last).

Returns the number of inserted points.

Template Parameters

InputIterator must be an input iterator with the value type Point.

template<typename Tr >

int CGAL::Constrained_triangulation_plus_2< Tr >::number_of_enclosing_constraints	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns the number of constraints enclosing the sub-constraint (va,vb).

Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Constrained_triangulation_plus_2 CGAL::Constrained_triangulation_plus_2< Tr >::operator= ( const Constrained_triangulation_plus_2< Tr > & tr)

Assignment.

All the vertices and faces are duplicated. The constraint hierarchy is also duplicated.

template<typename Tr >

void CGAL::Constrained_triangulation_plus_2< Tr >::remove_constraint	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Removes the constraint joining the vertices pointed by va and vb.

Precondition: va and vb have to refer to the endpoint vertices of an input constraint.

template<typename Tr >

void CGAL::Constrained_triangulation_plus_2< Tr >::swap ( Constrained_triangulation_plus_2< Tr > tr)

The triangulations tr and this triangulation are swapped.

This operation should be preferred to the assignment or to the copy constructor if tr is deleted after that.

template<typename Tr >

Vertices_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::vertices_in_constraint_begin	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns an iterator on the first vertex on the constraint (va,vb).

Precondition: va and vb refer to the vertices of an input constraint.

template<typename Tr >

Vertices_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::vertices_in_constraint_end	(	Vertex_handle	va,
		Vertex_handle	vb
	)

Returns an iterator past the last vertex on the constraint (va,vb).

Precondition: va and vb refer to the vertices of an input constraints.

Member Data Documentation

template<typename Tr >

typedef CGAL::Constrained_triangulation_plus_2< Tr >::Context

This type is intended to describe a constraint enclosing a sub-constraint and the position of the sub-constraint in this constraint.

It provides three member functions vertices_begin(), vertices_end() and current() returning iterators of the type Vertices_in_constraint_iterator on the sequence of vertices of the enclosing constraint. These iterators point respectively on the first vertex of the enclosing constraint, past the last vertex and on the first vertex of the sub-constraint.

template<typename Tr >

typedef CGAL::Constrained_triangulation_plus_2< Tr >::Context_iterator

An iterator on constraints enclosing a given sub-constraint.

The value type of this iterator is Context.

Inherits from

Definition

Types

Creation

Assignment

Insertion and Removal

Queries

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation