Spline

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Icône de paronymie Cet article possède un paronyme ; voir : Spleen.
Exemple de spline.

Dans le domaine mathématique de l'analyse numérique, une spline — mot anglais se prononçant « splaïne », mais souvent prononcé à la française — est une fonction définie par morceaux par des polynômes. Le terme français correspondant est cerce, mais l'usage a consacré le terme anglais (voir plus loin Étymologie).

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[modifier | modifier le code]

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é[modifier | modifier le code]

Le degré de la spline est défini comme étant celui du polynôme Pi 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é[modifier | modifier le code]

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 0 < i < 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[modifier | modifier le code]

Ligne polygonale[modifier | modifier le code]

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 où tous les points sont alignés.

Splines cubiques[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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 = \frac{Q_{i+1} - Q_{i-1}}{t_{i+1}-t_{i-1}} le coefficient directeur de la tangente au point de coordonnées (t_i, Q_i).
Graphiquement, la tangente en un point sera un vecteur parallèle au segment formé par ses points voisins.
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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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.

La continuité de la courbure est une méthode importante en mécanique, puisqu'elle permet de limiter les à-coups (jerk). Par exemple, si l'on conçoit une came à partir d'une série de points (positions que doit occuper le système), on peut en déduire un profile analytique grâce à une interpolation en courbure.

Mise en œuvre dans des logiciels[modifier | modifier le code]

B-splines (courbe de Bézier) utilisées dans Inkscape.

Les splines sont souvent intégrées dans des logiciels de dessin, que ce soient des logiciels généralistes, comme les fonctions de dessin des suites de logiciels de bureautique (Microsoft Office, LibreOffice, …), les logiciels de dessin et de traitement d'image (Inkscape, The Gimp, …) ou bien les logiciels de dessin assisté par ordinateur.

En général, l'utilisateur définit les points par lesquels passe la courbe, et agit avec la souris sur les extrémités des tangentes.

Les logiciels utilisent en général des B-splines.

Étymologie[modifier | modifier le code]

Cerce (spline).

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[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

Sources[modifier | modifier le code]

  • Gilbert Demengel et Jean-Pierre Pouget, Modèles de Bézier, des B-splines et des NURBS, Ellipses,‎ 1998, 286 p. (ISBN 978-2-72989-806-9) : 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.
  • de Yvon Gardan, éd. Hermès : modèles CSG, spline, B-REP, modeleur paramétrique ou variationnel, etc.
    • Yvon Gardan, Systèmes de C.F.A.O., conception et fabrication assistées par ordinateur : Introduction dans l'entreprise, méthode de réalisation, Hermès,‎ 1983, 279 p. (ISBN 978-2-86601-021-8)
    • Yvon Gardan, La CFAO, Hermès, coll. « Traité des nouvelles technologies »,‎ 1986, 327 p. (ISBN 978-2-86601-055-3)
    • Yvon Gardan, CAO mécanique, Hermès, coll. « Études en CFAO »,‎ 1986 (ISBN 978-2-86601-067-6)
    • Yvon Gardan, La CFAO. Introduction, technique et mise en œuvre, Hermès, coll. « Traité des nouvelles technologies »,‎ 1987
    • Yvon Gardan, Éléments de CAO : 1. Matériels et logiciels de base, Hermès,‎ 1988, 300 p. (ISBN 978-2-86601-128-4)

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]