OpenCV 3 lernen

Anhang A. Planare Unterteilungen

Delaunay-Triangulation, Voronoi-Tesselation

Die Delaunay-Triangulation ist eine 1934 erfundene Technik [Delaunay34], mit der Punkte in einem Raum zu dreieckigen Gruppen so verbunden werden, dass der kleinste Winkel aller Winkel in der Triangulation ein Maximum ist. Das bedeutet, dass die Delaunay-Triangulation versucht, lange und dünne Dreiecke zu vermeiden, wenn sie Punkte trianguliert. In Abbildung A-1 siehst du die Grundzüge der Triangulation, die so durchgeführt wird, dass jeder Kreis, der zu den Punkten an den Scheitelpunkten eines bestimmten Dreiecks passt, keine anderen Scheitelpunkte enthält. Das nennt man die Eigenschaft des Umkreises (siehe Tafel c).

Abbildung A-1. Delaunay-Triangulation: (a) Punktmenge; (b) Delaunay-Triangulation der Punktmenge mit Anhängern des äußeren Begrenzungsdreiecks; (c) Beispielkreise, die die Umkreiseigenschaft zeigen

Um die Berechnung effizienter zu gestalten, erfindet der Delaunay-Algorithmus ein weit entferntes äußeres Begrenzungsdreieck, von dem aus der Algorithmus startet. Abbildung A-1(b) stellt das fiktive äußere Dreieck durch gepunktete Linien dar, die zu seinem Scheitelpunkt führen. Abbildung A-1(c) zeigt einige Beispiele für die Eigenschaft des Umkreises, darunter einen der Kreise (der in der rechten unteren Ecke), der zwei äußere Punkte der realen Daten mit einem der Eckpunkte des fiktiven äußeren ...