Der Ablauf in der Implementation

Im vorherigen Kapitel wurde eine allgemeine Beschreibung der Klassen gegeben. Im Folgenden soll der Ablauf des Programms innerhalb der Klassen, wenn ein Polygon oder Polygonzug approximiert wird, am Beispiel eines nicht konvexen Polygons, das durch eine kubische Bézierkurve approximiert werden soll, erläutert werden.

Die Punkte des Polygons müssen zunächst in Instanzen der entsprechenden Klasse Punkt³³ gespeichert werden. Diese sollen dann in einer Instanz der Klasse Vector³⁴, in der vorgegebenen Reihenfolge vorliegen. Um dieses Polygon zu approximieren, wird die Methode poly2Kurve()³⁵ aufgerufen. Diese Methode benötigt das Vector³⁶ Objekt³⁷, in dem die Punkte gespeichert sind, drei Gleitkommazahlen, sowie einen Booleschen Wert, der angibt, ob es sich um einen Polygonzug oder ein Polygon handelt. Die ersten beiden Gleitkommazahlen geben die Stellen der Bézierkurve an, an denen die Abstände zur Kante gemessen werden sollen, die für die Optimierung benötigt werden. In den Gleichungen wurden die Werte $x_1$ und $x_2$ genannt. Die dritte Gleitkommazahl gibt an, wie nahe sich die mittleren Kontrollpunkte an den äußeren Kontrollpunkten befinden. In den Gleichungen wurde dieser Wert $k$ genannt.

In dieser Methode wird nun geprüft, welche Punkte in dem übergebenen Vector für die Approximation überflüssig sind. Alle Eckpunkte, deren Winkel und deren zugehörige Kanten einen bestimmten Faktor unterschreiten, werden bei der Approximation nicht berücksichtigt. Dazu wird mithilfe der Methode canDelete()³⁸ geprüft, ob ein Eckpunkt berücksichtigt werden muss. Dazu werden lediglich der Eckpunkt, sowie die beiden Nachbarpunkte benötigt.

Anschließend wird das Polygon in seine konvexen Polygonzüge zerlegt. Dies geschieht mithilfe der Methode split2Segments()³⁹. Dafür wird das Vector Objekt, sowie die Information, ob es sich um ein Polygon oder Polygonzug handelt, benötigt. Diese Information ist bedeutsam, weil Polygone an der zusätzlichen Kante, welche den ersten und den letzten Punkt verbindet, ebenfalls geteilt werden können.

Ein Richtungswechsel wird daran erkannt, dass der Rückgabewert der Methode getRichtung()⁴⁰, welche von der vorherigen Methode aufgerufen wird, das Vorzeichen ändert. Um die Richtung zu bestimmen, wird von der Methode lediglich ein Eckpunkt und die beiden benachbarten Eckpunkte benötigt. Die Richtung wird nach der Gleichung auf Seite 2.5 bestimmt.

An die Methode segment2Kurve()⁴¹ werden dann die konvexen Polygonzüge einzeln übergeben, welche die Kontrollpunkte der berechneten Bézierkurve zurückgibt. Durch diese Methode wird zu Beginn geprüft, ob die Punkte im Uhrzeigersinn verlaufen, also einer Rechtskurve folgen. Falls dies nicht der Fall sein sollte, wird die Reihenfolge umgekehrt, um eine Rechtskurve zu erzeugen. Der Sonderfall, dass es sich um einen Polygonzug mit weniger als 4 Eckpunkten handelt, wird abgefangen und gesondert bearbeitet. Die übrigen Fälle werden wie vorher theoretisch erläutert optimiert.

Dazu wird ein Gleichungssystem erzeugt und für jede Kante die entsprechende Gleichung eingetragen. Die einzelnen Einträge in der Matrix werden mithilfe der Klasse BezierFormeln⁴² berechnet. Dazu werden lediglich die Werte $x_i$ und $k$ sowie die vier Eckpunkte, welche die zur Gleichung gehörige Kante und die beiden Nachbarkanten definieren, benötigt. Die Klasse BezierFormeln⁴³ berechnet die Einträge mit Hilfe der Klasse Converter⁴⁴, welche die Formeln verarbeitet. Die zwei Parameter $d_{1,1}$ und $d_{n-1,2}$ , die für die korrekte Approximation der Endkanten sorgen, entfallen, da sie den Wert Null haben.

Um den Punkt im Polyeder zu berechnen, welcher die optimale Bézierkurve wiedergibt, wird bei der Instanz des erzeugten Gleichungssystems die Methode findMinAlgo()⁴⁵ aufgerufen. Diese Methode gibt dann den Punkt des Polyeders zurück, der die Parameter enthält, welche die optimale Bézierkurve wiedergeben.

Diese Methode formt das Gleichungssystem wie in Kapitel 3.1.3 beschrieben solange um, bis es den optimalen Punkt im Polyeder gefunden hat. Wenn der optimale Punkt im Polyeder gefunden wurde, wird dieser in Form eines Arrays zurückgegeben.

In der Methode segment2Kurve()⁴⁶ wird aus den Parametern, die in dem Array vorliegen, die Bézierkurve berechnet. Das geschieht ebenfalls unter Zuhilfenahme der Klasse BezierFormeln⁴⁷, welche die Formeln zur Berechnung der Kontrollpunkte aus den Parameter enthält.

Nachdem alle konvexen Teilstücke approximiert wurden, werden diese mit Hilfe der Methode unionSegments()⁴⁸ wieder zusammengefügt. Die entstandene Bézierkurve kann nun einfach in einem vektorgraphischen Format gespeichert werden.