Courbe du dragon

Courbe du dragon

La courbe du dragon (ou « fractale du dragon » ou « courbe de Heighway » ou « dragon de Heighway ») a été pour la première fois étudiée par les physiciens de la NASA John Heighway, Bruce Banks, et William Harter. Elle a été décrite par Martin Gardner dans sa chronique de jeux mathématiques du Modèle:Lang en 1967. Nombre de ses propriétés ont été publiées par Modèle:Lien et Donald Knuth. Elle est apparue dans le roman Modèle:Lang de Michael Crichton.

Construction

L-système

Construction récursive de la courbe

La courbe peut être construite par le L-système défini par :

• angle 90°
• graine FX
• règles :
  • X $\mapsto$ X+YF+
  • Y $\mapsto$ -FX-Y

Ce qui se traduit simplement comme suit : partir d'un segment de base ; puis en suivant la courbe, remplacer chaque segment par deux segments à angle droit en effectuant une rotation de 45° alternativement à droite puis à gauche :

On visualise ici les 5 premières itérations et la neuvième.

Système de fonctions itérées

La courbe du dragon est également l'ensemble limite du système de fonctions itérées suivant, dans le plan complexe :

$f_1(z)=\frac{(1+i)z}{2}$

$f_2(z)=1-\frac{(1-i)z}{2}$

(avec comme ensemble de points initial $S_0=\{0;1\}$).

ou encore, en coordonnées cartésiennes (représentation plus souvent utilisée dans des logiciels tels qu'Modèle:Lien) :

$f_1(x,y)=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\cos 45^{\circ }& -\sin 45^{\circ }\\ \sin 45^{\circ }& \cos 45^{\circ }\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)$

$f_2(x,y)=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\cos 135^{\circ }& -\sin 135^{\circ }\\ \sin 135^{\circ }& \cos 135^{\circ }\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}1\\ 0\end{array}\right).$

Pliage

Suivre une itération de la courbe du dragon fait apparaître une suite de rotations à 90° vers la droite ou vers la gauche. Pour les premières itérations, la séquence de « droite » (D) et « gauche » (G) est la suivante :

Modèle:1re itération : D

Modèle:2e itération : D D G

Modèle:3e itération : D D G D D G G

Modèle:4e itération : D D G D D G G D D D G G D G G

Empiriquement, on peut observer la règle de construction suivante : on peut construire l'itération suivante en prenant l'itération en cours, ajoutant un D, puis en ajoutant l'itération courante inversée et en intervertissant D et G.

Ce schéma suggère la méthode suivante de modélisation par pliage : prenez une bande de papier et pliez-la en son milieu par la droite. Pliez-la à nouveau par la droite et répétez l'opération autant de fois que possible. Dépliez la bande en conservant les pliures à 90°. La courbe du dragon apparaît.

Ce motif donne également une méthode pour déterminer la direction de la n-ième rotation dans la séquence. Écrivons un entier n sous la forme k2^m où k est un nombre impair. La direction de la n-ième rotation est déterminée par k modulo 4 (reste de la division de k par 4). Si le reste vaut 1 alors la n-ième rotation est « droite », sinon c'est « gauche ».

Exemple de programme

Exemple de programme en JavaScript (on suppose une balise Canvas d'Id "myCanvas" présente, faisant 1400px par 700px), facile à convertir dans tout autre langage.

     
    var nbStep = 2 ** 16;  // 2^16
    var dragonLen = 3;
    var dragonX = 400, dragonY = 400;
    var dragonDx = 1, dragonDy = 0;

    var c = document.getElementById("myCanvas");
    var ctx = c.getContext("2d");

    function move() {
        dragonX = dragonX + dragonDx * dragonLen;
        dragonY = dragonY + dragonDy * dragonLen;
        ctx.lineTo(dragonX, dragonY);
    }

    ctx.beginPath();
    ctx.moveTo(dragonX, dragonY);
    move();
    for (var n = 1; n < nbStep; n++) {
        var k = n;
        while ((k & 1) == 0)    // k mod 2 == 0
            k = k >> 1;         // k = k / 2
        var d = k & 0x3;        // k mod 4

        if (d == 1) {
            var t = dragonDy;
            dragonDy = -dragonDx;
            dragonDx = t;
        } else {
            var t = dragonDy;
            dragonDy = dragonDx;
            dragonDx = -t;
        }
        move();
    }
    ctx.stroke();

Propriétés de la courbe du dragon

Dimensions

• En dépit de son aspect irrégulier, la courbe du dragon s’inscrit dans des proportions simples. Ces résultats se déduisent de son mode de construction.

• Sa surface vaut ½ (considérant que le segment de base a pour longueur 1). Ce résultat se déduit de ses propriétés de pavage.
• Sa frontière a une longueur infinie.
• La courbe ne se traverse jamais.
• La courbe du dragon révèle nombre d’auto-similarités. La plus visible est la répétition du même motif après rotation de 45° et réduction de Modèle:Racine.

• Sa dimension de Hausdorff peut être calculée : à chaque itération le nombre de segments double avec un facteur de réduction de Modèle:Sqrt. La dimension de Hausdorff vaut donc $\frac{\log 2}{\log \sqrt{2}}=2$. Cette courbe couvre donc le plan.
• Sa frontière est une fractale dont la dimension de Hausdorff vaut ${\log }_2\left(\frac{1+\sqrt[3]{73-6\sqrt{87}}+\sqrt[3]{73+6\sqrt{87}}}{3}\right)\approx$ 1,5236 (calculée par Chang et Zhang).

Pavage

• La courbe du dragon peut paver le plan de multiples manières (voir encadré).

• 
  Modèle:1er de pavage par 4 courbes
• 
  Modèle:2e de pavage par 4 courbes
• 
  Modèle:3e de pavage par 4 courbes
• 
  La courbe du dragon peut se paver elle-même.
• 
  Modèle:1er de pavage par 2 courbes
• 
  Modèle:2e de pavage par 2 courbes (twin dragon)
• 
  Modèle:3e de pavage par 2 courbes
• 
  Un exemple de pavage du plan
• 
  Autre exemple de pavage du plan
• 
  Autre exemple de pavage du plan
• 
  Des courbes de taille croissante (ratio racine(2)) forment une spirale infinie. 4 de ces spirales, disposées à 90°, pavent le plan.

Variantes de la courbe du dragon

Twindragon

Twindragon construite à partir de 2 dragons

Frontière du Twindragon

La twindragon (mot à mot « dragon jumeau », connue également sous le nom de dragon de Davis-Knuth) est une variante de la courbe du dragon qui peut être construite en plaçant deux dragons dos à dos. Cette courbe est la limite de l’IFS suivante :

$f_1(z)=\frac{(1+i)z}{2}$

$f_2(z)=\frac{(1+i)z+1-i}{2}$.

Terdragon

Courbe Terdragon

La terdragon peut être construite à partir du L-système suivant :

• angle 120°
• graine F
• règle : F $\mapsto$ F+F-F

C’est également la limite de l'IFS suivant :

$f_1(z)=\lambda z$ ;

$f_2(z)=\frac{i}{\sqrt{3}}z+\lambda$ ;

$f_3(z)=\lambda z+{\lambda }^{*}$ ;

$\mathrm{o}\stackrel{`}{\mathrm{u}}\lambda =\frac{1}{2}-\frac{i}{2\sqrt{3}}\text{ et }{\lambda }^{*}=\frac{1}{2}+\frac{i}{2\sqrt{3}}.$

Voir aussi

Article connexe

Liste de fractales par dimension de Hausdorff

Liens externes

• Modèle:MathWorld
• Modèle:En Paperfolding and the Dragon curve
• Courbe du dragon en Flash