A Delaunay triangulation is a special triangulation of a set of points.
So it is natural to derive the class
CGAL_Delaunay_triangulation_2<Gt,Tds> from the basic class
CGAL_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
CGAL_Triangulation_2<Gt,Tds> or a
CGAL_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 is required to
provide some additional predicates namely the famous in_circle
test and also a Distance class. The additional requirements to be
fulfilled by the geometric traits class of a
CGAL_Delaunay_triangulation_2<Gt,Tds> are described in
subsection
. Changing the
Distance class and the in_circle test allows to build Delaunay
triangulation for different metrics such that
or 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 ) and can be ensured for other metrics
(like ) by the addition to the point
set of well chosen sentinel points.
Inherits all the types of the CGAL_Triangulation_2<Traits> . In addition, we need a type for the distance object function, and some types to represent the geometric dual features.
| ||
|
||
|
|
|
| ||
|
||
|
|
| |||
Introduces an empty Delaunay triangulation dt.
| |||
| |||
Introduces a Delaunay triangulation dt that is initialized
with the vertices and faces that are linked to vertex v. If
v has no incident face the triangulation consists only of
v. Otherwise v must be the vertex at infinity.
|
The following insertion and removal functions overwrite the functions inherited from the class CGAL_Triangulation_2<Gt,Tds> to maintain the Delaunay property.
|
| |||
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 initialized the location. | ||||
|
| |||
Same as above. Additionally, parameter lt describes where point p was located before updating the triangulation. | ||||
|
| |||
Equivalent to insert(p). | ||||
| ||||
|
| |||
Inserts the points in the range first,
last. Returns the number of inserted points.
Precondition: The value_type of first and last is Point. | ||||
|
| |||
Removes the vertex from the triangulation. |
Note that the other modifier functions of CGAL_Triangulation_2<Gt,Tds> are not overwritten. Thus a call to insert_in_face insert_in_edge, insert_outside or flip on a valid Delaunay triangulation might lead to a valid triangulation which is no longer a Delaunay triangulation.
|
| |||
Returns any nearest vertex of p. The implemented function begins with a location step and f may be used to initialize the location. |
|
| |
Returns the center of the circle circumscribed to face f.
Precondition: f is not infinite | ||
|
| If both incident faces are finite, returns a segment whose endpoints are the duals of each incident face. If only one incident face is finite, returns a ray whose endpoint is the dual of the finite incident face and supported by the line which is the bisector of the edge's endpoints. If both incident faces are infinite, returns the line which is the bisector of the edge's endpoints otherwise. |
|
| |
Idem | ||
|
| |
Idem |
|
| |
Returns the side of p with respect to the circle circumscribing the triangle associated with f |
The checking function is_valid() is also overwritten to
additionally test the empty circle property.
|
| |
Tests the validity of the triangulation as a CGAL_Triangulation_2 and additionally test the Delaunay property. This method is mainly useful for debugging Delaunay triangulation algorithms designed by the user. |
#include <CGAL/Homogeneous.h> #include <CGAL/Triangulation_euclidean_traits_xy_3.h> #include <CGAL/Delaunay_triangulation_2.h> #include <CGAL/IO/Geomview_stream.h> typedef CGAL_Homogeneous<leda_integer> Rep; typedef CGAL_Triangulation_euclidean_traits_xy_3<Rep> Terrain; 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_Delaunay_triangulation_2<Terrain, Tds> Delaunay; { Delaunay dt(Terrain()); CGAL_Point_3<Rep> p; while(cin >> p){ DT.insert(p); } CGAL_Geomview_stream G; G << DT; }
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 but this time using the Delaunay criterion. 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 O(1) for vertices distributed uniformly at random, and any query point.