Voronoi-Diagramm

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Voronoi-Diagramm, auch Thiessen-Polygone oder Dirichlet-Zerlegung, wird eine Zerlegung des Raumes in Regionen bezeichnet, die durch eine vorgegebene Menge an Punkten des Raumes, hier als Zentren bezeichnet, bestimmt werden. Jede Region wird durch genau ein Zentrum bestimmt und umfasst alle Punkte des Raumes, die in Bezug zur euklidischen Metrik näher an dem Zentrum der Region liegen als an jedem anderen Zentrum. Derartige Regionen werden auch als Voronoi-Regionen bezeichnet. Aus allen Punkten, die mehr als ein nächstgelegenes Zentrum besitzen und somit die Grenzen der Regionen bilden, entsteht das Voronoi-Diagramm.

Benannt sind Voronoi-Diagramme nach dem Mathematiker Georgi Feodosjewitsch Woronoi, die alternativen Bezeichnungen leiten sich von Alfred H. Thiessen respektive Peter Gustav Lejeune Dirichlet ab.

Beispiel einer Dirichlet-Zerlegung zu einer vorgegebenen Menge an Punkten.

Allgemeines[Bearbeiten]

Voronoi-Diagramme werden in verschiedensten wissenschaftlichen Bereichen wie der Biologie, Chemie, Meteorologie, Kristallographie, Architektur und anderen wissenschaftlichen Disziplinen wie der Algorithmischen Geometrie und der Materialwissenschaft verwendet. Ein Spezialfall des Voronoi-Diagramms im dreidimensionalen Raum ist die Wigner-Seitz-Zelle. Obwohl 1644 schon durch Descartes in seinem Buch Principia Philosophiae erwähnt, erfuhren sie erstmals durch Dirichlet und Voronoi eine genauere mathematische Analyse.[1] Voronoi-Diagramme können durchaus auch als Zerlegung hochdimensionaler Räume verwendet werden. In der Literatur ist die Definition meist auf den zweidimensionalen reellen Raum beschränkt.

Definition[Bearbeiten]

Die Thiessen-Polygone oder das Voronoi-Diagramm bestehen aus dem gesamten Raum abzüglich der Voronoi-Regionen, welche in Bezug auf den euklidischen Abstand aus allen Punkten des Raumes entstehen, die näher am korrespondierenden Zentrum liegen als an allen anderen Zentren. Diese können im Zweidimensionalen als Schnitt mehrerer offener Halbebenen betrachtet werden, welche wiederum durch einen Bisektor zwischen je zwei Punkten der Zentren begrenzt werden.

Formal ist eine Voronoi-Region VR(p, S) des Punktes p \in S, wobei S eine vorgegebene Menge an Punkten des \mathbb{R}^2 ist, gegeben durch

VR(p, S)=\bigcap_{q \in S \setminus \{p\}}D(p,q),

wobei D(p,q) als offene Halbebene definiert ist und durch

D(p,q)=\{x \in \mathbb{R}^2:|p-x|<|q-x|\}

gegeben ist. Sind nun alle Voronoi-Regionen durch

VR(S)=\bigcup_{p \in S}VR(p,S)

gegeben, erhält man das Voronoi-Diagramm durch

V(S)=\mathbb{R}^2 \setminus VR(S)

Informell bedeutet das, dass genau die Grenzen der Regionen, welche selbst nicht zu diesen dazu gehören, das Diagramm bzw. die Polygone bilden. Die resultierenden Polygone können in Voronoi-Kanten (Kanten des Polygons) und Voronoi-Knoten (Ecken des Polygons) eingeteilt werden. Alle Punkte auf den Voronoi-Kanten haben dabei zu den Punkten p \in S, deren Voronoi-Region neben der Kante liegen, den gleichen Abstand.

Erstellung des dualen Graphen eines Thiessen-Polygons

Dualität[Bearbeiten]

Das Voronoi-Diagramm verhält sich dual zur Delaunay-Triangulation und wird zur Konstruktion einer entsprechend triangulierten Oberfläche verwendet.

Um die Delaunay-Triangulation zu berechnen, wird der entsprechende duale Graph zum Voronoi-Diagramm gebildet. Dies geschieht, indem die Zentren der Polygone derart miteinander verbunden werden, so dass zu jeder Voronoi-Kante eine orthogonale Linie eingezeichnet wird, die die entsprechenden zwei Zentren miteinander verbindet (siehe Abbildung).

Polygon-Methode[Bearbeiten]

Thiessen-Polygone werden unter anderem bei der kartographischen Darstellung von Messwerten eingesetzt. Die Polygon-Methode ist ein nichtstatistisches (d. h. vergleichsweise einfaches) Interpolationsverfahren der Geostatistik zur einfachen Darstellung der räumlichen Verteilung georeferenzierter Messdaten.

Als Grundannahme gilt, dass die Ähnlichkeit des unbekannten Wertes eines Punktes in der Fläche zum bekannten Messwert mit der Entfernung von diesem abnimmt, die Daten also umso unähnlicher sind, je weiter sie auseinander liegen. Dieser Zusammenhang wird bei der Polygon-Methode dadurch zum Ausdruck gebracht, dass jeder Messwert für ein ihn umgebendes Thiessen-Polygon homogenisiert wird, also alle Schätzwerte innerhalb dieses Polygons identisch zum jeweiligen Messwert sind.

Das Verfahren bildet insofern eine schlechte Näherung an die beobachtbare Realität, da an den Polygongrenzen scharfe Wertesprünge auftreten; fließende Übergänge zwischen zwei Messwerten können mit dieser Methode also nicht dargestellt werden. Durch diesen Umstand ist die Polygon-Methode wiederum gut geeignet zur flächigen Verteilung von diskreten Daten, etwa binären (z. B. Messwert: "Schneefall: ja/nein").

Algorithmus[Bearbeiten]

Eingefärbtes Voronoi-Diagramm mit zufällig verteilten Punkten in der Ebene

Die Berechnung eines Voronoi-Diagramms mithilfe der Delaunay-Triangulation ist für beliebige Dimensionen möglich. Im Folgenden wird ein Algorithmus für den zweidimensionalen Fall beschrieben, der sich analog auf höhere Dimensionen erweitern lässt. Die Berechnung erfolgt in drei Schritten. Zunächst werden alle gegebenen Punkte in der x,y-Ebene in eine zusätzliche Dimension z auf einen (Hyper-)Paraboloid (x, y, x^2 + y^2) projiziert. Von den so gewonnenen Punkten wird die Konvexe Hülle berechnet. In einem zweiten Schritt werden alle Flächen der Konvexen Hülle, deren Flächennormale nach unten zeigt, wieder auf die ursprüngliche Ebene zurückprojiziert. Die so gewonnenen Regionen sind die Dreiecke der Delaunay-Triangulation. In einem letzten Schritt werden die Umkreismittelpunkte aller Dreiecke zwischen angrenzenden Dreiecken verbunden, was die gesuchten Kanten der Voronoi-Polygone ergibt.

In drei Dimensionen sind entsprechend die Kugelmittelpunkte durch Ecken der Delaunay-Tetraeder mit Flächen zu verbinden.

Pseudocode[Bearbeiten]

Bezeichnungen: Punkte P, Delaunay-Triangulation DT(P), Konvexe Hülle KH(P), Voronoi-Diagramm V(P).

 1: Initialisiere leere Mengen P', DT(P) und V(P)
 2:
 3: //Berechnung der konvexen Hülle
 4: Für alle p = (px, py) \in P:
 5:    Füge p' = (px, py, px2 + py2) zu P' hinzu
 6: Berechne KH(P') //Mit geeignetem Algorithmus
 7:
 8: //Berechnung der Delaunay-Triangulation
 9: Für alle Seiten s \in KH(P'):
10:    Falls Normalenvektor von s nach unten zeigt:
11:       Für alle Kanten k von s:
12:          Setze z-Wert von jedem Knoten \in k auf 0
13:          Erstelle neue Kante k' = k
14:          Füge k' zu DT(P) hinzu
15:
16: //Berechnung der Voronoi-Zellen
17: Für alle Dreiecke d in DT(P):
18:    Für alle an d angrenzenden Dreiecke d':
19:       Erstelle Kante m durch Verbindung der Umkreismittelpunkte von k und k'
20:       Füge m zu V(P) hinzu

Nach [2].

Literatur[Bearbeiten]

  •  Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu (Hrsg.): Spatial Tessallations: Concepts and Applications of Voronoi Diagrams. 2. Auflage. John Wiley & Sons, 2000, ISBN 978-0-47-198635-5.
  • Frank Aurenhammer, Rolf Klein, Der-Tsai Lee: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore 2013, ISBN 9814447633.

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Rolf Klein: Algorithmische Geometrie, Springer 2005, ISBN 978-3-540-20956-0
  2. John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4,8 MB)