The Triangulation Class CGAL_Triangulation_2<Gt,Tds>

The CGAL_Triangulation_2<Gt,Tds> expects a model of geometric traits class as first template argument and a model of triangulation data structure as second argument. The requirements and defaults for these classes are described in the next sections and .

#include <CGAL/Triangulation_2.h>

Types

typedef Gt	Geom_traits;	the geometric traits type.
typedef Tds	Triangulation_data_structure;
		the triangulation data structure type
typedef Gt::Point	Point;	Point
typedef Gt::Segment
	Segment;	Segment
typedef Gt::Triangle
	Triangle;	Triangle

The following types gives the classes representing the vertices and faces of the triangulation and the type corresponding to the edges. Recall that the edges are not explicitly represented and thus there is no corresponding class. The functionalities of the vertex and face classes are described in sections  and .

CGAL_Triangulation_2<Gt,Tds>::Vertex
	Vertex type.
CGAL_Triangulation_2<Gt,Tds>::Face
	Face type.

typedef pair<Face_handle, int>
	Edge;	Edge type. An Edge(f,i) is edge number i of face f.

The vertices and faces of the triangulations are accessed through handles, iterators and circulators. A handle is a type which supports the two dereference operators operator* and operator->. Iterator and circulators are bidirectional and non mutable. Circulators and iterators are assignable to the corresponding handle types. Whenever a handle appear in the parameter list of a function, an appropriate iterator or circulator can be used as well. The edges of the triangulation can also be visited through iterators and circulators which are bidirectional and non mutable.

CGAL_Triangulation_2<Gt,Tds>::Vertex_handle
	handle to a vertex
CGAL_Triangulation_2<Gt,Tds>::Face_handle
	handle to a facet
CGAL_Triangulation_2<Gt,Tds>::Face_iterator
	iterator over all faces.
CGAL_Triangulation_2<Gt,Tds>::Edge_iterator
	iterator over all edges.
CGAL_Triangulation_2<Gt,Tds>::Vertex_iterator
	iterator over all vertices.
CGAL_Triangulation_2<Gt,Tds>::Line_face_circulator
	circulator over all faces intersected by a line.
CGAL_Triangulation_2<Gt,Tds>::Face_circulator
	circulator over all faces incident to a given vertex.
CGAL_Triangulation_2<Gt,Tds>::Edge_circulator
	circulator over all edges incident to a given vertex.
CGAL_Triangulation_2<Gt,Tds>::Vertex_circulator
	circulator over all vertices incident to a given vertex.

The triangulation class also defines the following enum type to specify which case occurs when locating a point in the triangulation.

enum Locate_type { VERTEX=0, EDGE, FACE, OUTSIDE, COLLINEAR_OUTSIDE};
	OUTSIDE means outside the convex hull. COLLINEAR_OUTSIDE means collinear to a 1-dimensional tri\-angul\-a\-tion and outside the convex hull.

Creation

CGAL_Triangulation_2<Gt,Tds> t ( Geom_traits gt = Geom_traits());
	Introduces an empty triangulation t.
CGAL_Triangulation_2<Gt,Tds> t ( tr);
	Copy constructor. All the vertices and faces are duplicated. t and tr refer to different triangulations. After the copy, if tr is modified, t is not.

CGAL_Triangulation_2<Gt,Tds>
	t = tr	Assignation. The triangulation is duplicated, and modifying one after the copy does not modify the other.
void	t.swap ( & tr)	The triangulations tr and t are swapped. \ccVar.swap(tr) should be preferred to t = tr or to t(tr) if tr is deleted after that.
void ccTilde{	t.\ccVar} ()	Destructor. All vertices and faces are deleted.

Access Functions

Geom_traits	t.geom_traits ()	Returns a const reference to the triangulation traits object.
int	t.dimension ()	Returns the dimension of the convex hull.
int	t.number_of_vertices ()
		Returns the number of finite vertices.

Finite and Infinite Vertices and Faces

As previously said, the triangulation is a collection of triangular faces which either are finite or infinite where an infinite face is a face incident to the infinite_vertex. Similarly we call infinite an edge incident to the infinite_vertex.

bool	t.is_infinite ( Vertex_handle v)
		true, iff vertex v is the infinite_vertex.
bool	t.is_infinite ( Face_handle f)
		true, iff f is incident to the infinite_vertex .
bool	t.is_infinite ( Face_handle f, int i)
		true, iff the edge i of face f is incident to the infinite_vertex.
bool	t.is_infinite ( Edge e)
		true iff edge e incident to the infinite_vertex.
bool	t.is_infinite ( Edge_circulator ec)
		true iff edge *ec incident to the infinite_vertex.
bool	t.is_infinite ( Edge_iterator ei)
		true iff edge *ei incident to the infinite_vertex.
Face_handle	t.infinite_face ()	a face incident to the infinite_vertex.
Vertex_handle	t.infinite_vertex ()
		the infinite_vertex.
Vertex_handle	t.finite_vertex ()	a vertex distinct from the infinite_vertex

Queries

The class CGAL_Triangulation_2<Gt,Tds> provides two functions to locate a given point with respect to a triangulation. It provides also one function to test if a given point is inside a finite face or not.

Face_handle	t.locate ( Point query, Face_handle f = Face_handle())
		If the point query lies inside the convex hull of the points, the face that contains the query in its interior or on its boundary is returned. If the point query lies outside the convex hull of the points, an infinite face with vertices $(infinity,\; p,\; q)$ is returned such that query lies to the left of the oriented line $pq$ (the rest of the triangulation lies to the right of this line.) If the triangulation is 1-dim and query collinear with it, such a face does not exists. In that case, the face returned is such that $q$ is the vertex nearest to query. The optional Face_handle argument, if provided, is used as a hint of where the locate process has to start its search. Precondition: t has at least two vertices.
Face_handle	t.locate ( Point query, Locate_type& lt, int& li, Face_handle h =Face_handle())
		Same as above. Additionally, the parameters lt and li describe where the query point is located. The variable lt is set to the locate type of the query and the variable li is set to he index of the vertex or to the index of the vertex opposite to the edge, if the point lies on a vertex or on an edge. Otherwise li has no meaning. Precondition: t has at least two vertices.
CGAL_Oriented_side	t.oriented_side ( Face_handle f, Point p)
		Returns on which side of the oriented boundary of f lies the point p. Precondition: f is finite.

Insertion, Removal and other Modifiers

The following operations are guaranteed to lead to a valid triangulation when they are applied on a valid triangulation.

void	t.flip ( Face_handle f, int i)
		Exchange the edge incident to f and f->neighbor(i) with the other diagonal of the quadrilateral formed by f and f->neighbor(i). Precondition: The faces f and f->neighbor(i) are finite faces and their union form a convex quadrilateral.

void	t.insert_first ( Vertex_handle v)
		Insert the first finite vertex .
void	t.insert_second ( Vertex_handle v)
		Insert the second finite vertex .
void	t.insert_in_face ( Vertex_handle v, Face_handle f)
		Insert vertex v in face f. Face f is modified, two new faces are created. Precondition: The point in vertex v lies inside face f.
void	t.insert_in_edge ( Vertex_handle v, Face_handle f, int i)
		Insert vertex v in edge i of f. Precondition: The point in vertex v lies on the edge opposite to the vertex i of face f.
void	t.insert_collinear_outside ( Vertex * v, Face * loc, int li)
		insert in a 1 dimensional triangulation a vertex which is collinear to the triangulation and outside the convex hull. Precondition: loc->vertex(li) is the vertex of the triangulation closest to v.

Vertex_handle	t.insert ( Point p, Face_handle f = Face_handle())
		Inserts point p in the triangulation and returns the corresponding vertex. If point p coincides with an already existing vertex, this vertex is returned and the triangulation remains unchanged. If point p is on an edge, the two incident faces are split in two. If point p is strictly inside a face of the triangulation, the face is split in three. If point p is strictly outside the convex hull, $p$ is linked to all visible points on the convex hull to form the new triangulation. The last argument f is an indication to the underlying locate algorithm of where to start.
Vertex_handle	t.insert ( Point p, Locate_type& lt, Face_handle f =Face_handle())
		Same as above. Additionally, parameter lt describes where point p was located before updating the triangulation (see locate).
Vertex_handle	t.push_back ( Point p)
		Equivalent to insert(p).
template < class InputIterator >
int	t.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	t.remove_degree_3 ( Vertex_handle v)
		remove a vertex of degree 3. Two of the incident faces are destroyed, the third one is modified. Precondition: Vertex v is a finite vertex with degree 3.
void	t.remove_second ( Vertex_handle v)
		remove the before last finite vertex.
void	t.remove_first ( Vertex_handle v)
		remove the last finite vertex.

void	t.remove ( Vertex_handle v)
		Removes the vertex from the triangulation. The created hole is retriangulated. Precondition: Vertex v must be finite.
void	t.clear ()	Removes all finite vertices and faces.

Traversal of the Triangulation

A triangulation can be seen as a container of faces and vertices. Therefore the triangulation provides several iterators and circulators that allow to traverse it (completely or partially).

Face, Edge and Vertex Iterators

The following iterators allow respectively to visit all finite faces, all finite edges and all finite vertices of the triangulation. These iterators are non mutable, bidirectional and their value types are respectively Face, Edge and Vertex. They are all invalidated by any change in the triangulation.

Vertex_iterator	t.vertices_begin ()
		Starts at an arbitrary finite vertex
Vertex_iterator	t.vertices_end ()	Past-the-end iterator
Edge_iterator	t.edges_begin ()	Starts at an arbitrary finite edge
Edge_iterator	t.edges_end ()	Past-the-end iterator
Face_iterator	t.faces_begin ()	Starts at an arbitrary finite face
Face_iterator	t.faces_end ()	Past-the-end iterator

Line Face Circulator

The triangulation defines a circulator that allows to visit all faces that are intersected by a line. More precisely, a face f is enumerated by the circulator associated to the oriented line l if either

\itemsep0pt
• f is a finite face whose interior intersects l, or
• f has an edge collinear with l and lies to the left of l, or
• f is an infinite face incident to a convex hull edge whose interior is intersected by l, or
• f is an infinite face incident to a convex hull vertex lying on l and the finite edge of f lies to the left of l.

This circulator is non-mutable and bidirectional. Its value type is Face.

Line_face_circulator
	t.line_walk ( Point p, Point q, Face_handle f = Face_handle())
		This function returns a circulator that allows to visit the faces intersected by the line pq. The starting point of the circulator is the face f, if f != NULL, or the first finite face traversed by l. If there is no such face the circulator has a singular value. The circulator wraps around the infinite_vertex and and refers to the infinite face adjacent to the first finite traversed face just after the infinite face adjacent to the last finite traversed face. Precondition: If f != NULL, the point p must be inside or on the boundary of f.

The following figure illustrates which finite faces are enumerated. Lines $l$₁ and $l$₂ have no face to their left. Lines $l$₃ and $l$₄ have faces to their left. Note that the faces that are only vertex incident to lines $l$₃ and $l$₄ are not enumerated.

A line face circulator is invalidated if the face the circulator refers to is changed.

Face, Edge and Vertex Circulators

The triangulation also provides circulators that allows to visit respectively all faces or edges incident to a given vertex or all vertices adjacent to a given vertex. These circulator are non-mutable and bidirectional. The operator operator++ moves the circulator counterclockwise around the vertex while the operator-- moves clockwise. A face circulator is invalited by any modification of the face pointed to. An edge or a vertex circulator are invalidated by any modification of one of the two faces incident to the edge pointed to.

Face_circulator	t.incident_faces ( Vertex_handle v)
		Starts at an arbitrary face incident to v.
Face_circulator	t.incident_faces ( Vertex_handle v, Face_handle f)
		Start at face f.
Edge_circulator	t.incident_edges ( Vertex_handle v)
		Start at an arbitrary edge incident to v.
Edge_circulator	t.incident_edges ( Vertex_handle v, Face_handle f)
		Start at the the first edge of f incident to v, in counterclockwise order around v. Precondition: Face f is incident to vertex v.
Vertex_circulator	t.incident_vertices ( Vertex_handle v)
		Starts at an arbitrary vertex incident to v.
Vertex_circulator	t.incident_vertices ( Vertex_handle v, Face_handle f)
		Starts at the first vertex of f adjacent to v in counterclockwise order around v. Precondition: Face f is incident to vertex v.

Traversal of the Convex Hull

Applied on the infinite_vertex the above functions allow to visit the vertices on the convex hull, as well as the infinite edges and faces. Note that a counterclockwise traversal of the vertices adjacent to the infinite_vertex is a clockwise traversal of the convex hull.

Face_circulator	t.incident_faces ( t.infinite_vertex())
Face_circulator	t.incident_faces ( t.infinite_vertex(), Face_handle f)
Edge_circulator	t.incident_edges ( t.infinite_vertex())
Edge_circulator	t.incident_edges ( t.infinite_vertex(), Face_handle f)
Vertex_circulator	t.incident_vertices ( t.infinite_vertex() v)
Vertex_circulator	t.incident_vertices ( t.infinite_vertex(), Face_handle f)

Miscellaneous

int	t.ccw ( int i)	Returns $i+1$ modulo 3. Precondition: .
int	t.cw ( int i)	Returns $i+2$ modulo 3. Precondition: .
int	t.number_of_faces ()
		Returns the number of finite and infinite faces. TBC_TO Returns the number of finite faces. This access number functions requires to count the degree of the infinite_vertex and thus is not a constant time access function.
Triangle	t.triangle ( Face_handle f)
		Returns the triangle formed by the three vertices of f. Precondition: The face is finite.
Segment	t.segment ( Face_handle f, int i)
		Returns the line segment formed by the vertices ccw(i) and cw(i) of face f. Precondition: . The vertices ccw(i) and cw(i) of f are finite.
Segment	t.segment ( Edge e)
		Returns the line segment corresponding to edge e.
Segment	t.segment ( Edge_circulator ec)
		Returns the line segment corresponding to edge *ec.
Segment	t.segment ( Edge_iterator ei)
		Returns the line segment corresponding to edge *ei.

Setting

void	t.set_finite_vertex ( Vertex_handle v)
void	t.set_infinite_vertex ( Vertex_handle v)
void	t.set_number_of_vertices ( int n)

Checking

The responsibility of keeping a valid triangulation belongs to the users if advanced operations are used. Obviously the advanced user, who implements higher levels operations may have to make a triangulation invalid at some times. The following method is provided to help the debugging.

bool	t.is_valid ( bool verbose = false, int level = 0)
		Check the combinatorial validity of the triangulation and also the validity of its geometric embedding. This method is mainly a debugging help for the users of advanced features.

I/O

The I/O operators are defined for iostream, and for the window stream provided by CGAL. The format for the iostream is an internal format.

ostream&	ostream& os << CGAL_Triangulation_2<Traits> T
		Inserts the triangulation t into the stream os. Precondition: The insert operator must be defined for Point.
istream&	istream& is >> CGAL_Triangulation_2<Traits> T
		Reads a triangulation from stream is and assigns it to t. Precondition: The extract operator must be defined for Point.

#include <CGAL/IO/Window_stream.h>

CGAL_Window_stream&
	CGAL_Window_stream& W << CGAL_Triangulation_2<Traits> T
		Inserts the triangulation t into the window stream W. The insert operator must be defined for Point and Segment.

Example

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Triangulation_2.h>
#include <CGAL/Triangulation_euclidean_traits_2.h>

typedef CGAL_Cartesian<leda_rational> Rep;
typedef CGAL_Triangulation_euclidean_traits_2<Rep> Gt;
typedef CGAL_Triangulation_vertex_base_2<Gt> Vb;
typedef CGAL_Triangulation_face_base_2<Gt>  Fb;
typedef CGAL_Triangulation_default_data_structure_2<Gt,Vb,Fb> Tds;
typedef CGAL_Triangulation_2<Tds, Gt> Triangulation;
typedef Triangulation::Vertex_circulator Vertex_circulator;

{
    Triangulation t();

    Point p;
    while (cin >> p){
        t.insert(p);
    }

    Vertex_circulator vc = t.incident_vertices(t.infinite_vertex()),
                      done(vc);

    if (vc != NULL) {
        do{
            cout << vc->point();
        }while(++vc != done);
    }
}

Implementation

Locate is implemented by a line walk from a vertex of the face given as optional parameter (or from a finite vertex of infinite_face() if no optional parameter is given). It takes time O(n) in the worst case, but only O(sqrt(n)) on average if the vertices are distributed uniformly at random.

Insertion of a point is done by locating a face that contains the point, and then splitting this face. If the point falls outside the convex hull is restored by flips. Apart from the location, insertion takes a time time O(1). This bound is only amortized for points located outside the convex hull.

Removal of a vertex is done by removing all adjacent triangles, and retriangulating the hole. Removal takes time O(d^2) in the worst case, if d is the degree of the removed vertex, which is O(1) for a random vertex.

The face, edge, and vertex iterators are derived from the corresponding iterators of the triangulation data structure.