{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# La courbe de Von Koch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Marc Lorenzi - 2 mai 2018"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "from cmath import *\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Similitudes du plan complexe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une similitude (directe) est une application $f:\\mathbb C \\to \\mathbb C$ définie par $f(z)=az+b$ où $a,b\\in\\mathbb C$ et $a\\ne 0$. Certaines similitudes très particulières permettent, par composition, de fabriquer toutes les similitudes. Ce sont les __rotations__, les __homothéties__ et les __translations__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Les rotations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une rotation $f$ est caractérisée par son centre $\\omega\\in\\mathbb C$ et son angle $\\theta\\in\\mathbb R$ (on impose aussi parfois que $\\theta\\not\\in 2\\pi\\mathbb Z$). Elle est définie par\n",
    "\n",
    "$$f(z) = \\omega+e^{i\\theta}(z-\\omega)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotation(omega, theta, z):\n",
    "    return omega + exp(1j * theta) * (z - omega)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rotation(1, pi / 4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Les homothéties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une homothétie $f$ est caractérisée par son centre $\\omega\\in\\mathbb C$ et son rapport $\\mu\\in\\mathbb R_+^*$. Elle est définie par\n",
    "\n",
    "$$f(z) = \\omega+\\mu(z-\\omega)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def homothetie(omega, mu, z):\n",
    "    return omega + mu * (z - omega)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "homothetie(1, 3, 1+1j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Les translations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une translation $f$ est caractérisée par un nombre complexe $t$. Elle est définie par\n",
    "\n",
    "$$f(z) = z+t$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def translation(t, z): return z + t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "translation(1+1j, 2+3j)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Dessiner une liste de nombres complexes "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`matplotlib` n'est pas très amatrice de complexes. Écrivons donc une fonction qui nous permet de tracer une liste de points donnés par leurs affixes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `vers_points` prend en paramètre une liste `zs` de complexes. Elle renvoie un couple `(xs, ys)` où `xs` et `ys` sont respectivement les listes des parties réelles et imaginaires des éléments de `zs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vers_points(zs):\n",
    "    xs = [z.real for z in zs]\n",
    "    ys = [z.imag for z in zs]\n",
    "    return xs, ys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `plotC` prend en paramètre une liste de nombres complexes et affiche les points reliés dans le plan complexe. Il y a également un paramètre `bornes` qui permet d'affiner la zone de tracé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plotC(zs, bornes):\n",
    "    xs, ys = vers_points(zs)\n",
    "    plt.plot(xs, ys, 'k')\n",
    "    plt.axis(bornes)\n",
    "    plt.grid()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À titre d'exemple, traçons ... le cercle unité ? Pour être précis, on trace les racines millièmes de l'unité et on les relie :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "zs = [exp(2j * k * pi / 1000) for k in range(1000)]\n",
    "plotC(zs, [-1.2, 1.2, -1.2, 1.2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bon, ça fonctionne. Oubliés les $x$ et les $y$, les sinus, les cosinus. Vive $\\mathbb C$ ! Dorénavant, nous identifierons les points du plan et les nombres complexes. Quand je dirai \"soit $A$ un point\", je penserai souvent \"soit $A$ un nombre complexe\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. La courbe de Von Koch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Première étape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On part d'un segment $S=[A,B]$ où $A$ et $B$ sont deux points du plan. Notons $P$ le point situé au tiers du segment et $Q$ le point situé aux deux tiers du segment. On définit 4 nouveaux segments. \n",
    "\n",
    "- $S_0=[A,P]$.\n",
    "- Soit $U$ l'image de $Q$ par la rotation de centre $P$ et d'angle $\\frac \\pi 3$. On pose $S_1=[P,U]$ et $S_2=[U,Q]$.\n",
    "- Enfin, $S_3=[Q,B]$.\n",
    "\n",
    "On pose ensuite $S'=S_0\\bigcup S_1\\bigcup S_2\\bigcup S_3$. Nous appellerons $S'$ le __transformé de Von Koch__ de $S$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `transforme` prend les points $A$ et $B$ en paramètres. Elle renvoie la liste $[A, P, U, Q, B]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def barycentre(A, B, t):\n",
    "    return (1 - t) * A + t * B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transforme(S):\n",
    "    A, B = S[0], S[1]\n",
    "    P = barycentre(A, B, 1/3)\n",
    "    Q = barycentre(A, B, 2/3)\n",
    "    U = rotation(P, pi/3, Q)\n",
    "    return [A, P, U, Q, B]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = transforme([0, 1])\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici le dessin. Il vaut mieux que le discours ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(T, [0, 1, -0.1, 0.4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Deuxième étape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Définissons maintenant la transformée d'une réunion de segments comme la réunion des transformées des chacun des segments. La fonction ci-dessous prend en paramètre une liste de nombres complexes. Deux éléments successifs de la liste son censés représenter un segment. La fonction renvoie la transformée de Von Koch de la liste de segments.\n",
    "\n",
    "__Remarque__ : les concaténations de listes ci-dessous ne sont pas très efficaces, mais elles seront suffisantes pour nos besoins."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transforme2(zs):\n",
    "    s = []\n",
    "    n = len(zs)\n",
    "    for k in range(n -1):\n",
    "        s1 = transforme([zs[k], zs[k + 1]])\n",
    "        s = s + s1[:-1]\n",
    "    s.append(zs[n - 1])\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = transforme2(transforme([0, 1]))\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(T, [0, 1, -0.1, 0.4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a compris ... on va recommencer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 On itère"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $A$ et $B$ deux points du plan. On pose $K_0=[A,B]$ et, pour tout entier $n\\in\\mathbb N$, $K_{n+1}=\\mathcal T(K_n)$, où $\\mathcal T$ est la transformée de Von Koch.\n",
    "\n",
    "La fonction ci-dessous prend en paramètres un entier $n$ et les deux points $A$ et $B$. Elle renvoie la liste des extrémités des segments de l'ensemble $K_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vonkoch(n, A, B):\n",
    "    S = [A, B]\n",
    "    for k in range(n):\n",
    "        S = transforme2(S)\n",
    "    return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = vonkoch(2, 0, 1)\n",
    "print(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(vonkoch(6, 0, 1), [0, 1, -0.1, 0.4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Que prendre comme valeur de $n$ ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prenons comme unité de longueur de nos raisonnements le pixel. Supposons que la largeur de nos graphiques soit de 1000 pixels, ce qui est évidemment très optimiste. L'appel à `vonkoch(0, 0, 1)` trace donc un segment de 1000 pixels. À chaque itération de la transformation de Von Koch, la taille des segments est divisée par 3. Ainsi, la taille des segments lors du tracé de `vonkoch(n, 0, 1)` est $\\frac{1000}{3^n}$ pixels. Pour $n=7$, par exemple, qu'obtient-on ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1000 / 3 ** 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un demi-pixel, c'est peu. Inutile de dépasser $n=6$, cela ne se verra de toute façon pas sur le dessin."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Von Koch bis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 La \"courbe\" de Von Koch ? C'est quoi ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bon, tout cela est bien beau mais c'est quoi la \"courbe\" de Von Koch ? Nous allons réinterpréter la transformée de Von Koch. Regardons les deux figures ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(vonkoch(2, 0, 1), [0, 1, -0.1, 0.4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(vonkoch(3, 0, 1), [0, 1, -0.1, 0.4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit que $K_3$ est la réunion des images directes de $K_2$ par 4 similitudes que nous allons noter $s_0,\\ldots,s_3$.\n",
    "\n",
    "La première (enfin la zéroième), qui nous donne la partie gauche \"horizontale\", est évidente. C'est l'homothétie de centre $O$ et de rapport $\\frac 1 3$ : $s_0(z)=\\frac 1 3 z$. \n",
    "\n",
    "Pour la partie droite \"horizontale\", il s'agit de l'homothétie de centre $1$ et de rapport $\\frac 1 3$ : $s_3(z)=1 + \\frac 1 3 (z-1)=\\frac 2 3 + \\frac 1 3 z$. Mais inutile de les calculer, Python fera cela pour nous :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = 4 * [None]\n",
    "s[0] = lambda z: homothetie(0, 1/3, z)\n",
    "s[3] = lambda z: homothetie(1, 1/3, z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Passons à la partie milieu-gauche en biais. On commence par faire une homothétie $h$ de rapport $\\frac 1 3$ et de centre $\\frac 1 2$. Puis on effectue la rotation $\\rho$ de centre $\\frac 1 3$ et d'angle $\\frac \\pi 3$. Ainsi, $s_1=\\rho\\circ h$.\n",
    "\n",
    "Pour le morceau restant, à vous de deviner : $s_2=\\rho'\\circ h$, où $\\rho'=$ ? Cela dit la réponse est juste dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s[1] = lambda z: rotation(1/3, pi/3, homothetie(1/2, 1/3, z))\n",
    "s[2] = lambda z: rotation(2/3, -pi/3, homothetie(1/2, 1/3, z))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a donc $K_3=s_0(K_2)\\bigcup s_1(K_2)\\bigcup s_2(K_2)\\bigcup s_3(K_2)$. On peut maintenant définir une transformation $\\mathcal T$ plus générale que celle dont nous avons parlé plus haut. Pour __TOUTE__ partie $E$ du plan, posons \n",
    "\n",
    "$$\\mathcal T(E)=\\bigcup_{k=0}^3s_k(E)$$\n",
    "\n",
    "Nous disposons maintenant de la fonction $\\mathcal T:\\mathcal P(\\mathbb C)\\to\\mathcal P(\\mathbb C)$. Et on a $\\forall n\\in\\mathbb N, K_{n+1}=\\mathcal T(K_n)$.\n",
    "\n",
    "Considérons l'ensemble (que nous noterons $\\mathcal C$) des parties _compactes_ du plan complexe $\\mathbb C$. _Compact_ veut dire _fermé_ et _borné_, je n'en dirai pas plus ici. On peut munir $\\mathcal C$ d'une distance $D$ : la __distance de Hausdorff__. On peut alors montrer qu'il existe un ensemble $K$ tel que, lorsque $n\\to\\infty$, $D(K_n,K)\\to 0$. En d'autres termes, $K_n\\to K$ pour la distance de Hausdorff. \n",
    "\n",
    "__Définition__ : $K$ est appellé la courbe de Von Koch.\n",
    "\n",
    "__Fait__ : Personne n'a jamais vu $K$.\n",
    "\n",
    "En réalité, on a infiniment mieux que cela ...\n",
    "\n",
    "__Théorème__ : \n",
    "\n",
    "1. Il existe un unique $K\\in \\mathcal C$ tel que $\\mathcal T(K) = K$.\n",
    "2. Soit $E\\in\\mathcal C$. Soit $(E_n)_{n\\ge 0}$ la suite définie par récurrence par $E_0=E$ et, pour tout $n\\ge 0$, $E_{n+1}=\\mathcal T(E_n)$. Alors $E_n\\to K$ au sens de la distance de Hausdorff lorsque $n$ tend vers l'infini.\n",
    "\n",
    "Cela veut dire qu'au lieu de démarrer d'un segment $K_0$, comme nous l'avons fait, on peut démarrer de n'importe quoi. Par exemple de Bilbo le Hobbit, ou d'un yack tibétain.\n",
    "\n",
    "__Vous n'y croyez pas, c'est trop théorique, c'est du bluff ? Alors programmons, et regardons le yack se transformer en courbe de Koch.__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Fonctions élémentaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va manipuler des matrices de taille $N\\times N$ dont les éléments représentent des nombres complexes du carré $[0,1]\\times [0,1]$. Quelques petites fonctions auxiliaires vont nous être utiles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `pixel_vers_complexe` prend deux entiers $i$ et $j$ censés être entre 0 et $N-1$. Elle renvoie le nombre complexe correspondant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pixel_vers_complexe(i, j, N):\n",
    "    y = i / N\n",
    "    x = j / N\n",
    "    return x + y * 1j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pixel_vers_complexe(3, 8, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour arrondir ... $x$ est un réel _censé_ être entre 0 et $N$. On renvoie l'entier correspondant, ou à peu près. Si $x$ est trop petit ou trop grand on élague pour rester entre 0 et $N-1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def round(x, N):\n",
    "    i = int(x)\n",
    "    if i <= 0: i = 0\n",
    "    elif i >= N: i = N - 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "round(33.6, 67)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction réciproque de `pixel_vers_complexe`..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def complexe_vers_pixel(z, N):\n",
    "    x = z.real\n",
    "    y = z.imag\n",
    "    j = round(N * x + 0.5, N)\n",
    "    i = round(N * y + 0.5, N)\n",
    "    return (i, j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "complexe_vers_pixel(0.5+0.3j, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fabriquer une matrice $N\\times N$ remplie de zéros ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrice(N):\n",
    "    A = N * [None]\n",
    "    for i in range(N): A[i] = N * [0]\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(matrice(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 La transformée de Von Koch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous y voilà. Que fait `transforme3` ? Pour chaque case de la matrice $A$ égale à 1, elle calcule le nombre complexe $z$ correspondant à la case. Elle applique les 4 similitudes dont nous avons parlé plus haut et met à 1 les cases correspondantes d'une matrice $B$ initialement remplie de zéros. Enfin, la fonction renvoie $B$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transforme3(A):\n",
    "    N = len(A)\n",
    "    B = matrice(N)\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            if A[i][j] == 1:\n",
    "                z = pixel_vers_complexe(i, j, N)\n",
    "                for simil in s:\n",
    "                    u, v = complexe_vers_pixel(simil(z), N)\n",
    "                    B[u][v] = 1\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Petite fonction pour afficher le contenu d'une matrice ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_matrix(A):\n",
    "    plt.imshow(A, origin='lower', interpolation='bicubic', cmap='Greys')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour notre matrice d'exemple, nous allons prendre un yack. Mais un hobbit aurait tout aussi bien fait l'affaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_yack():\n",
    "    A = matrice(400)\n",
    "    f = open('yack-400x400.raw', 'rb')\n",
    "    for i in range(400):\n",
    "        for j in range(400):\n",
    "            c = f.read(3)\n",
    "            if int.from_bytes(c, byteorder='big',signed=False) ==0: A[399-i][j] = 1\n",
    "    f.close()\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = read_yack()\n",
    "plot_matrix(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Itérations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici la fonction qui itère $n$ fois $\\mathcal T$ à partir d'un compact du plan représenté par une matrice $A$ ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iter(n):\n",
    "    A = read_yack()\n",
    "    for k in range(n):\n",
    "        A = transforme3(A)\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lançons une itération."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_matrix(iter(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oui, bon, on a 4 disques. Normal. Alors deux itérations ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_matrix(iter(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je vous laisse tester 3 et 4. Je lance 5 itérations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_matrix(iter(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il fallait faire confiance aux maths. La courbe de Von Koch est bien la limite d'une itérée de yacks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. La dimension de $K$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout le monde le sait, une courbe c'est de dimension 1. Euh oui, les ensembles $K_n$ sont des courbes (des unions de segments en fait), mais $K$ c'est une autre paire de manches. Une limite de yacks tibétains est-elle une courbe ???\n",
    "\n",
    "Rappelez-vous le __fait__ : personne n'a jamais vu $K$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Longueur de $K_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La longueur $L(K_n)$ de $K_n$ ne pose aucun problème. $K_0$ est de longueur 1. Et à chaque étape on a 4 fois plus de segments, qui sont 3 fois plus petits. Donc $L(K_{n+1})=\\frac 4 3 L(K_n)$ et ainsi $L(K_n)=(\\frac 4 3)^n$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Longueur généralisée de $K_n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rigueur absente des deux prochains paragraphes ... tout ceci peut être mathématisé, mais c'est une longue histoire, trop longue pour un notebook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imaginons que je veuille mesurer la __longueur d'un segment__ (de longueur $\\pi$ par exemple) avec une règle __non graduée__, mais de longueur connue. Je dispose de tout un attirail de règles de longueur $1, \\frac 1 2,\\frac 1 3$, etc. J'applique 3 fois ma règle de longueur 1, trop peu. Je l'applique 4 fois, ça dépasse. J'en déduis que la longueur du segment est entre 3 et 4. Je recommence avec une règle de longueur $\\frac 1 {10}$, j'applique ma règle une trentaine de fois, j'en déduis que la longueur du segment est entre $3.1$ et $3.2$, etc ...\n",
    "\n",
    "Maintenant je veux mesurer la __surface d'un carré__. Cette fois-ci, je me procure des règles carrées de côtés divers, j'applique mes règles sur le carré à mesurer. J'en déduis des encadrements de la surface que je veux mesurer. Mais je n'oublie pas d'élever le côté de mes règles au carré, parce que ce sont des surfaces. Oui, j'imagine que vous êtes au courant, vous avez appris ça au CE1. Où veux-je en venir ?\n",
    "\n",
    "Je veux mesurer, idée folle, la __longueur d'un carré__. Je reprends mes règles plates, je les applique à l'intérieur du carré en essayant de le recouvrir ... peine perdue, je n'arrive pas à remplir le carré. Sa longueur est __infinie__.\n",
    "\n",
    "Allez, une dernière expérience. On n'en est plus à ça près, je veux mesurer la __surface d'un segment__ de longueur 1. Je prend par exemple une \"règle carrée\" de côté $\\frac 1 n$, je l'applique $n$ fois et je recouvre le segment. Ben oui ça dépasse, difficile de faire autrement. J'en déduis que la surface $S$ du segment vérifie $S\\le n \\times (\\frac 1 n)^2=\\frac 1 n$. Pour tout $n$, bien entendu. Donc $S=0$.\n",
    "\n",
    "Je peux recommencer, essayer de calculer le __volume d'un carré__, la __surface d'un cube__, etc. Arrêtons de parler de longueur, surface, volume, et parlons de 1-mesure, 2-mesure, 3-mesure. En dimension $d$ ce sera donc la $d$-mesure. L'idée c'est que pour chaque objet de dimension $d$, je dois choisir une règle adaptée pour obtenir une mesure qui ne soit ni nulle, ni infinie. Si j'utilise des $\\delta$-règles pour calculer la \"mesure\" d'un objet de dimension $d$, trois cas se présentent :\n",
    "\n",
    "1. $\\delta<d$ : j'obtiens une $\\delta$-mesure infinie, comme quand je mesure la longueur d'un carré.\n",
    "2. $\\delta>d$ : j'obtiens une $\\delta$-mesure nulle, comme quand je mesure la surface d'un segment.\n",
    "3. $\\delta=d$ : c'est le bon choix, j'obtiens une $\\delta$-mesure ni nulle, ni infinie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prenons un réel $d>0$ positif et $d$-mesurons $K_n$. On mesure $4^n$ segments, qui sont chacun de longueur $\\frac 1 {3^n}$. Je prends une $d$-règle de longueur $\\frac 1 {3^n}$, ce qui me donne une évaluation de la $d$-mesure du segment : $\\frac 1 {3^{nd}}$. Une estimation de la $d$-mesure $\\mu_d(K)$ de $K$ est peut-être :\n",
    "\n",
    "$$\\mu_d(K)\\simeq \\mu_n=\\frac{4^n}{3^{nd}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 La dimension de $K$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que se passe-t-il lorsque $n$ tend vers l'infini ?\n",
    "\n",
    "- Si $3^d<4$, $\\mu_n$ tend vers $+\\infty$. On est dans le cas de celui qui veut mesurer un carré avec une règle. On a visé un peu léger.\n",
    "\n",
    "- Si $3^d>4$, $\\mu_n$ tend vers $0$. Un peu comme le type qui veut mesurer la surface d'un segment.\n",
    "\n",
    "Mais si $3^d=4$, alors $\\mu_n=1$ et tend donc vers une limite ni nulle ni infinie. On a trouvé la bonne valeur, LE $d$ qui $K$ comme il faut, la bonne règle. Passons aux logaritmes, il vient $d\\ln 3 = \\ln 4$.\n",
    "\n",
    "Il se trouve que l'on peut vraiment définir mathématiquement la dimension d'un objet comme $K$. Il existe même beaucoup de définitions concurrentes (dimension de Hausdorff, dimension de boîte, etc.) et très différentes dans leur formulation. Mais pour l'ensemble $K$ elles donnent toutes la même valeur :\n",
    "\n",
    "__Théorème__ : $\\dim K =\\frac{\\ln 4}{\\ln 3}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On est entre 1 et 2. $K$ est plus gras qu'une courbe, mais plus maigre qu'une surface ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Annexe : le flocon de neige"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette annnexe n'est là que pour faire joli. Le \"flocon de neige\" est le recollement de 3 courbes de Von Koch d'extrémités $1, j, j^2$ où $j$ est la célèbre racine cubique de 1. Un dessin sera plus parlant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (8, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def flocon(n):\n",
    "    j = exp(2j * pi / 3)\n",
    "    j2 = exp(-2j * pi / 3)\n",
    "    v1 = vonkoch(n, 1, j2)\n",
    "    v2 = vonkoch(n, j2, j)\n",
    "    v3 = vonkoch(n, j, 1)\n",
    "    return v1 + v2 + v3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(flocon(6), [-1, 1, -1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On l'appelle le flocon de neige parce que ça ressemble à un flocon de neige. Au fait, on a pris $1, j^2,j$ dans cet ordre ... et si on se trompe ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def floconbis(n):\n",
    "    j = exp(2j * pi / 3)\n",
    "    j2 = exp(-2j * pi / 3)\n",
    "    v1 = vonkoch(n, 1, j)\n",
    "    v2 = vonkoch(n, j, j2)\n",
    "    v3 = vonkoch(n, j2, 1)\n",
    "    return v1 + v2 + v3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plotC(floconbis(6), [-1, 1, -1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est joli aussi, c'est un anti-flocon :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}