CGAL 4.3 - 2D Triangulation
|
#include <CGAL/Constrained_triangulation_plus_2.h>
Tr.
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.
Tr | must be either a CGAL::Constrained_triangulation_2 or a CGAL::Constrained_Delaunay_triangulation_2 |
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 >=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 >=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 | |
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... | |
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.
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.
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
.
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)
.
InputIterator | must be an input iterator with the value type Constraint . |
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)
.
va
and vb
refer to the vertices of a constrained edge of the triangulation. 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)
.
va
and vb
refer to the vertices of a constrained edge of the triangulation. 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)
.
va
and vb
refer to the vertices of a constrained edge of the triangulation. 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)
.
Triangulation_2::locate()
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.
InputIterator | must be an input iterator with the value type Point . |
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)
.
va
and vb
refer to the vertices of a constrained edge of the triangulation. 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.
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
.
va
and vb
have to refer to the endpoint vertices of an input constraint. 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.
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)
.
va
and vb
refer to the vertices of an input constraint. 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)
.
va
and vb
refer to the vertices of an input constraints. 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.
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
.