Konvexe Polygonzüge

In diesem Kapitel sollen die Kriterien für das Approximieren von konvexen Polygonzügen entwickelt werden. Diese Kriterien müssen eingeführt werden, um festzulegen, wie die quadratischen Bézierkurven an den Enden des Polygonzuges verlaufen sollen. Bei konvexen Polygonen wurden die Kriterien für die elementare Bézierkurve einer Kante durch die beiden Nachbarkanten beschrieben. Eine Kante, die am Anfang oder Ende eines Polygonzuges liegt, hat aber nur eine Nachbarkante. Deswegen müssen für diese Kante neue Überlegungen angestellt werden.

Für die Lage der Endpunkt der Bézierkurve sind zwei verschiedene Möglichkeiten denkbar. Die erste Möglichkeit ist, dass der Endpunkt, wie die anderen Eckpunkte in das Innere des Polygonzuges verschoben wird (siehe Abbildung 20). Wenn nun aber die Endpunkte eines Polygonzuges auf dem Rand einer Graphik liegen, kann dies dazu führen, dass eine Lücke entsteht und somit die Bézierkurve im Gegensatz zum Polygonzug keine Fläche mehr begrenzt. Um einen solchen Fall zu vermeiden, werden die Endpunkte der Bézierkurve auf die Endpunkte des Polygonzuges gesetzt.

Abbildung 20: Die Endpunkte sind ins Innere des Polygonzuges verschoben.

Die Kriterien werden an einem Polygonzug (siehe Abbildung 21) mit vier Punkten vorgestellt, wobei die linke Seite den Anfang des Polygonzuges beschreiben soll.

Als Tangente der Bézierkurve am Punkt $P0$ wurde der Vektor von $P0$ zu $P1$ gewählt. Der Endpunkt des Polygonzuges wurde nicht ins Innere des Polygonzuges verschoben, deswegen ist kein Ausgleich der Fläche notwendig. Ein Vektor, um den $P0$ verschoben wird, muss somit nicht aufgestellt werden. Für die Tangente in $P1$ muss, damit ein stetiger Übergang zu der nächsten elementaren Bézierkurve erreicht wird, der Vektor zwischen $P0$ und $P2$ gewählt werden. Die elementare quadratische Bézierkurve ist somit bereits festgelegt. Der erste Kontrollpunkt ist der Endpunkt, der dritte Kontrollpunkt ist der Punkt $Pt1$ , und der zweite Kontrollpunkt ist der Schnittpunkt der Tangenten mit der 1. Kante.

Die daraus resultierende Gleichung kann äquivalent zu den vorherigen Gleichungen aufgestellt werden. Sie wird aber nicht in das Gleichungssystem aufgenommen, da aus folgenden Gründen keine Optimierung dieser elementaren Bézierkurve möglich ist. Um einen stetigen Übergang von der elementaren Bézierkurve, welche die erste Kante beschreibt, zu der nächsten elementaren Bézierkurve zu erreichen, darf der Parameter $t_1$ nicht den Wert Null annehmen, da ansonsten der Übergang an dem Eckpunkt nicht stetig wäre. Der 2. Kontrollpunkt $PM$ wäre dann mit dem Eckpunkt $P1$ identisch. Beim Suchen der bestmöglichen Basislösung wird aber ein Teil der Parameter auf den Wert Null gesetzt, um eine Basislösung zu erhalten. Um zu verhindern, dass das Gleichungssystem eine Basislösung wiedergibt, die den Parameter $t_1$ auf den Wert Null setzt, wird von vornherein der Parameter $d_{1,1}$ auf den Wert Null gesetzt.

Dieses Vorgehen führt dazu, dass der Parameter $d_{1,1}$ den niedrigsten Wert annimmt, der möglich ist und somit zu einer guten Approximation führt. Des Weiteren kann der Parameter $t_1$ nicht den Wert Null annehmen, da ansonsten eine ungültige Basislösung erreicht wird.

In dem Fall, dass $t_1$ und $d_{1,1}$ den Wert Null annehmen, verläuft die elementare Bézierkurve der Kante, aufgrund der Tangente in $P1$ , wie in der Abbildung 22 zu sehen. Dies setzt vorraus, dass der Parameter $d_{1,2}$ negativ sein muss, was keiner gültigen Basislösung entspricht.

Abbildung 21: Benennung an der ersten Kante.

Abbildung 22: Ungültige Approximation wenn $d_{1,1}$ und $t_1$ den Wert Null annehmen.

Somit muss der Parameter $t_1$ einen positiven Wert annehmen und die Tangente in $Pt1$ nach Innen verschieben. Der mittlere Kontrollpunkt der ersten elementaren Bézierkurve muss zudem immer zwischen $P0$ und $P1$ liegen. Wenn der Abstand $d_{1,1}$ zwischen $P1$ und $P2$ angesetzt wird ist dies immer der Fall, da die Tangente in $Pt1$ passend gewählt wurde. Somit wird immer eine gültige elementare Bézierkurve für die erste Kante erreicht.

Also werden nach dem obigen Verfahren zunächst alle Gleichungen für die Kanten aufgestellt. Dabei werden die Anfangs- und Endkante vorerst vernachlässigt. Dann wird für die Anfangskante der Parameter $d_{1,1}$ auf den Wert Null gesetzt, sowie für die Endkante der entsprechende Parameter $d_{n-1,2}$ . Das Gleichungssystem hat dann folgende Gestalt.

$$\begin{array}{cccccccccc\vert l} d_{1,2} & d_{2,1} & \cdots ... ...vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array}$$

Die Gleichungen, in denen die Parameter $d_{1,1}$ und $d_{n-1,2}$ auf den Wert Null gesetzt wurden, sind in die letzten beiden Zeilen des Gleichungsystems eingetragen. Da $t_1$ und $t_n$ positiv sind und die Hauptdiagonale in dem Gleichungssystem bis $t_n$ reicht, wird ein negativer Eintrag in der b-Spalte verhindert. Durch diesen Aufbau wird der Rechenaufwand verringert, da die Hauptdiagonale nur noch in der $2\cdot n-1$ ten und $2 \cdot n$ ten Spalte erzeugt werden muss. Die Gleichungen werden mittels des Verfahrens, welches innerhalb der Approximation von konvexen Polygonen erläutert wurde, nach Bildung einer Hauptdiagonalen, äquivalent umgeformt und die Basislösung berechnet, welche die bestmögliche Bézierkurve wiedergibt.

Wegen der Wahl der Tangenten gibt es immer eine Bézierkurve, die der gültigen Anfangslösung entspricht. In dieser Lösung haben die Parameter $t_2$ bis $t_{n-1}$ , $d_{1,1}$ und $d_{n-1,2}$ jeweils den Wert Null. Die restlichen Parameter müssen dann, aufgrund der Tangenten an den Eckpunkten, positiv sein. Die einzige Ausnahme bilden Polygonzüge mit weniger als vier Eckpunkten. Polygonzüge mit drei Eckpunkten können ohne Optimierung folgendermaßen approximiert werden. Die zwei Kanten der Polygonzüge werden durch eine quadratische Bézierkurve approximiert. Der erste Kontrollpunkt ist der erste Eckpunkt, der mittlere Kontrollpunkt ist der mittlere Eckpunkt und der letzte Kontrollpunkt ist der letzte Eckpunkt. Dieses Verfahren wiederspricht zwar dem Anspruch den Flächeninhalt möglichst gleich zu halten, aber die Einhaltung dieser Forderung würde eine Bézierkurve aus mindestens zwei elementaren Bézierkurven erfordern, was den Aufwand zur Darstellung für diesen Polygonzug verdoppeln würde. Des Weiteren wird später ein Vorteil daraus gezogen, dass die Tangente am Ende der Bézierkurve, der Geraden durch die letzten zwei Eckpunkte entspricht. Um also die Komplexität gering zu halten und diesem Spezialfall eine nicht zu hohe Bedeutung beizumessen, wird eine ungenauere Approximation durch eine elementare Bézierkurve verwendet. In der Implementation wird dieser Fall gesondert behandelt und kann unter Verwendung der aufwändigeren Methode, falls erwünscht, schnell ausgetauscht werden.

Bei einem Polygonzug bestehend aus zwei Eckpunkten, ist der Polygonzug selber, also die Kante, die beste Approximation und wird somit nicht durch das Verfahren optimiert.