CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds,Itag>

Definition

As in the case of constrained triangulations, three different versions of Delaunay constrained triangulations are offered depending on wether the user wishes to handle intersecting input constraints or not. The desired version can be selected through the instantation of the third template parameter Itag which can be one of the following :
CGAL::No_intersection_tag if intersections of input constraints are disallowed,
CGAL::Exact_predicates_tag allows intersections between input constraints and is to be used when the traits class provides exact predicates but approximate constructions of the intersection points. CGAL::Exact_intersections_tag allows intersections between input constraints and is to be used in conjunction with an exact arithmetic type.

The template parameters Tds has to be instantiate with a model of TriangulationDataStructure_2. The geometric traits of a constrained Delaunay triangulation is required to provide the side_of_oriented_circle test as the geometric traits of a Delaunay triangulation and the Traits parameter has to be instantiated with a model DelaunayTriangulationTraits_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. and has then to be also a model of the concept ConstrainedTriangulationTraits_2.

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> derives from the class Constrained_triangulation_2<Traits,Tds>. Also, information about the status (constrained or not) of the edges of the triangulation is stored in the faces. 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 a default for the template parameters. 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_Delaunay_triangulation_2.h>

Inherits From

Types

Creation

Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Traits t = Traits());
	Introduces an empty constrained Delaunay triangulation cdt.
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Constrained_Delaunay_triangulation_2 cdt1);
	Copy constructor, all faces and vertices are duplicated and the constrained status of edges is copied.
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( 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_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( 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	cdt.insert ( Point p, Face_handle f = Face_handle())
		Inserts point p in the triangulation. If present f is used as an hint for the location of p.
Vertex_handle	cdt.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	cdt.push_back ( Point p)
		Equivalent to insert(p).
template < class InputIterator >
int	cdt.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	cdt.insert_constraint ( Point a, Point b)
		Inserts segment ab as a constrained edge in the triangulation.
void	cdt.push_back ( Constraint c)
		Inserts constraints c as above.
void	cdt.insert_constraint ( Vertex_handle va, Vertex_handle vb)
		Inserts the line segment whose endpoints are the vertices va and vb as a constrained edge e in the triangulation.
void	cdt.remove ( Vertex_handle & v)
		Removes vertex v. Precondition: Vertex v is not incident to a constrained edge.
void	cdt.remove_incident_constraints ( Vertex_handle v)
		Make the edges incident to vertex v unconstrained edges.
void	cdt.remove_constraint ( Face_handle f, int i)
		Edge (f,i) is no longer constrained.

Queries

template <class OutputItFaces, class OutputItBoundaryEdges>
std::pair<OutputItFaces,OutputItBoundaryEdges>
	cdt.get_conflicts_and_boundary ( Point p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start)
		OutItFaces is an output iterator with Face_handle as value type. OutItBoundaryEdges stands for an output iterator with Edge as value type. This members function outputs in the container pointed to by fit the faces which are in conflict with point p. It outputs in the container pointed to by eit the boundary of the zone in conflict with p. The boundary edges of the conflict zone are ouput in counterclockwise order and each edge is described through its incident face which is not in conflict with p. The function returns in a std::pair the resulting output iterators.
template <class OutputItFaces>
OutputItFaces	cdt.get_conflicts ( Point p, OutputItFaces fit, Face_handle start)
		Same as above except that only the faces in conflict with p are output. The function returns the resulting output iterator.
template <class OutputItBoundaryEdges>
OutputItBoundaryEdges
	cdt.get_boundary_of_conflicts ( Point p, OutputItBoundaryEdges eit, Face_handle start)
		OutputItBoundaryEdges stands for an output iterator with Edge as value type. This functions outputs in the container pointed to by eit, the boundary of the zone in conflict with p. The boundary edges of the conflict zone are ouput in counter-clockwise order and each edge is described through the incident face which is not in conflict with p. The function returns the resulting output iterator.

Checking

bool

cdt.is_valid ()

Checks if the triangulation is valid and if each constrained edge is consistently marked constrained in its two incident faces.

advanced

Flips

bool	cdt.is_flipable ( Face_handle f, int i)
		Determines if edge (f,i) can be flipped. Returns true if edge (f,i) is not constrained and the circle circumscribing f contains the vertex of f->neighbor(i) opposite to edge (f,i).
void	cdt.flip ( Face_handle& f, int i)
		Flip f and f->neighbor(i).
void	cdt.propagating_flip ( List_edges & edges)
		Makes the triangulation constrained Delaunay by flipping edges. List edges contains an initial list of edges to be flipped. The returned triangulation is constrained Delaunay if the initial list contains at least all the edges of the input triangulation that failed to be constrained Delaunay. (An edge is said to be constrained Delaunay if it is either constrained or locally Delaunay.)

advanced

See Also