Voronoi-Diagramm - de.LinkFang.org

Voronoi-Diagramm


(Weitergeleitet von Polygon-Methode)

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.

Inhaltsverzeichnis

Allgemeines


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.

Entdeckungen

Voronoi-Diagramme wurden mehrmals wiederentdeckt.[2]

1850 1908 1909 1911 1927 1933 1958 1965 1966 1985
Dirichlet Woronoi Boldyrew Alfred H. Thiessen Paul Niggli Eugene Paul Wigner und Frederick Seitz F. C. Frank und J. S. Kasper G. S. Brown[3] R. Mead[4] Louis Hoofd
Mathematik Mathematik Geologie Meteorologie Kristallographie Physik Physik Ökologie Ökologie Anatomie
Dirichlet-Zerlegung Thiessen-Polygone Wirkungsbereiche[5] Wigner-Seitz-Zellen Frank-Kasper-Phasen

Definition


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 \({\displaystyle VR(p,S)}\) des Punktes \({\displaystyle p\in S}\), wobei \({\displaystyle S}\) eine vorgegebene Menge an Punkten des \({\displaystyle \mathbb {R} ^{2}}\) ist, gegeben durch

\({\displaystyle VR(p,S)=\bigcap _{q\in S\setminus \{p\}}D(p,q)}\),

wobei \({\displaystyle D(p,q)}\) als offene Halbebene definiert ist und durch

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

gegeben ist. Sind nun alle Voronoi-Regionen durch

\({\displaystyle VR(S)=\bigcup _{p\in S}VR(p,S)}\)

gegeben, erhält man das Voronoi-Diagramm durch

\({\displaystyle 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 \({\displaystyle p\in S}\), deren Voronoi-Region neben der Kante liegen, den gleichen Abstand.

Dualität


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

Um die Delaunay-Triangulierung 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


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 auseinanderliegen. 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


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 \({\displaystyle x,y}\)-Ebene in eine zusätzliche Dimension \({\displaystyle z}\) auf einen (Hyper-)Paraboloid \({\displaystyle (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

Bezeichnungen: Punkte \({\displaystyle P}\), Delaunay-Triangulation \({\displaystyle DT(P)}\), Konvexe Hülle \({\displaystyle KH(P)}\), Voronoi-Diagramm \({\displaystyle 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) \({\displaystyle \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 \({\displaystyle \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 \({\displaystyle \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 d und d'
20:       Füge m zu V(P) hinzu

Nach [6].

Anwendungen


Geisteswissenschaften

Fußball

Literatur


Weblinks


Commons: Voronoi diagrams  – Sammlung von Bildern, Videos und Audiodateien

Einzelnachweise


  1. Rolf Klein: Algorithmische Geometrie, Springer 2005, ISBN 978-3-540-20956-0
  2. Thomas M. Liebling: Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twin. In: Documenta Mathematica. Extra Volume ISMP, 2012, S. 419–431 (http://www.math.uiuc.edu/documenta/vol-ismp/60_liebling-thomas.pdf (Memento vom 9. August 2017 im Internet Archive)). Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twin (Memento vom 9. August 2017 im Internet Archive)
  3. G. S. Brown: Point density in stems per acre (=  N.Z. For. Res. Notes), Band 38 1965, S. 11.
  4. R. Mead: A Relationship between Individual Plant-spacing and Yield. In: Annals of Botany. 30, Nr. 2, April 1966, S. 301–309.
  5. Paul Niggli: XXIV. Die topologische Strukturanalyse. I. In: Zeitschrift für Kristallographie. Band 65, Nr. 1-6, 1927, S. 391–415, doi:10.1524/zkri.1927.65.1.391 .
  6. John Fisher: Visualizing the connection among Convex Hull, Voronoi Diagram and Delaunay Triangulation (PDF; 4,8 MB)
  7. Tonio Hölscher, Susanne Krömker und Hubert Mara: Der Kopf Sabouroff in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung. In: Benaki-Museum (Hrsg.): Gedenkschrift für Georgios Despinis. Athen, Griechenland 2020.
  8. Voronoi Cells & Geodesic Distances - Sabouroff head auf YouTube. Analyse mit dem GigaMesh Software Framework wie in Hölscher et al. beschrieben, cf. doi:10.11588/heidok.00027985.
  9. a b Tobias Escher: Der Schlüssel zum Spiel: Wie moderner Fußball funktioniert. 2. Auflage. Rowohlt Verlag, Hamburg 2020, ISBN 978-3-499-00198-7, S. 29–31.
  10. Als Beispiel findet sich unter https://medium.com/football-crunching/using-voronoi-diagrams-in-football-ca730ea81c05 eine Analyse des fünften Tores aus dem WM-Halbfinale Brasilien-Deutschland (1:7) von 2014 mit Hilfe von Voronoi-Diagrammen.









Kategorien: Algorithmische Geometrie | Geostatistik | Diagramm




Stand der Informationen: 22.02.2021 06:45:03 CET

Quelle: Wikipedia (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.

Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.