{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

  Tracer des fractales à l'aide du langage L-System :  

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les L-systèmes sont une famille de grammaires formelles inventée par le biologiste `Aristid Lindenmayer` pour modéliser la croissance des plantes. Un L-système est constitué :\n", "\n", "- d'un axiome : la chaîne de caractère initiale ;\n", "- d'un ensemble de règles de réécriture : chaque règle est de la forme : lettre → chaine.\n", "\n", "Le principe est de partir de l'axiome, et de remplacer dans la chaîne chaque lettre par la partie droite de la règle correspondante, si elle existe. Sinon, on laisse la lettre telle quelle. On répète cette opération plusieurs fois en fonction de l'ordre (ou du nombre de générations souhaités)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Exemple:

\n", "\n", "#### Soit le L-System suivant: \n", "- variables: A, B \n", "- Axiom: A \n", "- Règles : \n", " - A —> AB\n", " - B —> A \n", "\n", "

Écrire à la main la suite des caractères obtenue avec ce L-system: à l'ordre 0 ; puis à l'ordre 1 et jusqu'à l'ordre 5.

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Répondre ici:\n", "- ordre 0 : => A\n", "- ordre 1 : => AB\n", "- ordre 2 : => ABA\n", "- ordre 3 : => ABAAB\n", "- ordre 4 : => ABAABA\n", "- ordre 5 : => ABAABABAAB\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Codage du L-System :

" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 => A\n", "1 => AB\n", "2 => ABA\n", "3 => ABAAB\n", "4 => ABAABABA\n" ] } ], "source": [ "def iterer_lSystem(chaine: str, k: int) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne initiale (l'axiome) et l'ordre k souhaité\n", " Retourne la chaîne obtenue après k applications du L-system\n", " \"\"\"\n", " for _ in range(k):\n", " chaine = lSystemConvert(chaine)\n", " return chaine\n", "\n", "def lSystemConvert(chaine: str) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne de caractères\n", " Retourne la chaîne obtenue après application des règles du L-System\n", " \"\"\"\n", " result = ''\n", " for car in chaine:\n", " if car == 'A': #règle 1 :\n", " result += 'AB' # A -> AB\n", " elif car == 'B': #règle 2 :\n", " result += 'A' # B -> A\n", " return result\n", "\n", "axiome = 'A'\n", "for k in range (5):\n", " print(f'{k} => {iterer_lSystem(axiome, k)}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Évolution :

\n", "\n", "Simplifier l'écriture de la fonction ```LSystemConvert()``` en utilisant d'une part un dictionnaire dont chacune des clés représente une règle du L-system et d'autre part une liste par compréhension pour remplacer l'itération sur ```chaine``` (le code : for car in chaine :)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 => A\n", "1 => AB\n", "2 => ABA\n", "3 => ABAAB\n", "4 => ABAABABA\n" ] } ], "source": [ "def iter_lSystem(chaine: str, k: int) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne initiale (l'axiome) et l'ordre k souhaité\n", " Retourne la chaîne obtenue après k applications du L-system\n", " \"\"\"\n", " for _ in range(k):\n", " chaine = lSystemConvert(chaine)\n", " return chaine\n", "\n", "def lSystemConvert(chaine: str) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne de caractères\n", " Retourne la chaîne obtenue après application des règles du L-System\n", " \"\"\"\n", " rules = {\"A\":\"AB\",\"B\":\"A\"} # A compléter : règles\n", " result = ''.join([rules[ch] for ch in chaine]) # A compléter : liste par compréhension et ''.join()\n", " return result\n", "\n", "axiome = 'A'\n", "for k in range (5):\n", " print(f'{k} => {iter_lSystem(axiome, k)}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Flocon de Von Koch :

\n", "\n", "On souhaite définir et utiliser un L-System nous permettant d'obtenir une suite de caractères représentant les commandes à donner au module Turtle de Python pour tracer la figure du flocon de Von Koch, ci dessous: \n", "![image](./images/FloconVK.png) \n", "Cette construction se décompose ainsi: \n", "![image](./images/DecomposeFlocon.png) \n", "Ainsi en observant la composition du segment d'ordre 0, à gauche, on en déduit le L-system suivant:\n", "- Axiome : F\n", "- Règle : F —> F+F--F+F \n", "Avec : F —> variable (commande *forward* de la tortue) \n", "Et deux constantes : \n", "- \\+ —> rotation de +60° de la tortue; \n", "- \\- —> rotation de -60°. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Écrire le L-system d'un segment du flocon de Von Koch :

" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "##### Segment du flocon de Von Koch: #####\n", "\"\"\"\n", "alphabet:\n", " variable: F\n", " constantes: +;-\n", "axiom: F\n", "règle: F —> F+F--F+F\n", "\"\"\"\n", "\n", "def iter_lSystem(chaine: str, k: int) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne initiale (l'axiome) et l'ordre k souhaité\n", " Retourne la chaîne obtenue après k applications du L-system\n", " \"\"\"\n", " for _ in range(k):\n", " chaine = lSystemConvert(chaine)\n", " return chaine\n", "\n", "def lSystemConvert(chaine: str) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne de caractères\n", " Retourne la chaîne obtenue après application des règles du L-System\n", " \"\"\"\n", " rules = {\"F\":\"F+F--F+F\"} # A compléter : règles\n", " result = ''.join([rules.get(ch, ch) for ch in chaine]) # A compléter : liste par compréhension et ''.join()\n", " return result\n", "\n", "axiome = 'F'\n", "\"\"\"\n", "for k in range (5):\n", " print(f'{k} => {iter_lSystem(axiome, k)}')\n", "\"\"\"\n", "\n", "resultat = iter_lSystem(axiome, 2)\n", "\n", "from turtle import Pen\n", "\n", "t = Pen()\n", "for instruction in resultat:\n", " if instruction == '+':\n", " t.right(60)\n", " elif instruction == '-':\n", " t.left(60)\n", " elif instruction == 'F':\n", " t.forward(5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Le flocon :

\n", "\n", "A partir du tracé d'un côté, la forme fermée du flocon est obtenue en partant d'un triangle équilatéral : \n", "![image](./images/Triangle.png) \n", "\n", "Adapter l'axiome du L-system pour obtenir la chaîne de commande du flocon." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "##### Flocon de Von Koch: #####\n", "\"\"\"\n", "alphabet:\n", " variable: F\n", " constantes: +;-\n", "axiom: \n", "règle: F —> F+F--F+F\n", "\"\"\"\n", "\n", "def iter_lSystem(chaine: str, k: int) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne initiale (l'axiome) et l'ordre k souhaité\n", " Retourne la chaîne obtenue après k applications du L-system\n", " \"\"\"\n", " for _ in range(k):\n", " chaine = lSystemConvert(chaine)\n", " return chaine\n", "\n", "def lSystemConvert(chaine: str) -> str:\n", " \"\"\"\n", " Prends en entrée une chaîne de caractères\n", " Retourne la chaîne obtenue après application des règles du L-System\n", " \"\"\"\n", " rules = {\"F\":\"F+F--F+F\"} # A compléter : règles\n", " result = ''.join([rules.get(ch, ch) for ch in chaine]) # A compléter : liste par compréhension et ''.join()\n", " return result\n", "\n", "axiome = '+F--F--F'\n", "resultat = iter_lSystem(axiome, 4)\n", "\n", "#print(resultat)\n", "\n", "from turtle import Pen, exitonclick\n", "\n", "t = Pen()\n", "\n", "t.up()\n", "t.goto(-300, -300)\n", "t.down()\n", "\n", "t.speed(0)\n", "t.color('#5B58A4', '#B5F8FF')\n", "t.begin_fill()\n", "for instruction in resultat:\n", " if instruction == '-':\n", " t.right(60)\n", " elif instruction == '+':\n", " t.left(60)\n", " elif instruction == 'F':\n", " t.forward(10)\n", "t.end_fill()\n", "exitonclick()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Commande du module Turtle :

\n", "\n", "Notre L-system permet d'obtenir la suite des commandes destinées à la tortue pour tracer le flocon de Von Koch. \n", "Remarque : Il faut appliquer un facteur d'échelle $<1$ sur la commande` forward()` de la tortue, en fonction de l'ordre renvoyé par le L-system, afin de conserver un tracé qui tienne dans la fenêtre." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import turtle as trtl # https://docs.python.org/fr/3/library/turtle.html# \n", "\n", "def dessine (taille) :\n", " trtl.pendown()\n", " trtl.forward(taille)\n", " trtl.right (90)\n", " trtl.forward (taille)\n", " trtl.right (90)\n", " trtl.penup()\n", "\n", "taille = 20\n", "for _ in range (10):\n", " trtl.penup()\n", " taille = taille * 1.2\n", " dessine (taille)\n", "trtl.exitonclick()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Applications :

\n", "\n", "Voici d'autres exemple de fractale à tracer avec votre algorithme L-System : " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from turtle import Pen\n", "\n", "# L'arbre binaire:\n", "\n", "def arbre_binaire():\n", " pile = []\n", "\n", " arbre_binaire = {\n", " 'longueur': 5,\n", " 'angle': 18, \n", " 'niveaux': 6,\n", " 'axiome': 'X',\n", " 'regles': { 'X': 'F[+X]-[-X]+', # Note: [ et ] —> enregistrer et restaurer la position de la tortue.\n", " 'F': 'FF' }\n", " }\n", "\n", " chaine = arbre_binaire['axiome']\n", " for _ in range(arbre_binaire['niveaux']):\n", " chaine = ''.join([arbre_binaire['regles'].get(ch, ch) for ch in chaine])\n", "\n", " t = Pen()\n", " t.left(90)\n", "\n", " for instruction in chaine:\n", " if instruction == '[':\n", " pile.append(t.pos())\n", " elif instruction == ']':\n", " t.goto(pile.pop())\n", " elif instruction == 'F':\n", " t.forward(arbre_binaire['longueur'])\n", " elif instruction == '+':\n", " t.left(arbre_binaire['angle'])\n", " elif instruction == '-':\n", " t.right(arbre_binaire['angle'])\n", "\n", "\"\"\"\n", "\n", "\n", "# Les arbres de la page 25 du livre The Algorithmic Beauty of Plants (http://algorithmicbotany.org/papers/abop/abop.pdf)\n", "arbre_a = {\n", " 'longueur': 4,\n", " 'angle': 25.7, \n", " 'niveaux': 5,\n", " 'axiome': 'F',\n", " 'regles': { 'F': 'F[+F]F[-F]F' }\n", "}\n", "\n", "arbre_b = {\n", " 'longueur': 9,\n", " 'angle': 20, \n", " 'niveaux': 5,\n", " 'axiome': 'F',\n", " 'regles': { 'F': 'F[+F]F[-F][F]' }\n", "}\n", "\n", "arbre_c = {\n", " 'longueur': 10,\n", " 'angle': 22.5, \n", " 'niveaux': 4,\n", " 'axiome': 'F',\n", " 'regles': { 'F': 'FF-[-F+F+F]+[+F-F-F]' }\n", "}\n", "\n", "arbre_d = {\n", " 'longueur': 3,\n", " 'angle': 20, \n", " 'niveaux': 7,\n", " 'axiome': 'X',\n", " 'regles': { \n", " 'X': 'F[+X]F[-X]+X', \n", " 'F': 'FF'\n", " }\n", "}\n", "\n", "arbre_e = {\n", " 'longueur': 3,\n", " 'angle': 25.7, \n", " 'niveaux': 7,\n", " 'axiome': 'X',\n", " 'regles': { \n", " 'X': 'F[+X][-X]FX',\n", " 'F': 'FF'\n", " }\n", "}\n", "\n", "arbre_f = {\n", " 'longueur': 7,\n", " 'angle': 22.5, \n", " 'niveaux': 5,\n", " 'axiome': 'X',\n", " 'regles': {\n", " 'X': 'F-[[X]+X]+F[+FX]-X',\n", " 'F': 'FF' \n", " }\n", "}\n", "\n", "\"\"\"\n", "\n", "arbre_binaire()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3.8.10 64-bit", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" }, "orig_nbformat": 4, "vscode": { "interpreter": { "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6" } } }, "nbformat": 4, "nbformat_minor": 2 }