Interpolation et Approximation de courbes

Interpolation de Lagrange

Pour $n+1$ points on fabrique un polynôme de degré $n$ de la façon suivante :

$${\cal L}_i(t)=\frac{(t-t_0)(t-t_1)\ldots(t-t_{i-1})(t-t_{i+1}... ...i-t_0)(t_i-t_1)\ldots(t_i-t_{i-1})(t_i-t_{i+1})\ldots(t_i-t_n)}$$

Alors le polynôme dont la représentation passe par les $n+1$ points est :

$${\cal Q}_i(t)=\sum_{i=0}^n P_i.{\cal L}_i(t)$$

Cubiques paramétrées d'Hermite

On veut définir une courbe de degré 3 passant par deux points et dont les tangentes en ce points sont données. Soit :

$${\cal T}=\left(\begin{tabular}{c} $t^3$\\ $t^2$\\ $t$\\ $1$\\ \end{tabular}\right)$$

On cherche à exprimer la courbe ${\cal Q}_h(t)={\cal C}_h.{\cal T}$. ${\cal C}$ étant la matrice des contraintes. Ces contraintes peuvent s'écrirent sous la forme ${\cal C}_h={\cal G}_h.{\cal M}_h$. ${\cal G}_h$ étant le vecteur de contrôle géométrique égal à : $(\,P_1\,\,P_4\,\,T_1\,\,T_4\,)$. On a donc :

$${\cal Q}_h(t)={\cal G}_h.{\cal M}_h.\left(\begin{tabular}{c} $t^3$\\ $t^2$\\ $t$\\ $1$\\ \end{tabular}\right)$$

et

$${\cal Q}_h'(t)=\frac{d{\cal Q}_h(t)}{dt}={\cal G}_h.{\cal M}_... ...{tabular}{c} $3t^2$\\ $2t$\\ $1$\\ $0$\\ \end{tabular}\right)$$

On a donc les quatres équations suivantes à résoudre :

$$\begin{tabular}{ll} ${\cal Q}_h(0)={\cal G}_h.{\cal M}_h.\lef... ...$\\ $2$\\ $1$\\ $0$\\ \end{tabular}\right)$ \\ \end{tabular}$$

ce que l'on peut écrire :

$$(\,{\cal Q}_h(0)\,\,{\cal Q}_h(1)\,\,{\cal Q}_h'(0)\,\,{\cal Q}_h'(1)\,)= {\cal G}_h.{\cal M}_h.m$$

avec

$$m=\left(\begin{tabular}{cccc} 0 & 1 & 0 & 3 \\ 0 & 1 & 0 & 2 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ \end{tabular}\right)$$

On a donc :

$$\left\{\begin{tabular}{l} ${\cal Q}_h(0)=P_1$ \\ ${\cal Q}_h(... ... Q}_h'(0)=T_1$ \\ ${\cal Q}_h'(1)=T_4$ \\ \end{tabular}\right.$$

donc

$${\cal M}_h.m=I_d\Longrightarrow m^{-1}={\cal M}_h$$

Ainsi :

$$\left(\begin{tabular}{cccc} 2 & -3 & 0 & 1 \\ -2 & 3 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ 1 & -1 & 0 & 0 \\ \end{tabular}\right)$$

$$\forall\,0\leq t\leq 1,\,{\cal Q}_h(t)=(2t^3-3t^2+1)P_1+t^2(3-2t)P_4+ t(t-1)^2T_1+t^2(t-1)T_4$$

Cubiques paramétrées de Bézier

La contrainte géométrique est cette fois définie par quatre points et non plus deux points et deux tangentes. On construit donc une courbe hermitienne avec $T_1=\beta (P_2-P_1)$ et $T_4=\beta' (P_4-P_3)$. On cherche une courbe du troisième degré ayant un bon comportement, notamment une vitesse uniforme sur la ligne engendrée par quatre points alignés. Prenons $P_1=0$, $P_2=1$, $P_3=2$ et $P_4=3$. On a :

$${\cal Q}_h'(t)=(6t^2-6t)P_1+(-6t^2+6t)P_4+(3t^2-4t+1)T_1+(3t^2-2t)T_4$$

Une vitesse uniforme signifie que $\forall\,t,\,{\cal Q}_h'(t)=K$, donc :

$${\cal Q}_h'(t)=(-6t^2+6t)3+(3t^2-4t+1)\beta+(3t^2-2t)\beta'$$

$${\cal Q}_h'(t)=t^2(-18+3\beta-3\beta')+t(18-4\beta-2\beta')+\beta$$

et donc

$$\beta=\beta'=3$$

On cherche, maintenant, à exprimer la courbe sous la forme ${\cal Q}_b(t)= {\cal G}_b.{\cal M}_b.{\cal T}$. On a ${\cal G}_h=(\,P_1\,\,P_4\,\,T_1\,\,T_4 \,)={\cal G}_b.{\cal M}_{hb}$, c'est-a-dire :

$$(\,P_1\,\,P_4\,\,T_1\,\,T_4\,)=(\,P_1\,\,P_2\,\,P_3\,\,P_4\,)... ...& 0 \\ 0 & 0 & 0 & -3 \\ 0 & 1 & 0 & 3 \\ \end{tabular}\right)$$

donc :

$${\cal Q}_h(t)={\cal G}_h.{\cal M}_h.{\cal T}={\cal G}_b.{\cal M}_{hb}. {\cal M}_h.{\cal T}={\cal G}_b.{\cal M}_b.{\cal T}$$

avec

$${\cal M}_b={\cal M}_{hb}.{\cal M}_h=\left(\begin{tabular}{ccc... ...& 0 \\ -3 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{tabular}\right)$$

Ainsi on obtient :

$$\forall\,0\leq t\leq 1,\,{\cal Q}_b(t)=(1-t)^3P_1+ 3t(1-t)^2P_2+3t^2(1-t)P_3+t^3P_4$$

On peut remarquer que $(1-t)^3+3t(1-t)+3t^2(1-t)+t^3=1$. La formule généralisée de la courbe de Bézier est :

$${\cal Q}_b^{(n+1)}(t)=\sum_{i=0}^nC_n^it^i(1-t)^{n-i}P_i$$

B-Splines Uniformes Cubiques

L'inconvenient des courbes de Bézier (entre autres courbes) est que la modification d'un seul des points influe sur l'ensemble de la courbe. On voudrait que les points ne contrôlent la courbe que localement. On se donne $m\geq 3$ points ( $P_0,\ldots,P_m$). Et l'on construit $m-2$ courbes cubiques : $Q_3,\ldots,Q_m$. Chaque courbe $Q_i$ sera contrôlée par les quatre points $P_{i-3},\,P_{i-2},\,P_{i-1},\,P_i$. On cherche donc à exprimer :

$${\cal Q}_{bs}^{(i)}(t)={\cal G}_{bs}^{(i)}.{\cal M}_{bs}.{\cal T}_i$$

La courbe ${\cal Q}_{bd}^{(i)}(t)$ est définie pour $t_i\leq t<t_{i+1}$. Pour des raisons de commodité on pose $t_3=0$. Et l'uniformité signifie que l'on pose que $\forall\,i,\,t_{i+1}-t_i=1$. On a :

$${\cal G}_{bs}^{(i)}=(\,P_{i-3}\,\,P_{i-2}\,\,P_{i-1}\,\,P_i\,)$$

$${\cal M}_{bs}=\frac{1}{6}\left(\begin{tabular}{cccc} -1 & 3 &... ... & 4 \\ -3 & 3 & 3 & 1 \\ 1 & 0 & 0 & 0 \\ \end{tabular}\right)$$

$$\forall\,t_i\leq t\leq t_{i+1},\,{\cal T}_i=\left(\begin{tabular}{c} $t^3$\\ $t^2$\\ $t$\\ $1$\\ \end{tabular}\right)$$

Un changement de variable ($t'=t-t_i$) nous permet d'obtenir :

$$\forall\,0\leq t\leq 1,\, {\cal Q}_{bs}^{(i)}(t')={\cal G}_{bs}^{(i)}.{\cal M}_{bs}.{\cal T}$$

$${\cal T}_i=\left(\begin{tabular}{c} $t'^3=(t-t_i)^3$\\ $t'^2=(t-t_i)^2$\\ $t'=t-t_i$\\ $1$\\ \end{tabular}\right)$$