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 .
Výhodou algoritmu je jeho vyšší výpočetní stabilita oproti přímé metodě.
Je dán Bernsteinův polynom B stupně n
kde b je základem Bernsteinova polynomu, lze polynom v bodě t 0 definovat pomocí rekurentního vztahu
Potom lze definici v bodě definovat v krocích algoritmu. Výsledek je dán:
Také Bézierovu křivku lze v bodě rozdělit na dvě křivky s odpovídajícími kotevními body:
Geometrický výklad de Castelljouova algoritmu je jednoduchý:
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 ).
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í.
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.