Algorytm de Casteljau

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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 . Ł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[edytuj]