The Constrained Triangulation Class

A constrained triangulation is represented in the CGAL library as an object of the class CGAL_Constrained_triangulation_2<Gt,Tds> . As usual the template parameters Gt and Tds stand respectively for a geometric traits class and a triangulation data structure class. There is no additional requirements for the instantiations used for this classes, they have to fulfill the requirements of section  and  .

#include <CGAL/Constrained_triangulation_2.h>

Inherits From

Types

typedef pair<Point,Point>
	Constraint;

Creation

The creators of the class build the constrained triangulation from a list of constrained edges. Constrained edges are assumed to have no intersection other than endpoints. Any number of constrained edges are allowed to share the same end-point. Vertical constrained edges or constrained edges with null length are allowed.

CGAL_Constrained_triangulation_2<Gt,Tds> ct ( Traits t = Traits());
	Introduces an empty constrained triangulation ct.
CGAL_Constrained_triangulation_2<Gt,Tds> ct ( 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>
CGAL_Constrained_triangulation_2<Gt,Tds> ct ( 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.

Modifiers

Implementation

The constructors build the triangulation using a sweeping line algorithm. The complexity of this algorithm is $O(nlog\; n)$ if $n$ endpoints are present. The sweep structure is an STL map.

There is no need for a special implementation of the method \ccVar.is_valid() because the default function CGAL_Triangulation_2<Traits>::is_valid() call the Face class method Traits::Face::is_valid() which, in the case of a constrained triangulation, includes a test of the consistency of the information about constrained edges.