====== Ensemble de Mandelbrot ======

{{ :nsi:tds:maths:fractales:mandelbrot_set.png?nolink&200|Ensemble de Mandelbrot}}

{{ :nsi:tds:maths:fractales:mandelbrot.jpg?nolink&140|Benoît Mandelbrot}}

Benoît Mandelbrot (1924 - 2010) est un mathématicien franco-polonais inventeur des fractales. L'ensemble qu'il a découvert, à la suite de son professeur Gaston Julia, est devenu un [[https://fr.wikipedia.org/wiki/M%C3%A8me|mème]].

Les fractales sont un champ d'étude aux multiples applications. On peut citer la théorie du Chaos et la génération procédurale : Par exemple, dans les jeux vidéos, les fractales permettent de générer automatiquement des environnement riches, denses, comme des forêts de feuillus.

===== Définition de l'ensemble =====

<WRAP important>La définition de l'ensemble utilise les nombres complexes et le plan complexe. Mais on peut comprendre sans avoir besoin de savoir ce qu'est un nombre complexe. Je vais donc adopter ici une description qui reste compréhensible même sans connaître les nombres complexes.

J'écrirais les coordonnées des points $(x ; y)$ comme s'il s'agissait d'un nombre $z$ et j'écrirais donc $z = (x ; y )$ ce qui ne respecte pas les notations mathématiques mais est compréhensible. Et pour aller jusqu'au bout de l'abus de notation, je parlerai indifféremment de point et de coordonnées comme si on pouvait dire point = coordonnées, ce qui, là encore, n'est pas tout à fait rigoureux.
</WRAP>

On se place dans le plan doté d'un repère orthonormé. Les points ont des coordonnées $(x ; y)$. Comme dit dans l'avertissement ci-dessus, je nomme $z$ à la fois le point et ses coordonnées ce qui me permet d'écrire $z = (x ; y )$.

On considère une suite de points $z_n$ définis par récurrence :

$$z_{n + 1} = z_n^2 + c \quad ; \quad z_0 = (0 ; 0)$$

Ce calcul se fait avec les nombres complexes mais pour ceux qui ne connaissent pas je l'explicite. avec $z_{n+1} = (x_{n+1} ; y_{n+1})$ :
$$x_{n+1} = x_n^2 - y_n^2 + x_c$$
$$y_{n+1} = 2 \cdot x_n \cdot y_n + y_c$$

==== Suite divergente ? ====

Les valeurs de $z_n$ n'ont pas d'importance par elles-mêmes. On veut juste savoir si la suite $z_n$ diverge ou non. Autrement dit, on veut savoir si $(x_n ; y_n)$ finit par s'éloigner infiniment de l'origine.

Prenons un exemple : si $c = (1 ; 1)$ alors la suite $z_n$ prend les valeurs :

$z_0 = (0 ; 0)$ ; $z_1 = (1 ; 1)$ ; $z_2 = (1 ; 3)$ ; $z_3 = (-7 ; 7)$ ; $z_4 = (1 ; 99)$ ; ...

On voit que le point $z_n$ s'éloigne de l'origine. On dira que cela diverge.

Autre exemple, si $c = (-1 ; 0)$. Alors :

$z_0 = (0 ; 0)$ ; $z_1 = (-1 ; 0)$ ; $z_2 = (0 ; 0)$ ; $z_3 = (-1 ; 0)$ ; $z_4 = (0 ; 0)$ ; ...

On voit que dans ce cas, $z_n$ oscille entre deux valeurs et donc ne s'éloigne pas indéfiniment de l'origine. Dans ce cas, cela ne diverge pas.

<WRAP tip>
L'ensemble de Mandelbrot est l'ensemble des valeurs de $c$ pour lesquelles la suite $z_n$ ne diverge pas.

Ces points sont ceux en noir sur la figure en haut.
</WRAP>

Donc $c = (1 ; 1)$ n'est pas dans l'ensemble de Mandelbrot. $c = (-1 ; 0)$ lui est dans l'ensemble.

==== Calcul pratique ====

Il est très difficile, pour un $c$ quelconque, de prévoir si la suite divergera ou non. Pour dessiner l'ensemble on se contente d'un critère simplifié.

  * On sait d'abord que si $|z_n| = \sqrt{x_n^2 + y_n^2} \geq 2$ alors la suite diverge.
  * On se fixe un nombre $N$, par exemple $N = 50$ ou $N = 500$.
  * On choisit la valeur de $c$ à tester,
  * on calcule les termes $z_n$ avec $0 \geq n \geq N$,
  * si on trouve un $|z_n| \geq 2$, alors c'est terminé, cette valeur de $c$ n'est pas dans l'ensemble. On pourra la représenté en blanc.
  * sinon, on considère que $c$ est est dans l'ensemble et on pourra le représenter en noir.

===== Implémentation =====

==== Un point est-il dans l'ensemble ? ====

Écrire la fonction suivante :

<code python>
ITERATIONS = 50

def is_mandelbrot(cx:float, cy:float) -> bool:
    '''
    cx, cy: coordonnées du point c testé
    renvoie True si c est dans l'ensemble de Mandelbrot
    '''
</code>

==== Créer une image ====

Ajoutez ces imports en début de programme :

<code python>
import matplotlib.image as mpimg
import numpy as np
</code>

  * ''numpy'', alias ''np'', permet de manipuler une image sous forme d'une grille
  * ''mpimg'' permet de sauvegarder l'image dans une fichier 

Créer une image 800x600 en monochrome (niveaux de gris) toute blanche :

<code python>
# (50,50) : dimensions (HAUTEUR, LARGEUR)
# np.uint8: chaque pixel est un octet donc entre 0 et 255
# 255: niveau max -> blanc
img = np.full((50, 50), 255, np.uint8)
</code>

Modifier le contenu d'un pixel :

<code python>
# mettre en noir la ligne 35 et colonne 12 :
img[35,12] = 0
</code>

Enfin, pour sauvegarder l'image :

<code python>
mpimg.imsave('mandelbrot.png', img, cmap="gray")
</code>

Maintenant à vous, créez la fonction suivante :

<code python>
def draw(filename:string, centerx:float, centery:float, largeur:int, hauteur:int, dot:float):
    '''
    filename: nom du fichier produit
    centerx, centery: coordonnées du point qui sera au centre de l'image
    largeur, hauteur: dimension de l'image, en pixels
    dot: taille du pixel
    produit un fichier image contenant l'ensemble de Mandelbrot
    '''
</code>

Pour arriver au bout, il faut :
  - créer le tableau numpy ''img'',
  - parcourir chaque pixel et pour chaque pixel :
    * calculer les coordonnées x, y correspondantes,
    * tester si ces coordonnées sont dans l'ensemble de Mandelbrot
    * si oui, mettre le pixel à 0, sinon mettre le pixel à 255
  - sauvegarder le tableau ''img'' dans un fichier

Il reste à prévoir une exécution. Par exemple :

<code python>
draw('mandelbrot.png', 0, 0, 800, 600, 0.01)
</code>

==== Niveaux de gris ====

L'image obtenue est en noir et blanc, tout ou rien. Ce n'est pas très joli. Pour obtenir une image plus belle, on veut mettre les points en plus ou moins clair.

On écrit la fonction :

<code python>
def mandelbrot_score(cx:float, cy:float) -> float:
    '''
    cx, cy: coordonnées du point c testé
    renvoie un score entre 0 et 1
      0 pour un point dans l'ensemble
      1 pour un point qui diverge vite
      un score intermédiaire pour les autres
    '''
</code>

Pour obtenir le score, on fait comme précédemment :
  * $z_0 = (0 ; 0)$
  * calcul en boucle de $z_{n+1} = z_n^2 + c$
  * si on trouve $z_{n+1}$ tel que $|z_{n+1}|\geq 2$, on renvoie $1 - \frac{n}{N}$
  * si on fait les $N$ boucles sans jamais avoir $|z_{n+1}|\geq 2$, alors on renvoie $0$

Et dans la fonction ''draw'', on colorie le pixel avec la couleur ''int(255*score)''.

==== Un peu de couleur ====

On aime avoir des images en couleurs.

C'est très simple : il suffit de modifier l'option ''cmap'' dans ''%%mpimg.imsave(filename, img, cmap="gray")%%''

Il y a beaucoup de possibilités, on peut les trouver [[https://matplotlib.org/stable/tutorials/colors/colormaps.html|ici]]. Par exemple, vous pouvez essayer ''%%mpimg.imsave(filename, img, cmap="plasma")%%''

===== Les complexes dans Python =====

Python prend nativement en charge les complexes : pour $z = 4 + 5i$, il suffira d'écrire ''z = 4 + 5j''.

Attention, si c'est $z = 4 + i$, il faut écrire ''z = 4 + 1j'' pour permettre à Python de reconnaître qu'on parle d'un complexe.

On pourra ensuite faire tous les calculs désirés. En particulier, pour $|z|$ il suffit d'écrire ''abs(z)''.

<code python>
>>> z = 2 + 3j
>>> c = 1 + 1j
>>> z**2 + c
(-4+13j)
>>> abs(z)
3.6055512754639896
</code>

===== Solutions dans d'autres langages =====

  * [[nsi:langages:processing:solutions:mandelbrot|Processing]]
  * [[nsi:langages:js:solutions:mandelbrot|Ensemble de Mandelbrot]]