#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 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 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 approximate.
- 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 Constrained Triangulations Plus.

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

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
	The type of input constraints. More...

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

Creation
	Constrained_triangulation_2 ()
	Default constructor. More...

	Constrained_triangulation_2 (const Constrained_triangulation_2 &ct1)
	Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied. More...

template<class InputIterator >
	Constrained_triangulation_2 (InputIterator first, InputIterator last, const Traits &t=Traits())
	A templated constructor which introduces and builds a constrained triangulation with constrained edges in the range `[first,last)`. More...

Queries
bool	is_constrained (Edge e) const
	Returns `true` if edge `e` is a constrained edge. More...

bool	are_there_incident_constraints (Vertex_handle v) const
	Returns `true` if at least one of the edges incident to vertex `v` is constrained. More...

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

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

template<class InputIterator >
std::ptrdiff_t	insert (InputIterator first, InputIterator last)
	Inserts the points in the range `[first,last)`. More...

void	insert_constraint (Point a, Point b)
	Inserts points `a` and `b`, and inserts segment `ab` as a constraint. More...

void	push_back (const Constraint &c)
	Equivalent to `insert(c.first, c.second)`. More...

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

void	remove_constrained_edge (Face_handle f, int i)
	Make edge `(f,i)` unconstrained. More...

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

Member Typedef Documentation

template<typename Traits , typename Tds , typename Itag >

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

The type of input constraints.

template<typename Traits , typename Tds , typename Itag >

typedef Itag CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Intersection_tag

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

Constructor & Destructor Documentation

template<typename Traits , typename Tds , typename Itag >

CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constrained_triangulation_2 ( )

Default constructor.

template<typename Traits , typename Tds , typename Itag >

CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constrained_triangulation_2 ( const Constrained_triangulation_2< Traits, Tds, Itag > & ct1 )

Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied.

template<typename Traits , typename Tds , typename Itag >

template<class InputIterator >

CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constrained_triangulation_2	(	InputIterator	first,
		InputIterator	last,
		const Traits &	t = `Traits()`
	)

A templated constructor which introduces and builds a constrained triangulation with constrained edges in the range [first,last).

Template Parameters

InputIterator must be an input iterator with the value type Constraint.

Member Function Documentation

template<typename Traits , typename Tds , typename Itag >

bool CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::are_there_incident_constraints ( Vertex_handle v ) const

Returns true if at least one of the edges incident to vertex v is constrained.

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

template<class InputIterator >

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

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, 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 proportional to the number of removed triangles.

Precondition: The relative interior of segment ab does not intersect the relative interior of another constrained edge.

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 constrained edge.

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

template<typename Traits , typename Tds , typename Itag >

bool CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::is_constrained ( Edge e ) const

Returns true if edge e is a constrained edge.

template<typename Traits , typename Tds , typename Itag >

bool CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::is_valid	(	bool	verbose = `false`,
		int	level = `0`
	)		const

Checks the validity of the triangulation and the consistency of the constrained marks in edges.

template<typename Traits , typename Tds , typename Itag >

Vertex_handle CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::push_back ( const Point & p )

Equivalent to insert(p).

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::push_back ( const Constraint & c )

Equivalent to insert(c.first, c.second).

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.

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::remove_constrained_edge	(	Face_handle	f,
		int	i
	)

Make edge (f,i) unconstrained.

template<typename Traits , typename Tds , typename Itag >

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

Make the edges incident to vertex v unconstrained edges.

Friends And Related Function Documentation

template<typename Traits , typename Tds , typename Itag >

ostream & operator<<	(	ostream &	os,
		const Constrained_triangulation_2< Traits, Tds > &	Ct
	)

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation