Algorytm de
Casteljau
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
4 + 1
wierzchołków oraz liczba
∈
0, 1 .
Każdy odcinek łamanej jest
dzielony w stosunku
/(1 − ),
czego wynikiem jest
4
wierzchołków, które wyznaczają
nową łamaną.
( )
( )
( )
( )
( )
( )
( )
( )
( )
(
)
(
)
( )
)
(
,
,
,
,
0
1
1
1
0
1
1
1
2
1
1
1
0
0
0
3
0
2
0
1
0
0
t
p
p
p
p
p
p
p
p
p
p
p
p
p
n
n
n
n
n
=
−
−
−
M
L
L
5
5
Algorytm de
Casteljau
Proces
powtarzany
jest do
chwili, aż zostanie jeden
punkt
5(), co wymaga
wykonania n kroków.
Ostatecznie otrzymuje się
4 + 1ciągów punktów
(indeks górny oznacza krok
algorytmu):
Punkt
5
8
leży na
krzywej Béziera, której
łamaną kontrolną
tworzą
wyjściowe punkty.
Wykonując algorytm dla
wielu
z przedziału 0,1
otrzymywane są punkty
krzywej Béziera.
( )
( )
( )
( )
( )
( )
( )
( )
( )
(
)
(
)
( )
)
(
,
,
,
,
0
1
1
1
0
1
1
1
2
1
1
1
0
0
0
3
0
2
0
1
0
0
t
p
p
p
p
p
p
p
p
p
p
p
p
p
n
n
n
n
n
=
−
−
−
M
L
L
5
5
Algorytm de Casteljau
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ą –
krz
ywa B-
sklejana
.
Podzielić krzywą na dwie krzywe w punkcie
5().
Łamane kontrolne są wyznaczane przez punkty leżące na
brzegach przedstawionego
trójkąta punktów
- łamaną
kontrolną pierwszej krzywej opisują punkty:
a drugą:
Obie krzywe są tego samego stopnia co dzielona krzywa.
5
8
;
, 5
8A
, 5
8A
, … , 5
8A
, 5
;
8
5
;
;
, 5
;
, 5
;
, … , 5
;
8A
, 5
;
8
