Spline

	Cet article possède un paronyme ; voir : Spleen.

Dans le domaine mathématique de l'analyse numérique, une spline est une fonction définie par morceaux par des polynômes.

Dans les problèmes d'interpolation, la méthode des splines est souvent préférée à l'interpolation polynomiale, car on obtient des résultats similaires en se servant de polynômes ayant des degrés inférieurs, tout en évitant le phénomène de Runge.

Dans le domaine du design, en construction automobile par exemple, les splines sont utilisées pour approcher des contours complexes. Leur simplicité d'implémentation les rend très populaires et elles sont fréquemment utilisées dans les logiciels de dessin.

Définition

Une courbe spline est une fonction polynomiale par morceaux définie sur un intervalle [a,b] divisé en sous intervalles $[t_{i-1}, t_i]$ tels que :

$a = t_0 < t_1 < \cdots < t_{k-1} < t_k = b$ :

on la note donc $S: [a,b]\to \mathbb{R}$.

Sur chaque intervalle $[t_{i-1}, t_i]$ on définit un polynôme

$P_i: [t_{i-1}, t_i] \to \mathbb{R}$,

Cela nous donne, pour une spline à k intervalles :

$S(t) = P_1 (t) \mbox{ , } t_0 \le t < t_1,$

$S(t) = P_2 (t) \mbox{ , } t_1 \le t < t_2,$

$\vdots$

$S(t) = P_k (t) \mbox{ , } t_{k-1} \le t \le t_k.$

Degré

Le degré de la spline est défini comme étant celui du polynôme $P_i (t)$ de plus haut degré. Si tous les polynômes ont le même degré, on dit que la spline est uniforme. Dans le cas contraire, elle est non uniforme.

Continuité

Sachant que la continuité d'un polynôme est infinie, la continuité d'une spline dépend de la continuité au niveau de la jointure des courbes polynômes.
Si pour tout i $\quad 1 \le i \le k$ et pour tout j tel que $\quad 0 \le j \le n$ l'égalité suivante est vérifiée :

$P_i^{(j)} (t_i) = P_{i+1}^{(j)} (t_i)$.

Alors la spline est de continuité n, notée $C_n$

Exemples

Ligne polygonale

La fonction spline la plus simple est de degré 1, ce qui correspond à une ligne polygonale, couramment appelé ligne brisée.
Graphiquement, ce seront des segments qui relieront chaque point $P_i(t_i)$.
La continuité d'une telle spline sera $C_0$ sauf dans le cas particulier ou tous les points sont alignés.

Splines cubiques

Le cas le plus courant des splines est la spline cubique. Elle est uniforme et définie par des polynômes de degré 3.
Un polynôme de degré 3 s'écrivant $P(t) = a+bt+ct^2+dt^3$,
il nécessite 4 contraintes (a,b,c,d) pour être défini.
Ces 4 contraintes par intervalle vont nous permettre d'interpoler des courbes splines passant par un ensemble de points donnés, dans différents cas :

Soit un ensemble de points $Q_i$ que nous souhaitons interpoler par une spline cubique. Nous définissons un paramètre $t_i$ associé à chaque point $Q_i$, qui seront les valeurs pour lesquelles $S(t_i) = Q_i$. De là, nous avons de multiples manières d'interpoler

Interpolation avec les tangentes

Nous connaissons les tangentes $T_i$ associées à chaque point $Q_i$.
Nous pouvons donc écrire que, pour chaque polynôme $P_i(t)$, nous avons :

$\left\{ \begin{matrix} P_i(t_{i-1}) = Q_{i-1} \\ P_i'(t_{i-1}) = T_{i-1} \\ P_i(t_i) = Q_i \\ P_i'(t_i) = T_i \end{matrix} \right.$

Ces quatre contraintes par intervalle permettent de calculer chaque polynôme et donc de définir complètement la spline.
La continuité d'une telle spline sera donc $C_1$

Interpolation avec méthode de Catmull–Rom

Cette fois ci, nous n'avons pas les tangentes, nous devons en calculer. La méthode de Catmull-Rom va permettre de calculer des tangentes pour tous les points internes (sauf les extrémités)
Soit $T_i = c(Q_{i+1} - Q_{i-1})$
Une bonne valeur pour c est 0.5, mais ce paramètre peut être modifié pour avoir d'autres formes de splines.
Graphiquement, la tangente en un point sera un vecteur parallèle au segment formé par ses points voisins, de la moitié de leur longueur.
Pour tous les intervalles internes, nous retombons sur le cas précédent, et pouvons calculer les polynômes.
Pour les intervalles du bord, il nous manque une contrainte.
Voici trois méthodes pour lever la contrainte :

Spline circulaire

Dans le cas d'une spline circulaire, c'est-à-dire qu'on attend une courbe fermée, avec $Q_1 = Q_k$, le problème n'existera pas, puisque plus aucun intervalle ne sera sur un bord. Chacun aura un intervalle voisin précédent, et suivant. On pourra alors appliquer la même règle pour calculer la tangente que sur tous les autres intervalles.

Spline serrée

Dite "clamped" en anglais, nous considérons que les tangentes extrêmes sont directement données.
Graphiquement, on donne la vitesse et la direction de la spline au début, et à la fin.

Spline naturelle

On dit qu'une spline est naturelle si son accélération à ses points extrémités est nulle.
Dans ce cas, on a $P_1''(t_0) = 0$ et $P_k''(t_k) = 0$.
Ces contraintes permettent de calculer les polynômes des bords.

Interpolation en courbure

Jusqu'à présent, les interpolations que nous avons vu assuraient une continuité $C_1$ Reprenons le cas ou nous n'avons pas les tangentes. L'interpolation en courbure pose comme contrainte que l'on souhaite une continuité $C_2$
Ainsi, les contraintes pour un polynôme deviennent les suivantes :

$\left\{ \begin{matrix} P_i(t_{i-1}) = Q_{i-1} \\ P_i(t_i) = Q_i \\ P_i'(t_i) = P_{i+1}'(t_i) \\ P_i''(t_i) = P_{i+1}''(t_i) \end{matrix} \right.$

Calculer les polynômes va demander une mise en système globale, et ne pourra plus se faire intervalle par intervalle comme les méthodes vues au-dessus.
Pour les points extrémités, nous pourrons envisager, comme au-dessus, les cas de splines circulaires, serrées, ou naturelles.

Étymologie

Pierre Bézier, dans Courbes et surfaces pour la CFAO, Techniques de l'ingénieur, Mathématiques pour l'ingénieur, précise

«  Le mot anglais spline a malencontreusement prévalu, alors qu'il se traduit en français par les substantifs latte ou baguette. »

The Oxford English Dictionnary 1989 donne les définitions suivantes pour le mot spline:

«  a long narrow, and relatively thin piece or strip of wood, metal, etc.; a slat. A flexible strip of wood or hard rubber used by draftsmen in laying out broad sweeping curves, especially in railroad work. »

Les menuisiers, charpentiers et autres escaliéteurs auront reconnu la cerce, latte souple en bois bien de fil qui sert à tracer les courbes quelconques (Courbes harmonieuses passant par un certain nombre de points mais ne pouvant être tracées à l'aide du compas).

Le curvigraphe est aussi un synonyme d'un tel pistolet de dessin souple.

Prononciation

Spline est un mot anglais qui se prononce [splajn], ce qui le distingue de spleen [spli:n].

Voir aussi

Liens internes

• Courbe de Bézier
• B-spline
• NURBS

Liens externes

• (en) Spline Curve

Références

• (fr) Modèles de Bézier, des B-splines et des NURBS, G Demengel, JP Pouget, éditions ellipses (Approche pédagogique pour dévoiler la boîte noire de ces modèles utilisés en CAO pour la modélisation des courbes et des surfaces.)
• (fr) 'Systèmes De Cfao', 'Études En Cfao Cao Mecanique ', 'Éléments De Cao Volume 1 Materiels Et Logiciels De Base', 'Cao Mécanique', 'Systèmes De C.F.A.O. : Conception Et Fabrication Assistées Par Ordinateur : - Introduction Dans L'entreprise, Méthode De Réalisation ', 'La Cfao - Introduction, Techniques Et Mises En Œuvre, 3^e Édition Revue Et Corrigée ', 'La Cfao ', Yvon Gardan, Livre, édition Hermes, (modèles CSG, Spline, B-REP, modeleur paramétrique ou variationnel, etc.)