vignette|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 en 1967. Nombre de ses propriétés ont été publiées par et Donald Knuth. Elle est apparue dans le roman de Michael Crichton.
Construction vignette L-système vignette|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 X+YF+ Y -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 : thumb|upright=3|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 :
(avec comme ensemble de points initial ).
ou encore, en coordonnées cartésiennes (représentation plus souvent utilisée dans des logiciels tels qu') :
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 :
itération : D itération : D D G itération : D D G D D G G 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. thumb|upright=2 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 k2m 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. none|500px Son aire 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. 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 . none|350px Sa dimension de Hausdorff peut être calculée : à chaque itération le nombre de segments double avec un facteur de réduction de . La dimension de Hausdorff vaut donc . Cette courbe couvre donc le plan. Sa frontière, de longueur infinie, est une fractale dont la dimension de Hausdorff vaut 1,5236 , voir la (valeur obtenue par Chang et Zhang en 1999).
Pavage La courbe du dragon peut paver le plan de multiples manières (voir encadré).
Variantes de la courbe du dragon Twindragon thumb|left|Twindragon construite à partir de 2 dragons Le 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 :
.
Terdragon Le Terdragon, ou dragon ternaire, est un reptuile du troisième ordre, comme le terpapillon, auquel il est comparé en raison de nombreuses propriétés communes. Cette fractale peut être construite à partir du L-système suivant : angle 30° (vers la droite) graine F règle : C’est également la limite de l'IFS composé de trois fonctions suivant :
La frontière supérieure du Terdragon est obtenue par la même construction que la courbe du dragon, en modifiant simplement les angles :
Notes et références
Voir aussi
Articles connexes Papillon de nuit (fractale) Terpapillon Liste de fractales par dimension de Hausdorff
Liens externes
Paperfolding and the Dragon curve Courbe du dragon en Flash
Catégorie:Courbe fractale