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,\mathrm{..}n\}$ reknar ein ut:

$c_i^r=(1-t)c_i^{r-1}+t{c}_{i+1}^{r-1}$

Der $i=\{0,1,\mathrm{..},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{array}{ccccc}{c}_0& =c_0^{(0)}& & & \\ & & c_0^{(1)}& & \\ c_1& =c_1^{(0)}& & & \\ & & & \ddots & \\ ⋮& & ⋮& & c_0^{(n)}\\ & & & & \\ c_{n-1}& =c_{n-1}^{(0)}& & & \\ & & c_{n-1}^{(1)}& & \\ c_n& =c_n^{(0)}& & & \end{array}$

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,c_1^{(0)}=c_1,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$.