Delaunay-Triangulation

The Delaunay triangulation is a common method to create a set of points of a triangular mesh. It is named after the Russian mathematician Boris Nikolaevich Delone (1890-1980, French form of the surname: Delaunay ) named, which has dealt in a publication so 1934.

• 3.1 Flip
• 3.2 Incremental Construction ( Incremental construction )
• 3.3 Divide and conquer
• 3.4 sweep
• 3.5 Voronoi
• 3.6 Calculation of the convex hull in 3D

Application

By the method of Delaunay triangulation points are crosslinked so as to triangles that no other points are contained within the circle on which are the three delta points. Using the method for example for the optimization of the calculation networks for the finite element method.

Principle

In a Delaunay triangulation all triangles of the triangular mesh satisfy the so-called radius Condition: The perimeter of a triangle of the network must not contain any other points of the given point set. Thus, the triangles of the network as possible on big interior angles; " the smallest interior angle is maximized over all triangles " is mathematically speaking. This property is very desirable in computer graphics, because it minimizes rounding errors.

The Delaunay triangulation is not unique if more than three points lie on a radius, ie the user can choose any which he connects three points to form a triangle.

In three-dimensional space, the analog Umkugelbedingung is used instead of the radius condition, which then generated from each of four points a tetrahedron.

Connection with Voronoi diagrams

The Delaunay triangulation is the dual graph of the Voronoi diagram of the point set: The corners of the Voronoizellen are the circumcenter of the triangles of the Delaunay triangulation (you get the Voronoi cells, when by all sides of the triangle, the perpendicular bisectors to the common point of intersection with the other two perpendicular bisectors of the same triangle inscribing, this point may well lie outside the triangular area in the obtuse-angled triangles, right triangles, it is at the point which bisects the hypotenuse ).

Voronoi diagram of the same set of points.

Voronoi diagram (orange) and Delaunay triangulation ( black)

Algorithms

There are several approaches for performing a Delaunay triangulation. The best term is reached at a memory footprint of.

Flip

The flip algorithm is a special form of two-dimensional triangle meshes. It is based on a local evaluation of the radius condition.

First, an arbitrary triangle network is generated by a simple algorithm. This must not meet the radius condition, it may not only overlapping edges included.

For each triangle, it is checked whether the radius of the triangle includes a further point, which is part of an adjacent triangle. In this case, a flip of the common edge is performed. That is, the shared edge is replaced with a new edge which connects the two points, which were not previously connected. After the flip, the radius condition is satisfied locally. However, can thus be disturbed again in the neighboring triangles, the radius condition. In the worst case, all other triangles need to be reviewed again after a flip, so is the computational complexity of the flip algorithm.

By the radius of the flip condition (local ) is satisfied.

Incremental Construction ( Incremental construction )

In the incremental method, the dots are added one after the other. In contrast to other methods, not only the Delaunay triangulation can thus generate a solid points in quantity, but also extend later by points that were not known at the beginning and only be determined by a process. The core of this method is an algorithm that requires an existing Delaunay triangulation and within this adds a point. As initialization, it is sufficient to specify a triangle, which includes the area of all projected points. The algorithm can be divided into three steps:

• In the triangulation of that triangle is sought, which contains the new point. A naive method, easy to test each triangle has the effort.
• The new point is connected to the three corners of the triangle found, so three new triangles. This triangulation may now no longer meets the Delaunay condition.
• Each of the three new triangles is then tested for the condition within and corrected as in the flip- algorithm. After each correction there are more triangles may no longer satisfy the area condition. This testing and correcting continues through the triangulation until all triangles satisfy the area condition. Since in the worst case, all triangles have to be corrected, the effort is theoretical. This case is but rarely occur. If the points are inserted in a random order, usually only a limited number of corrections must be performed so that the average cost of to be expected.

The search method perform with n points for all, has the effort. The corrections for n points ( in random order) only. The total cost is therefore determined by the search. A simple way to improve search is to go through the triangulation from an arbitrary triangle proceeding in the direction of the desired point. The cost of this method is. A slightly more complex search can be implemented when storing the history of all triangles generated in a tree. Although this tree needs additional space, but improves the search and therefore the entire Incremental algorithm.

Divide and conquer

The divide- and -conquer approach, each connecting two Delaunay triangulations in compliance with the Delaunay condition. The computational effort is.

Sweep

The sweep algorithm always adds a triangle while maintaining the Delaunay condition. In contrast to the incremental construction an adjacent triangle is here always be added, while in the incremental construction of any triangle can be added. The computational effort is.

Voronoi

In the Voronoi approach, the Voronoi graph for all points is first formed. By duality triangle mesh has been so determined all the necessary circumcenters and now just have to pull the corresponding circles.

Calculation of the convex hull in 3D

Each 2D point is added to a z-coordinate with. These 3D points is the convex hull - a faceted surface with triangles - created. The orientation of the triangle normals is set to the outside. If all down -oriented triangles ( ie those with negative z -coordinate of their normal vector ) is projected back into the original xy plane, to get there the searched 2D Delaunay triangular mesh. The time required is in.