Polygon-Triangle

Auf den ersten Blick scheint das Aufteilen einer Polygonfläche in Dreiecke ein sehr spezielles Programmierproblem darzustellen. Bei näherer Betrachtung eröffnen sich eine Reihe interessanter Anwendungsgebiete. Da sich die so gebildeten Dreiecksflächen, im Gegensatz zum Polygonzug, mathematisch behandeln lassen, kann man z.B. 3D-Routinen vereinfachen, die Fläche eines Polygons berechnen oder einen Button beliebiger Gestalt verwalten.

Die hier vorgestellte Assembler-Routine ist für den Aufruf aus GFA-BASIC 3.xx gedacht. Dank Markus Fritze und Kollegen dürfte der verwendete Assembler (TURBOASS) in jeder Programmsammlung vorhanden sein. Der Quellcode ist zwar gut dokumentiert, aber um eine Konvertierung auf andere Sprachen zu ermöglichen folgt nun die „verständliche Erschlagung“ des Problems.

Das eigentliche Problem bei der Zerlegung des Polygons liegt darin, festzustellen, ob ein zu generierendes Dreieck innerhalb oder außerhalb des Linienzuges liegt. Die Vektorrechnung bietet eine einfache Lösung in Form des vektoriellen Produkts (a x b = c). Der Vektor c steht senkrecht auf den Vektoren a und b, welche ein Rechtssystem bilden. Vereinfacht gesagt wird damit ermittelt, in welche Richtung sich ein Rechtsgewinde (z.B. eine Glühbirne) bewegen würde, wenn man es in die Richtung dreht, in welche sich der Vektor a auf kürzestem Wege auf den Vektor b rotieren läßt (Bild 1). Mit dieser einfachen Methode läßt sich also feststellen, ob die beiden untersuchten Linien (Vektoren) einen konkaven oder konvexen Anteil am Polygon haben. Sollten sie konvex sein, also eine Ausbuchtung bilden, sind es schon mal Kandidaten für ein Dreieck. Dieses Verfahren läßt sich, wie gesagt, nur anwenden, wenn man sich auf einen Umlaufsinn für den Linienzug geeinigt hat (hier wird das übliche Rechtssystem verwendet). Die Größe des Normalvektors c ist also gar nicht von Interesse, lediglich sein Vorzeichen wird benötigt. Die gesuchte z-Komponente des Vektors läßt sich wie folgt berechnen:

mit a=(x10,y10) und b=(x12,y12)
a x b = c = x10y12-x12y10

Sollte c nun negativ sein, steht noch immer nicht fest ob das Dreieck existiert, denn es kann noch von anderen Linien überschnitten werden. Es muß also noch die Bedingung erfüllt sein, daß keiner der Polygoneckpunkte im Dreieck liegt. Dies läßt sich ebenfalls mit der Vektorrechnung überprüfen (Bild 2). Die Linienvektoren, jeweils mit einem positiven Faktor zwischen 0 und 1 multipliziert, beschreiben jeden Punkt auf der von ihnen aufgespannten Raute. Mit der Bedingung, daß die Summe der beiden Faktoren 1 nicht überschreiten darf, begrenzt man die Betrachtung auf die halbe Raute (Dreieck). Die Vektorgleichung lautet mit s und t als Faktoren:

ptx = s * x10 + t * x12
pty = s * y10 + t * y12

Dieses Gleichungssystem mit zwei Unbekannten läßt sich am einfachsten über Determinanten lösen. Die Lösungsdeterminante D ist hierbei angenehmerweise gleich dem Normalvektor c (s.o.).

s = Ds/D mit Ds = ptx * y12 - pty * x12
t = Dt/D mit Dt = pty * x10 - ptx * y10

Da Divisionen zu Rundungsverlusten führen (besonders in der Maschinensprache), sollte man statt der Bedingung s + t <= 1 besser Ds + Dt <= D schreiben.

Das Programm prüft nun mit Hilfe dieser beiden Ansätze für jeweils zwei aufeinanderfolgende Linien, ob sie als Dreiecksseiten aufgenommen werden. Wenn dies der Fall ist, werden die Dreiecksdaten gesichert und der Poygonzug um die beiden Linien verkleinert.

Auf diese Weise wird der Linienzug solange eingekreist, bis er vollständig zerlegt ist - die Routine gibt als Erfolgsbestätigung -1 zurück. Dabei sollte man wissen, daß sich ein Polygon (ohne Überschneidungen) mit n Ecken immer in n-2 Dreiecke zerlegen läßt.

Die beiden zusätzlichen Test-Routinen gestatten es, ein einzelnes Dreieck oder ein ganzes Polygon auf die Inhärenz eines Punktes zu kontrollieren. Das Beispiel-Listing sollte die Verwendung hinreichend erklären.

Listing 1

Listing 2