CGAL::Constrained_triangulation_2<Traits,Tds,Itag>

Definition

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 additonnal functionalities to deal with this information. These additional functionalities induce additionnal 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

Triangulation_2<Traits,Tds>

Types

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.

Creation

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.


Constrained_triangulation_2<Traits,Tds,Itag> ct ( std::list<Constraint>& 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<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.

Queries

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 ouput 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 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.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

I/O

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

CGAL::Triangulation_2<Traits,Tds>,
TriangulationDataStructure_2,
TriangulationTraits_2
ConstrainedTriangulationTraits_2
ConstrainedTriangulationFaceBase_2

Implementation

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