\documentclass[10pt]{tpcaml}

% TP caml à LLG, Fin Avril
% par Gabriel Scherer

\tp{4}{Jolis dessins (Mandelbrot)\\}

\usepackage{amsfonts}

\begin{document}

  \maketitle
  Le but de ce TP est de faire de jolis dessins. On utilisera pour
  cela des mathématiques, et le module \code{graphics} de \camli.

\section{Préliminaires}

Une bonne méthode pour obtenir des dessins amusants vient de la
dynamique complexe. En deux mots, on choisit un polynôme complexe $P$,
et l'on étudie la suite $P^n(z)$, où $P^n$ est la fonction polynomiale
itérée ($P^{n+1} = P^n \circ P$) et $z$ un point du plan complexe.

On peut se poser de nombreuses questions au sujet de ces suites
$P^n(z)$ (la périodicité par exemple). On s'intéressera ici à un
critère très simple : on se demande si elles sont bornées en norme.

On va ``dessiner'' la question, en affichant à l'écran une partie du
plan complexe en mettant les points en noir et blanc (par exemple)
selon que la suite des normes correspondant est bornée ou non.

Pour ne pas se prendre la tête, on va commencer par les polynômes
intéressants les plus simples possibles, à savoir ceux de la forme
$P_c = X^2 + c,\, c \in \mathbb{C}$. La suite $(P_c^n(z))_{n \in \mathbb{N}}$ dépend des deux
paramètres $c$ et $z$. Dans un dessin à deux dimensions, seul un
paramètre complexe varie, il faut donc faire un choix. Si l'on décide
de faire varier $z$, on obtient des fractales de Julia; si l'on décide
de faire varier $c$, on obtient la fractale de Mandelbrot. La fractale
de Mandelbrot est plus simple puisqu'on peut faire un choix facile
pour $z$ : on prend $z = 0$, et on obtient de bons résultats. Les
fractales de Julia, au contraire, dépendent fortement du choix de $c$
et il peut être délicat de trouver des valeurs produisant un dessin
satisfaisant : clairement, $c = 0$ n'est pas très un choix très
excitant.

\subsection{Opérations complexes}

\begin{question}
  On représente les complexes par le type \code{float * float}. Écrire
  les fonctions \code{add}, \code{mul}, \code{norme2} d'addition, de
  multiplication et de norme au carré dans $\mathbb{C}$.
\end{question}

\vspace{12pt}

Le critère de divergence est très simple : on regarde la suite
jusqu'au terme $N$ (pour $N$ très grand), et si le carré de la norme de l'une des
valeurs est supérieure à $R$ (pour R assez grand), on considère que la suite
n'est pas bornée. C'est très rigoureux. On prendra par la suite $N =
50$ et $R = 4$.

\begin{question}
  Définir des valeurs \code{limite\_iterations = 50} et
  \code{limite\_norme2 = 4.}. Définir ensuite une fonction
  \code{mandelbrot : (float * float) -> (int * (float * float))} qui,
  étant donné $c$ en paramètre, calcule\footnote{récursivement, bien
    sûr} les valeurs de $P_c^n(0)$. La fonction doit s'arrêter :
  \begin{itemize}
  \item si $n = N$
  \item si $n < N$ mais $|P_c^n(0)|^2 > R$
  \end{itemize}
  Dans les deux cas, on renvoie le couple $(n, P_c^n(0))$.
\end{question}

\section{Affichage}

On calculera et affichera seulement des valeurs discrètes de la
fonction \code{mandelbrot} : concrètement, on parcourira avec deux
boucles les valeurs \code{(x,y)} avec \code{0 <= x < taille\_x} et \code{0
  <= y < taille\_y}. Il faut donc établir une correspondance entre ces
valeurs et les points dans la région du plan complexe qui nous
intéresse.

Dans le cas de l'ensemble de mandelbrot, on utilisera la traduction suivante :
\begin{displaymath}
  \left\{
    \begin{array}{l}
      x \to 2\frac{x}{taille_x} - 1.5 \\
      y \to 2\frac{y}{taille_y} - 1.
    \end{array}\right.
\end{displaymath}

\vspace{12pt}

\begin{question}
  Écrire une fonction \code{normalise : int -> int -> float} telle que
  $normalise(k, n) = \frac{k}{n}$.

  Écrire la fonction \code{point : int * int -> int * int -> float *
    float}, qui, étant donnés \\ \code{(taille\_x, taille\_y)} et
  \code{(x,y)}, effectue la traduction des coordonnées dans le plan
  complexe.
\end{question}

\subsection{Affichage moche}

Pour afficher une fenêtre avec des couleurs, on utilisera le module
\emph{graphics}. Mais pour commencer, on va essayer d'approximer la
forme de l'ensemble en se content d'afficher du texte (c'est plus
simple).

\vspace{12pt}

\begin{question}
  Écrire une fonction \code{mandelbrot\_texte : int -> int -> unit}
  qui, étant donné les paramètres \code{taille\_x} et \code{taille\_y}, affiche
  \code{taille\_y} lignes de \code{taille\_x} lettres de large, représentant
  l'ensemble de mandelbrot : on affichera (\code{print\_char}) le
  caractère \code{`X`} quand le point appartient à l'ensemble (cas
  d'arrêt $n = N$), \code{`-`} sinon.
\end{question}

Vous pouvez tester votre fonction avec des valeurs raisonnables (il
faut que cela tienne dans votre écran), par exemple 20x20.

\subsection{Affichage en couleurs}

On utilisera maintenant le module \emph{graphics}. N'hésitez pas
à consulter sa documentation dans le manuel.

Pour pouvoir utiliser les fonctions du module sans le préfixe
\code{graphics} (\code{graphics\_\_set\_color}, etc.), on utilise la
directive \code{\#open "graphics" ;;}.

Les couleurs sont représentées (comme souvent en informatique) par un
triplet $(r, g, b)$, où $r$ représente le taux de rouge, $g$ de vert
et $b$ de bleu. La fonction $rgb$ du module produit prend ces trois
paramètres (entiers entre 0 et 255 inclus), et produit une couleur
utilisable par les fonctions de dessin.

Pour produire une couleur à partir du résultat de \code{mandelbrot},
il est plus simple de travailler sur des triplets \code{(r,g,b)}
normalisés (de \code{float} dans $[0,1]$). On a donc besoin d'une
fonction de conversion, d'un triplet normalisé vers une couleur \caml,
qui réutilise \code{rgb}.

\vspace{12pt}

\begin{question}
  Écrire \code{caml\_couleur : float * float * float ->
    color}, qui produit une couleur \caml à partir d'un triplet
  normalisé $(r,g,b) \in [0,1]^3$.
\end{question}

\vspace{12pt}

Il faut choisir une représentation graphique du résultat de
\code{mandelbrot}. On commencera par une méthode simple, utilisant
uniquement des niveaux de gris : $r = g = b = \frac{n}{N}$, où $n$ est
l'itération à laquelle s'est arrêtée la fonction \code{mandelbrot}.

\begin{codesection}
  let mandelbrot\_graphique couleur taille\_x taille\_y =\\
\ \    open\_graph (printf\_\_sprintf " \%dx\%d" taille\_x taille\_y);\\
\ \    (* ... *)\\
\ \    let \_ = read\_key () in\\
\ \    close\_graph ();;
\end{codesection}

\vspace{12pt}

\begin{question}
  Écrire \code{couleur} :\\ \code{int * (float * float) ->
    color}, qui au résultat de \code{mandelbrot} associe une couleur
  \caml.
\end{question}

\vspace{12pt}

\begin{question}
  En utilisant le squelette ci-contre, écrire la fonction
  \code{mandelbrot\_graphique} prenant une fonction \code{couleur} en paramètre,
  et affichant l'ensemble de mandelbrot dans un rectangle de
  dimensions \code{taille\_x, taille\_y}.

  Pour afficher un point, on utilisera la fonction \code{plot : int ->
    int -> ()} prenant les coordonnées du point à afficher. Pour
  régler la couleur d'affichage (à changer pour chaque point à l'aide
  de la fonction \code{couleur}), on utilise au préalable
  \code{set\_color : color -> unit}.

  L'utilisation de la fonction \code{read\_key} permet d'attendre
  l'appui sur une touche par l'utilisateur avant de fermer l'image.
\end{question}

\vspace{12pt}

\begin{question}
  Tester la fonction \code{mandelbrot\_graphique} avec d'autres
  fonctions \code{couleur}. On pourra essayer par exemple la
  traduction suivante :
  \begin{displaymath}
    \left\{
      \begin{array}{l}
       (n, z) \mapsto (0,0,0) \quad \textrm{si}\ n < N\\
       (n, z) \mapsto (\frac{Re(z)^2}{|z|^2}, 0, \frac{Im(z)^2}{|z|^2}) \quad \textrm{quand}\ n = N
      \end{array} \right.
  \end{displaymath}
\end{question}

\end{document}
