Algorytm de Casteljau

Algorytm de Casteljau – algorytm opracowany przez Paula de Casteljau, pozwalający na wyznaczenie punktów na wielomianowej krzywej Béziera, czyli obliczanie wartości wielomianów w bazie wielomianów Bernsteina.

Dana jest dowolna łamana zdefiniowana przez $n+1$ wierzchołków $p_0,p_1,\dots ,p_n$ oraz liczba $t\in [0,1].$ Każdy odcinek łamanej jest dzielony w stosunku $t:1-t,$ czego wynikiem jest $n$ wierzchołków, które wyznaczają nową łamaną. Proces powtarzany jest do chwili, aż zostanie jeden punkt $p(t),$ co wymaga wykonania $n$ kroków. Ostatecznie otrzymuje się $n+1$ ciągów punktów (indeks górny oznacza krok algorytmu):

$\begin{array}{c}{p}_0^{(0)},p_1^{(0)},p_2^{(0)},p_3^{(0)},\dots ,p_n^{(0)}\\ p_0^{(1)},p_1^{(1)},p_2^{(1)},\dots ,p_{n-1}^{(1)}\\ ⋮\\ p_0^{(n-1)},p_1^{(n-1)}\\ p_0^{(n)}\end{array}$

Punkt $p(t{)}^{(n)}$ leży na krzywej Béziera, której łamaną kontrolną tworzą wyjściowe punkty $p_0^{(0)},p_1^{(0)},p_2^{(0)},\dots ,p_n^{(0)}.$ Wykonując algorytm dla wszystkich $t$ z przedziału $[0,1]$ otrzymywane są wszystkie punkty krzywej Béziera.

Algorytm de Casteljau – cztery kolejne łamane, na czerwono wynikowy punkt $p(t)(t=0,37).$ Kolorem czarnym narysowano krzywą Béziera, na której leży $p(t).$

Za pomocą algorytmu de Casteljau można również:

• Wyznaczyć punkty kontrolne dwóch krzywych, tak aby połączyć je z zadaną ciągłością geometryczną (zob. krzywa B-sklejana).
• Podzielić krzywą na dwie krzywe w punkcie $p(t).$ Łamane kontrolne są wyznaczane przez punkty leżące na brzegach przedstawionego wyżej „trójkąta punktów” – łamaną kontrolną pierwszej krzywej opisują punkty: $p_0^{(0)},p_0^{(1)},\dots ,p_0^{(n-1)},p_0^{(n)},$ a drugą: $p_n^{(0)},p_{n-1}^{(1)},\dots ,p_1^{(n-1)},p_0^{(n)}.$ Obie krzywe są tego samego stopnia co dzielona krzywa.

Podział krzywej Béziera algorytmem de Casteljau

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę