imported>Jesi: /* Idee */ lf

2025-11-23T13:51:07Z

Idee: lf

Neue Seite

Der '''Algorithmus von de Casteljau''' ermöglicht die effiziente Berechnung einer beliebig genauen Näherungsdarstellung von [[Bézierkurve]]n durch einen [[Polygonzug (Mathematik)|Polygonzug]]. Der [[Algorithmus]] wurde Anfang der 1960er Jahre von [[Paul de Casteljau|Paul de Faget de Casteljau]] bei [[Citroën]] entwickelt.

== 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über hinaus 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.<ref name="tour">[[Andreas Müller (Informatiker)|Andreas Müller]]: ''A tour d'horizon of de Casteljau's work.'' In: ''Computer Aided Geometric Design'' 113 (102366), September 2024, S. 1–56, [[doi:10.1016/j.cagd.2024.102366]] (englisch).</ref>

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

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

=== Bilden von Teilverhältnissen ===
[[Datei:De Casteljau construction 1.png|mini|Konstruktion der ersten Folge von Hilfspunkten Pi(1) aus den Ausgangspunkten Pi(0).]]
Statt durch direktes Einsetzen von <math>t_0</math> in die Gleichung der Kurve <math>C(t)</math> geschieht die Berechnung von <math>C(t_0)</math> über die Konstruktion von Punkten <math>P_i^{(k)}</math> aus den gegebenen Kontrollpunkten <math>P_0,\ \dots\ P_n</math>. Die Konstruktion startet mit den Ausgangspunkten <math>P_i^{(0)} = P_i</math>. Aus diesen werden durch Teilen der Verbindungslinien <math>\overline{P_{i}^{(k)} P_{i+1}^{(k)}}</math> im Verhältnis <math>t_0\ :\ 1 - t_0</math> neue Punkte <math>P_{i}^{(k+1)}</math> konstruiert. Der Punkt <math>P_{i}^{(k+1)}</math> berechnet sich nach der intuitiv einsichtigen Formel:

: <math>P_i^{(k+1)} = (1-t_0) \cdot P_i^{(k)} + t_0 \cdot P_{i+1}^{(k)}</math>

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

=== Konstruktion eines Kurvenpunktes ===
Es gilt die folgende Aussage (siehe [[#Beweis der Punktkonstruktion|Beweis der Punktkonstruktion]]):

: <math>C(t_0) = P_0^{(n)}</math>

[[Datei:De Casteljau construction 2.png|mini|Komplette Konstruktion von P0(3) für n=3]]
Das heißt, dass der Punkt <math>P_0^{(n)}</math>, welcher in der <math>n</math>ten [[Iteration]] durch fortgesetztes Streckenteilen konstruiert wird, ein Punkt der Kurve ist. Das Teilungsverhältnis <math>t_0</math> bestimmt dabei seine Lage auf der Kurve.

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

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

=== Teilen in zwei Bézierkurven ===
[[Datei:De Casteljau construction 3.png|mini|Zerlegung von C(t) in C1(t) und C2(t)]]
Nebenstehende Abbildung zeigt die Zerlegung von <math>C(t)</math> in <math>C_1(t)</math> und <math>C_2(t)</math> für <math>n = 3</math>. Dabei bilden die Punkte <math>P_0^{(0)}</math>, <math>P_0^{(1)}</math>, <math>P_0^{(2)}</math> und <math>P_0^{(3)}</math> das Kontrollpolygon von <math>C_1(t)</math> und entsprechend die Punkte <math>P_0^{(3)}</math>, <math>P_1^{(2)}</math>, <math>P_2^{(1)}</math> und <math>P_3^{(0)}</math> das Kontrollpolygon von <math>C_2(t)</math>.

An der Abbildung erkennt man außerdem, warum in der Regel ein Teilungsverhältnis von <math>t_0 = \frac 1 2</math> verwendet wird. Da in diesem Beispiel ein Teilungsverhältnis kleiner ½ verwendet wurde, teilt sich die Kurve <math>C(t)</math> in einem ungleichen Verhältnis in eine kurze Kurve <math>C_1(t)</math> und eine lange Kurve <math>C_2(t)</math> 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 <math>t_0 = \frac 1 2</math>.

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

=== Komplexität ===
Eine native [[Implementierung]] des Algorithmus benötigt <math>\mathcal{O}(n^2)</math> Rechenschritte für jeden zu berechnenden Näherungspunkt, wobei <math>n</math> die Anzahl der Kontrollpunkte ist. Durch Optimierungen kann eine Laufzeit von <math>\mathcal{O}(n\log n)</math> erreicht werden.<ref>{{Internetquelle |url=https://arxiv.org/pdf/1711.08453.pdf |titel=Fast and Stable Pascal Matrix Algorithms |format=PDF |abruf=2021-09-13}}</ref>

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

BEGIN
FOR i:=0..n
<math>P_i^{(0)} := P_i</math>

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

RETURN <math>P_0^{(n)}</math>
END

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

== Beweis der Punktkonstruktion ==
Die Aussage, dass über <math>n</math>-fach fortgesetzte Streckenteilung ein weiterer Punkt der Kurve konstruiert werden kann, lässt sich über Lösen der [[Rekursion]] beweisen, die <math>P_i^{(j)}</math> definiert.

=== Rekursionsgleichung ===
Die Rekursionsgleichung definiert die Punkte <math>P_i^{(k)}</math> in Abhängigkeit von den in der letzten Iteration berechneten Punkten <math>P_i^{(k-1)}</math>. Den Start der Rekursion bilden die Punkte <math>P_i</math>:

:<math>P_i^{(0)} = P_i</math>

:<math>P_i^{(k)} = (1-t_0) \cdot P_i^{(k-1)} + t_0 \cdot P_{i+1}^{(k-1)}</math>

=== Zu beweisende Aussage ===
Zu beweisen ist die Aussage, dass der Punkt <math>P_0^{(n)}</math> ein Punkt der Kurve an der Stelle <math>t_0</math> ist:

:<math>P_0^{(n)} = C(t_0)</math>

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

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

Der Induktionsschritt ist dann eine gradlinige Rechnung, bei der Aussagen über [[Binomialkoeffizient]]en benutzt werden.

== Siehe auch ==
* [[Bernsteinpolynom]]
* [[Konvexkombination]]

== 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.

== Literatur ==
* {{cite journal |title=De Casteljau's autobiography: My time at Citroën |date=August 1999 |journal=Computer Aided Geometric Design |volume=16 |issue=7 |pages=583–586 |doi=10.1016/S0167-8396(99)00024-2 |last1=de Faget de Casteljau |first1=Paul |language=en}}
* {{cite journal |title=On de Casteljau's algorithm |date=August 1999 |journal=Computer Aided Geometric Design |volume=16 |issue=7 |pages=587–605 |doi=10.1016/S0167-8396(99)00023-0 |last1=Boehm |first1=Wolfgang |last2=Mueller |first2=Andreas |language=en}}

== Weblinks ==
* [http://www.kaktoos.de/fh_projekte/cg_casteljau/casteljau.html De Casteljau Polygone und Bezierkurve (Applet)]
* [http://www.doc.ic.ac.uk/~dfg/AndysSplineTutorial/Beziers.html De Casteljau Bezierkurve (Applet, englisch)]
* Kaspar Fischer: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.162&rep=rep1&type=pdf ''Piecewise Linear Approximation of Bézier Curves.''] (PDF, englisch).

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus (Computergrafik)]]
[[Kategorie:Geometrische Modellierung]]
[[Kategorie:Numerische Mathematik]]

De-Casteljau-Algorithmus - Versionsgeschichte

imported>Jesi: /* Idee */ lf