The class is templated by a geometric traits class Gt and a triangulation data structure Tds. There are no special requirements for the triangulation data structure of a constrained Delaunay triangulations and the requirements for this class are those described in section . 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 requirements for this traits are described in section .

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2<Gt,Tds> derives from the class Constrained_triangulation_2<Gt,Tds>. Also, information about the status (constrained or not) of the edges of the triangulation has to be stored in the face class and the requirements for the base face class of a constrained Delaunay triangulation are identical to those described in section  for the face base class of a constrained triangulation.

#include <CGAL/Constrained_triangulation_2.h>

Inherits From

Types

Creation

Constrained_Delaunay_triangulation_2<Gt,Tds> cdt ( Traits t = Traits());
	Introduces an empty constrained Delaunay triangulation cdt.
Constrained_Delaunay_triangulation_2<Gt,Tds> cdt ( Constrained_Delaunay_triangulation_2 cdtbis);
	Copy constructor, all faces and vertices are duplicated and the constrained status of edges is copied. This last feature is not yet implemented.
Constrained_Delaunay_triangulation_2<Gt,Tds> cdt ( list<Constrained>& lc, Traits& t = Traits());
	Introduces a constrained triangulation, the constrained edges of which are the edges of the list lc.
template<class InputIterator>
Constrained_Delaunay_triangulation_2<Gt,Tds> 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$$.). Precondition: The value_type of first and last is Constraint.

Flips

bool	cdt.is_flipable ( Face_handle f, int i)
		Determines if edge (f,i) can be flipped. Returns true if 1. edge(f,i) is not constrained and 2. the circle circumscribing f does not contain the vertex of f->neighbor(i) not on edge(f,i).
void	cdt.flip ( Face_handle& f, int i)
		Flip f and f->neighbor(i). Precondition: f->is_constrained(i) == FALSE.
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 list edges contains all edges of the input triangulation that need to be flipped (plus possibly others).

Insertion and Removal

Vertex_handle	cdt.insert ( Point a)
		Inserts point a in the triangulation.
void	cdt.insert ( Point a, Point b)
		Inserts segment ab as a constrained edge in the triangulation.
void	cdt.insert ( Vertex_handle va, Vertex_handle vb)
		Inserts the line segment whose endpoints are the vertices va and vb as an edge e in the triangulation.
void	cdt.insert ( Vertex_handle va, Vertex_handle vb, Face_handle & fr, int & i)
		Same as the previous procedure. In addition, returns f and i such that e=(f,i) and f is the face lying to the right of the oriented edge (va,vb).
void	cdt.remove ( Vertex_handle & v)
		Removes vertex v.

Checking

bool

cdt.is_valid ()

Checks if the triangulation is valid and if each constrained edge is a constraint for its two incident faces.