jeudi 24 avril 2014

Le flocon de Von Koch

voici une courbe fascinante sur laquelle je trouve intéressant de faire travailler mes étudiants. En effet cela permet, sans en avoir l'air, de les faire travailler sur des concepts géométriques très simples : points, vecteurs, coordonnées, un peu de trigonométrie ... souvent mal maîtrisés par manque d’entraînement. Pour y arriver on joue sur la motivation d'aboutir à un  résultat intéressant : obtenir l'animation de la construction d'une fractale assez esthétique, que beaucoup d'étudiants on déjà vu   ou ailleurs  sans savoir comment la faire 



Le principe de base pour construire le flocon de Von Koch est de remplacer à, chaque étape, chaque  segment $[M_1,M_2]$ par 4 nouveaux segments $[M_1,M_3]$, $[M_3,M_5]$, $[M_5,M_4]$, $[M_4,M_2]$  de longueurs égales au 1/3 de la longueur du segment de départ, comme sur la figure ci-dessous :



Techniquement il faut donc à partir des coordonnées $(x_1,y_1)$ et $(x_2,y_2)$ des points $M_1$ et $M_2$  pour  calculer celles des autres points $M_3,M_4,M_5$. La stratégie  ne fait pas appel à des choses très compliquées mais  il faut décomposer le problèmes en un nombre suffisant d'étapes simples et dans le bon ordre : 
  • calculer les coordonnées du vecteur $\overrightarrow{u}=\overrightarrow{M_1M_2}$
  • calculer les coordonnées du vecteur $\overrightarrow{v}\perp \overrightarrow{u}$ (dans le sens direct )
  • calculer les coordonnées des points
    $M_3=M_1+{1\over 3}\overrightarrow{u}$
    $M_4=M_2-{1\over 3}\overrightarrow{u}$
    $M_5=M_1+{1\over 2}\overrightarrow{u}+{\sqrt{3}\over 2}{\overrightarrow{v}\over 3}$
 le ${\sqrt{3}\over 2}$  dans les coordonnées de $M_5$ vient du calcul de la hauteur dans le triangle équilatéral $M_3M_5M_4$, un exercice de base de trigonométrie  maitrisé par très peu d'étudiants!   A partir de ces formules la construction de la courbe de Von Koch  repose sur l'application récursive  des formules précédentes à tous les segments qui composent la courbe à une étape donnée. Le plus simple est de décomposer le problème  en 2 fonctions :

fonction VonKoch(n)
x,y= coordonnées des points définissants les 3 segments du triangle de départ
x=[-1/2            0            1/2        -1/2]
y=[    0       sqrt(3)/2       0             0 ]
pour k=1 à n
          m=nombre de segments dans (x,y) (=nombre de points- 1) 
          X,Y=tableaux pour contenir les nouvelles listes de coordonnées
          pour i=1 à m
                     récupérer les coordonnées de M1
                      x1=x(i),        y1=y(i)
                      récupérer les coordonnées de M2
                      x2=x(i+1),   y2=y(i+1)
                     calcul_nouveaux_segments([x1 X2],[y1 y2])
                     ajouter  [x1 x2 x5 x4 x2] à la fin de X
                     ajouter  [y1 y3 y5 y4 y2] à la fin de Y
          fin
          remplacer x,y par X,Y
           afficher la courbe des segments donnés par les points (x,y)
fin

fonction calcul_nouveaux_segments(x,y)
          récupérer les coordonnées de M1 (x1,y1)
          récupérer les coordonnées de M2 (x2,y2)
          calculer les coordonnées du vecteur u
          ux=x2-x1,  uy=y2-y1
          calculer les coordonnées du vecteur v
          vx=uy,       vy=-ux
          calculer les coordonnées du point M3
          x3=x1+ux/3,  y3=y1+uy/3
          calculer les coordonnées du point M4
          x4=x2-ux/3,  y4=y2-uy/3
          calculer les coordonnées du point M5
          x5=x1+ux/2+sqrt(3)*vx/6 y5=y1+uy/2+sqrt(3)*vy/6
          renvoyer en sortie  [x1 x2 x5 x4 x2]et [y1 y3 y5 y4 y2]

D'un point de vue pédagogique on peut ensuite faire de petites variations autour de la construction du flocon de Von Koch (en ne modifiant que les segments de départ ou bien la fonction calcul_nouveau_segments ) pour obtenir d'autres courbes fractales  tout en faisant travailler les étudiants sur des calculs formels associés à la géométrie ! Par exemple :



Je trouve que ce type d'exercice  permet de susciter l'intérêt des étudiants tout en travaillant des fondamentaux. Par exemple à  plusieurs reprises  j'ai vu des étudiants tenter de construire un flocon de Von Koch avec le plus de précision possible, avec les outils utilisés en cours ou en recodant  les algorithmes précédents dans d'autres langages plus performants. Certains sont arrivés à construire le flocon jusqu'à l'étape n=10 mais tous finissent par être bloqués par l'insuffisant de la mémoire disponible sur leur machine. Ce point peut facilement s'expliquer  en considérant  le nombre de points à stocker en mémoire pour tracer le flocon à l'étape n. En effet à chaque étape le nombre de segments est multiplié par 4 , comme on part de 3 segments on a donc $3\times 4^n$ segments à l'étape n  (au passage une bonne occasion d'utiliser les formules sur les suites géométriques). Ce nombre augmentant de manière exponentielle  on est vite bloqué ... C'est un point d'entré pour comprendre les propriétés étonnantes de la courbe de Von Koch obtenu en faisant tendre le nombre d'étapes vers l'infini :

  • la longueur de la courbe étant multiplié par 4/3 à chaque étape  elle est de $2\times \left({4\over 3}\right)^n\mathop{\rightarrow}_{n\to\infty}\infty$  !!!
  • Pour la surface  entourée par le Flocon de Von Koch est finie en effet à chaque étape on ajoute sur les $3\times 4^n$ segments des triangles dont l'aire à été divisée par 9 ...  ce qui donne (à l'aide d'une série géométrique!) une aire égale à $\sum_{n=0}^\infty {3\times 4^n\over 3^n}={9\over 5}$ de l'aire de départ
  • si la courbe peut être paramétrée (x(t),y(t)) par des fonctions continues celles-ci  ne peuvent  être différentiable sur aucun intervalle sinon  la courbe aurait une longueur  sur cet intervalle $\int \sqrt{x'(t)^2+y'(t)^2}dt$


Pourtant en étant  un peu malin (et bon en maths) on peut simuler  un zoom "infini" sur la courbe de Von Koch montrant sa structure auto-similaire comme ci-dessous :
zoom sur le flocon de Von Koch


Ayant vu ce type d'animation  j'ai voulu moi aussi la reproduire  et je dois avouer que c'est un excellent exercice de géométrie! L'astuce repose sur le fait de dessiner une portion du flocon de Von Koch et de zoomer sur une partie du dessin de telle sorte que le cadre sur lequel on a zoomé ait les mêmes dimensions relatives que le dessin de départ. En partant du segment défini par les points de coordonnées (0,0) et (1,0)  la  courbe peut être dessinée dans un rectangle de largeur 1 et de hauteur 0.3 (car le sommet de la pointe  se trouve à hauteur ${\sqrt{3}\over 6}\approx 0.2886751\dots$). Il faut alors  réaliser un zoom sur la partie  supérieure de la pointe sur un rectangle de largeur 1/3 (et donc de hauteur 0.1  pour garder la même échelle !). Il reste à fixer  une "ligne de fuite" de telle sorte que la figure de départ se recolle parfaitement sur la partie "zoomée", elle est définie à l'aide des points  $C_1=(0.5,0)$ (le milieu du segment de départ)  et  $C_2=(0.5,\sqrt{3}/9)$(le milieu de la branche supérieure).

Ces idées sont assez faciles à implémenter à l'aide de Scilab, c'est d'ailleurs avec ce logiciel que j'ai réalisé les gifs de ce billet en utilisant les propriétés des handles graphiques de scilab (voir la partie "Graphiques" de mon livre sur scilab. Une fois la figure tracée il suffit de jouer sur la propriété zoom_box de la figure  pour créer le zoom. Si vous arrivez à dessiner le flocon de Von Koch avec Scilab vous pouvez exécuter le script suivant pour générer le zoom  :

clf;                                  //  efface la figure
plot(x,y,'-r')                        //  tracer le flocon à partir de x,y 
A=gca();                              //  récupère les axes de la figure 
A.isoview="on";                       //  échelle isométrique 
A.axes_visible=["off" "off" "off"];   //  masque les axes de coordonnées 
A.box="off";                          //  pas de cadre autour de la figure
h=1/(3*sqrt(3));                      //  la hauteur du palier principal 
D=[0 0, 1 0.3];                       //  le rectangle de départ
F=[1/3 h, 2/3 h+0.1];                 //  le rectangle final
for t=0:0.002:1                       //  la boucle qui fait le zoom
    drawlater                         //  dessine dans le "buffer" graphique  
    A.zoom_box=(1-t)*D+t*F;           //  on change le zoom  par homothétie 
    drawnow                           //   (1-t)% de D et t% de F
    sleep(5)                          //  modifier pour accélérer/ralentir l'animation
end

on peut ensuite exporter les différentes images qui composent ce zoom pour créer un gif animé bouclant sur lui même (en utilisant la commande convert de Image Magick  et l'option -loop 0  )  pour donner cette impression de zoom infini !


2 commentaires:

  1. Bonjour,

    Merci pour l'idée du zoom, je vais essayer cela avec matplotlib et python.

    Je crois qu'il y a une erreur dans le calcul de x5 et y5 :
    x5=x1+ux/2+sqrt(3)*vx/6
    y5=y1+uy/2+sqrt(3)*vy/6

    RépondreSupprimer
    Réponses
    1. effectivement il y avait une coquille, merci !

      Supprimer

Pour écrire des formules mathématiques vous pouvez utiliser la syntaxe latex en mettant vos formules entre des "dollars" $ \$....\$ $ par exemple :
- $\sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}$ s'obtient avec \sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}
- $\mathbb R$ s'obtient avec {\mathbb R} et $\mathcal D$ s'obtient avec {\mathcal D}
- pour les crochets $\langle .,. \rangle$ dans les commentaires utilisez \langle .,. \rangle
vous pouvez écrire du html dans les commentaires :
- italique <i> ... </i> gras <b> ... </b>
- lien <a href="http://adresse "> .... </a>