Algorytm de Casteljau

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm de Casteljau opracowany przez Paula de Casteljau pozwala 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,\ldots,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):

p_0^{(0)}, p_1^{(0)}, p_2^{(0)}, p_3^{(0)}, \ldots, p_n^{(0)}
p_0^{(1)}, p_1^{(1)}, p_2^{(1)}, \ldots, p_{n-1}^{(1)}
\vdots
p_0^{(n-1)}, p_1^{(n-1)}
 p_0^{(n)}

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)}, \ldots, 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ą. Patrz: 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)}, \ldots, p_0^{(n-1)}, p_0^{(n)}, a drugą: p_n^{(0)}, p_{n-1}^{(1)}, \ldots, p_1^{(n-1)}, p_0^{(n)}. Obie krzywe są tego samego stopnia co dzielona krzywa.
Podział krzywej Béziera algorytmem de Casteljau

Bibliografia[edytuj | edytuj kod]