Delaunay Triangulation and Voronoi Diagram

Using the Delaunay triangulation method - named after Boris Nikolajewitsch Delone - a set of points is combined to form an area-wide network of triangles.
The Problem is that there are several ways by which to triangulate any given set of points, but not all meet the requirements for the Delaunay triangulation. Conditions are that all three points of a triangle lie on a circle within which there are no further points and that therefore they are as “well-shaped” as possible, i.e. at best, equilateral triangles are formed.
For the following example set three triangulation variants are possible, but only the first meets the requirements for a Delaunay triangulation. The other variants are showing at minimum one point (green) inside the circle through the three points of one of the triangles.


The Delaunay triangulation is used, for example, in digital terrain models to create a TIN data structure.
The Voronoi diagram (also Thiessen polygons or Dirichlet tessellation) is known as the so-called dual graph of the Delaunay triangulation. It was named after Georgi Feodosjewitsch Woronoi and enables the subdivision of surfaces into areas of influence.
The Voronoi diagram is used, for example, in robotics for route planning with existing obstacles or in zoology as a model and analysis of animal territories.

Algorithm

Given is a set of \( n \) unique points \( P \) in one level \[ P = (p_1, p_2, p_3, \cdots, p_n) \]


The Voronoi diagram of \( P \) is defined as subdividing the level into \( n \) cells. For each point in \( P \), a cell is created with the property that a point \( q \) is only in the cell belonging to \( p_i \) if: \[ dist(q,p_i) < dist(q,p_j) \] for every point \(p_j \in P\) with \(j \neq i\).
So, the Voronoi edges are constructed by creating the perpendicular bisector of the line between two points respectively and blending them.


The Delaunay triangulation of \(P\) is then created by connecting the points of all neighboring Voronoi cells.


In the end the combination of Delaunay triangulation and Voronoi diagram looks like this.


So, the Voronoi cell arises from the intersection of the perpendicular bisectors of the Delaunay triangle sides that belong together.

Hands-On

Click in the box to generate points. On the basis of these points the Delaunay triangulation and the Voronoi diagram will be calculated. You can clear the points by clicking on the Clear Button or you can return to the default point set by clicking the Reset Button. Change the Toggles for seeing only the Delaunay triangulation (orange) or only the Voronoi diagram (blue) or both.
Delaunay triangulation and Voronoi diagram

References