$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Algorithme de de Casteljau

L'algorithme de de Casteljau est un algorithme permettant la construction par barycentrages successifs de points d'une courbe de Bézier. On rappelle que la courbe de Bézier de points de contrôle $P_0,\dots,P_n$ est la courbe paramétrée donnée par $$M(t)=\textrm{Bar}\big( (P_0,B_0^n(t)), (P_1,B_1^n(t)),\dots, (P_n,B_n^n(t) ) \big)$$ où $$B_k^n(t)=\binom nk t^k(1-t)^{n-k}.$$

Si on a 4 points de contrôle, l'algorithme de de Casteljau pour construire le point $M(t)$ comporte 3 étapes :

  • Étape 1 : On commence par construire les 3 barycentres suivants : \begin{eqnarray*} \overrightarrow{OM_0(t)}&=&(1-t)\overrightarrow{OP_0}+t\overrightarrow{OP_1}\\ \overrightarrow{OM_1(t)}&=&(1-t)\overrightarrow{OP_1}+t\overrightarrow{OP_2}\\ \overrightarrow{OM_2(t)}&=&(1-t)\overrightarrow{OP_2}+t\overrightarrow{OP_3}\\ \end{eqnarray*}
  • Étape 2 : On itère et on construit les barycentres de $M_0(t)$ et de $M_1(t)$ avec poids respectifs $1-t$ et $t$, puis de $M_1(t)$ et de $M_2(t)$, avec les mêmes poids. On appelle $N_0(t)$ et $N_1(t)$ les points obtenus, qui vérifient donc : \begin{eqnarray*} \overrightarrow{ON_0(t)}&=&(1-t)\overrightarrow{OM_0(t)}+t\overrightarrow{OM_1(t)}\\ \overrightarrow{ON_1(t)}&=&(1-t)\overrightarrow{OM_1(t)}+t\overrightarrow{OM_2(t)} \end{eqnarray*}
  • Étape 3 : On itère et on construit les barycentres de $N_0(t)$ et de $N_1(t)$, toujours avec les poids respectifs $(1-t)$ et $t$. Le point obtenu est le point $M(t).$

Voici la formulation générale de l'algorithme de de Casteljau:

Théorème : Soient $P_0,\dots,P_n$ des points du plan $\mathcal P$ et soit $t\in[0,1]$. Notons $(M^\ell_k)$ la suite de points de $\mathcal P$ indexée par $\ell\in\{0,1,\cdots,n\}$ et $k\in\{0,1,\cdots,n-\ell\}$ définie par récurrence en posant
  • pour $\ell=0$ : $M_k^0=P_k$, pour tout $k\in\{0,1,\cdots,n\}$;
  • $M_k^{\ell+1}=\textrm{Bar}\big( (M_k^\ell, 1-t), (M_{k+1}^\ell, t)\big)$ pour $\ell\in\{0,1,\cdots,n-1\}$ et $k\in\{0,1,\cdots,n-\ell-1\}$.
Alors on a $$M_0^n=\textrm{Bar}\big( (P_0,B_0^n(t)), (P_1,B_1^n(t)),\dots, (P_n,B_n^n(t) ) \big).$$ En particulier, $M_0^n$ est le point de paramètre $t$ de la courbe de Bézier de points de contrôle $P_0,\dots,P_n$.
Consulter aussi
Recherche alphabétique
Recherche thématique