Algoritmus de Casteljo

Ve výpočetní matematice je de Castelljouův algoritmus , pojmenovaný po svém vynálezci Paulu de Castelljou , rekurzivní metodou pro určení tvaru Bernsteinových polynomů nebo Bezierových křivek . Algoritmus de Castelljot lze také použít k rozdělení Bezierovy křivky na dvě části libovolnou hodnotou parametru . $(t)$

Výhodou algoritmu je jeho vyšší výpočetní stabilita oproti přímé metodě.

Popis

Je dán Bernsteinův polynom B stupně n

B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),

kde b je základem Bernsteinova polynomu, lze polynom v bodě t 0 definovat pomocí rekurentního vztahu

\beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n

\beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{ (j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,nj{\mbox{ , }}j=1,\ldots ,n

Potom lze definici v bodě definovat v krocích algoritmu. Výsledek je dán: $B$ $t_0$ $n$ $B(t_{0})$

B(t_{0})=\beta _{0}^{(n)}.

Také Bézierovu křivku lze v bodě rozdělit na dvě křivky s odpovídajícími kotevními body: $B$ $t_0$

{\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)))

{\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)))

Geometrická interpretace

Geometrický výklad de Castelljouova algoritmu je jednoduchý:

Je dána Bezierova křivka s kotevními body . Spojením referenčních bodů v sérii od prvního k poslednímu dostaneme přerušovanou čáru . ${\displaystyle \scriptstyle P_{0},...,P_{n))$
Každý výsledný segment této přerušované čáry v poměru rozdělíme a výsledné body spojíme. V důsledku toho dostaneme přerušovanou čáru s počtem segmentů o jeden menším, než byla původní přerušovaná čára. $\scriptstyle t:(1-t)$
Postup opakujeme, dokud nezískáme jediný bod. Tento bod bude bodem na dané Bezierově křivce s parametrem . $\scriptstyle t$

Následující obrázek ukazuje tento proces pro kubickou Bezierovu křivku:

Je třeba poznamenat, že mezilehlé body získané během procesu výstavby jsou referenčními body pro dvě nové Bézierovy křivky, které se přesně shodují s tou původní, a dohromady dávají původní Bézierovu křivku. Tento algoritmus nejen určuje bod křivky v , ale také rozděluje křivku na dvě části v , a také poskytuje popis dvou dílčích křivek v Bézierově formě (v parametrické reprezentaci ). $\scriptstyle t$ $\scriptstyle t$

Popsaný algoritmus je platný pro neracionální Bézierovy křivky. Chcete-li vypočítat racionální křivky v , můžete promítnout bod do ; například křivka ve 3D prostoru musí mít kontrolní body a váhy promítnuté do kontrolních bodů hmotnosti . Pak obvykle algoritmus pokračuje v interpolaci v . Výsledné 4D body lze promítnout zpět do 3D prostoru pomocí perspektivního dělení. $\scriptstyle \mathbf {R} ^{n}$ $\scriptstyle \mathbf {R} ^{n+1}$ $\scriptstyle \{(x_{i},y_{i},z_{i})\}$ $\scriptstyle \{w_{i}\}$ $\scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$ ${\displaystyle \scriptstyle \mathbf {R} ^{4))$

Obecně jsou operace na racionálních křivkách (nebo plochách) ekvivalentní operacím na neracionálních křivkách v projektivním prostoru . Reprezentace kotevních bodů jako vážených je často užitečná pro definování racionálních křivek.

Algoritmus de Casteljo

Popis

Geometrická interpretace

Odkazy

Viz také