Triangulations

Introduction

A simplicial complex is a set $$C of simplices which satisfy 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 adjacence 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 or into TIN requires 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 edges are not explicitely represented, they are only represented through the adjacencies relations of two faces.

Figure:  The three layer design of triangulations.

The triangulations in CGAL are represented by a three layer structure analog to the design used for polyhedral surfaces, see Figure . In the bottom layer, 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 in the bottom layer 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 strong type checking is reestablished in the next layer 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 layer, the triangulation class implements the user interface with the triangulation. This classes offer 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 layer 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 or 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 of the plane whoses bounded faces are triangular. and cover the convex hull of $$ A. The single unbounded face of this partition is the complementary of the convex hull of $$ A. In many applications, such as Kirkpatrick's hierarchy or incremental Delaunay construction, 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.

Figure:  The infinite vertex.

The class 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 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 $$i is opposite to the vertex with the same index.

Many of the classes in the triangulation package 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.

Figure:  Vertices and neighbors.

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.

Figure:  Validity test.

• Class declaration of 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 Triangulation_2<Gt, Tds> has to fulfill. The second subsection presents some predefined geometric traits classes available in CGAL.

Requirements for the Geometric Traits Class

• Class declaration of Geom_traits.

Predefined Geometric Traits Classes

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

• Class declaration of Triangulation_euclidean_traits_2<R>.

• Class declaration of Triangulation_euclidean_traits_xy_3<R>.

CGAL provides also predefined geometric traits class Triangulation_euclidean_traits_yz_3<R> and 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 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 in 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 exists 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 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 Cartesian<double> Rp;
typedef Triangulation_euclidean_traits_2<Rp> Gt;
typedef Triangulation_vertex_base_2<Gt> Vb;
typedef Triangulation_face_base_2<Gt> Fb;
typedef Triangulation_default_data_structure_2<Gt,Vb,Fb > Tds;
typedef Triangulation_2<Gt,Tds> Triangulation;

Example

/*  colored_face.C   */     
/*  ---------------- */
#include <CGAL/basic.h>
#include <CGAL/Cartesian.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>

using namespace CGAL;
using namespace std;

/* A facet with a color member variable. */
template < class Gt >
class My_face_base : public Triangulation_face_base_2<Gt>
{
public:
  Color color;
  My_face_base() :
    Triangulation_face_base_2<Gt>() {}
  My_face_base(void* v0, void* v1, void* v2) : 
    Triangulation_face_base_2<Gt>(v0,v1,v2) {}
  My_face_base(void* v0, void* v1, void* v2, void* n0, void* n1, void* n2) : 
    Triangulation_face_base_2<Gt>(v0,v1,v2,n0,n1,n2) {}
};

typedef Cartesian<double> Rp;
typedef Triangulation_euclidean_traits_2<Rp> Gt;
typedef Triangulation_vertex_base_2<Gt> Vb;
typedef My_face_base<Gt> Fb;
typedef Triangulation_default_data_structure_2<Gt,Vb,Fb > Tds;
typedef Triangulation_2<Gt,Tds> Triangulation;
typedef Triangulation::Face_handle Face_handle;
typedef Triangulation::Face_iterator Face_iterator;
typedef Triangulation::Vertex_handle Vertex_handle;
typedef Point_2<Rp>  Point;

int main() {
  Triangulation t;
  Point p;

  while (std::cin >> p){
    t.insert(p);
  }
  Face_iterator fc = t.faces_begin();
  while (fc != t.faces_end()) {
    fc->color = BLUE;
    ++fc;
  }
  return 1;
}

Delaunay Triangulations

The Class Delaunay_triangulation_2<Gt,Tds>

• Class declaration of 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 a side_of_oriented_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 Delaunay_geom_traits.

Requirements for the Line, Direction and Ray Classes

Each of the three classes Line, Direction and Ray must know the two others. In addition, the Line class is required to have the two following member functions:

• Class declaration of Line.

• Class declaration of Ray.

• 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=sqrt(w_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 defined the power product of two weighted points $$(p_i, w_i) and $$(p_j, w_j) as:

$$(p_i, w_i,p_j, w_j) = p_ip_j ² - w_i - w_j .

$$(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 $$(, ) 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): a 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) of $$ PW 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 the weighted point $$(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	xj 2 + yj 2 - wj	xk 2 + yk 2 - wk	xl 2 + yl 2 -wl

|

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 convex hull of the set of three dimensional points $$ P'= { (p_i,p_i ² - w_i ), i = 1, ..., n }.

The Regular Triangulation Class

• Class declaration of Regular_triangulation_2<Gt, Tds>.

Example

The following code fragment creates a regular triangulation of a set of weighted points.

/*     regular.C */
/*-------------- */
#include <CGAL/basic.h>
#include <iostream>
#include <CGAL/Cartesian.h>
#include <CGAL/Regular_triangulation_euclidean_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>

using namespace CGAL;

typedef Cartesian<double> Rp;
typedef double W;
typedef Regular_triangulation_euclidean_traits_2<Rp,W>  Gt;
typedef Triangulation_vertex_base_2<Gt> Vb;
typedef Regular_triangulation_face_base_2<Gt> Fb;
typedef Triangulation_default_data_structure_2<Gt,Vb,Fb > Tds;
typedef Regular_triangulation_2<Gt, Tds> Regular_triangulation;

int main()
{
   Regular_triangulation rt;

   Gt::Weighted_point wp;
   while(std::cin >> wp){
     std::cout << wp << std::endl;
     rt.insert(wp);
   }
   rt.is_valid();
   return 1;	
}

The Base Face Type of a Regular Triangulation

Requirements for the Base Face Class of a Regular Triangulation

• Class declaration of Regular_face_base.

A Default Base Face Class for Regular Triangulations.

#include <CGAL/Regular_triangulation_face_base_2.h>

The Geometric Traits class of a Regular Triangulation

Requirements

• Class declaration of Regular_geom_traits.

A Predefined Geometric Traits Class

• Class declaration of 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 Constrained_triangulation_2<Gt,Tds>.

The Face Type of a Constrained Triangulation

• Class declaration of Constrained_face_base.

Of course CGAL provides a default Face_base class for the constrained triangulation. The class Constrained_triangulation_face_base_2<Gt> simply derived from Triangulation_face_base_2<Gt> and override the functions reorient(), ccw_permute() and cw_permute().

#include <CGAL/Constrained_triangulation_face_base_2.h>

A Constrained Triangulation Class for Animation Purposes

• Class declaration of Constrained_triangulation_demo_2<Gt,Tds>.

Constrained Delaunay Triangulations

A constrained Delaunay triangulation is a triangulation with constrained edges which tries to be as much Delaunay as possible. As constrained edges are not necessarily Delaunay edges, the triangles of a constrained Delaunay triangulation do not necessarily fulfill the empty circle property but they fulfill a weaker constrained empty circle property. To state this property, it is convenient to think of constrained edges as blocking the view. Then, a triangulation is constrained Delaunay if the circumscribing circle of any of its triangular faces includes in its interior no vertex that is visible from the interior of the triangle.

The Class Constrained_Delaunay_triangulation_2<Gt,Tds>

• Class declaration of Constrained_Delaunay_triangulation_2<Gt,Tds>.