Das Kefk Network Wiki befindet sich im Testbetrieb.

De Casteljau-Algorithmus

Aus Kefk.

Wechseln zu: Navigation, Suche

Der Algorithmus von de Casteljau ermöglicht die effiziente Berechnung einer beliebig genauen Näherungsdarstellung von Bézierkurven durch einen Polygonzug. Der Algorithmus wurde Anfang der 1960er Jahre von Paul de Faget de Casteljau (*1930 in Besançon, Frankreich) bei Citroën entwickelt.

Inhaltsverzeichnis

Idee

Der Algorithmus von de Casteljau beruht darauf, dass eine Bézierkurve geteilt und durch zwei aneinandergesetzte Bézierkurven dargestellt werden kann. Diese Unterteilung kann rekursiv fortgesetzt werden. Das Kontrollpolygon der zusammengesetzten Bézierkurve nähert sich dabei der Originalkurve an. Nach ausreichend vielen Verfeinerungsschritten kann der entstandene Polygonzug als Näherung für die Originalkurve verwendet werden. Ein Verfeinerungsschritt, der das Kontrollpolygon einer Ausgangskurve in ein Kontrollpolygon einer zusammengesetzten Kurve zerlegt, besteht nur aus wenigen einfachen Teilungen von Polygonkanten.

Darüberhinaus ermöglicht der Algorithmus die schnelle Bestimmung jedes einzelnen Punktes auf der Bézierkurve durch seine parametrische Darstellung.

Erweiterungen findet der Algorithmus im Blossoming wie auch im fokalen Algorithmus von de Casteljau.

Algorithmus

Gegeben sind die Kontrollpunkte P_0,\ P_1,\ \dots,\ P_n der Ausgangskurve C(t)=\sum_{i=0}^n P_i B_{i,n}(t) (t \in [0, 1]).

Von den Kontrollpunkten der Ausgangskurve C(t) liegen im Allgemeinen nur P0 und Pn auf der Kurve. Der Algorithmus berechnet im ersten Schritt einen weiteren Punkt C(t0) der Kurve. Dabei kann t_0 \in (0,1) frei gewählt werden. Die Kurve wird im Weiteren an diesem Punkt C(t0) geteilt. Es bietet sich daher die Wahl von t_0 = \frac 1 2 an, weil dies eine gleichmäßige Aufteilung und damit eine schnelle Annäherung des Kontrollpolygons an die Ausgangskurve gewährleistet.

Bilden von Teilverhältnissen

Bild:De Casteljau construction 1.png
Konstruktion der ersten Folge von Hilfspunkten Pi(1) aus den Ausgangspunkten Pi(0).

Statt durch direktes Einsetzen von t0 in die Gleichung der Kurve C(t) geschieht die Berechnung von C(t0) über die Konstruktion von Punkten P_i^{(k)} aus den gegebenen Kontrollpunkten P_0,\ \dots\ P_n. Die Konstruktion startet mit den Ausgangspunkten P_i^{(0)} = P_i. Aus diesen werden durch Teilen der Verbindungslinien \overline{P_{i}^{(k)} P_{i+1}^{(k)}} im Verhältnis t_0\ :\ 1 - t_0 neue Punkte P_{i}^{(k+1)} konstruiert. Der Punkt P_{i}^{(k+1)} berechnet sich nach der intuitiv einsichtigen Formel:

P_i^{(k+1)} = (1-t_0) \cdot P_i^{(k)} + t_0 \cdot P_{i+1}^{(k)}

In nebenstehender Abbildung sind die Punkte P_i^{(1)}, die aus den Ausgangspunkten P_i^{(0)} = P_i hervorgegangen sind, rot eingezeichnet. Durch Fortsetzen der Berechnungsvorschrift werden in gleicher Weise Punkte P_i^{(2)},\ P_i^{(3)},\ \dots,\ P_i^{(n)} bestimmt. Zur Berechnung von P_i^{(2)} werden dazu die blau gestrichelten Verbindungslinien der im ersten Schritt berechneten Punkte \overline{P_i^{(1)} P_{i+1}^{(1)}} im selben Verhältnis geteilt, usw.

Konstruktion eines Kurvenpunktes

Es gilt die folgende Aussage (siehe Beweis der Punktkonstruktion):

C(t_0) = P_0^{(n)}
Bild:De Casteljau construction 2.png
Komplette Konstruktion von P0(3) für n=3

Das heißt, dass der Punkt P_0^{(n)}, welcher in der nten Iteration durch fortgesetztes Streckenteilen konstruiert wird, ein Punkt der Kurve ist. Das Teilungsverhältnis t0 bestimmt dabei seine Lage auf der Kurve.

In nebenstehender Abbildung ist die Konstruktion für n = 3 vollständig durchgeführt. Der Punkt P_0^{(3)}, der durch dreifache Anwendung der Teilungsvorschrift aus den Ausgangspunkten P_0,\ \dots,\ P_3 hervorgegangen ist, liegt auf der gesuchten Kurve.

Die bei weitem interessantere Aussage ist aber, dass dieser Punkt P_0^{(n)} die Kurve C(t) in zwei Bézierkurven C1(t) und C2(t) teilt und dass die Punkte P_0^{(i)}\ (i=0\dots n) das Kontrollpolygon von C1(t) und die Punkte P_i^{(n-i)}\ (i=0\dots n) das Kontrollpolygon von C2(t) bilden.

Teilen in zwei Bézierkurven

Bild:De Casteljau construction 3.png
Zerlegung von C(t) in C1(t) und C2(t)

Nebenstehende Abbildung zeigt die Zerlegung von C(t) in C1(t) und C2(t) für n = 3. Dabei bilden die Punkte P_0^{(0)}, P_0^{(1)}, P_0^{(2)} und P_0^{(3)} das Kontrollpolygon von C1(t) und entsprechend die Punkte P_0^{(3)}, P_1^{(2)}, P_2^{(1)} und P_3^{(0)} das Kontrollpolygon von C2(t).

An der Abbildung erkennt man außerdem, warum in der Regel ein Teilungsverhältnis von t_0 = \frac 1 2 verwendet wird. Da in diesem Beispiel ein Teilungsverhältnis kleiner \frac 1 2 verwendet wurde, teilt sich die Kurve C(t) in einem ungleichen Verhältnis in eine kurze Kurve C1(t) und eine lange Kurve C2(t) auf. Der kürzere Teil ist viel besser an sein Kontrollpolygon angenähert als der längere. Möchte man (bei ungefähr gleich langen Strecken des Ausgangskontrollpolygons) eine gleichmäßige Näherung erreichen, eignet sich dazu das Teilungsverhältnis t_0 = \frac 1 2.

Die Unterteilung der Kurven wird so lange fortgesetzt, bis sie hinreichend genau durch ihre Kontrollpolygone angenähert sind.

Code

Pseudocode

Zu Beginn liegen die Punkte des Kontrollpolygons in einem Feld P_i,\ i=0 \ldots n vor. Bei gegebenem Parameter t0 wird der Punkt C(t0) folgendermaßen berechnet: 

BEGIN
    FOR i:=0..n
        P_i^{(0)} := P_i

    FOR j:=1..n
        FOR i:=0..(n-j)
            // Unterteilung mit Faktor t
            P_i^{(j)} = (1-t_0) \cdot P_i^{(j-1)} + t_0 \cdot P_{i+1}^{(j-1)} 

    RETURN P_0^{(n)}
END

Der obige Algorithmus ist insoweit unvollständig, dass nur der Punkt C(t0) bestimmt, aber keine fortgesetzte Unterteilung von C(t) durchgeführt wird. Der Algorithmus ist nicht speichereffizient, da für alle P_i^{(j)} neue Speicherplätze belegt werden.

Implementierung in Java

Eine vollständige rekursive Variante des Algorithmus zeigt folgender Javacode. Die Parameter sind:

  • Graphics g gibt die Grafikoberfläche an, auf die das Resultat gezeichnet werden soll. Der Parameter sollte sich leicht auf andere Sprachen übertragen lassen.
  • double[] px und py geben die Koordinaten der Anfangspunkte P_i,\ i=0 \ldots n an.
  • double t ist der Teilungsparameter t0
  • int iter gibt die Anzahl der Iterationen an. Es kann sinnvoll sein, eine andere Abbruchbedingung zu implementieren. Zum Beispiel bietet es sich an, den Algorithmus abbrechen zu lassen, sobald die Teilkurven eine bestimmte Länge unterschreiten 
public void drawBezier
   (Graphics g, double[] px, double[] py, double t, int iter)
{
  int X = 0;
  int Y = 1;

  int n = px.length-1;

  //Array für die Werte P_i^{(j)}
  //Feld 1 entspricht i
  //Feld 2 entspricht j
  //Feld 3 gibt an, um welche Koordinate es sich handelt
  double[][][] q = new double[n+1][n+1][2];

  for (int i = 0; i < n+1; i++)
  {
    q[i][0][X] = px[i];
    q[i][0][Y] = py[i];
  }

  for (int j = 1; j <= n; j++)
    for (int i = 0; i <= (n-j); i++)
    {
      q[i][j][X] = (1 - t) * q[i][j - 1][X] + t * q[i + 1][j - 1][X];
      q[i][j][Y] = (1 - t) * q[i][j - 1][Y] + t * q[i + 1][j - 1][Y];
    }

    //Arrays für die Punkte der geteilten Kontrollpolygone C1, C2)
    double[] c1x = new double[n+1];
    double[] c1y = new double[n+1];
    double[] c2x = new double[n+1];
    double[] c2y = new double[n+1];

    for (int i=0;i<n+1;i++)
    {
      c1x[i] = q[0][i][X];
      c1y[i] = q[0][i][Y];
      c2x[i] = q[i][n-i][X];
      c2y[i] = q[i][n-i][Y];
    }

    if(iter>=0)
    {
      drawBezier(g, c1x, c1y, t, --iter);
      drawBezier(g, c2x, c2y, t, --iter);
    }
    else
    {
      for (int i=0;i<n;i++)
      {
        //Kurve C1 zur Linie vereinfacht
        int b1x1 = (int) Math.round(q[0][i][X]);
        int b1y1 = (int) Math.round(q[0][i][Y]);
        int b1x2 = (int) Math.round(q[0][i+1][X]);
        int b1y2 = (int) Math.round(q[0][i+1][Y]);

        //Kurve C2 zur Linie vereinfacht
        int b2x1 = (int) Math.round(q[i][n-i][X]);
        int b2y1 = (int) Math.round(q[i][n-i][Y]);
        int b2x2 = (int) Math.round(q[i+1][n-i-1][X]);
        int b2y2 = (int) Math.round(q[i+1][n-i-1][Y]);

        g.drawLine(b1x1, b1y1, b1x2, b1y2);
        g.drawLine(b2x1, b2y1, b2x2, b2y2);
      }
    }
  }

Anmerkung: Der Code ist zwar vollständig, aber immer noch nicht bezüglich des Speicherplatzes optimiert.

Beweis der Punktkonstruktion

Die Aussage, dass über n-fach fortgesetzte Streckenteilung ein weiterer Punkt der Kurve konstruiert werden kann, lässt sich über Lösen der Rekurrenz beweisen, die P_i^{(j)} definiert.

Rekurrenz-Gleichung

Die Rekurrenz-Gleichung definiert die Punkte P_i^{(k)} in Abhängigkeit der in der letzten Iteration berechneten Punkte P_i^{(k-1)}. Den Start der Rekurrenz bilden die Punkte Pi:

P_i^{(0)} = P_i
P_i^{(k)} = (1-t_0) \cdot P_i^{(k-1)} + t_0 \cdot P_{i+1}^{(k-1)}

Zu beweisende Aussage

Zu beweisen ist die Aussage, dass der Punkt P_0^{(n)} ein Punkt der Kurve an der Stelle t0 ist:

P_0^{(n)} = C(t_0)

Verallgemeinerung der Aussage

Um eine Lösung der Rekurrenz für den speziellen Punkt P_0^{(n)} zu finden, wird eine geschlossene Form für alle Punkte P_i^{(k)} der Rekurrenz gesucht und gezeigt, dass diese insbesondere für P_0^{(n)} das gesuchte Resultat liefert. Der Beweis für P_i^{(k)} wird über vollständige Induktion mit folgender Induktionsannahme geführt:

P_i^{(k)} = \sum_{m=0}^{k} P_{i+m} {k \choose m} t_0^m (1-t_0)^{k-m}.

Der Induktionsschritt ist dann gradlinige Rechnung, bei der Aussagen über Binomialkoeffizienten benutzt werden.

Anwendung

Mit Hilfe des Algorithmus von de Casteljau ist es möglich, Näherungen von Bézierkurven durch gerade Linien zu errechnen. Dadurch kann eine Bézierkurve effizient mit dem Rechner gezeichnet werden.

Weblinks

Von „http://www.kefk.org/wiki/De_Casteljau-Algorithmus“
Persönliche Werkzeuge