CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag > Class Template Reference

#include <CGAL/Constrained_Delaunay_triangulation_2.h>

Inherits from

CGAL::Constrained_triangulation_2< Traits, Tds, Itag >.

Definition

template<typename Traits, typename Tds, typename Itag>
class CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >

A constrained Delaunay triangulation is a triangulation with constrained edges which tries to be as much Delaunay as possible.

Constrained edges are not necessarily Delaunay edges, therefore a constrained Delaunay triangulation is not a Delaunay triangulation. A constrained Delaunay is a triangulation whose faces do not necessarily fulfill the empty circle property but fulfill a weaker property called the constrained empty circle. To state this property, it is convenient to think of constrained edges as blocking the view. Then, a triangulation is constrained Delaunay if the circumscribing circle of any of its triangular faces includes in its interior no vertex that is visible from the interior of the triangle.

As in the case of constrained triangulations, three different versions of Delaunay constrained triangulations are offered depending on whether the user wishes to handle intersecting input constraints or not.

Template Parameters

Traits	is the geometric traits of a constrained Delaunay triangulation. It must be a model of DelaunayTriangulationTraits_2, providing the side_of_oriented_circle test of a Delaunay triangulation. 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.
Tds	must be a model of TriangulationDataStructure_2or Default.
Itag	allows to select if intersecting constraints are supported and how they are handled. No_constraint_intersection_tag if intersections of input constraints are disallowed, except for the configuration of a single common extremity; No_constraint_intersection_requiring_constructions_tag if intersections of input constraints are disallowed, except if no actual construction is needed to represent the intersection. For example, if two constraints intersect in a 'T'-like junction, the intersection point is one of the constraints' extremity and as such, no construction is in fact needed. Other similar configurations include overlapping segments, common extremities, or equal constraints. 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; Exact_intersections_tag allows intersections between input constraints and is to be used in conjunction with an exact arithmetic type.

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2 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 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 a default for the template parameters. If Gt is the geometric traits parameter, the default for ConstrainedTriangulationFaceBase_2 is the class Constrained_triangulation_face_base_2<Gt> and the default for the triangulation data structure parameter is the class Triangulation_data_structure_2< CGAL::Triangulation_vertex_base_2<Gt>, Constrained_triangulation_face_base_2<Gt> >. The default intersection tag is No_constraint_intersection_requiring_constructions_tag.

Types

All types used in this class are inherited from the base class Constrained_triangulation_2<Traits,Tds,Itag>.

See also

CGAL::Constrained_triangulation_2<Traits,Tds,Itag>

TriangulationDataStructure_2

DelaunayTriangulationTraits_2

ConstrainedTriangulationTraits_2

ConstrainedDelaunayTriangulationTraits_2

ConstrainedTriangulationFaceBase_2

Examples

Triangulation_2/constrained.cpp, Triangulation_2/constrained_hierarchy_plus.cpp, Triangulation_2/constrained_plus.cpp, Triangulation_2/polygon_triangulation.cpp, Triangulation_2/polylines_triangulation.cpp, Triangulation_2/segment_soup_to_polylines.cpp, and Triangulation_2/triangulation_projection_traits.cpp.

Creation
	Constrained_Delaunay_triangulation_2 (const Traits &t=Traits())
	Introduces an empty constrained Delaunay triangulation cdt.
	Constrained_Delaunay_triangulation_2 (const Constrained_Delaunay_triangulation_2 &cdt1)
	Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied.
template<class ConstraintIterator >
	Constrained_Delaunay_triangulation_2 (ConstraintIterator first, ConstraintIterator last, const Traits &t=Traits())
	Builds a constrained triangulation with constraints in the range [first,last) by calling insert_constraints(first, last).

Insertion and Removal
The following member functions overwrite the corresponding members of the base class to include a step restoring the Delaunay constrained property after modification of the triangulation.
Vertex_handle	insert (Point p, Face_handle f=Face_handle())
	Inserts point p in the triangulation, with face f as a hint for the location of p.
Vertex_handle	insert (const Point &p, Locate_type lt, Face_handle loc, int li)
	Inserts point p in the triangulation at the location given by (lt,loc,i).
Vertex_handle	push_back (const Point &p)
	Equivalent to insert(p).
template<class PointIterator >
std::ptrdiff_t	insert (PointIterator first, PointIterator last)
	Inserts the points in the range [first,last).
template<class PointWithInfoIterator >
std::ptrdiff_t	insert (PointWithInfoIterator first, PointWithInfoIterator last)
	inserts the points in the iterator range [first,last).
void	insert_constraint (Point a, Point b)
	Inserts the line segment ab as a constraint in the triangulation.
void	push_back (const std::pair< Point, Point > &c)
	Inserts the line segment between the points c.first and c.second as a constraint in the triangulation.
void	insert_constraint (Vertex_handle va, Vertex_handle vb)
	Inserts the line segment whose endpoints are the vertices va and vb as a constraint in the triangulation.
template<class PointIterator >
void	insert_constraint (PointIterator first, PointIterator last, bool close=false)
	Inserts a polyline defined by the points in the range [first,last).
template<class ConstraintIterator >
std::size_t	insert_constraints (ConstraintIterator first, ConstraintIterator last)
	inserts the constraints in the range [first,last).
template<class PointIterator , class IndicesIterator >
std::size_t	insert_constraints (PointIterator points_first, PointIterator points_last, IndicesIterator indices_first, IndicesIterator indices_last)
	Same as above except that each constraints is given as a pair of indices of the points in the range [points_first, points_last).
void	remove (Vertex_handle &v)
	Removes vertex v.
void	remove_incident_constraints (Vertex_handle v)
	Make the edges incident to vertex v unconstrained edges.
void	remove_constraint (const Face_handle &f, int i)
	Make the edge (f,i) unconstrained.

Queries
The following template member functions query the set of faces in conflict with a point p. The notion of conflict refers here to a constrained Delaunay setting which means the following. Constrained edges are considered as visibility obstacles and a point p is considered to be in conflict with a face f iff it is visible from the interior of f and included in the circumcircle of f.
template<class OutputItFaces , class OutputItBoundaryEdges >
std::pair< OutputItFaces, OutputItBoundaryEdges >	get_conflicts_and_boundary (const Point &p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start) const
	outputs the faces and boundary edges of the conflict zone of point p into output iterators.
template<class OutputItFaces >
OutputItFaces	get_conflicts (const Point &p, OutputItFaces fit, Face_handle start) const
	outputs the faces of the conflict zone of point p into an output iterator.
template<class OutputItBoundaryEdges >
OutputItBoundaryEdges	get_boundary_of_conflicts (const Point &p, OutputItBoundaryEdges eit, Face_handle start) const
	outputs the boundary edges of the conflict zone of point p into an output iterator.

Checking
bool	is_valid () const
	checks if the triangulation is valid and if each constrained edge is consistently marked constrained in its two incident faces.

Flips
bool	is_flipable (Face_handle f, int i) const
	determines if edge (f,i) can be flipped.
void	flip (Face_handle &f, int i)
	This is an advanced function.
void	propagating_flip (List_edges &edges)
	makes the triangulation constrained Delaunay by flipping edges.

Additional Inherited Members
Public Types inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
typedef std::pair< Point, Point >	Constraint
typedef unspecified_type	Constrained_edges_iterator
	A bidirectional iterator to visit all the edges e of the triangulation which are constrained.
typedef Iterator_range< Constrained_edges_iterator >	Constrained_edges
	A range type to iterate over the constrained edges.
typedef Itag	Intersection_tag
	The intersection tag which decides how intersections between input constraints are dealt with.
Public Types inherited from CGAL::Triangulation_2< Traits, Tds >
enum	Locate_type {   VERTEX =0 , EDGE , FACE , OUTSIDE_CONVEX_HULL ,   OUTSIDE_AFFINE_HULL }
	specifies which case occurs when locating a point in the triangulation. More...
typedef Tds::Vertex_handle	Vertex_handle
	handle to a vertex.
typedef Tds::Face_handle	Face_handle
	handle to a face.
typedef Tds::Face_iterator	All_faces_iterator
	iterator over all faces.
typedef Tds::Edge_iterator	All_edges_iterator
	iterator over all edges.
typedef Tds::Vertex_iterator	All_vertices_iterator
	iterator over all vertices.
typedef unspecified_type	Finite_faces_iterator
	iterator over finite faces.
typedef unspecified_type	Finite_edges_iterator
	iterator over finite edges.
typedef unspecified_type	Finite_vertices_iterator
	iterator over finite vertices.
typedef unspecified_type	Point_iterator
	iterator over the points corresponding to the finite vertices of the triangulation.
typedef Iterator_range< unspecified_type >	All_face_handles
	range type for iterating over all faces (including infinite faces), with a nested type iterator that has as value type Face_handle.
typedef Iterator_range< All_edges_iterator >	All_edges
	range type for iterating over all edges (including infinite ones).
typedef Iterator_range< unspecified_type >	All_vertex_handles
	range type for iterating over all vertices (including the infinite vertex), with a nested type iterator that has as value type Vertex_handle.
typedef Iterator_range< unspecified_type >	Finite_face_handles
	range type for iterating over finite faces, with a nested type iterator that has as value type Face_handle.
typedef Iterator_range< Finite_edges_iterator >	Finite_edges
	range type for iterating over finite edges.
typedef Iterator_range< unspecified_type >	Finite_vertex_handles
	range type for iterating over finite vertices, with a nested type iterator that has as value type Vertex_handle.
typedef Iterator_range< Point_iterator >	Points
	range type for iterating over the points of the finite vertices.
typedef unspecified_type	Line_face_circulator
	circulator over all faces intersected by a line.
typedef unspecified_type	Face_circulator
	circulator over all faces incident to a given vertex.
typedef unspecified_type	Edge_circulator
	circulator over all edges incident to a given vertex.
typedef unspecified_type	Vertex_circulator
	circulator over all vertices incident to a given vertex.
typedef Traits	Geom_traits
	the traits class.
typedef Tds	Triangulation_data_structure
	the triangulation data structure type.
typedef Traits::Point_2	Point
	the point type.
typedef Traits::Segment_2	Segment
	the segment type.
typedef Traits::Triangle_2	Triangle
	the triangle type.
typedef Tds::Vertex	Vertex
	the vertex type.
typedef Tds::Face	Face
	the face type.
typedef Tds::Edge	Edge
	the edge type.
typedef Tds::size_type	size_type
	Size type (an unsigned integral type).
typedef Tds::difference_type	difference_type
	Difference type (a signed integral type).
Public Member Functions inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
	Constrained_triangulation_2 ()
	Default constructor.
	Constrained_triangulation_2 (const Constrained_triangulation_2 &ct1)
	Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied.
bool	is_constrained (Edge e) const
	returns true if edge e is a constrained edge.
bool	are_there_incident_constraints (Vertex_handle v) const
	returns true if at least one of the edges incident to vertex v is constrained.
template<class OutputItEdges >
OutputItEdges	incident_constraints (Vertex_handle v, OutputItEdges out) const
	outputs the constrained edges incident to v into the output iterator out and returns the resulting output iterator.
Constrained_edges_iterator	constrained_edges_begin () const
	returns an iterator that enumerates the constrained edges.
Constrained_edges_iterator	constrained_edges_end () const
	returns the past-the-end iterator.
Constrained_edges	constrained_edges () const
	returns a range of constrained edges.
Vertex_handle	insert (Point p, Face_handle f=Face_handle())
	inserts point p and restores the status (constrained or not) of all the touched edges.
Vertex_handle	insert (const Point &p, Locate_type &lt, Face_handle loc, int li)
	inserts point p in the triangulation at the location given by (lt,loc,i).
Vertex_handle	push_back (const Point &p)
	Equivalent to insert(p).
void	insert_constraint (Point a, Point b)
	inserts points a and b in this order, and inserts the line segment ab as a constraint.
void	push_back (const std::pair< Point, Point > &c)
	Equivalent to insert(c.first, c.second).
void	insert_constraint (const Vertex_handle &va, const Vertex_handle &vb)
	inserts the line segment s whose endpoints are the vertices va and vb as a constraint.
template<class PointIterator >
void	insert_constraint (PointIterator first, PointIterator last, bool close=false)
	inserts a polyline defined by the points in the range [first,last).
void	remove (Vertex_handle v)
	removes a vertex v.
void	remove_incident_constraints (Vertex_handle v)
	makes the edges incident to vertex v unconstrained edges.
void	remove_constrained_edge (Face_handle f, int i)
	makes edge (f,i) unconstrained.
bool	is_valid (bool verbose=false, int level=0) const
	checks the validity of the triangulation and the consistency of the constrained marks in edges.
Public Member Functions inherited from CGAL::Triangulation_2< Traits, Tds >
	Triangulation_2 (const Traits &gt=Traits())
	Introduces an empty triangulation.
	Triangulation_2 (const Triangulation_2 &tr)
	Copy constructor.
template<class InputIterator >
	Triangulation_2 (InputIterator first, InputIterator last, const Traits &gt=Traits())
	Equivalent to constructing an empty triangulation with the optional traits class argument and calling insert(first,last).
Triangulation_2	operator= (const Triangulation_2< Traits, Tds > &tr)
	Assignment.
void	swap (Triangulation_2 &tr)
	The triangulations tr and *this are swapped.
void	clear ()
	Deletes all faces and finite vertices resulting in an empty triangulation.
int	dimension () const
	Returns the dimension of the convex hull.
size_type	number_of_vertices () const
	Returns the number of finite vertices.
size_type	number_of_faces () const
	Returns the number of finite faces.
Face_handle	infinite_face () const
	a face incident to the infinite vertex.
Vertex_handle	infinite_vertex () const
	the infinite vertex.
Vertex_handle	finite_vertex () const
	a vertex distinct from the infinite vertex.
const Geom_traits &	geom_traits () const
	Returns a const reference to the triangulation traits object.
const TriangulationDataStructure_2 &	tds () const
	Returns a const reference to the triangulation data structure.
TriangulationDataStructure_2 &	tds ()
	Returns a reference to the triangulation data structure.
bool	is_infinite (Vertex_handle v) const
	true iff v is the infinite vertex.
bool	is_infinite (Face_handle f) const
	true iff face f is infinite.
bool	is_infinite (Face_handle f, int i) const
	true iff edge (f,i) is infinite.
bool	is_infinite (Edge e) const
	true iff edge e is infinite.
bool	is_infinite (Edge_circulator ec) const
	true iff edge *ec is infinite.
bool	is_infinite (All_edges_iterator ei) const
	true iff edge *ei is infinite.
bool	is_edge (Vertex_handle va, Vertex_handle vb)
	true if there is an edge having va and vb as vertices.
bool	is_edge (Vertex_handle va, Vertex_handle vb, Face_handle &fr, int &i)
	as above.
bool	includes_edge (Vertex_handle va, Vertex_handle vb, Vertex_handle &vbb, Face_handle &fr, int &i)
	true if the line segment from va to vb includes an edge e incident to va.
bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)
	true if there is a face having v1, v2 and v3 as vertices.
bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3, Face_handle &fr)
	as above.
Face_handle	locate (const Point &query, Face_handle f=Face_handle()) const
	If the point query lies inside the convex hull of the points, a face that contains the query in its interior or on its boundary is returned.
Face_handle	inexact_locate (const Point &query, Face_handle start=Face_handle()) const
	Same as locate() but uses inexact predicates.
Face_handle	locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
	Same as above.
Oriented_side	oriented_side (Face_handle f, const Point &p) const
	Returns on which side of the oriented boundary of f lies the point p.
Oriented_side	side_of_oriented_circle (Face_handle f, const Point &p)
	Returns on which side of the circumcircle of face f lies the point p.
void	flip (Face_handle f, int i)
	Exchanges the edge incident to f and f->neighbor(i) with the other diagonal of the quadrilateral formed by f and f->neighbor(i).
Vertex_handle	insert (const Point &p, Face_handle f=Face_handle())
	Inserts point p in the triangulation and returns the corresponding vertex.
Vertex_handle	insert (const 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) (see the description of the locate method above.)
Vertex_handle	push_back (const Point &p)
	Equivalent to insert(p).
template<class PointInputIterator >
std::ptrdiff_t	insert (PointInputIterator first, PointInputIterator last)
	Inserts the points in the range [first,last) in the given order, and returns the number of inserted points.
template<class PointWithInfoInputIterator >
std::ptrdiff_t	insert (PointWithInfoInputIterator first, PointWithInfoInputIterator last)
	inserts the points in the iterator range [first,last) in the given order, and returns the number of inserted points.
void	remove (Vertex_handle v)
	Removes the vertex from the triangulation.
Vertex_handle	move_if_no_collision (Vertex_handle v, const Point &p)
	If there is not already another vertex placed on p, the triangulation is modified such that the new position of vertex v is p, and v is returned.
Vertex_handle	move (Vertex_handle v, const Point &p)
	If there is no collision during the move, this function is the same as move_if_no_collision .
Vertex_handle	insert_first (const Point &p)
	Inserts the first finite vertex .
Vertex_handle	insert_second (const Point &p)
	Inserts the second finite vertex .
Vertex_handle	insert_in_face (const Point &p, Face_handle f)
	Inserts vertex v in face f.
Vertex_handle	insert_in_edge (const Point &p, Face_handle f, int i)
	Inserts vertex v in edge i of f.
Vertex_handle	insert_outside_convex_hull (const Point &p, Face_handle f)
	Inserts a point which is outside the convex hull but in the affine hull.
Vertex_handle	insert_outside_affine_hull (const Point &p)
	Inserts a point which is outside the affine hull.
void	remove_degree_3 (Vertex_handle v)
	Removes a vertex of degree three.
void	remove_second (Vertex_handle v)
	Removes the before last finite vertex.
void	remove_first (Vertex_handle v)
	Removes the last finite vertex.
template<class EdgeIt >
Vertex_handle	star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end)
	creates a new vertex v and use it to star the hole whose boundary is described by the sequence of edges [edge_begin, edge_end).
template<class EdgeIt , class FaceIt >
Vertex_handle	star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end, FaceIt face_begin, FaceIt face_end)
	same as above, except that the algorithm first recycles faces in the sequence [face_begin, face_end) and create new ones only when the sequence is exhausted.
Finite_vertices_iterator	finite_vertices_begin () const
	Starts at an arbitrary finite vertex.
Finite_vertices_iterator	finite_vertices_end () const
	Past-the-end iterator.
Finite_edges_iterator	finite_edges_begin () const
	Starts at an arbitrary finite edge.
Finite_edges_iterator	finite_edges_end () const
	Past-the-end iterator.
Finite_faces_iterator	finite_faces_begin () const
	Starts at an arbitrary finite face.
Finite_faces_iterator	finite_faces_end () const
	Past-the-end iterator.
Point_iterator	points_begin () const
Point_iterator	points_end () const
	Past-the-end iterator.
Finite_vertex_handles	finite_vertex_handles () const
	returns a range of iterators over finite vertices.
Finite_edges	finite_edges () const
	returns a range of iterators over finite edges.
Finite_face_handles	finite_face_handles () const
	returns a range of iterators over finite faces.
Points	points () const
	returns a range of iterators over the points of finite vertices.
All_vertices_iterator	all_vertices_begin () const
	Starts at an arbitrary vertex.
All_vertices_iterator	all_vertices_end () const
	Past-the-end iterator.
All_edges_iterator	all_edges_begin () const
	Starts at an arbitrary edge.
All_edges_iterator	all_edges_end () const
	Past-the-end iterator.
All_faces_iterator	all_faces_begin () const
	Starts at an arbitrary face.
All_faces_iterator	all_faces_end () const
	Past-the-end iterator.
All_vertex_handles	all_vertex_handles () const
	returns a range of iterators over all vertices.
All_edges	all_edges () const
	returns a range of iterators over all edges.
All_face_handles	all_face_handles () const
	returns a range of iterators over all faces.
Line_face_circulator	line_walk (const Point &p, const Point &q, Face_handle f=Face_handle()) const
	This function returns a circulator that allows to visit the faces intersected by the line pq.
Face_circulator	incident_faces (Vertex_handle v) const
	Starts at an arbitrary face incident to v.
Face_circulator	incident_faces (Vertex_handle v, Face_handle f) const
	Starts at face f.
Edge_circulator	incident_edges (Vertex_handle v) const
	Starts at an arbitrary edge incident to v.
Edge_circulator	incident_edges (Vertex_handle v, Face_handle f) const
	Starts at the first edge of f incident to v, in counterclockwise order around v.
Vertex_circulator	incident_vertices (Vertex_handle v) const
	Starts at an arbitrary vertex incident to v.
Vertex_circulator	incident_vertices (Vertex_handle v, Face_handle f)
	Starts at the first vertex of f adjacent to v in counterclockwise order around v.
Vertex_handle	mirror_vertex (Face_handle f, int i) const
	returns the vertex of the \( i^{th}\) neighbor of f that is opposite to f.
int	mirror_index (Face_handle f, int i) const
	returns the index of f in its \( i^{th}\) neighbor.
Edge	mirror_edge (Edge e) const
	returns the same edge seen from the other adjacent face.
int	ccw (int i) const
	Returns \( i+1\) modulo 3.
int	cw (int i) const
	Returns \( i+2\) modulo 3.
Triangle	triangle (Face_handle f) const
	Returns the triangle formed by the three vertices of f.
Segment	segment (Face_handle f, int i) const
	Returns the line segment formed by the vertices ccw(i) and cw(i) of face f.
Segment	segment (const Edge &e) const
	Returns the line segment corresponding to edge e.
Segment	segment (const Edge_circulator &ec) const
	Returns the line segment corresponding to edge *ec.
Segment	segment (const Edge_iterator &ei) const
	Returns the line segment corresponding to edge *ei.
Point	circumcenter (Face_handle f) const
	Compute the circumcenter of the face pointed to by f.
void	set_infinite_vertex (const Vertex_handle &v)
	This is an advanced function.
bool	is_valid (bool verbose=false, int level=0) const
	Checks the combinatorial validity of the triangulation and also the validity of its geometric embedding.
Public Member Functions inherited from CGAL::Triangulation_cw_ccw_2
	Triangulation_cw_ccw_2 ()
	default constructor.
int	ccw (const int i) const
	returns the index of the neighbor or vertex that is next to the neighbor or vertex with index i in counterclockwise order around a face.
int	cw (const int i) const
	returns the index of the neighbor or vertex that is next to the neighbor or vertex with index i in counterclockwise order around a face.
Related Functions inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
template<typename Traits , typename Tds , typename Itag >
std::ostream &	operator<< (std::ostream &os, const Constrained_triangulation_2< Traits, Tds, Itag > &ct)
	writes the triangulation as for Triangulation_2<Traits,Tds> and, for each face f, and integers i=0,1,2, writes "C" or "N" depending whether edge (f,i) is constrained or not.
template<typename Traits , typename Tds , typename Itag >
std::istream &	operator>> (std::istream &is, Constrained_triangulation_2< Traits, Tds, Itag > Ct &ct)
	reads a triangulation from stream is and assigns it to ct.
Related Functions inherited from CGAL::Triangulation_2< Traits, Tds >
ostream &	operator<< (ostream &os, const Triangulation_2< Traits, Tds > &T)
	Inserts the triangulation into the stream os.
istream &	operator>> (istream &is, const Triangulation_2< Traits, Tds > &T)
	Reads a triangulation from stream is and assigns it to the triangulation.

Constructor & Destructor Documentation

Constrained_Delaunay_triangulation_2()

template<typename Traits , typename Tds , typename Itag >

template<class ConstraintIterator >

CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::Constrained_Delaunay_triangulation_2	(	ConstraintIterator	first,
		ConstraintIterator	last,
		const Traits &	t = Traits()
	)

Builds a constrained triangulation with constraints in the range [first,last) by calling insert_constraints(first, last).

Template Parameters

ConstraintIterator

must be an InputIterator with the value type std::pair<Point,Point> or Segment.

Member Function Documentation

flip()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::flip	(	Face_handle &	f,
		int	i
	)

This is an advanced function.

Advanced

Flip f and f->neighbor(i).

get_boundary_of_conflicts()

template<typename Traits , typename Tds , typename Itag >

template<class OutputItBoundaryEdges >

OutputItBoundaryEdges CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_boundary_of_conflicts	(	const Point &	p,
		OutputItBoundaryEdges	eit,
		Face_handle	start
	)		const

outputs the boundary edges of the conflict zone of point p into an output iterator.

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

Template Parameters

OutputItBoundaryEdges

is an OutputIterator with the value type Edge.

get_conflicts()

template<typename Traits , typename Tds , typename Itag >

template<class OutputItFaces >

OutputItFaces CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_conflicts	(	const Point &	p,
		OutputItFaces	fit,
		Face_handle	start
	)		const

outputs the faces of the conflict zone of point p into an output iterator.

Same as get_conflicts_and_boundary except that only the faces in conflict with p are output. The function returns the resulting output iterator.

Precondition

dimension()==2.

get_conflicts_and_boundary()

template<typename Traits , typename Tds , typename Itag >

template<class OutputItFaces , class OutputItBoundaryEdges >

std::pair< OutputItFaces, OutputItBoundaryEdges > CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_conflicts_and_boundary	(	const Point &	p,
		OutputItFaces	fit,
		OutputItBoundaryEdges	eit,
		Face_handle	start
	)		const

outputs the faces and boundary edges of the conflict zone of point p into output iterators.

This 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 output 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 Parameters

OutItFaces	is an OutputIterator with the value type Face_handle.
OutItBoundaryEdges	is an OutputIterator with the value type Edge.

Precondition

dimension()==2.

insert() [1/3]

template<typename Traits , typename Tds , typename Itag >

Vertex_handle CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert	(	const Point &	p,
		Locate_type	lt,
		Face_handle	loc,
		int	li
	)

Inserts point p in the triangulation at the location given by (lt,loc,i).

See also

Triangulation_2::locate()

insert() [2/3]

template<typename Traits , typename Tds , typename Itag >

template<class PointIterator >

std::ptrdiff_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert	(	PointIterator	first,
		PointIterator	last
	)

Inserts the points in the range [first,last).

Returns the number of inserted points.

Template Parameters

PointIterator

must be an InputIterator with the value type Point.

insert() [3/3]

template<typename Traits , typename Tds , typename Itag >

template<class PointWithInfoIterator >

std::ptrdiff_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert	(	PointWithInfoIterator	first,
		PointWithInfoIterator	last
	)

inserts the points in the iterator range [first,last).

Returns the number of inserted points. Note that this function is not guaranteed to insert the points following the order of PointWithInfoIterator, as spatial_sort() is used to improve efficiency. Given a pair (p,i), the vertex v storing p also stores i, that is v.point() == p and v.info() == i. If several pairs have the same point, only one vertex is created, and one of the objects of type Vertex::Info will be stored in the vertex.

Precondition

Vertex must be model of the concept TriangulationVertexBaseWithInfo_2.

Template Parameters

PointWithInfoIterator

must be an InputIterator with the value type std::pair<Point,Vertex::Info>.

insert_constraint()

template<typename Traits , typename Tds , typename Itag >

template<class PointIterator >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_constraint	(	PointIterator	first,
		PointIterator	last,
		bool	close = false
	)

Inserts a polyline defined by the points in the range [first,last).

The polyline is considered as a polygon if the first and last point are equal or if close = true. This enables for example passing the vertex range of a Polygon_2.

Template Parameters

PointIterator

must be an InputIterator with the value type Point.

insert_constraints() [1/2]

template<typename Traits , typename Tds , typename Itag >

template<class ConstraintIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_constraints	(	ConstraintIterator	first,
		ConstraintIterator	last
	)

inserts the constraints in the range [first,last).

Note that this function is not guaranteed to insert the constraints following the order of ConstraintIterator, as spatial_sort() is used to improve efficiency. More precisely, all endpoints are inserted prior to the segments and according to the order provided by the spatial sort. Once endpoints have been inserted, the segments are inserted in the order of the input iterator, using the vertex handles of its endpoints.

Returns

the number of inserted points.

Template Parameters

ConstraintIterator

must be an InputIterator with the value type std::pair<Point,Point> or Segment.

insert_constraints() [2/2]

template<typename Traits , typename Tds , typename Itag >

template<class PointIterator , class IndicesIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_constraints	(	PointIterator	points_first,
		PointIterator	points_last,
		IndicesIterator	indices_first,
		IndicesIterator	indices_last
	)

Same as above except that each constraints is given as a pair of indices of the points in the range [points_first, points_last).

The indices must go from 0 to std::distance(points_first, points_last)

Template Parameters

PointIterator	is an InputIterator with the value type Point.
IndicesIterator	is an InputIterator with std::pair<Int,Int> where Int is an integral type implicitly convertible to std::size_t

Note

points are inserted even if they are not endpoint of a constraint.

Returns

the number of inserted points.

is_flipable()

template<typename Traits , typename Tds , typename Itag >

bool CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::is_flipable	(	Face_handle	f,
		int	i
	)		const

determines if edge (f,i) can be flipped.

Advanced

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

propagating_flip()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::propagating_flip

(

List_edges &

edges

)

makes the triangulation constrained Delaunay by flipping edges.

Advanced

The 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.)

remove()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::remove

(

Vertex_handle &

v

)

Removes vertex v.

Precondition

Vertex v is not incident to a constrained edge.