Definition

The class Delaunay_triangulation_2<Gt,Tds> is designed to represent the Delaunay triangulation of a set of points in a plane. A Delaunay triangulation of a set of points is a triangulation of the sets of points that fulfills the following empty circle property (also called Delaunay property): the circumscribing circle of each face does not contain any vertex. For a point set with no case of cocircularity of more than three points, the Delaunay triangulation is unique, it is the dual of the Voronoi diagram of the points.

A Delaunay triangulation is a special triangulation of a set of points. So it is natural to derive the class Delaunay_triangulation_2<Gt,Tds> from the basic class Triangulation_2<Gt,Tds>. The template parameters Gt and Tds stand respectively for a model of geometric traits and for a model of triangulation data structure. The requirements for the triangulation data structure are those described previously in section  and the same models can be used to instantiate the triangulation data structure of either a Triangulation_2<Gt,Tds> or a Delaunay_triangulation_2<Gt,Tds>. On the contrary, because the concept of Delaunay triangulation relies on the notions of empty circles and of distance, the geometric traits has to provide the side_of_oriented_circle predicate (which was only optional in the traits of plain triangulation), and also a Distance class. The additional requirements to be fulfilled by the geometric traits class of a Delaunay_triangulation_2<Gt,Tds> are described in subsection . Changing the Distance class and the side_of_oriented_circle predicate allows to build Delaunay triangulations for different metrics such that $$L₁ or $$L or any metric defined by a convex object. However, the user of an exotic metric must be carefull that the constructed triangulation has to be a triangulation of the convex hull which means that convex hull edges have to be Delaunay edges. This is granted for any smooth convex metric (like $$L₂) and can be ensured for other metrics (like $$L ) by the addition to the point set of well chosen sentinel points.

Inherits From

Triangulation_2<Gt,Tds>

Types

Inherits all the types of the Triangulation_2<Traits>. In addition to the types inherited from Triangulation_2<Gt,Tds> the class Delaunay_triangulation_2<Gt,Tds> defines a type for the distance object function, and some types to represent the dual Voronoi diagram.

typedef Gt::Distance
	Distance;
typedef Gt::Line	Line;
typedef Gt::Direction
	Direction;
typedef Gt::Ray	Ray;

Creation

Delaunay_triangulation_2<Gt,Tds> dt ( Gt gt = Gt());
	introduces an empty Delaunay triangulation dt.
Delaunay_triangulation_2<Gt,Tds> dt ( tr);
	Copy constructor. All the vertices and faces are duplicated.

Insertion and Removal

The following insertion and removal functions overwrite the functions inherited from the class Triangulation_2<Gt,Tds> to maintain the Delaunay property.

Vertex_handle	dt.insert ( Point p, Face_handle f=Face_handle())
		Inserts point p. If point p coincides with an already existing vertex, this vertex is returned and the triangulation is not updated. Optional parameter f is used to initialize the location of p.
Vertex_handle	dt.insert ( Point p, Locate_type& lt, Face_handle loc, int li)
		inerts a point p, the location of which is supposed to be given by (lt,loc,li), see the description of member function locate in class Triangulation_2<Gt,Tds>.
Vertex_handle	dt.push_back ( Point p)
		Equivalent to insert(p).
template < class InputIterator >
int	dt.insert ( InputIterator first, InputIterator last)
		inserts the points in the range $$[.first, last$$.). Returns the number of inserted points. Precondition: The value_type of first and last is Point.
void	dt.remove ( Vertex_handle v)
		removes the vertex from the triangulation.

Note that the other modifier functions of Triangulation_2<Gt,Tds> are not overwritten. Thus a call to insert_in_face insert_in_edge, insert_outside_convex_hull, insert_outside_affine_hull or flip on a valid Delaunay triangulation might lead to a triangulation which is no longer a Delaunay triangulation.

Queries

Vertex_handle	dt.nearest_vertex ( Point p, Face_handle f=Face_handle())
		returns any nearest vertex of p. The implemented function begins with a location step and f may be used to initialize the location.

Duality

Point	dt.dual ( Face_handle f)
		Returns the center of the circle circumscribed to face f. Precondition: f is not infinite
Object	dt.dual ( Edge e)	returns a segment, a ray or a line supported by the bisector of the endpoints of e. If faces incident to e are both finite, a segment whose endpoints are the duals of each incident face is returned. If only one incident face is finite, a ray whose endpoint is the dual of the finite incident face is returned. Otherwise both incident faces are infinite and the bisector line is returned.
Object	dt.dual ( Edge_circulator ec)
		Idem
Object	dt.dual ( Edge_iterator ei)
		Idem

Geometric Predicates

Oriented_side	dt.side_of_oriented_circle ( Face_handle f, Point p)
		Returns the side of p with respect to the circle circumscribing the triangle associated with f

Miscellaneous

The checking function is_valid() is also overwritten to additionally test the empty circle property.

bool	dt.is_valid ( bool verbose = false, int level = 0)
		Tests the validity of the triangulation as a Triangulation_2 and additionally test the Delaunay property. This method is mainly useful for debugging Delaunay triangulation algorithms designed by the user.

I/O

template < class Stream>
Stream&	dt.draw_dual ( Stream & ps)
		output the dual voronoi diagram to stream ps.

Example

The following code fragment 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 and the predicates which are defined in the Delaunay triangulation traits class forget about the $$z-coordinate of these points.

/*  terrain.C      */
/*  -------------- */
#include <CGAL/Homogeneous.h>
#include <CGAL/leda_integer.h>
#include <CGAL/Triangulation_euclidean_traits_xy_3.h>
#include <CGAL/Delaunay_triangulation_2.h>

using namespace CGAL;

typedef Homogeneous<leda_integer>  Rp;
typedef Triangulation_euclidean_traits_xy_3<Rp>  Terrain;
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 Delaunay_triangulation_2<Terrain, Tds> Delaunay;

int main()
{
    Delaunay dt(Terrain());

    Point_3<Rp> p;
    while(std::cin >> p){
        dt.insert(p);
    }
    return 1;    
}

Implementation

Insertion is implemented by inserting in the triangulation, then performing a sequence of Delaunay flips. The number of flips is O(d) if the new vertex is of degree d in the new triangulation. For points distributed uniformly at random, insertion takes time O(1) on average.

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

Nearest neighbor 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.