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 {\displaystyle n+1} wierzchołków p 0 , p 1 , … , p n {\displaystyle p_{0},p_{1},\dots ,p_{n}} oraz liczba t ∈ [ 0 , 1 ] . {\displaystyle t\in [0,1].} Każdy odcinek łamanej jest dzielony w stosunku t : 1 − t , {\displaystyle t:{1-t},} czego wynikiem jest n {\displaystyle n} wierzchołków, które wyznaczają nową łamaną. Proces powtarzany jest do chwili, aż zostanie jeden punkt p ( t ) , {\displaystyle p(t),} co wymaga wykonania n {\displaystyle n} kroków. Ostatecznie otrzymuje się n + 1 {\displaystyle n+1} ciągów punktów (indeks górny oznacza krok algorytmu):


p 0 ( 0 ) , p 1 ( 0 ) , p 2 ( 0 ) , p 3 ( 0 ) , … , p n ( 0 ) p 0 ( 1 ) , p 1 ( 1 ) , p 2 ( 1 ) , … , p n − 1 ( 1 ) ⋮ p 0 ( n − 1 ) , p 1 ( n − 1 ) p 0 ( n ) {\displaystyle {\begin{matrix}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)}\\\vdots \\p_{0}^{(n-1)},p_{1}^{(n-1)}\\p_{0}^{(n)}\\{}\end{matrix}}}


Punkt p ( t ) ( n ) {\displaystyle 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 ) , … , p n ( 0 ) . {\displaystyle p_{0}^{(0)},p_{1}^{(0)},p_{2}^{(0)},\dots ,p_{n}^{(0)}.} Wykonując algorytm dla wszystkich t {\displaystyle t} z przedziału [ 0 , 1 ] {\displaystyle [0,1]} otrzymywane są wszystkie punkty krzywej Béziera.

Algorytm de Casteljau – cztery kolejne łamane, na czerwono wynikowy punkt p ( t )   ( t = 0 , 37 ) . {\displaystyle p(t)\ (t=0{,}37).} Kolorem czarnym narysowano krzywą Béziera, na której leży p ( t ) . {\displaystyle 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 ) . {\displaystyle 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 ) , … , p 0 ( n − 1 ) , p 0 ( n ) , {\displaystyle p_{0}^{(0)},p_{0}^{(1)},\dots ,p_{0}^{(n-1)},p_{0}^{(n)},} a drugą: p n ( 0 ) , p n − 1 ( 1 ) , … , p 1 ( n − 1 ) , p 0 ( n ) . {\displaystyle 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

  • Przemysław Kiciak: Podstawy modelowania krzywych i powierzchni: zastosowania w grafice komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 2000. ISBN 83-204-2464-X.
  • Michał Jankowski: Elementy grafiki komputerowej. Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, s. 135–138. ISBN 83-204-1326-5.