Résumé : Une extension tridimensionnelle de la courbe de Hilbert, faisant appel à une interprétation sur le modèle de la tortue logo des L-systèmes.
Mots-clés :L-système, tortue LOGO, rotation 3D, récursivité.
Solutions :
La solution actuellement proposée est donnée en P5JS.
thèmes
de plus
La courbe de Hilbert tridimensionnelle
L’exercice s’inspire du livre The Algorithmic Beauty of Plants de Przemyslaw Prusinkievicz et Aristid Lidenmayer, Springer Verlag, 1990.
La courbe de Hilbert est une courbe continue remplissant un carré décrite par le mathématicien allemand David Hilbert en 1891. Comme elle couvre un carré, sa dimension est 2. On la considère comme une fractale. (Voir les six premières étapes ci-dessous (image empruntée à Wikipedia))
La beauté des plantes a séduit les mathématiciens depuis longtemps: symétries des feuilles et fleurs, arrangement hélicoïdal des capitules et cones. L'auto-similarité observée chez les plantes est le résultat des processus de développement. En 1968, Aristid Lindenmayer introduisit le formalisme des L-systèmes pour décrire ce processus.
Les L-systems sont décrits par un axiome et des règles de production basées sur un alphabet. La tortue LOGO permet une représentation adéquate aux L-systèmes. La tortue est décrite par un triplet (x, y, α) où (x, y) donne la position de la tortue et α sa direction. De plus, en donnant la longueur du pas d et l'angle d'incrémentation δ, la tortue répond aux instructions données par les symboles: F pour avancer en traçant un trait d'un pas de longueur d et dans la direction α, f pour avancer sans tirer de trait, + pour faire tourner la tortue à gauche d'un angle δ et - pour faire tourner la tortue à droite du même incrément. Un flocon de Koch peut être décrit de la façon suivante selon les L-systèmes: l'axiome est "-F" et la règle, "F -> F+F-F-F+F". Le premier niveau est: "F+F-F-F+F". Pour le deuxième, on remplace chaque F par ce qui se trouve à droite dans la règle: "F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F". On peut appliquer cette règle à l'infini. Dans l'illustration ci-dessous, on a pris le niveau 4.
Une interprétation faisant appel à la tortue LOGO peut également être appliquée aux L-systèmes en suivant les idées d'Abelson et diSessa. On décrit l'orientation actuelle de la tortue par trois vecteurs H, L, U indiquant le cap (heading), la direction gauche (left) et la direction haute (up). Ces vecteurs sont unitaires et perpendiculaires les uns aux autres; ils satisfont l'équation: H x L = U. Les rotations sont effectuées par le produit des trois vecteurs et la matrice 3x3 de rotation R: [H L U] R.
Les matrices de rotation sont:
Les symboles suivant sont utilisés pour contrôlé l'orientation de la tortue dans l'espace: '+' pour tourner à gauche de δ autour de U, '-' pour tourner à droite de δ autour de U, '&' pour produire un tangage hait de δ autour de L, '^' pour produire un tangage bas de δ autour de L, '!' pour produire un roulis à gauche de δ autour de H, '/' pour produire un roulis à droite de δ autour de H et '|' pour une rotation de 180° autour de U.
Pour décrire la courbe de Hilbert tridimensionnelle les auteurs de 'The Algorithmic Beauty of Plants' suggèrent le L-système suivant:
l'axiome est A, δ = 90°, les règles sont:
A -> B-F+CFC+F-D&F^D-F+&&CFC+F+B//'
B -> A&F^CFB^F^D^^-F-D^|F^B|FC^F^A//
C -> |D^|F^B-F+C^F^A&&FA&F^C+F+B^F^D//
D -> |CFB-F+B|FA&F^A&&FB-F+B|FC//
Indications
Pour représenter la courbe de Hilbert tridimensionnelle, il faut construire une tortue qui interprète les symboles permettant de changer sa direction. Il suffit d'intégrer ensuite les formules du produit matriciel pour calculer le produit de deux matrices 3x3.
Pour profiter des L-systèmes, il suffit de remplacer dans une chaîne de caractères tous les symboles donnés à gauche des règles par la partie droite. On reprend la nouvelle chaîne et on recommence le processus de façon récursive jusqu'au niveau n attendu.
Version P5JS. Instructions: 'r' pour dessiner une courbe de Hilbert 3D de niveau compris entre 1 et 6, faire reset pour dessiner une courbe de Hilbert 3D de niveau aléatoire compris entre 1 et 6 avec animation.
