Triangulations

Introduction

A simplicial complex is a set $$C of simplices which satisfies two conditions:

1. Any face of a simplex in $$C is also a simplex in $$C
2. Two simplices in $$C either do not intersect or their intersection is a simplex of smaller dimension which is their common face of maximal dimension.

A triangulation is a 2-dimensional simplicial complex which is pure connected and without singularities. Thus a triangulation can be viewed as a collection of triangular faces, such that two faces either have an empty intersection or share an edge or a vertex. The absence of singularities means that each edge belongs to at most two triangles and that each vertex belongs to a set of faces whose union forms a topological disk.

Each face of a triangulation can be given an orientation (clockwise or counterclockwise) which in turn induces an orientation on the edges incident to that face. The orientation of two adjacent faces are said to be consistent if they induce opposite orientations on their common incident edge. A triangulation is said to be orientable if the orientation of each face can be chosen in such a way that all pairs of incident faces have consistent orientations.

In this chapter we present a framework to represent orientable triangulations which may be embedded in a plane or in a higher dimensional space. Examples of such triangulations are triangulations of a simple polygons in the plane, the Delaunay triangulations of points in the plane, or triangulated irregular networks (Tins) which are used as terrain model in Gis. Any such triangulation can be described as a set of vertices and triangular faces, with incidence and adjacency relations: two facets or two vertices are said to be adjacent (or neighboring) if they are incident to the same edge, a facet and a vertex are said to be incident if they are incident to the same edge.

On top of this abstract view of a triangulation come different geometric layers which define the geometric information associated to a vertex (e.g., two-dimensional points for triangulations in the plane, or three-dimensional points for Tins) or to a face, and which define the functionality of the triangulation. For example, the insertion of a point into a Delaunay triangulation and insertion into Tin require different update steps.

Design Rationale

Thus the basic elements of the representation are vertices and faces. Each triangular face gives access to its three incident vertices and to its three adjacent faces. Each vertex gives access to one of its incident faces, and through that face to the circular list of its incident faces.

The triangulations in CGAL are represented by a three level structure analogous to the design used for polyhedral surfaces, see Figure [ref:I1_Fig_three_levels]. At the bottom level, the base classes for vertices and faces store some geometric informations such as the coordinate of vertices and any other attribute (such as color, constraint edges etc.) needed by the application. The base classes handle incidence and adjacency relations in term of void* pointers. The use of void* pointers at the bottom level allows to easily change one of the base class, to deal with an extra attribute like a color for example, without having to change the rest of the structure. The advantages of stong type checking is reestablished at the next level where the triangulation data structure can be thought of as a container for faces and vertices which can take care of all the combinatorial aspects of the triangulation. The triangulation data structure implements adjacency and incidence relations with type safe pointer operations and maintains the combinatorial integrity of the triangulation. For that purpose, the triangulation data structure defines its own face and vertex classes which are derived from the corresponding base classes so that geometric and additional information on vertices and faces are simply inherited. At last, at the top level, the triangulation class implements the user interface with the triangulation. This class offers to the user the high level functionalities that can be expected from a triangulation: insertion or removal of a vertex, traversal of the faces, enumeration of the vertices, traversal of the faces incident to a given vertex, location of a given point etc. The triangulation class defines its own vertex and face classes derived from the corresponding class of the triangulation data structure. The vertices and faces of the triangulation class are only accessed through high levels concepts such as handles, iterators, or circulators, according to the required functionalities of the access. The top level triangulation class is responsible for the geometric embedding of the triangulation and comes in different flavors according to the kind of triangulation represented: planar triangulation of a set of points, Delaunay, regular, or constrained triangulations etc.

The triangulation classes of CGAL depends on two template parameters. The first template parameter stands for a geometric traits class which is assumed to provide the geometric objects (points, segments and triangles) forming the triangulation and the geometric predicates on those objects. The second template parameter stands for a model of triangulation data structure acting as a container for faces and vertices while taking care of the combinatorial aspects of the triangulation. The triangulation data structure class is itself a template class parametrized by the base classes for faces and vertices.

Organization of this chapter

Triangulation of points in the plane

The basic triangulation class of CGAL is primarily designed to represent the triangulations of a set of points $$A in the plane. Such a triangulation has as its vertices the points of $$A and its domain covers the convex hull of $$A. It can be viewed as a planar partition whoses bounded faces are triangular and cover the convex hull of $$A. The single unbounded face in this partition has the convex hull boundary as frontier. In many applications, such as Kirkpatrick's hierarchy or incremental Delaunay construction, it is convenient to deal only with triangular faces. Therefore, we let each convex hull edge be incident to an infinite face having as third vertex an auxiliary vertex called 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 CGAL_Triangulation_2<Gt,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 the above 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 conterclockwise order. The neighbor of a face are also indexed with 0,1,2 in such a way that the neighbor indexed by $i$ is opposite to the vertex with the same index.

Many of the CGAL triangulation classes 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. These functions do not depend on the actual object of the class, and they are implemented by static member functions. Thus, for example the neighbor f.neighbor(cw(i)) is the neighbor of f which is next to f.neighbor(i) turning clockwise around f. The face f.neighbor(f.cw(i)) is also first face encountered after f when turning clockwise around vertex i of f.

A triangulation is valid from the combinatorial point of view if the following is true.

(a) Two adjacent faces have neighbor pointers to each other and they have two vertices in common. The faces have a coherent orientation, that is, they index their common vertices in opposite order.

(b) All faces that are incident to a vertex v must be linked with neighbor pointers. Vertex v points to an arbitrary incident face.

Furthermore, it is said to be geometrically valid iff

(c) Any face has its vertices indexed according to counterclockwise order.

• Class declaration of CGAL_Triangulation_2<Gt,Tds>.

• Class declaration of Vertex.

• Class declaration of Face.

The geometric traits class

The first template parameter of the triangulation classes of CGAL is the geometric traits class which provides the geometric objects (points, segments and triangles) building up the triangulation together with the geometric predicates on those objects. The first subsection of this section describes the requirements that the geometric traits class of the basic triangulation class CGAL_Triangulation_2<Gt, Tds> has to fulfill. The second subsection presents some predefined geometric traits classes available in CGAL and provides some examples of their use.

Requirements for the geometric traits class

• Class declaration of Geom_traits.

Predefined Geometric Traits Classes

The CGAL library provides some predefined geometric traits class for the triangulations using the kernel geometric objects and predicates. These classes are themselves templated with a representation class.

• Class declaration of CGAL_Triangulation_euclidean_traits_2<R>.

• Class declaration of CGAL_Triangulation_euclidean_traits_xy_3<R>.

CGAL provides also predefined geometric traits classes CGAL_Triangulation_euclidean_traits_yz_3<R> and CGAL_Triangulation_euclidean_traits_zx_3<R> to deal with projections on the xz- or the yz-plane, respectively.

#include <CGAL/Triangulation_euclidean_traits_xz_3.h>
#include <CGAL/Triangulation_euclidean_traits_yz_3.h>

The Triangulation Data Structure

The second template parameter of the basic triangulation class CGAL_Triangulation_2<Gt,Tds> is a triangulation data structure class. This class can be seen has a container for the faces and vertices maintaining incidence and adjacency relations. The triangulation data structure class is responsible for the combinatorial integrity of the triangulation (i.e. proper incidence and adjacency relations among vertices and faces) while allowing to perform combinatorial modifications such has insertion of a new vertex in a face, or on an edge, suppression of a vertex of degree three, flip of two edges. (The term combinatorial means that those operation are purely topological and do not depend on the geometric embedding.)

The triangulation data structure is itself a template class parametrized by the base classes Vertex_base and Face_base, and derives from thoses base classes its own vertex and face classes. This design allows to restore at the triangulation data structure level the strong type checking which does not exist at the base classes levels.

The following subsections list the requirements for a triangulation data structure and for its nested vertex and face classes. The default triangulation data structure provided by CGAL is describe next.

Requirements for a Triangulation Data Structure Class

• Class declaration of Tds<Vb,Fb>.

Requirements for the Vertex Class of a Triangulation Data Strucure

• Class declaration of Tds::Vertex.

Requirements for the Face Class of a Triangulation Data Structure

• Class declaration of Tds::Face.

The Default Triangulation Data Structure

• Class declaration of CGAL_Triangulation_default_data_structure_2<Tds_gt,Vb,Fb>.

The Base Classes Vertex_base and Face_base

Requirements for the Vertex_base Class

• Class declaration of Vertex_base.

Requirements for the Face_base Class

• Class declaration of Face_base.

The Default Base Classes

These default base classes can be used directly or can serve as a base to derive other base classes with some additional attribute (a color for example) tuned for a specific application.

#include <CGAL/Triangulation_face_base_2.h>
#include <CGAL/Triangulation_vertex_base_2.h>

Examples

Example

typedef CGAL_Cartesian<CGAL_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<Gt,Tds> Triangulation;

Example

/*  Triangulation_with_colored_face.C     */
/*  ----------------------------------- */
#include <CGAL/basic.h>
#include <CGAL/IO/Color.h>
#include <CGAL/Triangulation_euclidean_traits_2.h>
#include <CGAL/Triangulation_default_data_structure_2.h>
#include <CGAL/Triangulation_2.h>


/* A facet with a color member variable. */
template < class Gt >
My_face_base<Gt> : public CGAL_Triangulation_face_base_2<Gt>
{
public:
    CGAL_Color color;
};

typedef CGAL_Cartesian<CGAL_Rational> Rep;
typedef CGAL_Triangulation_euclidean_traits_2<Rep> Gt;
typedef CGAL_Triangulation_vertex_base_2<Gt> Vb;
typedef CGAL_My_face_base_2<Gt> Fb;
typedef CGAL_Triangulation_default_data_structure_2<Gt,Vb,Fb > Tds;
typedef CGAL_Triangulation_2<Gt,Tds> Triangulation;
typedef Triangulation::Face_handle Face_handle;
typedef Triangulation::Face_iterator Face_iterator;
typedef Triangulation::Vertex_handle Vertex_handle;

int main() {
    Triangulation t;
    Point p;
   
    while (cin >> p){
        t.insert(p);
    }
    Face_iterator fc = t.faces_begin();
    while (fc != t.faces_end)
	fc->color = CGAL_BLUE;

    cin >> p;
    Face_handle fh = t.locate(p);
    fh->color = CGAL_RED;
}

Delaunay Triangulations

The Class CGAL_Delaunay_triangulation_2<Gt,Tds>

• Class declaration of CGAL_Delaunay_triangulation_2<Gt,Tds>.

Requirements for the Geometric Traits of a Delaunay Triangulation

In addition to the requirements described in section  for the geometrics traits of any triangulation, the geometrics traits of a Delaunay triangulation has to provide an in_circle test and some additional types. The in_circle test is the test used to maintain the empty circle property and actually defines the triangulation. The additional types Line, Direction and Ray are used to describe the dual Voronoi diagram. The additional Distance type is only used by the nearest_vertex(..) query and the requirements for this type are given below.

• Class declaration of Geom_traits.

• Class declaration of Distance<Gt>.

Predefined Geometric Traits Class

Regular triangulations

Let $$PW = {(p_i, w_i), i = 1, ..., n } be a set of weighted points where each $p$_i is a point and each $w$_i is a scalar called the weight of point $p$_i. Alternatively, each weighted point $(p$_i, w_i) can be regarded as a two dimensional sphere with center $p$_i and radius $r$_i.

The power diagram of the set $$PW is a planar partition such that each cell corresponds to sphere $(p$_i, w_i) of $$PW and is the locus of points $p$ whose power with respect to $(p$_i, w_i) is less than its power with respect to any other sphere $(p$_j, w_j) in $$PW. The dual of this diagram is a triangulation whose domain covers the convex hull of the set $$P= { p_i, i = 1, ..., n } of center points and whose vertices are a subset of $$P. Such a triangulation is called a regular triangulation. The three points $p$_i, p_j and $p$_k of $$P form a triangle in the regular triangulation of $$PW iff there is a point $p$ of the plane whose powers with respect to $(p$_i, w_i), $(p$_j, w_j) and $(p$_k, w_k) are equal and less than the power of $p$ with respect to any other sphere in $$PW.

Let us define the power product of two weighted points $(p$_i, w_i) and $(p$_j, w_j) as: $\Pi (p$_i, w_i,p_j, w_j) = p_ip_j ² - w_i ² - w_j ² . $\Pi (p$_i, w_i,p_j, 0) is simply the power of point $p$_j with respect to the sphere $(p$_i, w_i), and two weighted points are said to be orthogonal if their power product is null. The power circle of three weighted points $(p$_i, w_i), $(p$_j, w_j) and $(p$_k, w_k) is defined as the unique circle $(pi,\; \omega )$ orthogonal to $(p$_i, w_i), $(p$_j, w_j) and $(p$_k, w_k).

The regular triangulation of the sets $$PW satisfies the following regular property (which just reduces to the Delaunay property when all the weights are null): Any triangle $p$_ip_jp_k of the regular triangulation of $$PW is such that the power product of any weighted point $(p$_l, w_l) with the power circle of $(p$_i, w_i), $(p$_j, w_j) is $(p$_k, w_k) is positive or null. We call power test of points $(p$_l, w_l) with respect to the face $p$_ip_jp_k, the predicates which amount to compute the sign of the power product of $(p$_l, w_l) with respect to the power circle of $(p$_i, w_i), $(p$_j, w_j) is $(p$_k, w_k), which is given by the following determinant $|$

1	1	1	1
xi	xj	xk	xl
yi	yj	yk	yl
xi 2 + yi 2 -wi 2	xj 2 + yj 2 - wj 2	xk 2 + yk 2 - wk 2	xl 2 + yl 2 -wl 2

|

A pair of neighboring faces $p$_ip_jp_k and $p$_ip_jp_l is said to be locally regular (with respect to the weights in $$PW) if the power test of $(p$_l,w_l) with respect to $p$_ip_jp_k is positive. A classical result of computational geometry establishes that a triangulation of the convex hull of $$P such that any pair of neighboring faces is regular with respect to $$PW, is a regular triangulation of $$PW.

Alternatively, the regular triangulation of the weighted points set $$PW can be obtained as the projection on the two dimensional plane of the set of three dimensional points $$P'= { (p_i,p_i ² - w_i ²), i = 1, ..., n }.

The Regular Triangulation Class

• Class declaration of CGAL_Regular_triangulation_2<Gt, Tds>.

Example

#include <CGAL/Cartesian.h>
#include <CGAL/Weighted_point_2.h>
#include <CGAL/Regular_triangulation_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>
#include <CGAL/IO/Geomview_stream.h>

typedef CGAL_Cartesian<double> Rep;
typedef double Weight_type;
typedef CGAL_Weighted_point_2<Rep,Weight_type> Weighted_point
typedef CGAL_Regular_triangulation_traits_2<Rep>  Gt;
typedef CGAL_Triangulation_vertex_base_2<Gt> Vb;
typedef CGAL_regular_triangulation_face_base_2<Gt> Fb;
typedef CGAL_Triangulation_default_data_structure_2<Gt,Vb,Fb > Tds;
typedef CGAL_Regular_triangulation_2<Gt, Tds> Regular_triangulation;

{
   Regular_triangulation rt;

    Weighted_point wp;
    while(cin >> wp){
        rt.insert(wp);
    }
    CGAL_Geomview_stream gs;
    gs << rt;
}

The Geometric Traits class of a Regular Triangulation

Requirements

• Class declaration of Geom_traits.

A Predefined Geometric Traits Class

• Class declaration of CGAL_Regular_triangulation_traits_2<Rep,Weight>.

Weighted Points

requirements for a weighted-point

• Class declaration of Weighted_point.

Default Class for a Weighted Point

Constrained triangulations

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 corresponding edges are called constrained edges.

The set of points defining the vertices of the triangulation includes the set of constrained edges endpoints. It may include other points (considered as null length constrained edges) as well. The set of constrained edges forms a set of segments which do not intersect except possibly at their endpoints. Any number of constrained edges are allowed to share the same endpoint. Vertical constrained edges or constrained edges with null length are allowed.

• Class declaration of CGAL_Constrained_triangulation_2<Gt,Tds>.

The Face Type of a Constraint Triangulation

• Class declaration of Face_base.

Of course CGAL provides a default Face_base class for the constrained triangulation. The class CGAL_Constrained_triangulation_face_base_2<Gt> simply derived from CGAL_Triangulation_face_base_2<Gt>.

#include <CGAL/Constrained_triangulation_face_base_2.h>

A Constrained Triangulation Class for Animation Purposes

• Class declaration of CGAL_Constrained_triangulation_2_demo<T>.