Algoritmus de Casteljau – applet

Tento applet demonstruje algoritmus „de Casteljau“ pro vykreslení Bézierovy křivky. Pomocí ovládacích panelů lze detailně prozkoumat jednotlivé kroky při konstrukci algoritmu.

Ovládání appletu

Zvolíme čtyři řídící body postupným naklikáním v ploše grafu. Grafické znázornění algoritmu de Casteljau vyvoláme zaškrtnutím „zobrazit algoritmus“. V případě Bézierových kubik má algoritmus tři iterace, přičemž v poslední dostáváme bod na křivce pro konkrétně zvolené t. Tlačítky „+“ a „–“ můžeme zvyšovat či snižovat počet iterací a sledovat tak průběh algoritmu. Roletkové nabídky vpravo nám umožňují měnit barvy jednotlivých kroků a lépe je rozslišit. Posuvník slouží k volbě „času“ t v intervalu od 0 do 1.

Vpravo nahoře schéma pro výpočet finálního bodu. Textová pole jsou uspořádána do převrácené pyramidy a zobrazují souřadnice nově vypočtených bodů ze zadaných čtyř řídicích. Ty jsou zobrazeny v textových polích v horním řádku. Každá další iterace algoritmu odpovídá dalšímu řádku – směr výpočtu je znázorněn šipkami s příslušným násobkem vedle ní.

Trocha teorie

Algoritmus de Casteljau lze zapsat v rekurentním vztahu takto:

Rekurentní vztah algoritmu de Casteljau.

kde j nese číslo cyklu a i hodnotu pořadí bodu v daném cyklu. Volíme i = 1,2,…,n a j = ii + 1, i + 2,…,n.

Při vykreslování bodu na křivce tímto algoritmem je otázkou, jak daleko od sebe volit hodnoty t, které se pak pospojují úsečkami. Můžeme použít dva postupy. Jedním z nich je rozdělení intervalu času od 0 do 1 s konstantním krokem, např. 0,05. Nevýhodou tohoto způsobu je, že bez ohledu na míru lokálního zakřivení křivky je tento krok, a proto může docházet k nahrazení relativně rovné části zbytečně mnoha úsečkami, zatímco zakřivená část je vykreslena příliš hrubě.

Ukázka způsobů vykreslení křivky.

Na ilustrativním obrázku výše je zřejmé, že vykreslení křivky s konstantním časovým krokem není nejkvalitnější způsob, i když jeho implementace je snadná. Obrázek vlevo ilustruje vykreslení křivky konstantním krokem, který je znázorněn černými body. Pravý obrázek ilustruje kvalitnější způsob vykreslení, kde zakulacená část je aproximována větším množstvím úseček než její rovná část. Výhodou je, že tato metoda generuje menší množství dat než metoda s konstantním krokem, nicméně dobrá implementace je složitější.


(c) 2010, Jakub Malina, Pavel Rajmic, Ústav telekomunikací, FEKT, VUT v Brně