CGAL::Constrained_triangulation_plus_2<Tr>

The class Constrained_triangulation_plus_2<Tr> 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 subconstraints 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.

#include <CGAL/Constrained_triangulation_plus_2.h>

Inherits From

Tr

Types

typedef Tr Triangulation; the triangulation base class.
typedef Itag Intersection_tag; the intersection tag.s

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.


Constrained_triangulation_plus_2<Tr>::Subconstraint_iterator;
An iterator to visit all the subconstraints of the triangulation. The order of visit is arbitrary. The value type of this iterator is a pair std::pair<Vertex_handle, Vertex_handle> correponding to the vertices of the subconstraint.


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.

typedef Context; This type is intended to describe a constraint enclosing a subconstraint and the position of the subconstraint 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 subconstraint.

typedef Context_iterator; An iterator on constraints enclosing a given subconstraint. The value type of this iterator is Context.

Creation

Constrained_triangulation_plus_2<Tr> ctp ( Geom_traits gt=Geom_traits());
Introduces an empty triangulation.


Constrained_triangulation_plus_2<Tr> ctp ( Constrained_triangulation_plus_2 ct);
Copy constructor.


Constrained_triangulation_plus_2<Tr> ctp ( std::list<Constrained>& lc,
Geom_traits t = Geom_traits());
Introduces and builds a constrained triangulation from the list of constraints lc.


template<class InputIterator>
Constrained_triangulation_plus_2<Tr> ctp ( InputIterator first,
InputIterator last,
Geom_traits gt= Geom_traits());
Introduces and builds a constrained triangulation from the constraints in the range [.first, last.).
Precondition: The value_type of first and last is Constraint.

void ~ ctp () Destructor. All vertices and faces are deleted. The constraint hierarchy is deleted.

Assignment

Constrained_triangulation_plus_2
ctp = Constrained_triangulation_plus_2 tr
Assignment. All the vertices and faces are duplicated. The constraint hierarchy is also duplicated.

void ctp.swap ( Constrained_triangulation_plus_2 tr)
The triangulations tr and ctp are swapped. This operation should be preferred to ctp = tr or to t(tr) if tr is deleted after that.

Insertion and Removal

The class Constrained_triangulation_plus_2<Tr> overwrites the following insertion and removal member functions for points and constraints.

Vertex_handle
ctp.insert ( Point p,
Face_handle start = Face_handle())
Inserts point p as a vertex of the triangulation.

Vertex_handle
ctp.insert ( Point p,
Locate_type lt,
Face_handle loc,
int li)
inserts a point p whose location is assumed to be given by (lt,loc,li).

Vertex_handle ctp.push_back ( Point p)
Equivalent to insert(p).

template < class InputIterator >
int ctp.insert ( InputIterator first, InputIterator last)
Inserts the points in the range [.first, last.). Returns the number of inserted points.
Precondition: The value_type of first and last is Point.

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

void ctp.push_back ( Constraint c)
Inserts the constraint c.

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

Queries

Constraint_iterator
ctp.constraints_begin ()
Returns a Constraint_iterator pointing on the first constraint.
Constraint_iterator
ctp.constraints_end ()
Returns a Constraint_iterator pointing past the last constraint.
Subconstraint_iterator
ctp.subconstraints_begin ()
Returns a Subconstraint_iterator pointing on the first subconstraint.
Subconstraint_iterator
ctp.subconstraints_end ()
Returns a Subconstraint_iterator pointing past the last subconstraint.
int
ctp.number_of_enclosing_constraints ( Vertex_handle va,
Vertex_handle vb)
Returns the number of constraints enclosing the subconstraint (va,vb).
Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.
Context ctp.context ( Vertex_handle va, Vertex_handle vb)
Returns the Context relative to one of the constraint enclosing the subconstraint (va,vb).
Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.
Context_iterator
ctp.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 subconstraint(va,vb).
Precondition: va and vb refer to the vertices of a constrained edge of the triangulation.
Context_iterator ctp.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.
Vertices_in_constraint_iterator
ctp.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.
Vertices_in_constraint_iterator
ctp.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.

See Also

CGAL::Constrained_triangulation_2<Traits,Tds>
CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds>
ConstrainedTriangulationTraits_2
ConstrainedDelaunayTriangulationTraits_2