The class Triangulation_2<Traits,Tds> is the basic class designed to handle triangulations of set of points in the plane.
Such a triangulation has vertices at the points of and its domain covers the convex hull of . It can be viewed as a planar partition of the plane whoses bounded faces are triangular and cover the convex hull of . The single unbounded face of this partition is the complementary of the convex hull of .
In many applications, it is convenient to deal only with triangular faces. Therefore, we add to the triangulation a fictitious vertex, called the infinite vertex and we make each convex hull edge incident to an infinite face having as third vertex the infinite vertex. In that way, each edge is incident to exactly two faces and special cases at the boundary of the convex hull are simpler to deal with.
The class Triangulation_2<Traits,Tds> implements this point of view and therefore considers the triangulation of the set of points as a set of triangular, finite and infinite faces. Although it is convenient to draw a triangulation as in figure , note that the infinite vertex has no significant coordinates and that no geometric predicate can be applied on it or on an infinite face.
A triangulation is a collection of vertices and faces that are linked together through incidence and adjacency relations. Each face give access to its three incident vertices and to its three adjacent faces. Each vertex give access to one of its incident faces.
The three vertices of a face are indexed with 0, 1 and 2 in counterclockwise order. The neighbor of a face are also indexed with 0,1,2 in such a way that the neighbor indexed by is opposite to the vertex with the same index.
The triangulation class offer two functions int cw(int i) and int ccw(int i) which given the index of a vertex in a face compute the index of the next vertex of the same face in clockwise or counterclockwise order. Thus, for example the neighbor neighbor(cw(i)) is the neighbor of f which is next to neighbor(i) turning clockwise around f. The face neighbor(cw(i)) is also the first face encountered after f when turning clockwise around vertex i of f (see Figure ).
Figure: Vertices and neighbors.
#include <CGAL/Triangulation_2.h>
The second parameter is the triangulation data structure, it has to be instantiated by a model of the concept TriangulationDataStructure_2. By befault, the triangulation data structure is instanciated by CGAL::Triangulation_data_structure_2 < CGAL::Triangulation_vertex_base_2<Gt>, CGAL::Triangulation_face_base_2<Gt> > >.
|
| the traits class. |
|
| |
the triangulation data structure type. | ||
| ||
| the point type | |
| ||
| the segment type | |
| ||
| the triangle type | |
| ||
| the vertex type. | |
|
| the face type. |
|
| the edge type. |
| ||
| Size type (an unsigned integral type) | |
| ||
| Difference type (a signed integral type) |
The vertices and faces of the triangulations are accessed through handles, iterators and circulators. The handles are models of the concept Handle which basically offers the two dereference operators * and ->. The iterators and circulators are all bidirectional and non mutable. The circulators and iterators are convertible to handles with the same value type, so that whenever a handle appear in the parameter list of a function, an appropriate iterator or circulator can be passed as well.
The edges of the triangulation can also be visited through iterators and circulators, the edge circulators and iterators are also bidirectional and non mutable.
In the following, we called infinite any face or edge incident to the infinite vertex and the infinite vertex itself. Any other feature (face, edge or vertex) of the triangulation is said to be finite. Some iterators (the All iterators ) allows to visit finite or infinite feature while others (the Finite iterators) visit only finite features. Circulators visit infinite features as well as finite ones.
| |
iterator over finite faces.
| |
| |
iterator over finite edges.
| |
| |
iterator over finite
vertices.
| |
| |
iterator over the points corresponding the
finite vertices of the triangulation.
| |
| |
circulator over all faces intersected by a line.
| |
| |
circulator over all faces incident to a given vertex.
| |
| |
circulator over all edges incident to a given vertex.
| |
| |
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.
| |||
The locate type is OUTSIDE_CONVEX_HULL when the point
is outside the convex hull but in the affine hull of the current triangulation. The locate type is OUTSIDE_AFFINE_HULL when the point is outside the affine hull of the current triangulation.
|
| |
default constructor.
| |
| |
Introduces an empty triangulation t.
| |
| |
Copy constructor. All the vertices and faces are duplicated.
After the copy, t and tr
refer to different triangulations :
if tr is modified, t is not.
|
|
| |
Assignement. All the vertices and faces are duplicated. After the assignement, t and tr refer to different triangulations : if tr is modified, t is not. | ||
|
| |
The triangulations tr and t are swapped. t.swap(tr) should be preferred to t = tr or to t(tr) if tr is deleted after that. | ||
|
| Deletes all faces and finite vertices resulting in an empty triangulation. |
|
| Destructor. All vertices and faces are deleted. |
|
| Returns a const reference to the triangulation traits object. |
| ||
| Returns a const reference to the triangulation data structure. |
advanced |
| ||
| Returns a reference to the triangulation data structure. |
This method is mainly a help for users implementing their own triangulation algorithms.
advanced |
The class Triangulation_2<Traits,Tds> provides methods to locate a given point with respect to a triangulation. It also provides methods to locate a point with respect to a given finite face of the triangulation.
|
| |||
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. If the point query lies outside the convex hull of the triangulation but in the affine hull, the returned face is an infinite face which is a proof of the point's location : - for a two dimensional triangulation, it is a face such that query lies to the left of the oriented line (the rest of the triangulation lying to the right of this line). - for a degenerate one dimensional triangulation it is the (degenarate one dimensional) face such that query and the triangulation lie on either side of p. If the point query lies outside the affine hull, the returned Face_handle is NULL. The optional Face_handle argument, if provided, is used as a hint of where the locate process has to start its search. | ||||
|
| |||
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. If lt==VERTEX the variable li is set to the index of the vertex, and if lt==EDGE li is set to the index of the vertex opposite to the edge. Be careful that li has no meaning when the query type is FACE, OUTSIDE_CONVEX_HULL, or OUTSIDE_AFFINE_HULL or when the triangulation is -dimensional. | ||||
|
| |||
Returns on which side of the oriented boundary of f lies
the point p. Precondition: f is finite. | ||||
|
| |||
Returns on which side of the circumcircle of face f lies the point p. The circle is assumed to be counterclockwisely oriented, so its positive side correspond to its bounded side. This predicate is available only if the corresponding predicates on points is provided in the geometric traits class. |
The following operations are guaranteed to lead to a valid triangulation when they are applied on a valid triangulation.
|
| |||
Exchanges 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. | ||||
|
| |||
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. At last, if p is outside the affine hull (in case of degenerate 1-dimensional or 0-dimensional triangulations), p is linked all the other vertices to form a triangulation whose dimension is increased by one. The last argument f is an indication to the underlying locate algorithm of where to start. | ||||
|
| |||
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.) | ||||
|
| |||
Equivalent to insert(p). | ||||
| ||||
|
| |||
Inserts the points in the range
first, last.
Returns the number of inserted points. Precondition: The value_type of InputIterator is Point. | ||||
|
| |||
Removes the vertex from the triangulation. The created hole is
retriangulated. Precondition: Vertex v must be finite. |
Figure: Insertion of a point on an edge.
Figure: Insertion outside the convex hull.
advanced |
|
| |
Inserts the first finite vertex . | ||
|
| |
Inserts the second finite vertex . | ||
|
| |
Inserts vertex v in face
f. Face f is modified,
two new faces are created. Precondition: The point in vertex v lies inside face f. | ||
|
| |
Inserts 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. | ||
|
| |
Inserts
a point which is outside the convex hull but in the affine hull. Precondition: The handle f points to a face which is a proof of the location ofp, see the description of the locate method above. | ||
|
| |
Inserts a point which is outside the affine hull. | ||
|
| |
Removes a vertex of degree three. Two of the incident faces are destroyed,
the third one is modified. Precondition: Vertex v is a finite vertex with degree three. | ||
|
| |
Removes the before last finite vertex. | ||
|
| |
Removes the last finite vertex. |
The following fonctions are mainly intended to be used in conjunction with the find_conflicts() member fonctions of Delaunay and constrained Delaunay triangulations to perform insertions.
| ||||
|
| |||
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[. Returns a handle to the new vertex. | ||||
| ||||
|
| |||
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. |
advanced |
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).
The following iterators allow respectively to visit finite faces, finite edges and 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.
| ||
| ||
Starts at an arbitrary finite vertex | ||
| ||
| ||
Past-the-end iterator | ||
| ||
| ||
Starts at an arbitrary finite edge | ||
| ||
| ||
Past-the-end iterator | ||
| ||
| ||
Starts at an arbitrary finite face | ||
| ||
| ||
Past-the-end iterator | ||
|
|
|
|
| Past-the-end iterator |
The following iterators allow respectively to visit all (finite or infinite) faces, edges and 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.
| ||
| ||
Starts at an arbitrary vertex | ||
| ||
| ||
Past-the-end iterator | ||
|
| |
Starts at an arbitrary edge | ||
|
| Past-the-end iterator |
|
| |
Starts at an arbitrary face | ||
|
| Past-the-end iterator |
The triangulation defines a circulator that allows to visit all faces that are intersected by a line. A face f is considered has being intersected by the oriented line l if either:
| ||||
| ||||
This function returns a circulator that allows to visit the
faces intersected by the line pq.
If there is no such face the circulator has a singular value. The starting point of the circulator is the face f, or, if f is omitted, the first finite face traversed by l. The circulator wraps around the infinite_vertex : after the last traversed finite face, it steps through the infinite face adjacent to this face then through the infinite face adjacent to the first traversed finite face then through the first finite traversed face again. Precondition: Points p and q must be different points. Precondition: If f != NULL, the point p must be inside or on the boundary of f. |
Figure illustrates which finite faces are enumerated. Lines and have no face to their left. Lines and have faces to their left. Note that the finite faces that are only vertex incident to lines and are not enumerated.
Figure: The line face circulator.
A line face circulator is invalidated if the face the circulator refers to is changed.
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 circulators are non-mutable and bidirectional. The operator++ moves the circulator counterclockwise around the vertex while the operator-- moves clockwise. A face circulator is invalidated 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.
|
| |
Starts at an arbitrary face incident to v. | ||
|
| |
Starts at face f. Precondition: Face f is incident to vertex v. | ||
|
| |
Starts at an arbitrary edge incident to v. | ||
|
| |
Starts at the the first edge of f incident to
v, in counterclockwise order around v. Precondition: Face f is incident to vertex v. | ||
|
| |
Starts at an arbitrary vertex incident to v. | ||
|
| |
Starts at the first vertex of f adjacent to v
in counterclockwise order around v. Precondition: Face f is incident to vertex v. |
Applied on the infinite_vertex the above functions allow to visit the vertices on the convex hull and 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.
|
| |||
|
| |||
|
| |||
|
| |||
|
| |||
|
|
|
|
Returns modulo 3. Precondition: . |
|
|
Returns modulo 3. Precondition: . |
|
| |
Returns the triangle formed by the three vertices of f. Precondition: The face is finite. | ||
|
| |
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. | ||
|
| |
Returns the line segment corresponding to edge e. Precondition: e is a finite edge | ||
|
| |
Returns the line segment corresponding to edge *ec. Precondition: *ec is a finite edge. | ||
|
| |
Returns the line segment corresponding to edge *ei. Precondition: *ei is a finite edge. | ||
|
| |
Compute the circumcenter of the face pointed to by f. This function is available only if the correspoding function is provided in the geometric traits. |
advanced |
|
|
|
| |
Checks 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. |
advanced |
The I/O operators are defined for iostream. The format for the iostream is an internal format.
|
|
Inserts the triangulation t into the stream os. Precondition: The insert operator must be defined for Point. |
|
|
Reads a triangulation from stream is and assigns it
to t. Precondition: The extract operator must be defined for Point. |
The information ouput in the iostream is:
- the dimension, the number of vertices (including the infinite one),
and the number of faces (including infinite ones).
- for each vertex (except the infinite vertex),
the non combinatorial information stored in that vertex
(point, etc.).
- for each faces, the indices of its vertices and
the non combinatorial information (if any) in this face.
- for each face again
the indices of the neighboring faces.
The index of an item (vertex of face) is
the rank of this item in the ouput order.
When dimension 2, the same information is ouput
for faces of maximal dimension instead of faces.
CGAL also provides stream operators << to draw triangulations
on CGAL::Window_stream, the LEDA based graphic package,
and on CGAL::Qt_widget, the Qt based graphic package.
These operators requires respectively the include statements :
#include CGAL/IO/Window_stream.h
#include CGAL/IO/Qt_widget_Triangulation_2.h
See the chapters on Window_stream and on Qt_widget in
the Support Library manual.
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, the triangulation is restored by flips. Apart from the location, insertion takes a time time O(1). This bound is only an amortized bound 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 on finite features are derived from their counterparts visiting all (finite and infinite) features which are themselves derived from the corresponding iterators of the triangulation data structure.