Triangulation (Punktemenge)

aus Wikipedia, der freien Enzyklopädie

Eine Triangulation einer Menge von Punkten P in der Ebene bezeichnet die Zerlegung der von den Punkten eingeschlossenen Fläche in Dreiecke. Präziser ausgedrückt ist eine Triangulation ein ebener Dreiecksgraph, dessen Knoten genau die Punkte aus P sind. Alle inneren Gebiete einer Triangulation sind Dreiecke, während das äußere Gebiet von der konvexen Hülle von P begrenzt wird.

Ist die Menge P in konvexer Lage, so ist die Anzahl der möglichen Triangulationen genau die n-2-te Catalan-Zahl, wobei n die Anzahl der Punkte in P bezeichnet.

Triangulationen finden beispielsweise in der 3D-Computergrafik Anwendung, wenn geschwungene Flächen, wie z. B. der Kotflügel eines Autos, in Dreiecke zerlegt werden. Bei einer hinreichend großen Zahl von Dreiecken können diese näherungsweise als eben betrachtet werden, was ihre mathematische Behandlung in der Bildverarbeitung vereinfacht.

Oft ist man daran interessiert, eine Triangulation mit besonderen Eigenschaften zu berechnen. Zum Beispiel gibt es die Delaunay-Triangulation, welche besonders spitze Dreiecke vermeidet, oder die Minimum-Weight-Triangulation, welche die Gesamtlänge aller Kanten minimiert.