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
References
- Franz Aurenhammer, Rolf Klein, Der-Tsai Lee: Voronoi Diagrams and Delaunay Triangulation. World Scientific, 2013
- Ivan Kutskir: Voronoi Diagram in JavaScript, 2009, accessed July 2020
- Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen. Springer, 2005
- Samuel Peterson: Computing Constrained Delaunay Triangulations, 1998, accessed July 2020