#include <CGAL/Constrained_triangulation_2.h>

Inherits from

Inherited by CGAL::Constrained_Delaunay_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 polylines joining the points.

The given polylines 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 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 polylines that do not intersect except possibly at their endpoints. Any number of constrained edges may share the same endpoint. Constrained edges may be vertical or have zero length.
The two other versions support intersecting input constraints. In those versions, input constraints may consist of intersecting, overlapping or partially overlapping segments. The triangulation introduces 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. There are two ways to deal with intersecting constraints.
- The first one is robust when predicates are evaluated exactly but constructions (i. e. intersection computations) are approximate.
- The second one should be used with exact arithmetic (meaning exact evaluation of predicates and exact computation of intersections.)

In order to retrieve the constrained edges of a constraint, or the constraints overlapping with a constrained edge, we provide the class Constrained_triangulation_plus_2. This class maintains a constraint hierarchy data structure. See Section Constrained Triangulations with a Bidirectional Mapping between Constaints and Subconstraints for details. This class should also be used when doing exact intersection computations as it avoids the cascading of intersection computations.

Template Parameters

Traits	is a geometric traits class and must 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`.
Tds	must be a model of the concept `TriangulationDataStructure_2` or `Default`.
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: `No_intersection_tag` disallows intersections of input constraints, `Exact_predicates_tag` is to be used when the traits class provides exact predicates but approximate constructions of the intersection points. `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 face base class plugged into the triangulation data structure of a constrained Delaunay triangulation. The face base 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 class 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 < Triangulation_vertex_base_2<Gt>, Constrained_triangulation_face_base_2<Gt> >. The default intersection tag is No_intersection_tag.

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 proportional to the number of triangles intersected by this edge.

Related Functions
(Note that these are not member functions.)
ostream &	operator<< (ostream &os, const Constrained_triangulation_2< Traits, Tds > &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.

istream &	operator>> (istream &is, Constrained_triangulation_2< Traits, Tds > Ct &t)
	Reads a triangulation from stream `is` and assigns it to `t`. More...

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`. More...

istream &	operator>> (istream &is, const Triangulation_2< Traits, Tds > &T)
	Reads a triangulation from stream `is` and assigns it to the triangulation. More...

Types
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. More...

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

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

Queries
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. More...

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.

Insertion and Removal
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. More...

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

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

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

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

void	remove (Vertex_handle v)
	Removes a vertex `v`. More...

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

void	remove_constrained_edge (Face_handle f, int i)
	Make 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.

Additional Inherited Members
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 the finite vertices of the triangulation.

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::Triangulation_2< Traits, Tds >
	Triangulation_2 (const Traits &gt=Traits())
	Introduces an empty triangulation.

	Triangulation_2 (const Triangulation_2 &tr)
	Copy constructor. More...

Triangulation_2	operator= (const Triangulation_2< Traits, Tds > &tr)
	Assignment. More...

void	swap (Triangulation_2 &tr)
	The triangulations `tr` and `*this` are swapped. More...

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

bool	includes_edge (Vertex_handle va, Vertex_handle vb, Vertex_handle &vbr, Face_handle &fr, int &i)
	`true` if the line segment from `va` to `vb` includes an edge `e` incident to `va`. More...

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

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

Face_handle	inexact_locate (const Point &query, Face_handle start=Face_handle()) const
	Same as `locate()` but uses inexact predicates. More...

Face_handle	locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
	Same as above. More...

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`. More...

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`. More...

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

Vertex_handle	insert (const Point &p, Face_handle f=Face_handle())
	Inserts point `p` in the triangulation and returns the corresponding vertex. More...

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 InputIterator >
std::ptrdiff_t	insert (InputIterator first, InputIterator last)
	Inserts the points in the range `[first,last)`. More...

void	remove (Vertex_handle v)
	Removes the vertex from the triangulation. More...

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

Vertex_handle	move (Vertex_handle v, const Point &p)
	same as above if there is no collision. More...

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`. More...

Vertex_handle	insert_in_edge (const Point &p, Face_handle f, int i)
	Inserts vertex v in edge `i` of `f`. More...

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

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

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

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

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.

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.

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`. More...

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`. More...

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`. More...

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`. More...

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`. More...

int	mirror_index (Face_handle f, int i) const
	returns the index of `f` in its \( i^{th}\) neighbor. More...

Edge	mirror_edge (Edge e) const
	returns the same edge seen from the other adjacent face. More...

int	ccw (int i) const
	Returns \( i+1\) modulo 3. More...

int	cw (int i) const
	Returns \( i+2\) modulo 3. More...

Triangle	triangle (Face_handle f) const
	Returns the triangle formed by the three vertices of `f`. More...

Segment	segment (Face_handle f, int i) const
	Returns the line segment formed by the vertices `ccw(i)` and `cw(i)` of face `f`. More...

Segment	segment (const Edge &e) const
	Returns the line segment corresponding to edge `e`. More...

Segment	segment (const Edge_circulator &ec) const
	Returns the line segment corresponding to edge `*ec`. More...

Segment	segment (const Edge_iterator &ei) const
	Returns the line segment corresponding to edge `*ei`. More...

Point	circumcenter (Face_handle f) const
	Compute the circumcenter of the face pointed to by f. More...

void	set_infinite_vertex (const Vertex_handle &v)
	This is an advanced function. More...

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

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.

Member Typedef Documentation

template<typename Traits , typename Tds , typename Itag >

typedef unspecified_type CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constrained_edges_iterator

A bidirectional iterator to visit all the edges e of the triangulation which are constrained.

The order of visit is undefined. The value type of this iterator is Edge.

template<typename Traits , typename Tds , typename Itag >

typedef std::pair<Point,Point> CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constraint

Deprecated:: The type of constraints.

Member Function Documentation

template<typename Traits , typename Tds , typename Itag >

template<class OutputItEdges >

OutputItEdges CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::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.

Template Parameters

OutputItEdges is an OutputIterator with Edge as value type.

template<typename Traits , typename Tds , typename Itag >

Vertex_handle CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::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.

template<typename Traits , typename Tds , typename Itag >

Vertex_handle CGAL::Constrained_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()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::insert_constraint	(	Point	a,
		Point	b
	)

Inserts points a and b in this order, and inserts the line 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.

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::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.

The triangles intersected by s are removed and new ones are created.

template<typename Traits , typename Tds , typename Itag >

template<class PointIterator >

void CGAL::Constrained_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.

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::remove ( Vertex_handle v)

Removes a vertex v.

Precondition: Vertex v is not incident to a constrained edge.

Friends And Related Function Documentation

template<typename Traits , typename Tds , typename Itag >

istream & operator>>	(	istream &	is,
		Constrained_triangulation_2< Traits, Tds > Ct &	t
	)

Data in the stream must have the same format operator<< uses. Note that t is first cleared.

Inherits from

Definition

Related Functions

Types

Creation

Queries

Insertion and Removal

Additional Inherited Members

Member Typedef Documentation

Member Function Documentation

Friends And Related Function Documentation