Algorytm de Casteljau

Algorytm de Casteljaualgorytm 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 wierzchołków oraz liczba Każdy odcinek łamanej jest dzielony w stosunku czego wynikiem jest wierzchołków, które wyznaczają nową łamaną. Proces powtarzany jest do chwili, aż zostanie jeden punkt co wymaga wykonania kroków. Ostatecznie otrzymuje się ciągów punktów (indeks górny oznacza krok algorytmu):

Punkt leży na krzywej Béziera, której łamaną kontrolną tworzą wyjściowe punkty Wykonując algorytm dla wszystkich z przedziału otrzymywane są wszystkie punkty krzywej Béziera.

Algorytm de Casteljau – cztery kolejne łamane, na czerwono wynikowy punkt Kolorem czarnym narysowano krzywą Béziera, na której leży

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 Łamane kontrolne są wyznaczane przez punkty leżące na brzegach przedstawionego wyżej „trójkąta punktów” – łamaną kontrolną pierwszej krzywej opisują punkty: a drugą: 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.

Media użyte na tej stronie

DeCasteljau-split Bezier curve.svg
Autor: Wojciech Muła, Licencja: CC-BY-SA-3.0
Podział krzywej Beziera za pomocą algorytmu deCasteljau
DeCasteljau-evaluate point.svg
Autor: Wojciech Muła, Licencja: CC-BY-SA-3.0
Algotytm deCasteljau - wyznaczanie punktu na krzywej Beziera