As in the case of constrained triangulations, three different versions
of Delaunay constrained triangulations are offered
depending on whether the user wishes to handle
intersecting input constraints or not.
The desired version can be selected through the instantiation of the
third template parameter Itag which can be one of the
following :
CGAL::No_intersection_tag if intersections of
input constraints are disallowed,
CGAL::Exact_predicates_tag allows intersections between input
constraints
and is to be used when the traits
class
provides exact predicates but approximate constructions of the
intersection points.
CGAL::Exact_intersections_tag allows intersections between input
constraints
and is to be used in conjunction
with an exact arithmetic type.
The template parameters Tds has to be instantiate with a model of TriangulationDataStructure_2. The geometric traits of a constrained Delaunay triangulation is required to provide the side_of_oriented_circle test as the geometric traits of a Delaunay triangulation and the Traits parameter has to be instantiated with a model DelaunayTriangulationTraits_2. When intersection of input constraints are supported, the geometric traits class is required to provide additional function object types to compute the intersection of two segments. and has then to be also a model of the concept ConstrainedTriangulationTraits_2.
A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> derives from the class Constrained_triangulation_2<Traits,Tds>. Also, information about the status (constrained or not) of the edges of the triangulation is stored in the faces. Thus the nested Face type of a constrained triangulation offers additional functionalities to deal with this information. These additional functionalities induce additional requirements on the base face class plugged into the triangulation data structure of a constrained Delaunay triangulation. The base face of a constrained Delaunay triangulation has to be a model of the concept ConstrainedTriangulationFaceBase_2.
Cgal provides a default for the template parameters. If Gt is the geometric traits parameter, the default for ConstrainedTriangulationFaceBase_2 is the class CGAL::Constrained_triangulation_face_base_2<Gt> and the default for the triangulation data structure parameter is the class CGAL::Triangulation_data_structure_2< CGAL::Triangulation_vertex_base_2<Gt>, CGAL::Constrained_triangulation_face_base_2<Gt> >. The default intersection tag is CGAL::No_intersection_tag.
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Traits t = Traits());  
Introduces an empty constrained Delaunay triangulation cdt.
 
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Constrained_Delaunay_triangulation_2 cdt1);  
Copy constructor, all faces and vertices
are duplicated and the constrained status of edges
is copied.
 
template<class InputIterator>  
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( InputIterator first, InputIterator last, Traits t=Traits());  
A templated constructor which introduces and builds
a constrained triangulation with constrained edges in the range
[.first, last.).

Vertex_handle  cdt.insert ( Point p, Face_handle f = Face_handle())  
Inserts point p in the triangulation. If present f is used as an hint for the location of p.  
Vertex_handle  cdt.insert ( Point p, Locate_type& lt, Face_handle loc, int li)  
Same as above except that the location of the point p to be inserted is assumed to be given by (lt,loc,i).  
Vertex_handle  cdt.push_back ( Point p)  Equivalent to insert(p).  
template < class InputIterator >  
std::ptrdiff_t  cdt.insert ( InputIterator first, InputIterator last)  
Inserts the points in the range
[.first, last.).
Returns the number of inserted points.
 
void  cdt.insert_constraint ( Point a, Point b)  
Inserts segment ab as a constrained edge in the triangulation.  
void  cdt.push_back ( Constraint c)  Inserts constraints c as above.  
void  cdt.insert_constraint ( Vertex_handle va, Vertex_handle vb)  
Inserts the line segment whose endpoints are the vertices va and vb as a constrained edge e in the triangulation.  
void  cdt.remove ( Vertex_handle & v) 
Removes vertex v.
 
void  cdt.remove_incident_constraints ( Vertex_handle v)  
Make the edges incident to vertex v unconstrained edges.  
void  cdt.remove_constraint ( Face_handle f, int i)  
Edge (f,i) is no longer constrained. 
bool  cdt.is_valid ()  Checks if the triangulation is valid and if each constrained edge is consistently marked constrained in its two incident faces. 
bool  cdt.is_flipable ( Face_handle f, int i)  
Determines if edge (f,i) can be flipped. Returns true if edge (f,i) is not constrained and the circle circumscribing f contains the vertex of f>neighbor(i) opposite to edge (f,i).  
void  cdt.flip ( Face_handle& f, int i)  
Flip f and f>neighbor(i).  
void  cdt.propagating_flip ( List_edges & edges)  
Makes the triangulation constrained Delaunay by flipping edges. List edges contains an initial list of edges to be flipped. The returned triangulation is constrained Delaunay if the initial list contains at least all the edges of the input triangulation that failed to be constrained Delaunay. (An edge is said to be constrained Delaunay if it is either constrained or locally Delaunay.) 