De Casteljau-algoritmen

De Casteljau-algoritmen innanføre numerisk analyse er ein rekursiv algoritme for å rekna ut bézier-kurver eller polynom på bernsteinform.

Algoritmen er tregare enn å rekna ut bézier-kurva direkte, men algoritmen har føremonen med at han er meir numerisk stabil.

Definisjon

La $c_{i}$ vera kontrollpunkta til kurva.

Det initielle steget i algoritmen er:

$c_{i}^{0}=c_{i}$

For kvar $r=\{1,..n\}$ reknar ein ut:

$c_{i}^{r}=(1-t)c_{i}^{r-1}+tc_{i+1}^{r-1}$

Der $i=\{0,1,..,n-r\}$.

Algoritmen kan illustrerast ved ein trestruktur. Første kolonnen utgjer verdiane for $c_{i}^{0}$, altså dei initielle verdiane til algoritmen. Andre kolonnen er resultatet av første iterasjon av algoritmen. Det siste punktet algoritmen reknar ut er $c_{0}^{n}=p(t)$, altså den siste kolonnen. Dette svarar til bézier-kurva av grad n.

${\begin{matrix}c_{0}&=c_{0}^{(0)}&&&\\&&c_{0}^{(1)}&&\\c_{1}&=c_{1}^{(0)}&&&\\&&&\ddots &\\\vdots &&\vdots &&c_{0}^{(n)}\\&&&&\\c_{n-1}&=c_{n-1}^{(0)}&&&\\&&c_{n-1}^{(1)}&&\\c_{n}&=c_{n}^{(0)}&&&\\\end{matrix}}$

Kvar $c_{i}^{r}$ er i seg sjølv ei bézierkurve med grad $r$.

Døme

Me går ut i frå tre kontrollpunkt $c_{0},c_{1},c_{2}$.

$c_{0}^{(0)}=c_{0},\qquad c_{1}^{(0)}=c_{1},\qquad c_{2}^{(0)}=c_{2}$

Første iterering:

$c_{0}^{(1)}=c_{0}^{(0)}(1-t_{0})+c_{1}^{(0)}t_{0}=c_{0}(1-t_{0})+c_{1}t_{0}$

$c_{1}^{(1)}=c_{1}^{(0)}(1-t_{0})+c_{2}^{(0)}t_{0}=c_{1}(1-t_{0})+c_{2}t_{0}$

Andre og siste iterering:

$c_{0}^{(2)}=c_{0}^{(1)}(1-t_{0})+c_{1}^{(1)}t_{0}$

$=c_{0}(1-t_{0})(1-t_{0})+c_{1}t_{0}(1-t_{0})+c_{1}(1-t_{0})t_{0}+c_{2}t_{0}t_{0}$

$=c_{0}(1-t_{0})^{2}+c_{1}2t_{0}(1-t_{0})+c_{2}t_{0}^{2}$

Som er bézier-kurva av grad 2 funnen ut i frå dei gjevne kontrollpunkta $c_{0},c_{1},c_{2}$.