Discussion :

[Charly910]

Bonjour,

je suis un habitué du forum Delphi, mais nouveau sur celui-ci.

Je souhaite dessiner une série de Splines passant par n points. Pour cela j'écris pour les n-1 Splines :

- que chaque courbe passe par les 2 points (début et fin) ;
- qu'aux points intermédiaires les tangentes sont égales à gauche et à droite ;
- qu'à ces mêmes points les dérivées secondes sont égales ;
- qu'aux points 1 et n les dérivées secondes sont nulles (Splines naturelles).

Je trace les courbes (voir l'image suivantes) :



Cela fonctionne bien, mais au point P3, les pentes sont bien égales, mais j'ai un point de rebroussement.
Comment faire arriver la courbe 2 de l'autre coté de P3 pour assurer la continuité ?

Est ce que c'est un problème de la position relative des points ?

Merci

Cordialement
Charly

[wiwaxia]

Bonjour,

Les courbes présentent un bel aspect, mais leur contour excessif est peut-être dû au développement polynomial des équations.
Quel est l'ordre des splines ? Passer à l'ordre supérieur ne te donnerait-il pas plus de latitude au sujet de l'orientation des tangentes, et ne te permettrait-il pas de supprimer la singularité centrale ?

[Charly910]

Bonjour,
merci pour votre réponse.

ce sont des cubiques et donc 4 coeff inconnus par courbe. Avec un degré 4 il me faudrait des équations supplémentaires.

Charly

[Flodelarab]

Bonjour

les tangentes sont égales à gauche et à droite ;

Si elles sont "égales", c'est normal d'avoir un point de rebroussement.
Elles doivent être algébriquement opposées, au sens du vecteur :

• même direction (c'est ce que tu appelles "égales", j'imagine)
• même amplitude
• même point d'application
• mais sens opposé !

Pour illustrer, j'ai fait un dessin vite fait avec gimp.

Les 3 points ont les même positions relatives. (c'est un copier-coller)
Mais j'ai opposé le vecteur de la spline pour le troisième point.
Du coup, on peut abouter les splines.
Sinon, avec le même vecteur, on aurait forcément un rebroussement.

[wiwaxia]

Autre solution, moins coûteuse en calcul et pointée par Flodelarab: le raccordement des tangentes au point central implique la colinéarité des vecteurs dérivée:
T_a = D_t(OM_a) , T_b = D_t(OM_b)
condition qui s'exprime par l'annulation du déterminant correspondant: Det(T_a, T_b) = 0
et conduit à un réel (K) vérifiant: T_b = K.T_a .

Il n'est pas exclu que pour ce dernier deux valeurs soient envisageables,
# l'une positive (K>0), correspondant à deux vecteurs dérivée de même sens au point de raccordement, alors dépourvu de singularité;
# l'autre négative (K<0), correspondant à deux vecteurs de sens opposés et se manifestant par 1e rebroussement observé.

La première éventualité t'as peut-être discrètement échappé au cours des calculs.
L'"égalité des tangentes", lorsqu'elle s'exprime par une équation du type Tan(u) = Tan(v) ,
conduit à une solution du type: v = u + m*Pi
donc à deux relations différant par le signe d'un terme - selon que (m) vaut 0 ou 1 .

[Charly910]

Merci à tous les 2,

@ wiwaxia : Effectivement j'ai écris que les pentes étaient égales et donc la solution est à Pi près. Je vais essayer de mettre en œuvre ta solution mais il me faudrait quelques éclaircissements supplémentaire car je ne suis pas un super matheux !

mes équations sont de la forme y = a x3 + b x2 + c x + d. J'utilise y' pour la pente des tangentes.

qu'est ce que OMa et OMb et comment calculer det() ?

A+
Charly

[Charly910]

ce qui est curieux dans mon cas, c'est que mon calcul fonctionne pour P2 et P4, mais pas pour p3 ?

alors que je fais la même chose : 4 n - 4 équations linéaires résolues par la méthode de Gauss-Jordan

J'ai vu sur Wikipedia que lorsque la pente entre 2 segments était supérieure à 1, il pouvait y avoir des problèmes d'instabilité.

[wiwaxia]

Ne souhaiterais-tu pas obtenir un graphe apparenté à celui figurant sur l'image ci-dessous ? les vecteurs tangents y sont colinéaires au point de jonction, et de même sens ...

[wiwaxia]

Je ne comprends pas bien le procédé de calcul: il y aurait deux splines cubiques (S₁, S₂) construites chacune sur 3 points (P₁, P₂, P₃) et (P₃, P₄, P₅) , avec contrainte de raccordement tangentiel au point commun (P₃) ?
Ou deux splines décalées construites d'une façon classique sur 4 points (1, 2, 3, 4) et (2, 3, 4, 5) ? Leur chevauchement partiel donnerait deux arcs distincts entre (P₂) et (P₄), et il ne serait plus possible d'ajuster l'orientation des tangentes ...

A partir de quelles équations générales commences-tu le calcul ?

De plus on s'aperçoit, en relisant ta demande initiale, que tu exiges des contraintes relativement sévères avec les conditions concernant les dérivées secondes:

... Je souhaite dessiner une série de Splines passant par n points. Pour cela j'écris pour les n-1 Splines :

- que chaque courbe passe par les 2 points (début et fin) ;
- qu'aux points intermédiaires les tangentes sont égales à gauche et à droite ;
- qu'à ces mêmes points les dérivées secondes sont égales ;
- qu'aux points 1 et n les dérivées secondes sont nulles (Splines naturelles) ...

Et d'ailleurs, dérivées secondes par rapport à quelle variable ? Tu travailles en principe sur des équations paramétriques:
x = F(t) , y = G(t) .
Il s'agit sans doute de conditions concernant la courbure locale du graphe obtenu.

# Pour clore ces interrogations et répondre à ce que tu demandais, (OM_a) et (OM_b) représentent les vecteurs position des points pour les deux splines considérées (S₁, S₂) - notation pas très heureuse, j'en conviens - et les vecteurs tangents les dérivées correspondantes par rapport au paramètre (t):
OM_a = X_a(t).i + Y_a(t).j ; T_a = X'_a(t).i + Y'_a(t).j ;

OM_b = X_b(t).i + Y_b(t).j ; T_b = X'_b(t).i + Y'_b(t).j .

Quant au déterminant en question, il s'agit tout simplement de l'expression
Det(T_a, T_b) = X'_a*Y'_b - X'_b*Y'_a .

Il se pourrait bien que, compte tenu de l'aspect du graphe, tu aies réussi une programmation (presque) partout correcte, et que le changement souhaité puisse résulter d'une modification mineure de ton code.

PS: Il y a actuellement quelques problèmes de transmission d'image.

[Charly910]

En fait, j'ai 4 Splines (ou cubiques) une de P1 à P2, une de P2 à P3, une de P3 à P4, et une de P4 à P5 (S1 à S4).

Je travaille avec y = f(x) = ai x3 + bi x2 + ci x + di pour la courbe i de 1 à 4 (et non en paramétrique)

je cherche les ai, bi, ci, di :

Chaque courbe passe par les points Pi et Pi+1 (2 x 4 équations) ;
elles ont même tangente aux points intermédiaires commun (3 équations) ;
et même dérivée seconde en ces points (3 équations)
il manque 2 équations ==> dérivées secondes nulles en P1 et P5.

Chaque condition me donne une équation linéaire en ai, bi, ci, di pour chaque courbe (16 inconnues)

je résous et je trace les courbes.

les courbes S1 et S2 se raccordent bien (tangentes opposées), mais entre s2 et S3 la tangente est du même coté (ce qui ne va pas). S3 et S4 se raccordent bien (tangentes opposées)

je voudrais donc comprendre pourquoi, et inverser la tangente en fin de S2


PS : sinon sur ton dessin c'est bien cela sauf que j'ai 4 courbes

[wiwaxia]

En fait, j'ai 4 Splines (ou cubiques) une de P1 à P2, une de P2 à P3, une de P3 à P4, et une de P4 à P5 (S1 à S4).

Je travaille avec y = f(x) = a_i*x³ + b_i*x² + c_i*x + d_i pour la courbe i de 1 à 4 (et non en paramétrique ...

Le vice fondamental de ton procédé est de recourir à des équations du type y = F(x), alors que la ligne brisée des points successifs (1, 2 ... 5) repasse en-dessous d'elle-même en repartant vers la gauche: la courbe continue que tu recherches présente donc nécessairement une tangente verticale en l'un de ses points (#8), ce qu'il est impossible d'obtenir à partir d'une expression polynomiale - la dérivée F'(x) devant tendre vers l'infini au point considéré.

Tu ne peux donc échapper au point de rebroussement

[Charly910]

Effectivement, tu as raison le problème vient de l'angle entre P2P3 et P3P4. Avec Y=f(X) pas de solution possible.

Vois tu une autre solution à mon problème : Je voudrais faire passer une courbe par n points comme sait le faire Excel ...

Charly

PS : si les xi sont croissants alors ma méthode est correcte et j'ai une courbe lisse. C'est déjà une bonne chose ...

[Flodelarab]

Je voudrais faire passer une courbe par n points comme sait le faire Excel ...

Oh là là. Tu aurais dû dire cela dès le début.
Ça n'a rien à voir avec la piste sur laquelle tu nous a mis.
Ton premier dessin ressemblait à quelqu'un qui cherchait à dessiner une enveloppe convexe par splines.

Il y a une infinité de solutions qui remplissent tes contraintes, de toute façon.
Ce que fait Excel, c'est minimiser l'erreur entre ce que voudrait l'utilisateur et les données réelles.
Tous les points de tes données sont-ils des noeuds ?
Ne réponds pas trop vite. Ce n'est pas obligatoire.
Et surtout, tu vas te retrouver avec un changement de variation à chaque point. Alors que, si l'interpolation est bonne, un point bien placé ne provoque pas de nouvelle spline.

Les splines nécessitent des points de contrôles dont tu ne parles jamais.

Il te suffirait de mettre tes points dans l'ordre pour faire de l'interpolation sans prise de tête : P1 P5 P2 P4 P3

Et pour finir, un lien :
http://morpheo.inrialpes.fr/people/B...ng/RICM/c5.pdf
Je l'ai choisi car:

• Les équations sont paramétriques.
• Il y a un bout de code.
• Il parle de continuité C¹ et C².
• Il parle de dérivées (premières et secondes) aux extrémités.

Y a encore du boulot.

[wiwaxia]

... Vois tu une autre solution à mon problème : Je voudrais faire passer une courbe par n points comme sait le faire Excel ...
PS : si les xi sont croissants alors ma méthode est correcte et j'ai une courbe lisse. C'est déjà une bonne chose ...

Effectivement.

Les références concernant la question posée ne manquent pas:

# Courbe de Bézier passant par des points donnés

# Systèmes d’équations linéaires et courbes passant par des points fixés

# Interpolation polynomiale

# Courbes et interpolations

[Charly910]

Bonjour et merci à tous les 2,

@ Floderab :
je ne cherche pas à minimiser l'erreur, je veux une courbe qui passe par tous les points. C'est à dire comme dans un graphique de semis de points (avec courbes) dans Excel.

Je ne savais pas que les Splines avaient des points de contrôles (peut être que c'est pour la définition des tangentes aux extrémités ?). Je croyais que seules les courbes de Bézier en avaient. J'ai déjà traité le cas des courbes de Bézier avec continuité des tangentes entre 2 courbes. Cela marche bien, mais il faut donner les points de contrôles en plus des points de passage (4 points par courbe donc). Avec mes Splines, je n'en ai pas ...
Merci pour la doc que je vais lire attentivement.

@wiwaxia :

Merci pour toutes ces références. Je vais commencer par l'interpolation de lagrange, mais j'ai peur que la matrice à traiter soit très grosse si n est assez grand.

Je laisse le post ouvert et vous tiens au courant de mes recherches.

Merci en tout cas de m'avoir permis de comprendre pourquoi mon premier essai n'était pas concluant avec y=f(x) !!

A+
Charly

[wiwaxia]

... Vois tu une autre solution à mon problème : Je voudrais faire passer une courbe par n points comme sait le faire Excel ...

La méthode précédente, que tu maîtrises, peut être étendue à tout ensemble fini (x_k, y_k) de points du plan; il suffit de considérer désormais une double suite de fonctions (x = F(t), y = G(t)) où la variable (t) est un réel du domaine [k - 1 ; k + 1] contenant les 3 points consécutifs (P_k-1, P_k, P_k+1).

En reprenant les contraintes précédentes

... Je souhaite dessiner une série de Splines passant par n points. Pour cela j'écris pour les n-1 Splines :

- que chaque courbe passe par les 2 points (début et fin) ;
- qu'aux points intermédiaires les tangentes sont égales à gauche et à droite ;
- qu'à ces mêmes points les dérivées secondes sont égales ;
- qu'aux points 1 et n les dérivées secondes sont nulles (Splines naturelles) ...

les mêmes propriétés doivent se retrouver au niveau de la courbe paramétrée (je n'ai pas le temps de le vérifier).

[Charly910]

Oui, je pense chercher du coté des cubiques paramétriques de Hermite (qui sont citées dans un lien que tu m'as donné).

Je vais déjà essayer de calculer et de tracer une courbe passant par 2 points avec des vecteurs tangents donnés. Puis j'attaquerai une succession de courbes avec continuité aux points intermédiaires.

Je marque résolu et reviendrai si besoin.

Merci en tout cas pour toutes ces explications

Cordialement
Charly