2D Triangulations

This chapter describes the two dimensional triangulations of CGAL. After a few definitions in section , the overall software design of the 2D triangulation package is described in section . The next sections present the different two dimensional triangulations classes available in CGAL : basic triangulations (section ), Delaunay triangulations (section ), regular triangulations (section ), constrained triangulations (section ), and Delaunay constrained triangulations (section ). At last, the section  described a hierarchical data structure for fast point location queries.

Definitions

Each facet of a triangulation can be given an orientation which in turn induces an orientation on the edges incident to that facet. The orientation of two adjacent facets 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 facet can be chosen in such a way that all pairs of incident facets have consistent orientations. The two-dimensional triangulations represented in CGAL are orientable triangulations embedded in a plane or in a higher dimensional space.

Strictly speaking, the term face should be used to design a face of any dimension, and the two-dimensional faces of a triangulation should be properly called facets. However, following a common usage, we hereafter often call faces, the facets of a two dimensional triangulation.

Software Design

Because a triangulation is merely a set of triangular faces with constant-size complexity, triangulations are not implemented as a layer on top of a planar map. CGAL uses a proper internal representation of triangulations based on faces and vertices rather than on edges. Such a representation saves storage space and results in faster algorithms  [BDuY00].

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 explicitly represented, they are only represented through the adjacency relations of two faces.

Figure:  The three-layer design of triangulations.

The triangulations in CGAL are represented by a three-layer structure analogous to the design used for polyhedral surfaces, see Figure .
The bottom layer is made of the base classes for vertices and faces. These base classes store some geometric informations such as the coordinate of vertices and any other attribute (such as a color, or boolean marks for constrained 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 makes easy the change of one of the base classes, to deal with an extra attribute like a color for example.
The second layer is the triangulation data structure which can be can be thought of as a container for faces and vertices and takes care of all the combinatorial aspects of the triangulation. The triangulation data structure restores strong type checking, implementing adjacency and incidence relations with type safe pointer operations. 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, the top layer, is the triangulation class which implements the user interface and is responsible for the geometric embedding of 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. Being responsible for the geometric embedding the triangulation class comes in different flavors according to the kind of triangulation represented: basic, Delaunay, regular, constrained or constrained Delaunay triangulations etc.

The triangulation classes of CGAL depend 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.

Basic Triangulations

Description

The class Triangulation_2<Traits,Tds> serves as a base class for all planar embedded two-dimensional triangulations in CGAL. This class expects a model of geometric traits class as first template argument and a model of triangulation data structure as second argument. The requirements for the geometric traits are described later in this section. The concept of triangulation data structure and some models for this concept are described in chapter . CGAL provides a default for the triangulation data structure template argument.

The class Triangulation_2<Traits,Tds> is designed to represent triangulations of a sets of points in the plane. Lets $$ A be a planar set of points. A triangulation of the set $$ A has vertices at the points of $$ A and its domain covers the convex hull of $$ A. It can be viewed as a planar partition of the plane whose 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 with only 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. In the following, we called infinite the infinite vertex and any face or edge incident to the infinite vertex. Any face or edge non incident to the infinite vertex as well as any vertex different from the infinite vertex is said to be finite. 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.

Figure:  The infinite vertex.

A triangulation is represented as a collection of vertices and faces that are linked together through incidence and adjacency relations. Each face gives access to its three incident vertices and to its three adjacent faces. Each vertex gives 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.

The edges are only implicitly represented through the adjacency relations between their two incident faces. Each edge has two implicit representations : the edge of a face f which is opposed to the vertex indexed i, can be represented as well as an edge of the neighbor(i) of f.

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

Figure:  Vertices and neighbors.

The vertices and faces of the triangulations are accessed through handles¹, iterators and circulators. Handles are used whenever the accessed element is not part of a sequence, iterators and circulators are used to visit parts of the triangulation.

The triangulation class offers some iterators to visit all the (finite or infinite) faces, edges or vertices and also iterators to visit all the finite faces, edges or vertices. The triangulation offers circulators to visit the edges or faces incident to a given vertex or the vertices adjacent to it. It also provides a circulator type to visit all the faces traversed by a given line. Circulators step through infinite features as well as through finite ones. The iterators and circulators are all bidirectional and non mutable. The circulators and iterators are assignable to the corresponding handle types. When calling a member function, any handle type argument can be replaced by an iterator or a circulator with the same value type.

The triangulation class provides methods to test the infinite character of any feature, and also methods to test the presence in the triangulation of a particular feature (edge or face) given its vertices.

The triangulation class provides a method to locate a given point with respect to a triangulation. In particular, this method reports wether the point coincides with a vertex of the triangulation, lies on an edge, in a face or outside of the convex hull. In case of a degenerate lower dimensional triangulation, the query point may also lie outside the triangulation affine hull.

The triangulation class also provides methods to locate a point with respect to a given finite face of the triangulation or with respect to its circumcircle. The faces of the triangulation and their circimcircles have the counterclockwise orientation.

The triangulation can be modified by several functions : insertion of a point, removal of a vertex, flipping of an edge. The flipping of an edge is possible when the union of the two incident faces forms a convex body (see Figure ).

Figure:  Flip.

Implementation

Locate is implemented by a line walk. The walk begins at a vertex of the face which is given as an optional argument or at an arbitrary vertex of the triangulation if no optional argument 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. The class Triangulation_hierarchy_2<Traits,Tds>, described in section , implements a data structure designed to offer an alternate more efficient point location algorithm.

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 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 a time at most proportionnal to d^2, where 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.

Geometric Traits

The first template parameter of the triangulation classes of CGAL is a geometric traits class. This parameter has to be instanciated by a model of the concept TriangulationTraits_2 described of the reference manual. The geometric traits class is required to provide the geometric objects (points, segments and triangles) building up the triangulation together with the geometric predicates on those objects. The required predicates are:
- comparison of the x or y coordinates of two points.
- orientation tests providing CGAL_orientation corresponding to the order type of three given point.

The CGAL kernel classes Homogeneous<Nt> and Cartesian<Nt>, templated by the number type Nt are models of the concept TriangulationTraits_2.

The CGAL library provides other models of TriangulationTraits_2 using the kernel geometric objects and predicates. These classes are themselves templated with a representation class. The traits class Triangulation_euclidean_traits_2<R> is designed to deal with ordinary two dimensional points. The class Triangulation_euclidean_traits_xy_3<R> is a geometric traits class to build the triangulation of a terrain. Such a triangulation is a two-dimensional triangulation embedded the three-dimensional space. The data points are three-dimensional points. The triangulation is build according to the projections of those points on the $$xy plane and then lifted up to the original three-dimensional data points. This is the usual case when dealing with GIS terrains. Instead of really projecting the three-dimensional points and maintaining a mapping between each point and its projection (which costs space and is error prone), the traits class supplies geometric predicates that ignore the z-coordinates of the points. CGAL provides also the geometric traits classes Triangulation_euclidean_traits_yz_3<R> and Triangulation_euclidean_traits_zx_3<R> to deal with projections on the xz plane and yz-plane, respectively.

Example of a Basic Triangulation

The following program creates a triangulation of 2D points using the kernel model class CGAL::Cartesian<double> as geometric traits and the default triangulation data structure template parameter. The input points are read from a file and inserted in the triangulation. Finally points on the convex hull are written to cout.

// file          : examples/Triangulation_2/triangulation_prog1.C
#include <CGAL/basic.h>
#include <fstream>

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

typedef CGAL::Cartesian<double> Gt;
typedef CGAL::Triangulation_2<Gt> Triangulation;
typedef Triangulation::Vertex_circulator Vertex_circulator;
typedef Gt::Point_2   Point;

int main() {
  std::ifstream in("data/triangulation_prog1.cin");
  std::istream_iterator<Point> begin(in);
  std::istream_iterator<Point> end;

  Triangulation t;
  t.insert(begin, end);
    
  Vertex_circulator vc = t.incident_vertices(t.infinite_vertex()),
    done(vc);
  if (vc != 0) {
    do { std::cout << vc->point() << std::endl;
    }while(++vc != done);
  }
  return 0;
}

Delaunay Triangulations

Description

A Delaunay triangulation is a special triangulation of a set of points. So it is natural to derive the class Delaunay_triangulation_2<Traits,Tds> from the basic class Triangulation_2<Traits,Tds>. Like its base class, the Delaunay triangulation class is parametrized by two template parameters, the geometric traits Traits and the triangulation data structureTds. Just like the triangulation data structure of a basic triangulation, the triangulation data strucure of a Delaunay triangulation has to be a model of the concept TriangulationDataStructure_2. In contrast, because the concept of Delaunay triangulation relies on the notions of distance and empty circles, the geometric traits has to be a model of the concept DelaunayTriangulationTraits_2 which refines the concept TriangulationTraits_2.

The class Delaunay_triangulation_2<Traits,Tds> inherits the types defined by the basic class Triangulation_2<Traits,Tds>. Additionnal types, provided by the traits class, are defined to represent the dual Voronoi diagram.

The class Delaunay_triangulation_2<Traits,Tds> overwrite the member functions that insert a new point in the triangulation or or remove a vertex from it to maintain the Delaunay property. It also has a member function (Vertex_handle nearest_vertex(const Point& p)) to answer nearest neighbor queries and member functions to construct the elements (vertices and edges) of the dual Voronoi diagram.

Geometric traits

L

L

The CGAL kernel classes Homogeneous<Nt> and Cartesian<Nt>, and the class Triangulation_euclidean_traits_2<R> are models of the concept DelaunayTriangulationTraits_2 for the euclidean metric. CGAL also provides traits classes to deal with terrains, that are two dimensional triangulated surfaces embedded in the three dimensional space that have project on a two dimensional Delaunay triangulation. Namely, the traits classes Triangulation_euclidean_traits_xy_3<R>,
Triangulation_euclidean_traits_yz_3<R>, and
Triangulation_euclidean_traits_zx_3<R>
are to be used to build a a triangulated surface projecting on the Delaunay triangulation of respectively the xy, yz or zx projections of its vertices:
The requirements for the duality functions and nearest vertex queries are not yet satisfied by these last three classes.

Implementation

Removal calls the removal in the triangulation and then retriangulates the hole created in such a way that the Delaunay criterion is satisfied. Removal of a vertex of degree d takes time O(d^2). The degree $$d is O(1) for a random vertex in the triangulation.

After having performed a point location, the nearest neighbor of a point is found in time O(n) in the worst case, but in time O(1) for vertices distributed uniformly at random and any query point.

Example : a Delaunay Terrain

The following code creates a Delaunay triangulation with the usual Euclidean metric for the vertical projection of a terrain model. The points have elevation, that is they are 3D points, but the predicates used to build the Delaunay triangulation are computed using only the $$x and $$y coordinates of these points.

// file          : examples/Triangulation_2/terrain.C
#include <CGAL/Homogeneous.h>
#include <fstream>
#include <CGAL/Gmpz.h>
#include <CGAL/Triangulation_euclidean_traits_xy_3.h>
#include <CGAL/Delaunay_triangulation_2.h>

typedef CGAL::Homogeneous<CGAL::Gmpz>  Rp;
typedef CGAL::Triangulation_euclidean_traits_xy_3<Rp>  Gt;
typedef CGAL::Delaunay_triangulation_2<Gt> Delaunay;

typedef Rp::Point_3   Point;

int main()
{
  std::ifstream in("data/terrain.cin");
  std::istream_iterator<Point> begin(in);
  std::istream_iterator<Point> end;

  Delaunay dt;
  dt.insert(begin, end);
  return 0;
}

Example : Voronoi Diagram

// file          : examples/Triangulation_2/voronoi.C
#include <CGAL/basic.h>
#include <fstream>

#include <CGAL/Cartesian.h>
#include <CGAL/Delaunay_triangulation_2.h>

typedef double coord_type;
typedef CGAL::Cartesian<coord_type>  Gt;
typedef CGAL::Delaunay_triangulation_2<Gt>  Triangulation;
typedef Triangulation::Edge_iterator  Edge_iterator;

int main( )
{
  std::ifstream in("data/voronoi.cin");
  std::istream_iterator<Gt::Point_2> begin(in);
  std::istream_iterator<Gt::Point_2> end;
  Triangulation T;
  T.insert(begin, end);

  int ns = 0;
  int nr = 0;  
  Edge_iterator eit =T.edges_begin();
  for ( ; eit !=T.edges_end(); ++eit) {
    CGAL::Object o = T.dual(eit);
    Gt::Segment_2 s;
    Gt::Ray_2     r;
    if (CGAL::assign(s,o)) {++ns;}
    if (CGAL::assign(r,o)) {++nr;}
  }
  std::cout << "The voronoi diagram as " << ns << "finite edges " 
	    << " and " << nr << " rays" << std::endl;
  return 0;
}
 

Regular triangulations

Description

The power diagram of the set $$ PW is a space partition in which each cell corresponds to a 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 in $$ PW. In the two-dimensional space, 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 form a subset of $$ P. Such a triangulation is called a regular triangulation. 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 with equal powers with respect to $$(p_i, w_i), $$(p_j, w_j) and $$(p_k, w_k) and such that this power is 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 is a face of the regular triangulation of $$ PW iff 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) and $$(p_k, w_k) is positive or null. We call power test of $$(p_i, w_i), $$(p_j, w_j), $$(p_k, w_k), and $$(p_l, w_l), 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) and $$(p_k, w_k). This predicate amounts to computing the sign of the following determinant

$$|

1	xi	yi	xi 2 + yi 2 - wi
1	xj	yj	xj 2 + yj 2 - wj
1	xk	yk	xk 2 + yk 2 - wk
1	xl	yl	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_i, w_i), $$(p_j, w_j), $$(p_k, w_k), and $$(p_l, w_l) 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 class Regular_triangulation_2<Traits, Tds> is designed to maintain the regular triangulation of a set of $$2d weighted points. The template parameters Traits and Tds stand respectively for a geometric traits class and a triangulation data structure class. The triangulation data structure has to be a model of the concept TriangulationDataStructure_2. The geometric traits class must provide a weighted point type and a power test on these weighted points and the concept for this parameter, called RegularTriangulationTraits_2, is a refinement of the concept TriangulationTraits_2. CGAL provides the class Regular_triangulation_euclidean_traits_2<Rep,Weight> which is a model for the traits concept RegularTriangulationTraits_2. The class Regular_triangulation_euclidean_traits_2<Rep,Weight> derives from the class Triangulation_euclidean_traits_2<Rep> and uses a Weighted_point type derived from the type Point_2 of Triangulation_euclidean_traits_2<Rep>.

The class Regular_triangulation_2<Traits, Tds> derives from the class Triangulation_2<Traits, Tds>. The functions insert and remove are overwritten to maintain the regular property. The vertices of the regular triangulation of a set of weighted points $$ PW form only a subset of the set of center points of $$ PW. Some of the input weigthed points have no cell in the dual power diagrams and therefore do not correspond to a vertex of the regular triangulation. Therefore the insertion of a weighted point in a regular triangulation does not necessarily imply the creation of a new vertex.

Regular triangulation have member functions to construct the vertices and edges of the dual power diagrams.

The Face Type of a Regular Triangulation

An input point that does not appear as a vertex in the regular triangulation is said to be hidden by the face in which the corresponding center point is located. A point which is hidden at a given time may appear later as a vertex of the regular triangulation if some other weighted points are removed. Therefore, hidden points have to be stored somewhere. A hidden point can appear as vertex of the triangulation only when the two dimensional face that hides it is removed from the triangulation. Therefore the hidden point are stored in the faces that hide them and the nested face type of a regular triangulation is assumed to include a list of hidden weighted points. This list of weighted point is in fact included in the base face of a regular triangulation.

Therefore the base face type of a regular triangulation is required to provide a list of weigthed points, designed to store the points hidden by the face. It has to be a model of the concept RegularTriangulationFaceBase_2. CGAL provides the templated class Regular_triangulation_face_base_2<Traits> as a default base class for faces of regular triangulations. This class derives from Triangulation_face_base_2<Traits>.

Example : a Regular Triangulation

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

// file example/Triangulation_2/regular.C
#include <CGAL/Cartesian.h>
#include <fstream>
#include <CGAL/Regular_triangulation_euclidean_traits_2.h>
#include <CGAL/Regular_triangulation_2.h>

typedef CGAL::Cartesian<double> Rp;
typedef double W;
typedef CGAL::Regular_triangulation_euclidean_traits_2<Rp,W>  Gt;
typedef CGAL::Regular_triangulation_2<Gt> Regular_triangulation;

int main()
{
   Regular_triangulation rt;
   std::ifstream in("data/regular.cin");

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

Constrained Triangulations

A constrained triangulation is a triangulation of a set of points that has to include among its edges a given set of segments joining the points. The corresponding edges are called constrained edges.

The endpoints of constrained edges are of course vertices of the triangulation. However the triangulation may include include other vertices as well. The set of constrained edges forms 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 or constrained edges with null length are allowed.

A constrained triangulation is represented in the CGAL library as an object of the class Constrained_triangulation_2<Traits,Tds>. The template parameter Traits stands for a geometric traits class that has to be a model of the concept TriangulationTraits_2. The template parameter Tds stands for a triangulation data structure class that has to be a model of the concept TriangulationDataStructure_2.

The class Constrained_triangulation_2<Traits,Tds> inherits from Triangulation_2<Traits,Tds>. It defines an additionnal type Constraint to represent the constraints. A constraint is represented as a pair of points.

A constrained triangulation can be created from a list of constrained edges. The class Constrained_triangulation_2<Traits,Tds> overrides the insertion and removal of a point to take care of the information about constrained edges. The class also allows inline insertion of a new constraint, given by its two endpoints or the removal of a constraint.

The Base Face of a Constrained Triangulation

CGAL provides a default base face class for constrained triangulations. This class, named Constrained_triangulation_face_base_2<Traits>, derives from the class Triangulation_face_base_2<Traits> and add three boolean to store the status of its edges.

Figure:  Constrained and Constrained Delaunay triangulation : the constraining edges are the green edges, a constrained triangulation is shown on the left, the constrained Delaunay triangulation with two examples of circumcircles is shown on the right.

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 iff the circumscribing circle of any facets encloses no vertex visible from the interior of the facet.

The CGAL class Constrained_Delaunay_triangulation_2<Traits,Tds> is designed to represent constrained Delaunay triangulations.

The class is templated by a geometric traits class Traits and a triangulation data structure Tds. The triangulation data structure has to be a model of the concept TriangulationDataStructure_2. The geometric traits of a constrained Delaunay triangulation is required to provide the side_of_oriented_circle test as the geometric traits of a Delaunay triangulation and has to a model of the concept DelaunayTriangulationTraits_2.

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2<Traits,Tds> derives from the class Constrained_triangulation_2<Traits,Tds>. Also, information about the status (constrained or not) of the edges of the triangulation has to be stored in the face class and the base face class of a constrained Delaunay triangulation has to be a model of ConstrainedFaceBase_2.

The constrained Delaunay triangulation has member functions to override the insertion and removal of a point or of a constraint. Each of those member function takes care to restore the constrained empty circle property.

Example : a constrained Delaunay triangulation

// file          : examples/Triangulation_2/constrained.C
#include <CGAL/basic.h>
#include <CGAL/Cartesian.h>
#include <fstream>
#include <list>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>

typedef double Coord_type;
typedef CGAL::Cartesian<Coord_type>  Gt;
typedef Gt::Point_2    Point;
typedef CGAL::Constrained_Delaunay_triangulation_2<Gt>  CDT;
typedef CDT::Constraint     Constraint;

int
main( )
{
  std::ifstream is("data/constrained.cin");
  std::list<Constraint> lc;
  int n;
  Point p,q;
  is >> n;
  std::cerr << "Reading " << n << " constraints" << std::endl;
  for(; n > 0; n--) {
    is >> p >> q;
    lc.push_back(std::make_pair(p,q));
  }

  CDT cdt(lc.begin(),lc.end());
  assert(cdt.is_valid());
  return 0;
}
  

The Triangulation Hierarchy

The class Triangulation_hierarchy_2<Tr> implements a triangulation augmented with a data structure to answer efficiently point location queries. The data structure is a hierarchy of triangulations. The triangulation at the lowest level is the original triangulation where operations and point location are to be performed. Then at each succedding level, the data structure stores a triangulation of a small random sample of the vertices of the triangulation at the preceeding level. Point location is done through a top down nearest neighbor query. The nearest neighbor query is first performed naively in the top level triangulation. Then, at each following level, the nearest neighbor at that level is found through a linear walk performed from the nearest neighbor found at the preceeding level. Because the number of vertices in each triangulation is only a small fraction of the number of vertices of the preceeding triangulation, the data structure remains small and achieves fast point location queries on real data. As proved in [Dev98], this structure has an optimal behaviour when it is built for Delaunay triangulations. However it can be used as well for other triangulations and the class Triangulation_hierarchy_2<Tr> is templated by a parameter which is to be instantiated by one of the CGAL triangulation classes. More precisely a triangulation hierarchy can be set for all two dimensional triangulations of CGAL except for regular triangulations.

The class Triangulation_hierarchy_2<Tr> inherits from the triangulation type passed as template parameter Tr. The insert and remove member functions are overwritten to update the data structure at each operation. The locate queries are also overwritten to take advantage of the data structure for a fast processing.

The Vertex of a Triangulation Hierarchy

CGAL provides the class Triangulation_hierarchy_vertex_base_2<Vb> which is a model for the concept TriangulationHierarchyVertexBase_2. This class is templated by a parameter Vb which is to be instantiated by a model of the concept TriangulationVertexBase_2. The class Triangulation_hierarchy_vertex_base_2<Vb> inherits from its template parameter Vb. This design allows to use for Vb either the default vertex base class or a user customized vertex base with additionnal functionalities.

Footnotes

1	A handle is a type which supports the two dereference operators operator* and operator->.