CGAL::Constrained_triangulation_2<Traits,Tds,Itag>

Definition

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

• In the basic version, the constrained triangulation does not handle intersecting constraints, and the set of input constraints is required to be a set of segments that do not intersect except possibly at their endpoints. Any number of constrained edges are allowed to share the same endpoint. Vertical constrained edges are allowed as well as constrained edges with null length.
• The two other versions support intersecting input constraints. In those versions, input constraints are allowed to be intersecting, overlapping or partially overlapping segments. The triangulation introduce additional vertices at each point which is a proper intersection point of two constraints. A single constraint intersecting other constraints will then appear as the union of several constrained edges of the triangulation. The two versions dealing with intersecting constraints, slightly differ in the way intersecting constraints are dealt with.
  • One of them is designed to be robust when predicates are evaluated exactly but constructions (i. e. intersection computations) are approximative.
  • The other one is designed to be used with an exact arithmetic (meaning exact evaluation of predicates and exact computation of intersections.) This last version finds its full efficiency when used in conjunction with a constraint hierarchy data structure as provided in the class Constrained_triangulation_plus_2. See section 20.9.

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

Triangulation_2<Traits,Tds>

Types

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

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.

advanced

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.

advanced

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

Implementation

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