Voronoi diagram

As a Voronoi diagram, also Thiessen polygons or Dirichlet decomposition, a decomposition of the space into regions is referred to that, here denoted by a predetermined amount of points in the space as centers are determined. Each region is determined by exactly one center and includes all points of space, which at the center of the region are closer with respect to Euclidean metric than at any other center. Such regions are also referred to as a Voronoi regions. From all points that have more than one nearest the center, thus forming the boundaries of regions, there arises the Voronoi diagram.

Named Voronoi diagrams are named after the mathematician Georgy Feodosjewitsch Woronoi, the alternative names derived from Alfred H. Thiessen respectively Peter Gustav Lejeune Dirichlet.

General

Voronoi diagrams are used in various scientific fields such as biology, chemistry, meteorology, crystallography, architecture and other scientific disciplines such as computational geometry and material science. A special case of the Voronoi diagram in the three-dimensional space is the Wigner-Seitz cell. Although in 1644 mentioned by Descartes in his book Principia Philosophiae, they learned for the first time by Dirichlet and Voronoi a precise mathematical analysis. Voronoi diagrams can certainly be used as a decomposition of high-dimensional spaces. In the literature, the definition is mostly confined to the two-dimensional real space.

Definition

The Thiessen polygons or Voronoi diagram consist of the entire space minus the Voronoi regions, which are formed on the Euclidean distance from all points of space in terms that are closer to the corresponding center are as at all other centers. These can be viewed in two dimensions as a cut of any open half-planes, which are in turn limited by a bisector between two points of the centers.

Formally, a Voronoi region of the point, where a predetermined amount of the points is given by

Which is defined as an open half-plane and by

Is given. Now, if all Voronoi regions by

Optionally, is obtained by a Voronoi diagram

Informally, this means that exactly form the boundaries of the regions, which themselves do not belong to these to the chart or polygons. The resulting polygons ( edges of the polygon ) and Voronoi nodes are divided ( vertices of the polygon ) into Voronoi edges. All points on the Voronoi edges have it to the points whose Voronoi region are adjacent to the edge, the same distance.

Duality

The Voronoi diagram behaves dual of the Delaunay triangulation and is used to construct a corresponding triangulated surface.

To calculate the Delaunay triangulation, the corresponding dual graph is formed for the Voronoi diagram. This is done by the centers of the polygons are connected to each other so that to each Voronoi edge orthogonal line is drawn connecting the centers of two corresponding to each other ( see diagram).

Polygon method

Thiessen polygons are used, among other things, in the cartographic representation of measured values ​​. The polygon method is not random (i.e. comparatively easy ) geostatistical interpolation for easy illustration of the spatial distribution of geo-referenced data.

The basic assumption is that the similarity of the unknown value of a point in the plane to the known measured value with the distance from this decreases, the data therefore are more dissimilar, the further they are apart. This relationship is thereby brought on the polygon method to express that each reading is a Thiessen polygon surrounding it is homogenized, so all estimates are identical to the respective measurement value within this polygon.

The process so far is a poor approximation to the observable reality, as sharp jumps in parameter values ​​occur at the boundaries of a polygon; smooth transitions between two measured values ​​therefore can not be represented using this method. Due to this circumstance, the polygon method is again well suited for planar distribution of discrete data, such as binary (eg, reading: " snowfall: yes / no").

Algorithm

The computation of a Voronoi diagram using the Delaunay triangulation is possible for arbitrary dimensions. The following is an algorithm for the two-dimensional case is described, which can be extended by analogy to higher dimensions. The calculation is performed in three steps. Initially, all the given points in the plane to be projected in an additional dimension a ( hyper) paraboloid. From the points thus obtained, the convex hull is calculated. In a second step, all surfaces of the convex hull, whose surface normal points downward, projected back to its original level. The regions obtained in this way, the triangles of the Delaunay triangulation. In a last step, the radius centers of all triangles between adjacent triangles are connected, which gives the sought edges of the Voronoi polygons.

In three dimensions are in accordance with the centers of the spheres to connect through corners of the Delaunay tetrahedron with faces.

Pseudocode

Designations: points, Delaunay triangulation, convex hull, Voronoi diagram.

1: Initialize empty set P ', DT ( P ) and V ( P)   2:   3: / / computing the convex hull   4: For any p = (px, py ) P:   5: Add p ' = (px, py, px2 py2 ) to P' added   6: Compute KH (P ' ) / / Use a suitable algorithm   7:   8: / / calculate the Delaunay triangulation   9: For all pages KH ( P '): 10: If the normal vector from s to below shows: 11: For all edges e of s: 12: Set the z- value of each node k to 0 13: Create new edge k '= k 14: Joining k ' to DT ( P ) is added 15: 16: / / calculation of the Voronoi cells 17: For all triangles d in DT (P): 18: For all of d adjacent triangles d ': 19: Create edge m by connecting the circumcenter points of k and k ' 20: Add to V m add (P) Following.