Algorytm de Casteljau
Z Wikipedii
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 Bernstaina.
Dana jest dowolna łamana zdefiniowana przez n + 1 wierzchołków oraz liczba . 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):
Punkt p(t)(n) leży na krzywej Béziera, której łamaną kontrolną tworzą wyjściowe punkty . Wykonując algorytm dla wszystkich t z przedziału [0,1] otrzymywane są wszystkie punkty krzywej Béziera.
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: , a drugą: . Obie krzywe są tego samego stopnia co dzielona krzywa.