Algorytm de Casteljau

Algorytm de Casteljau

Algorytm de Casteljau, opracowany przez Paula de Casteljau, służy do wyznaczania punktów na krzywej Béziera, korzystając z baz wielomianów Bernsteina. Proces ten opiera się na łamanej zdefiniowanej przez $n+1$ wierzchołków $p\_0,p\_1,\backslash dots,p\_n$ oraz parametrze $t\; \backslash in\; [0,1]$.

W algorytmie każdy odcinek łamanej dzieli się w stosunku $t\; :\; \{1-t\}$, co generuje $n$ nowych wierzchołków, tworzących nową łamaną. Proces ten powtarza się, aż uzyskamy jeden punkt $p(t)$, co wymaga wykonania $n$ kroków. Rezultatem jest ciąg $n+1$ punktów w kolejnych krokach:

$\backslash begin\{matrix\}\; p\_0^\{(0)\},\; p\_1^\{(0)\},\; p\_2^\{(0)\},\; \backslash dots,\; p\_n^\{(0)\}\; \backslash \backslash \; p\_0^\{(1)\},\; p\_1^\{(1)\},\; p\_2^\{(1)\},\; \backslash dots,\; p\_\{n-1\}^\{(1)\}\; \backslash \backslash \; \backslash vdots\; \backslash \backslash \; p\_0^\{(n-1)\},\; p\_1^\{(n-1)\}\; \backslash \backslash \; p\_0^\{(n)\}\; \backslash \backslash \; \{\}\; \backslash end\{matrix\}$

Punkt $p(t)^\{(n)\}$ leży na krzywej Béziera, której kontrolną łamaną są punkty wyjściowe $p\_0^\{(0)\},\; p\_1^\{(0)\},\; \backslash dots,\; p\_n^\{(0)\}.$ Stosując algorytm dla wszystkich wartości $t$ w przedziale $[0,1]$, otrzymujemy pełną krzywą Béziera.

Zastosowania algorytmu de Casteljau

• Wyznaczanie punktów kontrolnych dla dwóch krzywych, zapewniając ich ciągłość geometryczną (np. krzywa B-sklejana).
• Podział krzywej na dwie w punkcie $p(t)$. Łamane kontrolne obu krzywych są definiowane przez punkty na brzegach „trójkąta punktów”:

Kontrolna łamana pierwszej krzywej: $p\_0^\{(0)\},\; p\_0^\{(1)\},\; \backslash dots,\; p\_0^\{(n-1)\},\; p\_0^\{(n)\}.$ Kontrolna łamana drugiej krzywej: $p\_n^\{(0)\},\; p\_\{n-1\}^\{(1)\},\; \backslash dots,\; p\_1^\{(n-1)\},\; p\_0^\{(n)\}.$ Obie krzywe mają ten sam stopień co dzielona krzywa.

Bibliografia

• Casteljau