|
1.6 De Casteljauov algoritmus
De Casteljauov algoritmus patrí medzi najzákladnejšie algoritmy, používané pri modelovaní kriviek a plôch. Algoritmus má veľké využitie nielen pri vyčísľovaní a vykresľovaní Bézierovych kriviek, ale svoju významnú úlohu zohráva aj pri skúmaní samotných vlastností Bézierovych kriviek.
Algoritmus
Vstup: Vrcholy V0,...,Vn riadiaceho polygónu Bézierovej krivky a parameter t z intervalu <0,1>
Výstup: Hodnota (bod ležiaci na krivke) prislúchajúca parametru t
Algoritmus na n+1 krokov vypočíta bod
V
0
n
prislúchajúci parametru t. V r-tom kroku algoritmu vypočítame z množiny n-r+1 bodov
V
0
r
,
.
.
.
,
V
n-r
r
pomocou predpisu
V
i
r
+
1
=
1
−
t
V
i
r
+
t
V
i
+
1
r
,
kde
i
=
0
,
.
.
.
,
n-(r+1)
n-r bodov ktoré budú použité v nasledujúcom r+2 kroku. V prvom kroku sú pre výpočet použité vstupné body t.j.
V
i
0
=
V
i
. V poslednom kroku získame práve jeden bod prislúchajúci
V
0
r
prislúchajúci parametru t.
Formálny zápis
1,
V
i
0
=
V
i
,
kde
i
=
0
,
1
,
.
.
.
,
n
2, Pre r=1,...,n vypočítaj množinu bodov pomocou predpisu
V
i
r
=
1
−
t
V
i
r
−
1
+
t
V
i
+
1
r
−
1
,
kde
i
=
0
,
.
.
.
,
n
-
r
3, Polož
B
n
t
=
V
0
n
Algoritmus 1.1: De Casteljauov algoritmus pre vyčíslenie Bézierovej krivky pre parameter t.
Poznámky
- Výpočet bodu
B
n
t
je možné samozrejme robiť aj dosadením do predpisu Bézierovej krivky. De Casteljauov algoritmus je však numericky stabilnejší a je možné použiť ho aj na vykresľovanie celej krivky.
- Predpis
V
i
r
=
1
−
t
V
i
r
−
1
+
t
V
i
+
1
r
−
1
umiestni bod
V
i
r
na spojnicu bodov
V
i
r
−
1
a
V
i
+
1
r
−
1
vypočítaných v predchádzajúcom kroku, pričom vzdialenosť bodu
V
i
r
od bodov
V
i
r
−
1
, resp
V
i
+
1
r
−
1
je daná parametrom t.
- Vypočítaný bod
V
0
n
leží na Bézierovej krivke danej bodmi V0,...,Vn, pričom túto krivku rozdeľuje na dve časti, ktorých kontrolné polygóny sú dané bodmi
V
0
0
t
,
V
0
1
t
,
.
.
.
,
V
0
n
t
, resp.
V
0
n
t
,
V
1
n
−
1
t
,
.
.
.
,
V
n
0
t
.
|
 |
