The Constrained Triangulation Class

#include <CGAL/Constrained_triangulation_2.h>

Inherits From

Triangulation_2<Gt,Tds>

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 endpoint. Vertical constrained edges or constrained edges with null length are allowed.

Constrained_triangulation_2<Gt,Tds> ct ( Traits t = Traits());
	Introduces an empty constrained triangulation ct.
Constrained_triangulation_2<Gt,Tds> ct ( Constrained_triangulation_2 ctbis);
	Copy constructor, all faces and vertices are duplicated and the constrained status of edges is copied. This last feature is not yet implemented.
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>
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.

Insertion and removal

Vertex_handle	ct.insert ( Point a)
		Inserts point a and restore the status (constrained or not) of all the touched edges.
void	ct.insert ( Point a, Point b)
		Inserts points a and b, and inserts segment ab as a constraint. Removes the faces crossed by segment ab and creates new faces instead. If a vertex c lies on segment ab, constraint ab is replaced by the two constraints ac and cb. Apart from the insertion of a and b, the algorithm runs in time proportionnal to the number of removed triangles. Precondition: The relative interior of segment ab does not intersect the relative interior of another constrained edge
void	ct.insert ( Vertex_handle va, Vertex_handle vb)
		Inserts the line segment s whose endpoints are the vertices va and vb as a constraintedge e. The triangles intersected by s are removed and new ones are created. Precondition: The relative interior of s does not intersect the relative interior of another constrained edge. Precondition: va and vb are distinct vertices of t.
void	ct.insert ( Vertex_handle va, Vertex_handle vb, Face_handle & fr, int & i)
		Same as above. In addition, sets the face fr incident to the egde e and on the right of e oriented from va to vb and the index i of the vertex of fr opposite to e, i.e. e=(fr,i).
void	ct.insert ( Vertex_handle va, Vertex_handle vb, Face_handle & fr, int & i, List_edges & new_edges)
		Same as above. In addition, the edges that are created are put in the list new_edges.
void	ct.remove ( Vertex_handle v)
		Removes a vertex v. All constraints incident to the removed vertex are removed.
void	ct.remove_constraint ( Face_handle f, int i)
		Edge e=(f,i)=(g,j) is no longer constrained.

I/O

ostream &	ostream& os << CGAL_Constrained_triangulation_2<Gt,Tds> Ct
		Writes the triangulation and, for each face f, and integers i=0,1,2, write ``C'' or ``N'' depending whether edge (f,i) is constrained or not.

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. The insertion of a constrained edge runs in time proportionnal to the number of triangles intersected by this edge.

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