A constrained triangulation is a triangulation of a set of points which has to include among its edges a given set of segments joining the points. The given segments are called constraints and the corresponding edges in the triangulation are called constrained edges.

The endpoints of constrained edges are of course vertices of the triangulation. However the triangulation may include include other vertices as well. There are three versions of constrained triangulations

A set of
constraints and its constrained triangulation

The class Constrained_triangulation_2<Traits,Tds,Itag> of the CGAL library implements constrained triangulations. The template parameter Traits stands for a geometric traits class. It has to be a model of the concept TriangulationTraits_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. It has then to be a model of the concept ConstrainedTriangulationTraits_2. The template parameter Tds stands for a triangulation data structure class that has to be a model of the concept TriangulationDataStructure_2. The third parameter Itag is the intersection tag which serves to choose between the different strategies to deal with constraints intersections. CGAL provides three valid types for this parameter :
CGAL::No_intersection_tag disallows intersections of input constraints,
CGAL::Exact_predicates_tag is to be used when the traits class provides exact predicates but approximate constructions of the intersection points.
CGAL::Exact_intersections_tag is to be used in conjunction with an exact arithmetic type.

The information about constrained edges is stored in the faces of the triangulation. 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 default instantiations for the template parameters Tds and Itag, and for the ConstrainedTriangulationFaceBase_2. 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_triangulation_2.h>

Inherits From



typedef std::pair<Point,Point> Constraint; The type of input constraints

typedef Itag Intersection_tag; The intersection tag which decides how intersections between input constraints are dealt with.


Constrained_triangulation_2<Traits,Tds,Itag> ct;
default constructor.

Constrained_triangulation_2<Traits,Tds,Itag> ct ( Constrained_triangulation_2 ct1);
Copy constructor, all faces and vertices are duplicated and the constrained status of edges is copied.

template<class InputIterator>
Constrained_triangulation_2<Traits,Tds,Itag> 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.


bool ct.is_constrained ( Edge e) Returns true if edge e is a constrained edge.

bool ct.are_there_incident_constraints ( Vertex_handle v)
Returns true if at least one of the edges incident to vertex v is constrained.

template<class OutputItEdges>
OutputItEdges ct.incident_constraints ( Vertex_handle v, OutputItEdges out)
OutputItEdges is an output iterator with Edge as value type. Outputs the constrained edges incident to v in the sequence pointed to by out and returns the resulting output iterator.

Insertion and removal

Vertex_handle ct.insert ( Point p, Face_handle f = Face_handle())
Inserts point p and restores the status (constrained or not) of all the touched edges. If present f is used as an hint for the location of p.

Vertex_handle ct.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 ct.push_back ( Point p) Equivalent to insert(p).

template < class InputIterator >
int ct.insert ( InputIterator first, InputIterator last)
Inserts the points in the range [.first, last.). Returns the number of inserted points.
Precondition: The value_type of first and last is Point.

void ct.insert_constraint ( 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 proportional 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.push_back ( Constraint c) Inserts constraints c as above.

void ct.insert_constraint ( Vertex_handle va, Vertex_handle vb)
Inserts the line segment s whose endpoints are the vertices va and vb as a constrained edge e. The triangles intersected by s are removed and new ones are created.

void ct.remove ( Vertex_handle v) Removes a vertex v.
Precondition: Vertex v is not incident to a constrained edge.

void ct.remove_incident_constraints ( Vertex_handle v)
Make the edges incident to vertex v unconstrained edges.

void ct.remove_constrained_edge ( Face_handle f, int i)
Make edge (f,i) no longer constrained.

begin of advanced section  advanced  begin of advanced section
bool ct.is_valid ( bool verbose = false, int level = 0)
Checks the validity of the triangulation and the consistency of the constrained marks in edges.

end of advanced section  advanced  end of advanced section


ostream & ostream& os << Constrained_triangulation_2<Traits,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.

See Also



The insertion of a constrained edge runs in time proportional to the number of triangles intersected by this edge.