CGAL 5.6  2D Triangulations

#include <CGAL/Constrained_triangulation_plus_2.h>
Tr.
The class Constrained_triangulation_plus_2<Tr>
provides a constrained triangulation with an additional data structure 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. The intersection tag of the base class determines whether intersecting input constraints are supported 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.
The data structure maintains for each input constraint the sequence of vertices on this constraint. Note that there is not a onetoone correspondence between an input constraint and the sequence of vertices. These vertices are either vertices of the input constraint or intersection points. Also consecutive identical points in the input constraint result in a single vertex in the sequence of vertices on this constraint. In case of an input constraint being degenerate to a point, this point is inserted but there will not be a zero length constraint.
Two consecutive vertices of a constraint form a subconstraint. A subconstraint is a pair of vertex handles and corresponds to a constrained edge of the triangulation, which is a pair of a face handle and an index.
The triangulation also enables the retrieval of the set of subconstraints of the triangulation (not ordered along constraints). It further enables the retrieval of the set of input constraints that induce a subconstraint. As it is straightforward to obtain a subconstraint from a constrained edge e
, one can obtain the input constraints which induce e
.
Tr  must be either a CGAL::Constrained_triangulation_2 or a CGAL::Constrained_Delaunay_triangulation_2 
Classes  
class  Context 
A context enables the access to the vertices of a constraint that pass through a subconstraint. More...  
Related Functions  
(Note that these are not member functions.)  
template<typename Tr >  
std::ostream &  operator<< (std::ostream &os, const Constrained_triangulation_plus_2< Tr > &ctp) 
Writes the triangulation as for Tr , then writes one constraint per line, starting with the number of vertices and the indices of the vertices of the constraint.  
template<typename Tr >  
std::istream &  operator>> (std::istream &is, Constrained_triangulation_plus_2< Tr > &ctp) 
Reads a triangulation from stream is and assigns it to the triangulation.  
Types  
typedef Tr  Triangulation 
The triangulation base class.  
typedef Tr::Intersection_tag  Intersection_tag 
The intersection tag as defined in Tr .  
typedef unspecified_type  Constraint_id 
The identifier of a polyline constraint. More...  
typedef unspecified_type  Constraint_iterator 
An iterator to visit all the input constraints. More...  
typedef Iterator_range< Constraint_iterator >  Constraints 
A range type for iterating over all constraints.  
typedef std::pair< Vertex_handle, Vertex_handle >  Subconstraint 
A subconstraint is a pair of vertices that correspond to an Edge .  
typedef unspecified_type  Subconstraint_iterator 
An iterator to visit all the subconstraints of the triangulation. More...  
typedef Iterator_range< Subconstraint_iterator >  Subconstraints 
A range type for iterating over all subconstraints.  
typedef unspecified_type  Vertices_in_constraint_iterator 
An iterator on the vertices of the chain of subconstraints representing a constraint. More...  
typedef unspecified_type  Vertices_in_constraint 
A range type for iterating over the vertices of the constraint.  
typedef unspecified_type  Context_iterator 
An iterator on constraints enclosing a given subconstraint. More...  
typedef Iterator_range< Context_iterator >  Contexts 
range type for iterating over contexts.  
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.  
template<class ConstraintIterator >  
Constrained_triangulation_plus_2 (ConstraintIterator first, ConstraintIterator 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 PointIterator >  
size_type  insert (PointIterator first, PointIterator last) 
inserts the points in the range [first,last) . More...  
Constraint_id  insert_constraint (Point a, Point b) 
inserts the constraint segment ab in the triangulation. More...  
void  push_back (const std::pair< Point, Point > &c) 
inserts the constraint c in the triangulation. More...  
Constraint_id  insert_constraint (Vertex_handle va, Vertex_handle vb) 
inserts a constraint whose endpoints are the vertices pointed by va and vb in the triangulation. More...  
template<class PointIterator >  
Constraint_id  insert_constraint (PointIterator first, PointIterator last, bool close=false) 
inserts a polyline defined by the points in the range [first,last) and returns the constraint id. More...  
template<class ConstraintIterator >  
std::size_t  insert_constraints (ConstraintIterator first, ConstraintIterator last) 
inserts the constraints in the range [first,last) . More...  
template<class PointIterator , class IndicesIterator >  
std::size_t  insert_constraints (PointIterator points_first, PointIterator points_last, IndicesIterator indices_first, IndicesIterator indices_last) 
Same as above except that each constraint is given as a pair of indices of the points in the range [points_first, points_last). More...  
void  split_subconstraint_graph_into_constraints (const std::function< bool(Vertex_handle)> &is_terminal) 
splits into constraints the graph of subconstraints. More...  
void  remove_constraint (Constraint_id cid) 
removes the constraint cid , without removing the points from the triangulation.  
Access  
Constraint_iterator  constraints_begin () const 
returns a Constraint_iterator that points at the first constraint of the triangulation.  
Constraint_iterator  constraints_end () const 
returns the pasttheend iterator of the constraints of the triangulation.  
Constraints  constraints () const 
returns a range of constraints.  
Subconstraint_iterator  subconstraints_begin () const 
returns a Subconstraint_iterator pointing at the first subconstraint of the triangulation.  
Subconstraint_iterator  subconstraints_end () const 
returns the pasttheend iterator of the subconstraints of the triangulation.  
Subconstraints  subconstraints () const 
returns a range of subconstraints.  
int  number_of_enclosing_constraints (Vertex_handle va, Vertex_handle vb) const 
returns the number of constraints enclosing the subconstraint (va,vb) . More...  
Context  context (Vertex_handle va, Vertex_handle vb) const 
returns the Context relative to one of the constraints enclosing the subconstraint (va,vb) . More...  
Context_iterator  contexts_begin (Vertex_handle va, Vertex_handle vb) const 
returns an iterator pointing at the first Context of the sequence of contexts corresponding to the constraints enclosing the subconstraint (va,vb) . More...  
Context_iterator  contexts_end (Vertex_handle va, Vertex_handle vb) const 
returns an iterator past the end Context of the sequence of contexts corresponding to the constraints enclosing the subconstraint (va,vb) . More...  
Contexts  contexts (Vertex_handle va, Vertex_handle vb) const 
returns a range of contexts.  
Vertices_in_constraint_iterator  vertices_in_constraint_begin (Constraint_id cid) const 
returns an iterator on the first vertex on the constraint cid .  
Vertices_in_constraint_iterator  vertices_in_constraint_end (Constraint_id cid) const 
returns an iterator past the last vertex on the constraint cid .  
Vertices_in_constraint  vertices_in_constraint (Constraint_id cid) const 
returns a range of the vertices on the constraint cid .  
Polyline Simplification  
Advanced
The polyline simplification algorithm described in Chapter Chapter_2D_Polyline_simplification operates on polyline constraints. The algorithm removes in each simplification step a vertex of a constraint and at the same time from the triangulation. The class It enables the simplification algorithm to compute the error introduced by each simplification step: it is the distance of the current sequence (vertices) to the original sequence (points). Those stored points which do not correspond to a vertex can be removed afterward either for a single constraint or for all constraints. The simplification algorithm uses the following types and functions.  
typedef unspecified_type  Points_in_constraint_iterator 
This is an advanced type. More...  
Points_in_constraint_iterator  points_in_constraint_begin (Constraint_id cid) const 
This is an advanced function. More...  
Points_in_constraint_iterator  points_in_constraint_end (Constraint_id cid) const 
This is an advanced function. More...  
void  simplify (Vertices_in_constraint_iterator vicq) 
This is an advanced function. More...  
size_type  remove_points_without_corresponding_vertex (Constraint_id cid) 
This is an advanced function. More...  
void  remove_points_without_corresponding_vertex () 
This is an advanced function. More...  
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Constraint_id 
The identifier of a polyline constraint.
The class is model of Assignable
, CopyConstructible
, DefaultConstructible
, LessThanComparable
and EqualityComparable
.
A default constructed Constraint_id
is a singular value that can not be the ID of a constraint.
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Constraint_iterator 
An iterator to visit all the input constraints.
The order of visit is undefined. The value type of this iterator is Constraint_id
.
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Context_iterator 
An iterator on constraints enclosing a given subconstraint.
The value type of this iterator is Context
.
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Points_in_constraint_iterator 
This is an advanced type.
An iterator on the points of the original constraint before simplification steps are applied. The value type of this iterator is Point
. A Vertices_in_constraint_iterator
can be converted into a Points_in_constraint_iterator
, but not the other way around.
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Subconstraint_iterator 
An iterator to visit all the subconstraints of the triangulation.
The order of visit is undefined. The value type of this iterator is std::pair<Subconstraint,std::list<Context>*>
corresponding to the vertices of the subconstraint.
typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Vertices_in_constraint_iterator 
An iterator on the vertices of the chain of subconstraints representing a constraint.
The value type of this iterator is Vertex_handle
.
CGAL::Constrained_triangulation_plus_2< Tr >::Constrained_triangulation_plus_2  (  ConstraintIterator  first, 
ConstraintIterator  last,  
const Geom_traits &  gt = Geom_traits() 

) 
Introduces a constrained triangulation from the constraints in the range [first,last)
.
ConstraintIterator  must be an InputIterator with the value type std::pair<Point,Point> or Segment . 
Context CGAL::Constrained_triangulation_plus_2< Tr >::context  (  Vertex_handle  va, 
Vertex_handle  vb  
)  const 
returns the Context
relative to one of the constraints enclosing the subconstraint (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  
)  const 
returns an iterator pointing at the first Context
of the sequence of contexts corresponding to the constraints enclosing the subconstraint (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  
)  const 
returns an iterator past the end Context
of the sequence of contexts corresponding to the constraints enclosing the subconstraint (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  (  PointIterator  first, 
PointIterator  last  
) 
inserts the points in the range [first,last)
.
Returns the number of inserted points.
PointIterator  must be an InputIterator with the value type Point . 
Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint  (  Point  a, 
Point  b  
) 
inserts the constraint segment ab
in the triangulation.
If the two points are equal the point is inserted but no constraint, and a default constructed Constraint_id
is returned.
Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint  (  Vertex_handle  va, 
Vertex_handle  vb  
) 
inserts a constraint whose endpoints are the vertices pointed by va
and vb
in the triangulation.
If the two vertex handles are equal no constraint is inserted, and a default constructed Constraint_id
is returned.
Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint  (  PointIterator  first, 
PointIterator  last,  
bool  close = false 

) 
inserts a polyline defined by the points in the range [first,last)
and returns the constraint id.
The polyline is considered as a closed curve if the first and last point are equal or if close == true
. This enables for example passing the vertex range of a Polygon_2
. When traversing the vertices of a closed polyline constraint with a Vertices_in_constraint_iterator
the first and last vertex are the same. In case the range is empty a default constructed Constraint_id
is returned. In case the range contains only one point or all points are equal the point is inserted but no constraint, and a default constructed Constraint_id
is returned.
PointIterator  must be an InputIterator with the value type Point . 
std::size_t CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraints  (  ConstraintIterator  first, 
ConstraintIterator  last  
) 
inserts the constraints in the range [first,last)
.
Note that this function is not guaranteed to insert the constraints following the order of ConstraintIterator
, as spatial_sort()
is used to improve efficiency. More precisely, all endpoints are inserted prior to the segments and according to the order provided by the spatial sort. Once endpoints have been inserted, the segments are inserted in the order of the input iterator, using the vertex handles of its endpoints. In case the constraints are degenerate the points are inserted, but no constraints.
ConstraintIterator  must be an InputIterator with the value type std::pair<Point,Point> or Segment . 
std::size_t CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraints  (  PointIterator  points_first, 
PointIterator  points_last,  
IndicesIterator  indices_first,  
IndicesIterator  indices_last  
) 
Same as above except that each constraint is given as a pair of indices of the points in the range [points_first, points_last).
The indices must go from 0 to std::distance(points_first, points_last)
PointIterator  is an InputIterator with the value type Point . 
IndicesIterator  is an InputIterator with std::pair<Int, Int> where Int is an integral type implicitly convertible to std::size_t 
int CGAL::Constrained_triangulation_plus_2< Tr >::number_of_enclosing_constraints  (  Vertex_handle  va, 
Vertex_handle  vb  
)  const 
returns the number of constraints enclosing the subconstraint (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 bidirectional mapping between constraints and subconstraints is also duplicated.
Points_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::points_in_constraint_begin  (  Constraint_id  cid  )  const 
This is an advanced function.
Returns an iterator to the first point on the constraint before any simplification step.
Points_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::points_in_constraint_end  (  Constraint_id  cid  )  const 
This is an advanced function.
Returns an iterator past the last point on the constraint before any simplification step.
void CGAL::Constrained_triangulation_plus_2< Tr >::push_back  (  const std::pair< Point, Point > &  c  ) 
inserts the constraint c
in the triangulation.
If the two points are equal the point is inserted but no constraint, and a default constructed Constraint_id
is returned.
size_type CGAL::Constrained_triangulation_plus_2< Tr >::remove_points_without_corresponding_vertex  (  Constraint_id  cid  ) 
This is an advanced function.
Removes the original points that correspond to vertices in the constraint cid
which have been removed by the simplify()
function.
void CGAL::Constrained_triangulation_plus_2< Tr >::remove_points_without_corresponding_vertex  (  ) 
This is an advanced function.
Removes all original points that correspond to vertices in the constraints which have been removed by the simplify()
function.
void CGAL::Constrained_triangulation_plus_2< Tr >::simplify  (  Vertices_in_constraint_iterator  vicq  ) 
This is an advanced function.
Removes the vertex at vicq
from the constraint and the triangulation. The point of that vertex remains stored in the sequence of original points of the constraint until remove_points_without_corresponding_vertex(Constraint_id)
or remove_points_without_corresponding_vertex()
is called.
The polyline simplification algorithm described in Chapter Chapter_2D_Polyline_simplification operates on polyline constraints and applies simplify()
to vertices in constraints based on a cost and stop function.
vicq
must neither be the first nor the last vertex on a constraint. vip
and vir
be defined as vip = std::prev(vicq)
and vir = std::next(vicr)
. *vicp>point()
and *vicr>point()
must not intersect any constraint. void CGAL::Constrained_triangulation_plus_2< Tr >::split_subconstraint_graph_into_constraints  (  const std::function< bool(Vertex_handle)> &  is_terminal  ) 
splits into constraints the graph of subconstraints.
Consider the graph g={V,E}
where V
is the set of vertices of the triangulation and E
is the set of all subconstraints of all constraints of the triangulation.
This function splits into polylines the graph g
at vertices of degree greater than 2 and at vertices for which is_terminal(v)==true
.
Each computed polyline is stored as a constraint of the triangulation.
is_terminal  An optional function returning true if the vertex v of degree 2 is a polyline endpoint and false otherwise. If omitted, a function always returning false will be used, that is no degree 2 vertex will be considered as a polyline endpoint. 
split_graph_into_polylines()
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.