Table des matières
Spline de Hermite
Il faut avoir fait les deux TDs précédents pour comprendre ce qui suit :
Spline de Hermite
On appelle spline cubique d'Hermite une spline de degré trois, nommée en hommage à Charles Hermite, permettant de construire un polynôme de degré minimal interpolant une fonction en deux points avec ses tangentes.
Autrement dit, on devra fournir la liste des points par lesquels la courbe doit passer ainsi que la liste des tangentes en ces points.
Cette spline est adaptée au cas où on veut simuler le mouvement d'un objet.
Formule
Un arc de courbe donné est défini par deux points $P_0$ et $P_1$ qui en forment les extrémités ainsi que des deux tangentes $\vec{v_0}$ et $\vec{v_1}$.
On veut un polynôme de degré 3 donc de la forme : $$M(t) = c_0 + c_1\cdot t + c_2 \cdot t^2 + c_3 \cdot t^3$$
On souhaite par ailleurs que $M(0) = P_0$, $M(1) = P_1$, $M'(0) = \vec{v_0}$ et $M'(1) = \vec{v_1}$.
Tout calculs faits on obtient :
- $c_0 = P_0$ ;
- $c_1 = v_0$ ;
- $c_2 = 3(P_1 - P_0) - v_1 - 2v_0$ ;
- $c_3 = v_0 + v_1 + 2(P_0 - P_1)$.
Quoi faire ?
Une courbe de Bézier interviendrait dans un projet. Par exemple un jeu Pygame ou un logiciel de dessin.
Nous allons commencer par concevoir tous les outils pour calculer les coordonnées des points d'une courbe de Bezier puis nous allons l'appliquer dans différents exemples.
Implémentation
On souhaite faire une implémentation semblable à celle faite dans la fiche Courbe de Bézier.
Une classe Point
On reprend la classe Point identique à celle faite dans Courbe de Bézier.
La classe Point sert surtout à faciliter les calculs sur les paires (x,y), car tous les calculs que l'on fait sur x doivent être faits à l'identique sur y. On pourra utiliser la classe Point pour les vecteurs, le fonctionnement est le même.
Les données fournies
Pour produire la spline de Hermite, on devra lui fournir une liste de paires (x,y) pour les points et une autre liste de paires pour les vecteurs tangents.
Exemple :
pts = [(10,50), (200, 400), (300, 300), (500, 200)] vecteurs = [(50,20), (60, -10), (10, -50), (30,0)]
Une classe Hermite
Cette classe aura la responsabilité des calculs liés à la spline de Hermite.
Ajoutez le module suivant à votre projet et complétez les fonctions.
# hermite.py
from point import Point
class Hermite:
def __init__(self, pts, vecteurs):
'''
pts: liste de paires (x,y) représentant les points
vecteurs: liste de paires (x,y) représentant les vecteurs
'''
assert len(pts) >= 2, "Il faut au moins deux points dans la spline."
assert len(pts) == len(vecteurs), "pts et vecteurs doivent être de même taille"
self.points = [Point(x,y) for x,y in pts]
self.vecteurs = [Point(x,y) for x,y in vecteurs]
def calc_coeffs(self, i:int):
'''
i:indice de l'arc considéré
la courbe de Bézier est calculée avec les points P0, P1, P2, P3 de l'arc
on calcule 4 coefficients :
c0 = P0
c1 = v0
c2 = 3(P1 - P0) -v1 -2v0
c3 = v0 + v2 + 2(P0 - P1)
La fonction renvoie c0, c1, c2, c3
remarque: chaque coefficient est de type Point.
'''
# vérifie que i est bien une valeur valide : 0 <= i <= n-2
# récupérer les P0 et P1 aux rangs i et i+1 dans les points
# récupérer les v0 et v1 aux rangs i et i+1 dans les vecteurs
# calculer les coefficients et les renvoie
def M(self, t:float, i:int):
'''
t: flottant entre 0 et 1, compris
i: rang de l'arc considéré
renvoie c0 + c1*t + c2*t**2 + c3*t**3 avec c0, c1, c2, c3
les coeffs de la fonction précédente.
'''
# obtenir les valeurs des coefficients
# renvoie le résultat du calcul
def tangent(self, t:float, i:int):
t: flottant entre 0 et 1, compris
i: rang de l'arc considéré
renvoie c1 + 2*c2*t + 3*c3*t**2 avec c0, c1, c2, c3
'''
# obtenir les valeurs des coefficients
# renvoie le résultat du calcul
def plot_points(self, N=100):
'''
renvoie la liste des points (type Point) constituant la courbe.
N représente le nombre de points à calculer pour chaque arc.
'''
# préparer une liste vide
# pour chaque arc i,
# pour chaque t allant de 0/N à (N-1)/N
# calculer M(t, i) et l'ajouter à la liste
# compléter la liste avec une copie du dernier point de self.points
# renvoyer la liste
Lors de l'utilisation, pour un arc donné, on calculera M(t) une bonne centaine de fois. Il serait donc bienvenu de ne pas devoir recalculer les coefficients c0, c1, c2, c3 à chaque fois. Le mieux serait de calculer les coefficients de chaque arc dès le début (__init__) et les placer dans un tableau de façon à ne plus avoir à refaire le calcul ensuite.
Utilisation avec matplotlib
On se propose d'expérimenter le module précédent avec un tracer dans matplotlib.
# demohermite.py # démonstration en utilisant matplotlib import matplotlib.pyplot as plt from hermite import Hermite pts = [(10,50), (200, 400), (300, 300), (500, 200)] vecteurs = [(50,20), (60, -10), (10, -50), (30,0)] spline = Hermite(pts, vecteurs) # tracé de la courbe plot_pts = spline .plot_points() # dans matplotlib, il faut placer les x et les y dans deux listes séparées x = [pt.x for pt in plot_pts ] y = [pt.y for pt in plot_pts ] plt.plot(x, y) # tracé des points : x = [x for x,y in pts] y = [y for x,y in pts] plt.scatter(x, y, c='b') plt.show()