Suchen der optimalen Bézierkurve

Die Lösung eines linearen Gleichungssystem ist nach der linearen Algebra ein linearer Unterraum (im Weiteren LU genannt). Jeder Punkt in diesem LU beschreibt eine Bézierkurve, aber nicht jeder Punkt in diesem LU beschreibt nach den bis jetzt genannten Kriterien eine gültige Bézierkurve. Im LU können die Parameter negative Werte annehmen, die hier ungültig sind. Der optimale Punkt im LU, der die Parameter für die Bézierkurve beschreibt, hat die Eigenschaft, dass alle Einträge positiv sind. Des Weiteren sollte die Abweichung der Bézierkurve vom Polygon minimal sein und somit auch die Summe aller Einträge des Punktes. Dieser Punkt kann durch Umformung des Gleichungssystems ermittelt werden.

Dazu muss vorab geklärt werden, ob es überhaupt für jedes Polygon eine Bézierkurve gibt, die alle Kriterien erfüllt. Andernfalls würde ein Punkt gesucht werden, der nicht im LU vorhanden ist. Im Falle eines konvexen Polygons existiert allerdings immer ein solcher Punkt, der eine gültige Bézierkurve beschreibt. Die Bézierkurve dessen Graph durch die Eckpunkte des Polygons verläuft, erfüllt alle Kriterien. Die Werte der Parameter $t_i$ sind Null, sowie die der Parameter $d_{i,j}$ größer Null, da die Tangenten in den Eckpunkten die Kontrollpunkte vorgeben. In Abbildung 17 ist ein Beispiel gezeigt. Unabhängig davon wie ein konvexes geschlossenes Polygon verläuft, die Bézierkurve durch die Eckpunkte ist eine gültige Lösung nach diesen Kriterien. Da also immer eine Lösung vorhanden ist, muss durch Wahl eines geeigneten Suchverfahrens der optimale Punkt im LU ermittelt werden.

Abbildung 17: Gültige Anfangslösung.

Ein Gleichungssystem kann nach dem Gauß'schen Eliminationsverfahren¹² vereinfacht werden, so dass eine Hauptdiagonale entsteht. Dazu wird wie folgt vorgegangen: Es werden die Gleichungen von oben im Gleichungssystem angefangen, also von der 1-sten Zeile, der Reihe nach umgeformt, also bis zur $2 \cdot n$ -ten Zeile. Dabei weist das zum Gleichungssystem gehörige Polygon $n$ Kanten auf. Zuerst wird die entsprechende Zeile, angenommen die j-te, normiert, so dass der j-te Eintrag in der j-ten Zeile auf Eins normiert wird. Das wird erreicht indem die j-te Zeile durch den Eintrag $a_{j,j}$ dividiert wird, sofern $a_{j,j} \neq 0$ . Anschließend werden die Zeilen unterhalb der j-ten Zeile umgeformt, so dass in der j-ten Spalte unterhalb des j-ten Eintrags nur noch Nullen vorhanden sind, indem von den unteren Zeilen die j-te Zeile mit einem passendem Faktor abgezogen wird. Diese Schritte sind an folgendem Gleichungssystem gezeigt. Das Gleichungssystem enthält nur 3 Gleichungen, da es nur die Schritte der Umformung veranschaulichen soll.

$$\begin{array}{llllll\vert l} a_{1,1}&a_{1,2}&a_{1,3}&a_{1,4}... ...a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}&a_{3,5}&a_{3,6}&b_3 \end{array}$$

1. Schritt: Normieren der 1. Zeile $\left( a_{j,j} \neq 0 \right)$

$$\begin{array}{llllll\vert l} 1 &a'_{1,2}&a'_{1,3}&a'_{1,4}&a... ...a_{3,1}&a_{3,2}&a_{3,3}&a_{3,4}&a_{3,5}&a_{3,6}&b_3 \end{array}$$

2. Schritt: Erzeugen der Nullen

$$\begin{array}{llllll\vert l} 1 &a'_{1,2}&a'_{1,3}&a'_{1,4}&a... ... &a'_{3,2}&a'_{3,3}&a'_{3,4}&a'_{3,5}&a'_{3,6}&b'_3 \end{array}$$

Restlichen Zeilen analog

$$\begin{array}{llllll\vert l} 1 &a'_{1,2}&a'_{1,3}&a'_{1,4}&a... ...''_2\\ 0 &0 &1&a''_{3,4}&a''_{3,5}&a''_{3,6}&b''_3 \end{array}$$

Um die restlichen Einträge zu dem Wert Null umzuformen, wird analog vorgegangen. Diesmal wird von der $2 \cdot n$ -ten Zeile beginnend nach oben und von der $2 \cdot n$ -ten Spalte nach links umgeformt. Das Normieren entfällt und die Einträge in der j-ten Spalte über dem j-ten Eintrag werden zum Wert Null umgeformt, indem die j-te Zeile mit dem entsprechenden Faktor von der jeweiligen Zeile abgezogen wird. Dies wird wiederum am Gleichungssystem, das zu einem Reduzierten System¹³ umgeformt wird, verdeutlicht.

Die oberen Nullen erzeugen

$$\begin{array}{llllll\vert l} 1 &0 &0 &c_{1,4}&c_{1,5}&c_{1,6... ...}_2\\ 0 &0 &1 &c_{3,4}&c_{3,5}&c_{3,6}&\tilde{b}_3 \end{array}$$

Beim Erzeugen der Hauptdiagonalen ist Folgendes zu berücksichtigen. An der Stelle $a_{j,j}$ muss zum Einen nicht immer ein Eintrag sein, dessen Wert ungleich Null ist. Somit könnte dann keine Normierung durchgeführt werden. Das Gleichungssystem wird aber so aufgestellt, dass die Einträge auf der Hauptdiagonalen immer ungleich Null sind. Das Gleichungssystem für ein konvexes Polygon mit $n$ Kanten soll folgende Form haben.

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

Das Gleichungssystem wird so aufgebaut, dass die Gleichungen entsprechend der Reihenfolge der Parameter in das Gleichungssystem eingetragen werden. Folglich steht in der ersten Zeile die Gleichung mit $d_{1,1}$ , dann die mit $d_{1,2}$ usw., so dass die Gleichung für $d_{n,2}$ in der $2 \cdot n$ ten Zeile steht. Aus diesem Aufbau ergibt sich eine Hauptdiagonale, die nur noch normiert werden muss. Dies folgt aus der Tatsache, dass in jeweils einer Gleichung nur ein Parameter $d_{i,j}$ und die Parameter $t_i$ und $t_{i+1}$ auftreten (siehe Gleichung 11).

Das obige System kann nur Verwendung finden, wenn die Anzahl der freien Variablen höher ist als die der Gleichungen. Da dies bei konvexen Polygonen der Fall ist, kann diese Vorgehensweise bei diesen zur Anwendung kommen. Bei einem Polygon mit $n$ Punkten, gibt es $n$ Kanten die zu approximieren sind. Das bedeutet, das für jede Kante zwei Gleichungen aufgestellt werden müssen und das Gleichungssystem $2 \cdot n$ Gleichungen enthält. Für jeden Eckpunkt existiert ein freier Parameter $t_i$ und für jede Kante zwei Parameter $d_{i,j}$ . Daraus folgt, dass es $3\cdot n$ freie Variablen gibt, also $n$ mehr als Gleichungen.

Ein Punkt des LU kann berechnet werden, indem alle Parameter bis auf die ersten $2 \cdot n$ des Gleichungssystems mit $2 \cdot n$ Gleichungen auf Null gesetzt und die restlichen dann berechnet werden. Die so berechnete Lösung wird Basislösung des Gleichungsystems genannt¹⁴. Der Lösungsvektor entspricht der b-Spalte¹⁵ die um Null-Einträge ergänzt worden ist. Da nach dem vorher genannten Aufbau alle Werte der $t_i$ zu Beginn auf Null gesetzt wurden, entspricht die Anfangslösung einer gültigen Lösung. Die Basislösung muss aber nicht die bestmögliche Bézierkurve wiedergeben. Dazu werden nun Überlegungen durchgeführt, wie von dieser Basislösung zu einer besseren Basislösung übergegangen werden kann.

Ein Gleichungssystem, mit dessen Hilfe ein Lösungsvektor berechnet wurde, hat nach Bildung einer Hauptdiagonalen folgende Gestalt.

$$\begin{array}{cccccccccc\vert l} a_1 & a_2 & \cdots & \cdots... ...cdot n-1} & c_{2 \cdot n,3 \cdot n} & b_{2 \cdot n} \end{array}$$

Da der Lösungsvektor berechnet wird, indem die Werte der Variablen $c_1$ bis $c_n$ auf Null gesetzt werden, ist die Summe der Einträge der Basislösung gleich der Summe der Einträge der b-Spalte. Im Folgenden soll mit Min-Schritt eine Umformung im Gleichungssystem bezeichnet werden, die eine Verringerung der Summe der Einträge der b-Spalte zur Folge hat, aber nicht zu einer ungültigen Lösung führt. Dieses Verfahren basiert auf dem Simplex-Algorithmus. Der angewendete Min-Schritt ist dem Austauschschritt des Simplex-Algorithmus ähnlich. In diesem Verfahren, wird aber auf die Zielfunktion verzichtet, da immer die Summe aller Einträge berechnet werden soll.

Ein Min-Schritt besteht aus den folgenden, beispielhaft an einem kleinen Gleichungssystem gezeigten, Schritten¹⁶:

• Wählen eines geeigneten Eintrags $c_{i,j}$

  Eintrag $c_{1,6}$ wird gewählt.

  $$\begin{array}{llllll\vert l} 1 &0 &0 &c_{1,4}&c_{1,5}&\mathb... ...c_{2,6}&b_2\\ 0 &0 &1 &c_{3,4}&c_{3,5}&c_{3,6}&b_3 \end{array}$$

• Tauschen der Spalten j und i

  Tauschen der Spalten 6 und 3.

  $$\begin{array}{llllll\vert l} \mathbf{c_{1,6}}&0 &0 &c_{1,4}&... ...,5}&0 &b_2\\ c_{3,6} &0 &1 &c_{3,4}&c_{3,5}&0 &b_3 \end{array}$$

• Umformen um eine Hauptdiagonale zu erstellen
  $$\begin{array}{llllll\vert l} 1 &0 &0 &c'_{1,4}&c'_{1,5}&c'_{... ...6}&b'_2\\ 0 &0 &1 &c'_{3,4}&c'_{3,5}&c'_{3,6}&b'_3 \end{array}$$

Zu klären ist nun, welchen Kriterien der Eintrag $c_{i,j}$ , der zu einer Verringerung der Summe führen soll, entsprechen muss. Je nach Wahl des Eintrags $c_{i,j}$ , ergibt sich nach Durchführung des Min-Schrittes, eine entsprechende b-Spalte und somit auch eine entsprechende Basislösung. Um die Kriterien, die an den Eintrag $c_{i,j}$ gestellt werden, zu bestimmen, wird der dritte Schritt genauer untersucht, da der erste und der zweite Schritt keine Veränderung der b-Spalte erzeugen und somit auch keine Veränderung der Basislösung.

Der dritte Schritt kann wiederum in zwei Teile unterteilt werden. Im ersten Teil wird die Zeile durch den Eintrag $c_{i,j}$ dividiert. Wenn der Eintrag $c_{i,j}$ negativ war, ergibt sich eine nicht gültige Basislösung, da mit einer gültigen Anfangslösung begonnen wurde. Der Eintrag $b_j$ war daher vorher positiv und wird durch das Dividieren mit einem negativen Eintrag $c_{i,j}$ negativ. Die erste Einschränkung für $c_{i,j}$ besteht somit darin, dass dieser Eintrag positiv sein muss, um bei einer korrekten Basislösung zu bleiben. Darüber hinaus darf der Eintrag $c_{i,j}$ nicht den Wert Null haben, um den Austausch der Spalten durchführen zu können. Wenn der Eintrag Null wäre, könnte durch den beschriebenen Min-Schritt keine Hauptdiagonale entstehen.

Im zweiten Teil wird dann von den übrigen Zeilen das $c_{i,l}$ -te der $j$ -ten Zeile von der $l$ -ten Zeile abgezogen, wobei gilt $l\neq j$ . Da dies zu Veränderungen in der b-Spalte führt, ist darauf zu achten, dass die Einträge in der b-Spalte nicht negativ werden oder dass es zu einer Vergrößerung der Summe kommt und somit dann zu einer schlechteren Approximation.

Um die Bedingungen für den Eintrag $c_{i,j}$ weiter einzugrenzen, werden die Veränderungen in der b-Spalte betrachtet. Nachdem ein Min-Schritt durchgeführt wurde, ergibt sich die neue b-Spalte aus der alten in folgender Weise. Die neuen Einträge sind durch eine Tilde über dem Buchstaben kenntlich gemacht.

$$\tilde{b}_j = \frac{b_j}{c_{i,j}}$$

$$\tilde{b}_l = b_l - \frac{c_{i,l} \cdot b_j}{c_{i,j}} l\neq j$$

Da die Summe der Einträge der b-Spalte verringert werden soll, wird nun die Veränderung dieser in den Blick genommen.

$$\sum\limits_{l=1}^n \left( \tilde{b}_l \right) = \sum\limits_{\substack{l=1\\ l\neq j}}^n \left( b_l - \frac{c_{i,l} \cdot b_j}{c_{i,j}} \right) + \frac{b_j}{c_{i,j}}$$

$$= \sum\limits_{\substack{l=1\\ l\neq j}}^n \left( b_l \right) - \... ...eq j}}^n \left( \frac{c_{i,l} \cdot b_j}{c_{i,j}} \right) + \frac{b_j}{c_{i,j}}$$

$$= \underbrace{\sum\limits_{\substack{l=1\\ l\neq j}}^n \left( b_l... ...( c_{i,l} \right)}_{2. Summand} + \underbrace{\frac{b_j}{c_{i,j}}}_{3. Summand}$$

Der Wert des ersten Summanden ist größer Null, da mit einer gültigen Basislösung begonnen wurde und die b-Spalte somit nur positive Einträge hatte. Der dritte Summand ist ebenfalls positiv, da der Eintrag $b_j$ der vorherigen Basislösung ebenfalls positiv war, sowie der Eintrag $c_{i,j}$ . Daraus folgt, dass der zweite Summand einen Wert kleiner Null haben muss, um die Summe der Einträge zu verringern. Damit der Wert des zweiten Summanden kleiner Null ist, muss die Summe der Einträge in der i-ten Spalte ohne $c_{i,j}$ größer Null sein. Dies ergibt sich aus der Wahl des Eintrags $c_{i,j}$ , der bereits nach den oben genannten Voraussetzung positiv sein soll. Eine weitere Einschränkung für die Wahl von $c_{i,j}$ ist somit, dass die Summe der Einträge der Spalte, in der das $c_{i,j}$ gewählt wird, ohne $c_{i,j}$ einen Wert größer Null haben muss, sowie der Eintrag $b_j$ einen ungleich Null, da ansonsten der zweite Summand den Wert Null hätte. Die Spalte in der das $c_{i,j}$ gewählt werden soll, kann sogar noch weiter eingeschränkt werden. Die folgenden Umformungen zeigen, dass die Summe ohne $c_{i,j}$ sogar größer als Eins sein muss, um die Summe zu verringern.

$$-\frac{b_j}{c_{i,j}} \cdot \sum\limits_{\substack{l=1\\ l\neq j}}^n \left( c_{i,l} \right) + \frac{b_j}{c_{i,j}} < 0$$

$$\Longleftrightarrow -\sum\limits_{\substack{l=1\\ l\neq j}}^n \left( c_{i,l} \right) + 1 < 0 b_j c_{i,j}$$

$$\Longleftrightarrow \sum\limits_{\substack{l=1\\ l\neq j}}^n \left( c_{i,l} \right) - 1 > 0$$

$$\Longleftrightarrow \sum\limits_{\substack{l=1\\ l\neq j}}^n \left( c_{i,l} \right) > 1$$

Ein Eintrag $c_{i,j}$ , der diese Voraussetzungen erfüllt, garantiert noch nicht, dass nach dem Min-Schritt mindestens ein Eintrag in der b-Spalte negativ ist. Somit muss, nachdem ein Eintrag nach diesen sehr einfachen Kriterien gefunden ist, geprüft werden, ob sich ein ungültiges Ergebnis ergibt.

Damit die minimale Summe der b-Spalte und somit das bestmögliche Ergebnis gefunden wird, muss so oft ein Min-Schritt durchgeführt werden, bis kein dafür geeignetes Element mehr vorhanden ist. Durch Einsetzen der im Gleichungsystem stehenden Einträge in die genannten Formeln¹⁷, können die entsprechenden Kontrollpunkte berechnet werden.