Aufstellen eines Gleichungssystems

Aus den im vorherigen Kapitel genannten Bedingungen können Gleichungen aufgestellt werden, die den allgemeinen Verlauf der Bézierkurven im Verhältnis zu den Polygonecken beschreiben. Die in den Gleichungen verwendeten Variablen sollen hier definiert werden. Die Bedingungen für die elementaren Bézierkurven sollen an einem konkreten Polygonzug verdeutlicht werden. Dieser Polygonzug⁸ besteht aus vier Punkten, wobei Gleichungen für die mittlere Kante aufgestellt werden sollen. Der Polygonzug ist konvex und kann für einen beliebigen Teil eines konvexen Polygons stehen. Die Eckpunkte des Polygonzuges sind von $P0$ bis $P3$ nummeriert. Da sich die Endpunkte der Bézierkurve durch die Verschiebung der Eckpunkte ergeben sollen, sind sie nach diesen benannt worden. Die Endpunkte der Bézierkurve lauten $Pt1$ und $Pt2$ , wobei das ,,t`` im Namen verdeutlichen soll, dass der Punkt aus einem Eckpunkt hervorgeht, der um einen Parameter $t$ verschoben ist.

Abbildung 12: Benennung der Richtungsvektoren für die Verschiebung.

Der Vektor, der vom Eckpunkt $P1$ in Richtung Kontrollpunkt $Pt1$ der Bézierkurve zeigt, sei durch $Vt1$ gegeben. Der entsprechende Vektor für $P2$ sei mit $Vt2$ benannt. Der Vektor, der die Tangente an der Bézierkurve im Punkt $Pt1$ angibt, sei mit $V1$ benannt sowie der im Punkt $Pt2$ mit $V2$ . Um alle Vektoren zu Vereinheitlichen, wird festgelegt, dass die Vektoren für die Verschiebung immer nach innen zeigen und die Richtungsvektoren der Tangenten immer in Richtung der Nummerierung, also in dem Teilstück von $P0$ zu $P2$ und von $P1$ zu $P3$ ⁹

Abbildung 13: Benennung der Richtungsvektoren der Tangenten.

$Pt1$ und $Pt2$ sind definiert als die Summe des Vektors zu $P1$ bzw $P2$ und dem entsprechenden Richtungsvektor der Winkelhalbierenden, der mit einem entsprechenden Parameter $t_1$ oder $t_2$ multipliziert wird. Da die Punkte somit von den Parametern abhängig sind, können sie als Funktion angesehen. Also:

$$Pt1(t_1) := P1 + t_1 \cdot Vt1$$ (2)

$$Pt2(t_2) := P2 + t_2 \cdot Vt2$$ (3)

Die Nummerierungen der Bezeichnungen der Parameter, soll die Zugehörigkeit zu einem Punkt verdeutlichen. So gehört zum Beispiel der Parameter $t_1$ zum Punkt $P1$ .

Da eine Verschiebung ins Innere des Polygonzuges definiert und eine Verschiebung nach Außen ausgeschlossen werden soll, weil dies einer schlechteren Approximation entsprechen würde, ergibt sich, dass die $t_i$ keinen negativen Wert annehmen dürfen.

Die Vektoren $Vti$ sollen auf die Länge $1$ normiert sein, denn dann werden die Abstände zwischen den Endpunkten der elementaren Bézierkurve und denen der Polygonkante, durch die Parameter $t_1$ und $t_2$ wiedergegeben. Der kürzeste Abstand zwischen der Bézierkurve und dem Polygon wird aber nicht immer durch die Werte der Parameter $t_1$ und $t_2$ wiedergegeben, sondern sie repräsentieren den Abstand zwischen zwei bestimmten Punkten. Die Parameter können negative Werte abnehmen, was aber nicht erwünscht ist. Der Ausschluss dieser negativen Werte führt so zu einer besseren Approximation und schließt eventuell auftretende Sonderfälle aus.

Die Parameter $t_1$ und $t_2$ werden als Indikatoren für die Abweichung der Bézierkurve vom Polygon festgesetzt, da sie die tatsächliche Verschiebung des Eckpunktes und somit einen Wert für die Veränderung des Polygons wiedergeben. Die kürzeste Strecke zwischen Eckpunkt und Bézierkurve ließe sich nicht durch eine lineare Gleichung beschreiben und würde ein komplett anderes Verfahren, welches auf quadratischen Gleichungen beruht, erfordern. Es ist zudem auch nicht notwendig die kürzeste Stecke zu verwenden, da der Wert der Verschiebung einen gleichwertigen Indikator darstellt, da durch ihn ein Verfahren ermöglicht wird, das auf linearen Gleichungen basiert und somit bei weitem nicht so komplex ist wie ein Verfahren das quadratischen Gleichungen beinhaltet.

Damit die elementaren Bézierkurven stetig ineinander übergehen, muss der 2. Kontrollpunkt, im Folgenden $PM$ genannt, als Schnittpunkt der Tangenten der Endpunkte festgelegt werden. Dafür sind zwei weitere Parameter $s_1$ und $r_2$ erforderlich. $PM$ ist durch die Parameter folgendermaßen festgelegt:

$$PM := Pt1(t_1) + s_1 \cdot V1$$ (4)

$$PM \phantom{ }= Pt2(t_2) - r_2 \cdot V2$$ (5)

Als weiterer Parameter für die Abweichung wird ein Abstand $d_i$ von einem Punkt der entsprechenden elementaren Bézierkurve zur Kante $K_i$ berechnet. Dazu wird der Parameter $x$ der Bézierkurve $C_i(x)$ festgelegt und von dem daraus resultierenden Punkt der Abstand zur Kante berechnet. Daraus ergibt sich der Vorteil, dass dieser Abstand zur Kante von jedem Punkt der Bézierkurve aus durch eine lineare Gleichung beschrieben werden kann, während es bei einem Abstand, der von einem Punkt auf der Kante ausgehend angegeben wird, zu quadratischen Gleichungen kommt.

Die elementare Bézierkurve wird nach dem Algorithmus von de Casteljau wie folgt festgelegt:

$$B1(x) := Pt1(t_1) + x \cdot s_1 \cdot V1$$ (6)

$$B2(x) := PM + x \cdot r_2 \cdot V2$$ (7)

$$C(x) := B1(x) + x \cdot (B2(x) - B1(x))$$ (8)

Für die Gleichung, welche die Abstandsmessung definiert, wird zum einen eine Matrix $D$ benötigt. $D$ ist diejenige Matrix, durch die ein Vektor um 90^&cir#circ; im Uhrzeigersinn gedreht wird. Zum anderen die Funktion $N(v)$ , die einen Vektor auf die Länge $1$ normiert, wobei $v$ der zu normierende Vektor ist. Die Gleichung für $d_1$ an der Stelle $C(x_1)$ lautet:

$$P1 + e_1 \cdot (P2 - P1) = C(x_1) + d_1 \cdot D \cdot N(P2 - P1)$$ (9)

Es ist an dieser Stelle zu betonen, dass durch die Gleichungen keine Veränderung der Polygonzugkante beschrieben wird, die zu einer Bézierkurve führt, die das Polygon bestmöglich approximieren würde. Sondern es werden aufgrund der Lage der Eckpunkte des Polygons Gleichungen aufgestellt, welche die Lage der Kontrollpunkte der Bézierkurve beschreiben. Durch die Gleichungen sind alle Kontrollpunkte einer Bézierkurve nur noch in einem bestimmten Rahmen variabel. Der Graph der Bézierkurve kann nur in bestimmten Bereichen, welche durch die Gleichungen vorgegeben sind, verändert werden.

Die in den Gleichungen vorkommenden Parameter sollen, wie die Parameter $t_1$ und $t_2$ , auf positive Werte eingeschränkt werden. Die Einschränkung, dass $d_i$ nur positive Werte annehmen darf, führt dazu, dass die Bézierkurve nicht beliebig weit ins Innere des Polygonzuges geschoben werden kann. Negative Werte von $d_1$ könnten zum Beispiel bei einem konvexen Polygon zu einem vollständigen Verlauf einer Bézierkurve innerhalb eines Polygons führen (siehe Abbildung 14). Dies wurde keiner Approximation eines Polygons, nach den genannten Kriterien entsprechen. In dieser Arbeit wird die Qualität der Approximation eines Polygons durch eine Bézierkurve, anhand der Summe der freien Parameter $t_i$ und $d_i$ gemessen. Dabei gilt, dass die bestmöglichste Bézierkurve die geringste Summe der Parameter in den Gleichungen aufweist. Zudem führt ein negativer Parameter zu einer ungültigen Approximation.

Abbildung 14: Bézierkurve, die innerhalb eines Polygons verläuft.

Für jede Kante von $\overline {P}$ werden Gleichungen aufgestellt, die elementare Bézierkurven beschreiben, die diese Kante approximieren. Diese werden dann zu einem linearen Gleichungssystem zusammengefasst, das quadratische Bézierkurven beschreibt, die das gesamte Polygon approximieren. Diese Gleichungen sollen als Parameter nur noch $t_i$ und $d_i$ enthalten, die zur Bewertung der Approximation herangezogen werden. Diese Gleichungen werden nachfolgend vorgestellt. Die Bennennung erfolgt wiederum anhand des Polygonzuges aus Abbildung 12.

Zur Berechnung und Lösung von Gleichungen und Gleichungssystemen wurde das Computer Algebra System (CAS) Derive verwendet. Ein Ausdruck der jeweiligen Eingaben ist der beigelegten CD-ROM im PDF-Format beigefügt.

Nach Eingabe der Gleichungen 2 bis 9 in das CAS Derive, kann aus den Gleichungen 5 und 9 ein lineares Gleichungssystem aufgestellt werden, und dieses nach $s_1$ , $e_1$ , $r_2$ und $d_1$ gelöst werden. Das CAS Derive liefert als Ergebnis vier Gleichungen¹⁰. In den Gleichungen werden $s_1$ , $e_1$ , $r_2$ und $d_1$ jeweils in Abhängigkeit von $t_1$ , $t_2$ und $x$ beschrieben. Der Parameter $x$ ist zwar frei wählbar, ist hier aber keine freie Variable. Der Wert von $x$ soll zu Beginn der Approximation eines Polygons gewählt werden und geht somit nicht als freier Parameter in die Gleichungen ein, sondern als Konstante. Die Auswirkungen der Wahl des Wertes des Parameters werden in Kapitel 5.1 erläutert, da dies anhand der dann erstellten Bézierkurven einfacher ist.

Die vierte Gleichung (siehe Kapitel A.1.4) spielt in den folgenden Überlegungen eine zentrale Rolle. In dieser Gleichung wird das Verhältnis zwischen der Verschiebung der Eckpunkte $P1$ und $P2$ ins Innere des Polygonzuges und dem Abstand der Bézierkurve B zur Polygonkante beschrieben. Es soll mit Hilfe einer geringen Verschiebung $t_1$ und $t_2$ ein geringer Abstand $d_1$ erreicht werden. Diese Gleichung wird für jede Polygonkante eines konvexen Polygons mit $n$ Kanten aufgestellt. Daraus ergeben sich $n$ Gleichungen, die alle Kriterien für eine quadratische Bézierkurve enthalten, und ein Gleichungssystem bilden. Eine solche Gleichung für eine Kante hat die allgemeine Form

$$a_{i}^{(1)} \cdot d_{i} + a_{i}^{(2)} \cdot t_i + a_{i}^{(3)} t_{i+1} = a_{i}^{(4)}$$ (10)

Wenn für jede Kante nur ein Parameter $d_i$ in das Gleichungssystem eingeht, kann es zu einer ungleichmäßigen Approximation kommen. In Abbildung 15 ist ein Beispiel für eine solche ungleichmäßige Approximation gezeigt. Um gleichmäßigere Abstände zu erhalten, wird eine weitere Gleichung für jede Kante in das Gleichungssystem aufgenommen. In dieser Gleichung wird der Wert des Parameters $x$ auf einen anderen wiederum vorher festgesetzten Wert gesetzt¹¹. Dadurch ergibt sich eine gleichmäßige Approximation (siehe Abbildung 16) und ein weiterer Punkt auf der Bézierkurve $C_i$ an dem der Abstand zur Kante berechnet wird. Damit die zwei Parameter, die den Abstand zwischen Bézierkurve und Kante angeben nicht verwechselt werden, wird ein weiterer Index an den Parameter angefügt. Der erste Abstand an der Kante zwischen $P1$ und $P2$ lautet $d_{1,1}$ und der zweite $d_{1,2}$ . Für jede Kante werden also zwei Gleichungen aufgestellt, mit zwei verschiedenen Parametern $x_1$ und $x_2$ , welche den Ort der Abstandsmessung an der Bézierkurve angeben. Folglich gehen zwei Gleichungen der folgenden Form für jede Kante in ein Gleichungssystem ein.

$$a_{i,j}^{(1)} \cdot d_{i,j} + a_{i,j}^{(2)} \cdot t_i + a_{i,j}^{(3)} t_{i+1} = a_{i,j}^{(4)}$$ (11)

Abbildung 15: Unausgeglichene Approximation: Die Abstände sind nicht gleichmäßig auf alle Eckpunkte verteilt.
Abbildung 16: Ausgeglichene Approximation: Die Abstände sind gleichmäßig auf alle Eckpunkte verteilt.