👼🏻 ↪️ 🤑 Fractales en Python. Procédure pas à pas 🥫 🚵🏾 🚣🏻

Bonjour, Habr! La publication d'aujourd'hui sur les fractales est apparue dans le cadre d'un thème Python , en particulier, Matplotlib. Suivez l'exemple de l'auteur et avertissez que dans le post, il y a beaucoup d'animation lourde qui peut même ne pas fonctionner sur un appareil mobile. Mais comme c'est beau.

Tous aiment lire

Les fractales sont belles. Ils s'alignent selon un motif très complexe et sont conservés sans distorsion à n'importe quel grossissement! Dans cet article, nous verrons comment vous pouvez facilement dessiner des fractales de plusieurs types, en utilisant un outil appelé L-Systems et le module Turtle pour Python pour effectuer un dessin étape par étape.

Dans cet article, nous n'entrerons pas trop dans les détails techniques; au lieu de cela, je me limite à une brève introduction, montre beaucoup d'exemples animés et de code avec lesquels vous pouvez générer un tel exemple. Si vous voulez sauter la théorie et simplement regarder l'animation, allez directement aux exemples. De plus, à la fin, je soulignerai plusieurs ressources, à la fois en écriture de code et en mathématiques de base, que vous voudrez peut-être explorer.

Qu'est-ce qu'une fractale?

Pour commencer, donnons une définition «lâche» d'une fractale. En principe, une fractale est une figure géométrique qui démontre les mêmes propriétés quel que soit le degré d'augmentation.

Cette définition n'est pas parfaite, alors voici une plus précise du site Web de Math World:

Une fractale est un objet ou une quantité qui démontre l'auto-similitude (au sens formel) à n'importe quelle échelle. Un objet ne présente pas des structures identiques à différentes échelles, mais des structures du même «type» doivent apparaître à tous les niveaux de la fractale. Dans ce cas, le graphique est tracé dans un système de coordonnées avec une échelle logarithmique, où la magnitude et l'échelle sont comptées le long des axes, le graphique est une ligne droite avec une pente reflétant la dimension de la fractale. - Math World

Comment dessiner des fractales en utilisant Python?

En règle générale, le rendu des fractales est complexe, car la nature profonde des fractales est déterminée par le concept de récursivité. En parlant des graphiques et de leur dessin, nous pensons généralement qu'ils sont formés de pixels ou de vecteurs, mais le nombre de pixels ou de vecteurs est toujours limité et les fractales, par définition, sont infiniment récursives. Ainsi, en essayant d'appliquer une fractale à la grille de coordonnées, nous devrons nous arrêter à un moment donné, et c'est pourquoi nous parlons ici d'itérations. À chaque itération, la fractale devient plus compliquée et à un moment donné, il devient impossible de distinguer deux de ses itérations l'une après l'autre (un tel moment se produit lorsque des changements se produisent à un niveau comparable à la taille du pixel). Il est logique de s'arrêter ici, mais, en règle générale, la forme de la fractale apparaît plus rapidement et vous pouvez vous arrêter encore plus tôt.

Deux de ces exemples sont l'île carrée de Koch, dont la structure émerge clairement après trois itérations, et le dragon Carter-Heitway, pour lequel 8 itérations suffisent pour construire la structure complète. Le nombre d'itérations requis dépend fortement de la fractale spécifique avec laquelle nous travaillons.

Bien sûr, il existe de nombreuses bibliothèques Python pour le traçage, parmi lesquelles la plus populaire est Matplotlib, mais elles sont généralement conçues pour dessiner des statistiques et dessiner des graphiques bien connus. En particulier, Matplotlib contient des constructions de bas niveau qui peuvent être utilisées pour construire des fractales, mais cette fois-ci, nous nous concentrerons sur le module méconnu et peu mérité de la bibliothèque standard appelé Turtle.

Module Turtle

dans la documentation Pythonnous lisons: «Les graphiques de tortues sont un outil populaire pour la première connaissance des enfants avec la programmation. Il faisait partie du langage de programmation Logo original, développé par Wally Förzeg et Seymour Papert en 1966. »

L'essentiel est que la tortue reconnaît 3 commandes par défaut:

Avancer
Faire pivoter l'angle gauche
Faire pivoter l'angle droit

Remarque: d'autres commandes sont fournies dans la bibliothèque standard, mais ici nous n'utiliserons que ces trois.

Nous pouvons également:

Enregistrement muet
Activer l'enregistrement

Ces caractéristiques semblent trop simples pour s'appuyer sur un graphique aussi complexe qu'une fractale, en ne s'appuyant que sur elles, mais nous utiliserons un autre outil qui n'utilise que ce petit ensemble d'instructions. Je parle de L-systèmes.

L-systems Un

L-system est un moyen de représenter des structures récursives (par exemple, des fractales) comme une chaîne de caractères et de réécrire une telle chaîne plusieurs fois. Encore une fois, nous donnons une définition formelle:

Le système Lindenmeyer, également connu sous le nom de système L, est un mécanisme de réécriture de lignes qui peut être utilisé pour générer des fractales avec des dimensions de 1 à 2 - Math World

Après avoir compris ce qu'est un L-système, nous pouvons créer des structures récursives, mais d'abord, essayons de comprendre de quels composants nous avons besoin pour cela. Chaque système L a:

: , L-.
: .
: , .

Remarque pour les fans d'informatique: si vous avez étudié l'informatique en profondeur, alors tout ce qui précède peut vous rappeler quelque chose. En effet, les grammaires formelles sont définies de manière très similaire; la principale différence est que, contrairement aux grammaires, ici à chaque itération autant de règles s'appliquent que possible, et pas seulement une. Par conséquent, les systèmes L sont un sous-ensemble de grammaires sans contexte.

Étant donné que nous allons utiliser Turtle pour construire des graphiques et le système L pour représenter ce que nous allons tracer, nous devons créer une relation entre eux.

Étant donné que dans Turtle, nous n'avons que les équipes énumérées ci-dessus, nous attribuons à chacune d'entre elles un symbole; l'alphabet sera composé de ces caractères.

F: ramper vers l'avant
+: tourner à droite
-: tournez à gauche

Pour que cela fonctionne, un angle doit être prévu pour chaque fractale; ce sera l'angle auquel la tortue se tournera vers la droite ou la gauche. Par souci de simplicité, nous convenons qu'un seul coin doit être fourni, et nous allons écrire le système L, en gardant cela à l'esprit.
L'axiome et les instructions pour créer des chaînes dépendront uniquement de la fractale, mais la fractale doit être écrite de manière à ne pouvoir être représentée que par ces trois caractères. Il y a donc une restriction, en vertu de laquelle nous ne pouvons construire que des fractales unifilaires, c'est-à-dire que quelque chose comme l'ensemble de Cantor ne peut pas être obtenu de cette manière. Mais ce n'est qu'une simplification, car nous pouvons toujours saisir deux autres commandes pour avancer sans enregistrer, et la même pour revenir en arrière.

Passons maintenant aux exemples!

Exemples animés

Les exemples suivants ont été extraits en ligne de plusieurs sources accessibles au public, et j'ai décidé de les porter sur Python à l'aide du module Turtle, de les centrer, de les coloriser et de fournir un moyen d'exporter vers un format vectoriel.

ATTENTION: les animations proposées sont assez grandes, il est recommandé de les regarder uniquement avec un bon internet. Le code Repl peut ne pas fonctionner car il consomme vos ressources et il peut y avoir des problèmes d'affichage des fractales sur les appareils mobiles.

Remarque: Skulpt utilise VOTRE NAVIGATEUR pour rendre et créer des animations, donc lorsque vous suspendez, retardez ou tout autre comportement étrange, il suffit généralement de relire l'animation ou de recharger la page. Peut ne pas fonctionner sur un appareil mobile.

Les exemples sont donnés par ordre de complexité (à mon avis subjectif), donc la chose la plus intéressante est à la fin.

Flocon de neige de Koch

axiom = "F--F--F"
rules = {"F":"F+F--F+F"}
iterations = 4 # TOP: 7
angle = 60

Île Koch Square

axiom = "F+F+F+F"
rules = {"F":"F-F+F+FFF-F-F+F"}
iterations = 2 # TOP: 4
angle = 90

Cristal

axiom = "F+F+F+F"
rules = {"F":"FF+F++F+F"}
iterations = 3 # TOP: 6
angle = 90

Flocon de neige carré

axiom = "F--F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90

Fractal Wicheka

axiom = "F-F-F-F"
rules = {"F":"F-F+F+F-F"}
iterations = 4 # TOP: 6
angle = 90

Courbe de prélèvement

axiom = "F"
rules = {"F":"+F--F+"}
iterations = 10 # TOP: 16
angle = 45

Tapis Sierpinski

axiom = "YF"
rules = {"X":"YF+XF+Y", "Y":"XF-YF-X"}
iterations = 1 # TOP: 10
angle = 60

Réseau de Sierpinski

axiom = "FXF--FF--FF"
rules = {"F":"FF", "X":"--FXF++FXF++FXF--"}
iterations = 7 # TOP: 8
angle = 60

Carré

axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+FF"}
iterations = 3 # TOP: 5
angle = 90

Carrelage

axiom = "F+F+F+F"
rules = {"F":"FF+F-F+F+FF"}
iterations = 3 # TOP: 4
angle = 90

Anneaux

axiom = "F+F+F+F"
rules = {"F":"FF+F+F+F+F+F-F"}
iterations = 2 # TOP: 4
angle = 90

Croix 2

axiom = "F+F+F+F"
rules = {"F":"F+F-F+F+F"}
iterations = 3 # TOP: 6
angle = 90

Pentaplexité

axiom = "F++F++F++F++F"
rules = {"F":"F++F++F+++++F-F++F"}
iterations = 1 # TOP: 5
angle = 36

Courbe à 32 segments

axiom = "F+F+F+F"
rules = {"F":"-F+F-F-F+F+FF-F+F+FF+F-F-FF+FF-FF+F+F-FF-F-F+FF-F-F+F+F-F+"}
iterations = 3 # TOP: 3
angle = 90

Peano Gosper Curve

axiom = "FX"
rules = {"X":"X+YF++YF-FX--FXFX-YF+", "Y":"-FX+YFYF++YF+FX--FX-Y"}
iterations = 4 # TOP: 6
angle = 60

Courbe de Sierpinski

axiom = "F+XF+F+XF"
rules = {"X":"XF-F+F-XF+F+XF-F+F-X"}
iterations = 4 # TOP: 8
angle = 90

Questionlets de Krishna

axiom = " -X--X"
rules = {"X":"XFX--XFX"}
iterations = 3 # TOP: 9
angle = 45

Fractale carrée Gosper

axiom = "YF"
rules = {"X": "XFX-YF-YF+FX+FX-YF-YFFX+YF+FXFXYF-FX+YF+FXFX+YF-FXYF-YF-FX+FX+YFYF-", 
        "Y": "+FXFX-YF-YF+FX+FXYF+FX-YFYF-FX-YF+FXYFYF-FX-YFFX+FX+YF-YF-FX+FX+YFY"}
iterations = 2 # TOP: 3
angle = 90

Courbe de Moore

axiom = "LFL-F-LFL"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 0 # TOP: 8
angle = 90

Courbe de Hilbert

axiom = "L"
rules = {"L":"+RF-LFL-FR+", "R":"-LF+RFR+FL-"}
iterations = 8 # TOP: 9
angle = 90

Hilbert Curve II

axiom = "X"
rules = {"X":"XFYFX+F+YFXFY-F-XFYFX", "Y":"YFXFY-F-XFYFX+F+YFXFY"}
iterations = 4 # TOP: 6
angle = 90

Courbe de Peano

axiom = "F"
rules = {"F":"F+F-F-F-F+F+F+F-F"}
iterations = 2 # TOP: 5
angle = 90

Traverser

axiom = "F+F+F+F"
rules = {"F":"F+FF++F+F"}
iterations = 3 # TOP: 6
angle = 90

Triangle

axiom = "F+F+F"
rules = {"F":"F-F+F"}
iterations = 2 # TOP: 9
angle = 120

Courbe de dragon

axiom = "FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 8 # TOP: 16
angle = 90

Courbe de Terdragon

axiom = "F"
rules = {"F":"F-F+F"}
iterations = 5 # TOP: 10
angle = 120

Double courbe du dragon

axiom = "FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 6 # TOP: 16
angle = 90

Courbe du dragon triple

axiom = "FX+FX+FX"
rules = {"X":"X+YF+", "Y":"-FX-Y"}
iterations = 7 # TOP: 15
angle = 90

Code

Tous les exemples ci-dessus ont été obtenus en utilisant le même code, et lors de leur utilisation, certaines difficultés sont survenues (par exemple, comment garder la fractale au centre autant que possible), en travaillant avec la couleur, l'inversion, les décalages, ainsi qu'en fournissant une exportation rapide vers format vectoriel. Ici, je ne vous montre que la version la plus simple.
Cette version affiche les fractales en noir et blanc et n'est pas équipée de la fonction d'exportation

import turtle

def create_l_system(iters, axiom, rules):
    start_string = axiom
    if iters == 0:
        return axiom
    end_string = ""
    for _ in range(iters):
        end_string = "".join(rules[i] if i in rules else i for i in start_string)
        start_string = end_string

    return end_string


def draw_l_system(t, instructions, angle, distance):
    for cmd in instructions:
        if cmd == 'F':
            t.forward(distance)
        elif cmd == '+':
            t.right(angle)
        elif cmd == '-':
            t.left(angle)


def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
        x_offset=0, offset_angle=0, width=450, height=450):

    inst = create_l_system(iterations, axiom, rules)

    t = turtle.Turtle()
    wn = turtle.Screen()
    wn.setup(width, height)

    t.up()
    t.backward(-x_offset)
    t.left(90)
    t.backward(-y_offset)
    t.left(offset_angle)
    t.down()
    t.speed(0)
    t.pensize(size)
    draw_l_system(t, inst, angle, length)
    t.hideturtle()

    wn.exitonclick()

Explication du code

import turtle

Vous devez d'abord importer le module Turtle

def create_l_system(iters, axiom, rules):
    start_string = axiom
    if iters == 0:
        return axiom
    end_string = ""
    for _ in range(iters):
        end_string = "".join(rules[i] if i in rules else i for i in start_string)
        start_string = end_string

    return end_string

Ensuite, vous devez générer un système L, qui sera un ensemble d'instructions pour la tortue. Nous définissons une fonction create_l_systemqui reçoit le nombre d'itérations, un axiome et des règles de construction. Il commence par un axiome et utilise une variable auxiliaire end_string, si l'itération est 0, alors il renverra l'axiome, car certaines fractales peuvent être appliquées avec zéro itérations. Dans ce cas, il est supposé que les règles ont la forme de dictionnaires, donc chaque clé est unique, représente un symbole et la valeur indique ce qui doit être remplacé et ce qui doit être remplacé. Nous combinons donc tous les remplacements pour chaque caractère et obtenons finalement une chaîne pour la prochaine itération.

def draw_l_system(t, instructions, angle, distance):
    for cmd in instructions:
        if cmd == 'F':
            t.forward(distance)
        elif cmd == '+':
            t.right(angle)
        elif cmd == '-':
            t.left(angle)

Ensuite, nous déterminons draw_l_systemqui accepte la tortue, un ensemble d'instructions (sortie du système L), l'angle de rotation à gauche ou à droite et la longueur de chaque ligne individuelle. Il consiste en une structure simple elifpour chacune des équipes précédemment définies.

def main(iterations, axiom, rules, angle, length=8, size=2, y_offset=0,
        x_offset=0, offset_angle=0, width=450, height=450):

    inst = create_l_system(iterations, axiom, rules)

    t = turtle.Turtle()
    wn = turtle.Screen()
    wn.setup(width, height)

    t.up()
    t.backward(-x_offset)
    t.left(90)
    t.backward(-y_offset)
    t.left(offset_angle)
    t.down()
    t.speed(0)
    t.pensize(size)
    draw_l_system(t, inst, angle, length)
    t.hideturtle()

    wn.exitonclick()

Enfin, PARLONS sur la fonction main, qui prend tous les paramètres nécessaires à la production de L-systèmes, ainsi que y_offset, x_offset, offset_angle, widthet height. Les trois premiers décrivent le déplacement de la tortue, il suffit de positionner le graphe sur la toile comme on le souhaite.

La fonction génère d'abord un ensemble d'instructions et les enregistre en inst, puis initialise la tortue et l'écran et place la tortue à un point spécifique, puis dessine un graphique conformément aux instructions et attend un clic pour fermer.

Considérations particulières

Comme je l'ai mentionné ci-dessus, de nombreuses restrictions sont laissées ici. Premièrement, nous n'avons pas prévu pour la tortue la possibilité de se déplacer sans rendu; cela nécessiterait un autre caractère. Il n'y a pas non plus de symbole pour reculer et pour se souvenir des positions précédentes. Ils n'étaient pas requis pour toutes les fractales décrites ci-dessus, mais ils sont requis pour d'autres (par exemple, les arbres fractals).

Ressources supplémentaires

Internet possède de nombreuses ressources sur les fractales, où elles sont considérées à la fois du point de vue de la programmation et du point de vue des mathématiques. Les deux suivants m'ont paru particulièrement intéressants: 3Blue1Brown (math) et CodingTrain (code).

L'article a été inspiré par un article de Math World et l' article Paula Burka.

Fractales en Python. Procédure pas à pas

More articles: