"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Titre de l'oral : « *Comment dessiner des droites sur un écran d'ordinateur ?* »\n",
"## Texte d'oral de modélisation, agrég maths option D \"Droite Discrète\" (public 2012 D5)\n",
"\n",
"> Voir : [cette page](https://agreg.org/index.php?id=option-d) et [ce texte (public2012-D5.pdf)](https://agreg.org/Textes/public2012-D5.pdf) :\n",
"> **2012-D5** À partir du problème de la représentation des droites sur un écran d’ordinateur, on étudie la notion de droite discrète, et le mot binaire périodique associé. On met en évidence la relation biunivoque entre droites discrètes et certains mots binaires, puis entre ces mots et les nombres rationnels de [0, 1]. Mots clefs : algorithmes, géométrie discrète, mots binaires, topologie.\n",
"\n",
"- Auteur : [Lilian Besson](https://github.com/Naereen/)\n",
"- Écrit en Python 3\n",
"- License : [MIT Licensed](https://lbesson.mit-license.org/)\n",
"- Date : 25/01/2021 (j'avais écrit [une solution en OCaml en 2014](https://github.com/Naereen/notebooks/tree/master/agreg/public2012_D5_OCaml.ipynb))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Introduction\n",
"\n",
"Donner un petit discours d'introduction :\n",
"\n",
"> On cherche à dessiner des courbes mathématiques sur un écran d'ordinateur. Pour simplifier l'exposé, on ne va considérer que des écrans quadrillés, où chaque case est un \"pixel\", et aussi on se restreint à des graphismes en noir et blanc. Ainsi, un écran est un tableau 2D, une matrice, de pixels, et chaque pixel est soit éteint, soit allumé.\n",
"> Si on cherche à tracer une courbe mathématique, par exemple une droite, un cercle ou d'autres courbes plus compliquée, sur un tel écran d'ordinateur, on va devoir décider quels pixels allumer ou garder éteint, le long du tracé de la courbe.\n",
"> [faire un dessin au tableau]\n",
"\n",
"> Pour commencer, on va uniquement s'intéresser au cas d'une droite, qui va du pixel O=(0,0) tout en bas à droite de l'écran, jusqu'à un autre point B=(b1,b2) de l'écran (à coordonnées entières, donc), situé à droite et en haut de l'origine O.\n",
"> On pose $\\alpha=b2/b1 \\in \\mathbb{R} \\cup \\{\\pm\\infty\\}$ la pente de cette droite.\n",
"\n",
"> Comme on le voit, si la courbe est un cas particulier très facile, il n'y a pas de difficultés particulières.\n",
"> Les cas faciles sont les courbes horizontales, de pente $1$ ou verticales, soit $\\alpha \\in \\{0,1,\\infty\\}$.\n",
"> Dans les autres cas, la pente est toujours rationnelle, mais en général elle ne sera pas entière.\n",
"> Nous allons d'abord étudier le cas particulier d'une pente $\\alpha < 1$, mais il est très facile de généraliser aux sept autres quadrants [faire un dessin], avec des rotations, et en échangeant le point de départ A et l'arrivée B.\n",
"\n",
"> Nous formalisons le problème, en faisant le lien entre les coordonnées réelles des points $M_i = (x_i,y_i)$ sur la droite [AB], qui sont $x_i = i$ et $y_i \\in \\mathbb{R}$ peut être réel et même irrationnels, et les points $(x_i, \\tilde{y_i})$ qui sont les coordonnées\n",
"> (par convention, le point de référence des pixels est le point en bas à gauche)\n",
"\n",
"> Nous présenterons et implémenterons trois différentes méthodes, qui ont toute la même complexité algorithmique, mais qui donnent des tracés différents dans le cas d'une droite quelconque.\n",
"\n",
"> \n",
"\n",
"**Plan** : voir table des matières pour le détail. [écrire au tableau]\n",
"\n",
"- I) *Introduction*\n",
"- II) Tracé de droites, formalisation\n",
"- III) Trois méthodes différentes : algorithmes, implémentations, exemples *[visualisation si le temps ?]*\n",
"- IV) Mathématiques des droites discrètes\n",
"- V) Mots binaires\n",
"- VI) Liens entre les (pentes) rationnels et les mots binaires *[si le temps ?]*\n",
"- VII) *Conclusion et ouvertures*"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Tracé de droites, formalisation\n",
"AU TABLEAU"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Formalisation, et hypothèses"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Présentation du problème\n",
"\n",
"TODO\n",
"\n",
"TL;DR : on cherche des algorithmes qui évitent de calculer des erreurs sur des nombres réels, parce qu'on sait que les flottants propagent des erreurs de calculs."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Généralisation au delà de ces hypothèses ?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Trois méthodes différentes : algorithmes, implémentations, exemples "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implémentation de l'exercice de programmation\n",
"\n",
"ATTENTION depuis 2019, l'*exercice de programmation obligatoire* qui était indiqué dans les anciens textes d'option D est devenu, comme pour les autres options A/B/C, une simple *suggestion*.\n",
"- Avant 2019, il fallait absolument implémenter l'exercice demandé, et éventuellement faire plus ;\n",
"- Maintenant, on fait ce qu'on veut. Le jury n'a pas encore diffusé de texte suivant la nouvelle consigne, donc je vous conseille l'approche suivante : pour les vieux textes, il faut juste remplacer *exercice de programmation obligatoire* par *suggestion de programmation*."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> Écrire un programme permettant de représenter le segment [AB], où A= (a1,a2) et B=(b1,b2), en suivant l’algorithme de Bresenham. On supposera que a1 La sortie du programme sera la liste des couples (xi,yi) des points représentant le segment."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Un bidouillage avec Python : un \"wrapper\" qui gère les symétries, pour ne pas avoir à les coder plusieurs fois\n",
"\n",
"On peut écrire un décorateur Python qui se charge de gérer toutes les symétries, afin de ne pas à avoir à copier-coller ça pour les méthodes suivantes."
]
},
{
"cell_type": "code",
"execution_count": 198,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:28.131968Z",
"start_time": "2021-01-24T22:37:28.109997Z"
},
"code_folding": [
0,
22,
30,
39,
56
]
},
"outputs": [],
"source": [
"def gerersymetrie(nom=\"\"):\n",
" def decorator(f):\n",
" def g(A, B):\n",
" a1, a2 = int(A[0]), int(A[1])\n",
" b1, b2 = int(B[0]), int(B[1])\n",
" # on commence à traiter les symétries\n",
"\n",
" if a1 == b1:\n",
" # il faut renvoyer une droite verticale, facile à faire\n",
" if b2 < a2:\n",
" print(f\"{nom} (avant symétries) avec une pente = -oo\")\n",
" return g(B, A)\n",
" # OK maintenant b2 >= a2\n",
" print(f\"{nom} (avant symétries) avec une pente = +oo\")\n",
" points = [\n",
" (a1, a2 + i) for i in range(b2 - a2 + 1)\n",
" # droite verticale, même x, y change\n",
" ]\n",
" return points\n",
"\n",
" pente = float(b2-a2) / float(b1-a1)\n",
"\n",
" if a1 > b1: # cas facile !\n",
" print(f\"{nom} (avant symétries) avec une pente = {pente}\")\n",
" return g(B, A)\n",
"\n",
" # OK maintenant a1 < b1\n",
" # vérification des hypothèses 1/2\n",
" assert a1 < b1, f\"Erreur : {nom} demande a1 = {a1} < a2 = {b1}.\"\n",
"\n",
" if pente > 1: # cas plus difficile, il faudra calculer une symétrie\n",
" # --> i) symétrie % axe horizontal\n",
" Bx = [B[1], B[0]]\n",
" print(f\"{nom} (avant symétries) avec une pente = {pente}\")\n",
" points = g(A, Bx)\n",
" # <-- i) symétrie % droite {(x,x)}\n",
" points = [ (y, x) for (x,y) in points ]\n",
" return points\n",
"\n",
" if a2 > b2: # cas plus difficile, il faudra calculer une symétrie\n",
" Ax = [0,0]\n",
" # --> i) translation =>\n",
" Bx = [b1 - a1, b2 - a2]\n",
" # --> --> ii) symétrie % axe horizontal\n",
" Bxx = [Bx[0], -Bx[1]]\n",
" print(f\"{nom} (avant symétries) avec une pente = {pente}\")\n",
" points = g(Ax, Bxx)\n",
" # <-- <-- ii) symétrie % axe horizontal\n",
" points = [ (x, -y) for (x,y) in points ]\n",
" # <-- i) translation <=\n",
" points = [ (x + a1, y + a2) for (x,y) in points ]\n",
" return points\n",
" \n",
" # cas de base, on propage\n",
" return f(A, B)\n",
"\n",
" if f.__doc__:\n",
" g.__doc__ = f.__doc__\n",
" g.__nom__ = nom\n",
" # maintenant on a un wrapper g(A,B) qui gère les symétries\n",
" return g\n",
" # et voilà on a un decorateur\n",
" return decorator"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Maintenant on peut écrire la méthode de Bresenham, en gérant uniquement le cas qui nous arrange :"
]
},
{
"cell_type": "code",
"execution_count": 199,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:29.348723Z",
"start_time": "2021-01-24T22:37:29.338102Z"
}
},
"outputs": [],
"source": [
"# cette ligne fait que la fonction finale va gérer les symétries !\n",
"@gerersymetrie(nom=\"Méthode de Bresenham\")\n",
"def methode_bresenham(A, B):\n",
" \"\"\" Méthode de Bresenham.\n",
" \n",
" - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)\n",
" N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical\n",
"\n",
" - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,\n",
" et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :\n",
" a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)\n",
" \"\"\"\n",
" a1, a2 = int(A[0]), int(A[1])\n",
" b1, b2 = int(B[0]), int(B[1])\n",
"\n",
" pente = float(b2-a2) / float(b1-a1)\n",
"\n",
" # vérification des hypothèses 2/2\n",
" assert 0 <= pente <= 1, f\"Erreur : la méthode de Bresenham demande 0 <= pente = {pente} <= 1.\"\n",
" print(f\"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1\")\n",
"\n",
" points = []\n",
" points.append(A) # premier point A\n",
"\n",
" nombre_point = b1 - a1 # c'est le n du texte\n",
" pente_normalise = b2 - a2 # le m du texte = b2-a2, c'est la pente normalisée alpha*n\n",
" xi = int(a1)\n",
" yi = int(a2)\n",
" ei = 0\n",
" \n",
" for i in range(1, nombre_point):\n",
" xi += 1\n",
"\n",
" # cette partie spécifique à Bresenham, et change selon les trois méthodes\n",
" if 2 * ( ei + pente_normalise ) <= nombre_point:\n",
" ei += pente_normalise\n",
" yi += 0 # inutile, juste pour le montrer\n",
" else:\n",
" ei += pente_normalise - nombre_point\n",
" yi += 1\n",
"\n",
" points.append((xi, yi))\n",
" \n",
" # et dernier point B\n",
" points.append(B)\n",
" return points"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples : deux premiers quadrants, deux premières demi-droites"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha=1$, tous les `yi += O/1` seront `yi += 1` :"
]
},
{
"cell_type": "code",
"execution_count": 200,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:29.598475Z",
"start_time": "2021-01-24T22:37:29.591847Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 4) # pente 1\n",
"print(methode_bresenham(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha=0$, tous les `yi += O/1` seront `yi += 0` :"
]
},
{
"cell_type": "code",
"execution_count": 201,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:29.889802Z",
"start_time": "2021-01-24T22:37:29.883263Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1\n",
"[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 0) # pente 0\n",
"print(methode_bresenham(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $0 < \\alpha < 1$, tous les `yi += O/1` suivent la méthode de Bresenham :"
]
},
{
"cell_type": "code",
"execution_count": 202,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:29.889802Z",
"start_time": "2021-01-24T22:37:29.883263Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 3) # pente 3/4\n",
"print(methode_bresenham(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $1 < \\alpha < +\\infty$, ce sont maintenant les `yi += 1` mais les `xi += O/1` qui suivent la méthode de Bresenham :"
]
},
{
"cell_type": "code",
"execution_count": 203,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:30.095535Z",
"start_time": "2021-01-24T22:37:30.087219Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (3, 4) # pente 4/3\n",
"print(methode_bresenham(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha = -\\infty$, ce sont maintenant les `yi += 1` et tous les `xi += O/1` sont des `+= 1` :"
]
},
{
"cell_type": "code",
"execution_count": 204,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:30.270888Z",
"start_time": "2021-01-24T22:37:30.263713Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = +oo\n",
"[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (0, 4) # pente +infini\n",
"print(methode_bresenham(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Autres exemples : six autre premiers quadrants, deux autres demi-droites\n",
"\n",
"On fera ces autres exemples quand on aura les deux autres méthodes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Deux autres méthodes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Une fois que l'on aura écrit la méthode de Bresenham, on peut rapidement implémenter deux autres approches qui consistent en longer au plus près inférieurement, supérieurement."
]
},
{
"cell_type": "code",
"execution_count": 206,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:30.766758Z",
"start_time": "2021-01-24T22:37:30.764023Z"
}
},
"outputs": [],
"source": [
"from math import floor, ceil"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Longer au plus près inférieurement"
]
},
{
"cell_type": "code",
"execution_count": 207,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:31.210056Z",
"start_time": "2021-01-24T22:37:31.200399Z"
}
},
"outputs": [],
"source": [
"@gerersymetrie(nom=\"Méthode de longer au plus près inférieurement\")\n",
"def methode_longer_inferieurement(A, B):\n",
" \"\"\" Méthode de longer au plus près inférieurement.\n",
" \n",
" - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)\n",
" N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical\n",
"\n",
" - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,\n",
" et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :\n",
" a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)\n",
" \"\"\"\n",
" a1, a2 = int(A[0]), int(A[1])\n",
" b1, b2 = int(B[0]), int(B[1])\n",
"\n",
" pente = float(b2-a2) / float(b1-a1)\n",
"\n",
" # vérification des hypothèses 2/2\n",
" assert 0 <= pente <= 1, f\"Erreur : la méthode de longer au plus près inférieurement demande 0 <= pente = {pente} <= 1.\"\n",
" print(f\"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1\")\n",
"\n",
" points = []\n",
" points.append(A) # premier point A\n",
"\n",
" nombre_point = b1 - a1 # c'est le n du texte\n",
" pente_normalise = b2 - a2 # le m du texte = b2-a2, c'est la pente normalisée alpha*n\n",
" xi = int(a1)\n",
" yi = int(a2)\n",
" ei = 0\n",
" \n",
" for i in range(1, nombre_point):\n",
" xi += 1\n",
" # cette partie est spécifique à cette méthode\n",
" yi = floor(a2 + pente*i)\n",
"\n",
" points.append((xi, yi))\n",
" \n",
" # et dernier point B\n",
" points.append(B)\n",
" return points"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Longer au plus près supérieurement"
]
},
{
"cell_type": "code",
"execution_count": 208,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:31.986722Z",
"start_time": "2021-01-24T22:37:31.979352Z"
},
"code_folding": [
1
]
},
"outputs": [],
"source": [
"@gerersymetrie(nom=\"Méthode de longer au plus près supérieurement\")\n",
"def methode_longer_superieurement(A, B):\n",
" \"\"\" Méthode de longer au plus près supérieurement.\n",
" \n",
" - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)\n",
" N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical\n",
"\n",
" - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,\n",
" et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :\n",
" a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)\n",
" \"\"\"\n",
" a1, a2 = int(A[0]), int(A[1])\n",
" b1, b2 = int(B[0]), int(B[1])\n",
"\n",
" pente = float(b2-a2) / float(b1-a1)\n",
"\n",
" # vérification des hypothèses 2/2\n",
" assert 0 <= pente <= 1, f\"Erreur : la méthode de longer au plus près supérieurement demande 0 <= pente = {pente} <= 1.\"\n",
" print(f\"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1\")\n",
"\n",
" points = []\n",
" points.append(A) # premier point A\n",
"\n",
" nombre_point = b1 - a1 # c'est le n du texte\n",
" pente_normalise = b2 - a2 # le m du texte = b2-a2, c'est la pente normalisée alpha*n\n",
" xi = int(a1)\n",
" yi = int(a2)\n",
" ei = 0\n",
" \n",
" for i in range(1, nombre_point):\n",
" xi += 1\n",
" # cette partie est spécifique à cette méthode\n",
" yi = ceil(a2 + pente*i)\n",
"\n",
" points.append((xi, yi))\n",
" \n",
" # et dernier point B\n",
" points.append(B)\n",
" return points"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Une dernière méthode ?\n",
"\n",
"On peut aussi longer la droite aléatoirement, en prenant inférieurement ou supérieurement uniformément au hasard.\n",
"Cela n'a pas d'intérêt particulier, mais c'est rapide à écrire alors autant le faire :"
]
},
{
"cell_type": "code",
"execution_count": 209,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:32.339027Z",
"start_time": "2021-01-24T22:37:32.333454Z"
}
},
"outputs": [],
"source": [
"import random"
]
},
{
"cell_type": "code",
"execution_count": 210,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:32.486088Z",
"start_time": "2021-01-24T22:37:32.478159Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"[0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0]"
]
},
"execution_count": 210,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[ random.randint(0, 1) for _ in range(20) ]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"On peut facilement remplacer le calcul de $\\tilde{y_i}$ par simplement un choix aléatoire uniforme entre le choix floor et le choix ceil :"
]
},
{
"cell_type": "code",
"execution_count": 347,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T23:20:52.877379Z",
"start_time": "2021-01-24T23:20:52.866203Z"
}
},
"outputs": [],
"source": [
"@gerersymetrie(nom=\"Méthode de longer aléatoirement\")\n",
"def methode_longer_aleatoirement(A, B):\n",
" \"\"\" Méthode de longer aléatoirement.\n",
" \n",
" - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)\n",
" N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical\n",
"\n",
" - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,\n",
" et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :\n",
" a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)\n",
" \"\"\"\n",
" a1, a2 = int(A[0]), int(A[1])\n",
" b1, b2 = int(B[0]), int(B[1])\n",
"\n",
" pente = float(b2-a2) / float(b1-a1)\n",
"\n",
" # vérification des hypothèses 2/2\n",
" assert 0 <= pente <= 1, f\"Erreur : la méthode de longer aléatoirement demande 0 <= pente = {pente} <= 1.\"\n",
" print(f\"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1\")\n",
"\n",
" points = []\n",
" points.append(A) # premier point A\n",
"\n",
" nombre_point = b1 - a1 # c'est le n du texte\n",
" pente_normalise = b2 - a2 # le m du texte = b2-a2, c'est la pente normalisée alpha*n\n",
" xi = int(a1)\n",
" yi = int(a2)\n",
" ei = 0\n",
" \n",
" for i in range(1, nombre_point):\n",
" xi += 1\n",
" # cette partie est spécifique à cette méthode\n",
" if random.randint(0, 1) == 0:\n",
" yi = floor(a2 + pente*i)\n",
" else:\n",
" yi = ceil(a2 + pente*i)\n",
" # écrire cela est aussi possible\n",
" # yi += random.randint(0, 1) # TODO\n",
"\n",
" points.append((xi, yi))\n",
" \n",
" # et dernier point B\n",
" points.append(B)\n",
" return points"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples : deux premiers quadrants, deux premières demi-droites"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha=1$, tous les `yi += O/1` seront `yi += 1` :"
]
},
{
"cell_type": "code",
"execution_count": 212,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:33.292404Z",
"start_time": "2021-01-24T22:37:33.284199Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 4) # pente 1\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha=0$, tous les `yi += O/1` seront `yi += 0` :"
]
},
{
"cell_type": "code",
"execution_count": 213,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:33.641823Z",
"start_time": "2021-01-24T22:37:33.633142Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1\n",
"[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1\n",
"[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1\n",
"[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 0) # pente 0\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $0 < \\alpha < 1$, tous les `yi += O/1` suivent la méthode choisie :"
]
},
{
"cell_type": "code",
"execution_count": 214,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:33.994500Z",
"start_time": "2021-01-24T22:37:33.985254Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 0), (2, 1), (3, 2), (4, 3)]\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 0), (2, 2), (3, 3), (4, 3)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, 3) # pente 3/4\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $1 < \\alpha < +\\infty$, ce sont maintenant les `yi += 1` mais les `xi += O/1` qui suivent la méthode choisie :"
]
},
{
"cell_type": "code",
"execution_count": 215,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:34.337779Z",
"start_time": "2021-01-24T22:37:34.327759Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (0, 1), (1, 2), (2, 3), (3, 4)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (3, 4) # pente 4/3\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Avec une pente $\\alpha = -\\infty$, ce sont maintenant les `yi += 1` et tous les `xi += O/1` sont des `+= 1` :"
]
},
{
"cell_type": "code",
"execution_count": 216,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:34.681052Z",
"start_time": "2021-01-24T22:37:34.672852Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = +oo\n",
"[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = +oo\n",
"[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = +oo\n",
"[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (0, 4) # pente +infini\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Autres exemples : six autre premiers quadrants, deux autres demi-droites\n",
"\n",
"On fera ces autres exemples quand on aura les deux autres méthodes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #3, b1 < a1 mais b2 > a2 et b2 >= b1 :"
]
},
{
"cell_type": "code",
"execution_count": 217,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:35.192068Z",
"start_time": "2021-01-24T22:37:35.182237Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-3, 4), (-2, 3), (-2, 2), (-1, 1), (0, 0)]\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-3, 4), (-3, 3), (-2, 2), (-1, 1), (0, 0)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-3, 4), (-2, 3), (-1, 2), (0, 1), (0, 0)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-3, 4), (-2, 3), (-2, 2), (-1, 1), (0, 0)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (-3, 4) # pente -4/3\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #4, b1 < a1 mais b2 > a2 et b2 < b1 :"
]
},
{
"cell_type": "code",
"execution_count": 218,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:35.701745Z",
"start_time": "2021-01-24T22:37:35.693358Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = -0.75\n",
"Méthode de Bresenham (avant symétries) avec une pente = -0.75\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, 3), (-3, 2), (-2, 2), (-1, 1), (0, 0)]\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, 3), (-3, 3), (-2, 2), (-1, 1), (0, 0)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, 3), (-3, 2), (-2, 1), (-1, 0), (0, 0)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, 3), (-3, 2), (-2, 2), (-1, 1), (0, 0)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (-4, 3) # pente -3/4\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #5 :"
]
},
{
"cell_type": "code",
"execution_count": 219,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:36.204290Z",
"start_time": "2021-01-24T22:37:36.197039Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = 0.75\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, -3), (-3, -2), (-2, -2), (-1, -1), (0, 0)]\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 0.75\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, -3), (-3, -3), (-2, -2), (-1, -1), (0, 0)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 0.75\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, -3), (-3, -2), (-2, -1), (-1, 0), (0, 0)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = 0.75\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(-4, -3), (-3, -2), (-2, -2), (-1, -1), (0, 0)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (-4, -3) # pente -3/-4\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #6 :"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:40.248836Z",
"start_time": "2021-01-24T22:37:36.685560Z"
}
},
"outputs": [],
"source": [
"A = (0, 0)\n",
"B = (-3, -4) # pente -4/-3\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**TODO fix this bug?**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #7 :"
]
},
{
"cell_type": "code",
"execution_count": 348,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T23:21:12.538573Z",
"start_time": "2021-01-24T23:21:12.529799Z"
},
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, -1), (1, -2), (2, -3), (3, -4)]\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (0, -1), (1, -2), (2, -3), (3, -4)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, -1), (2, -2), (3, -3), (3, -4)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (0, -1), (2, -2), (3, -3), (3, -4)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (3, -4) # pente 3/-4\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- Quadrant #8 :"
]
},
{
"cell_type": "code",
"execution_count": 349,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T23:21:14.780806Z",
"start_time": "2021-01-24T23:21:14.770766Z"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Méthode de Bresenham (avant symétries) avec une pente = -0.75\n",
"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, -1), (2, -1), (3, -2), (4, -3)]\n",
"Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 0), (2, -1), (3, -2), (4, -3)]\n",
"Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, -1), (2, -2), (3, -3), (4, -3)]\n",
"Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75\n",
"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1\n",
"[(0, 0), (1, 0), (2, -2), (3, -3), (4, -3)]\n"
]
}
],
"source": [
"A = (0, 0)\n",
"B = (4, -3) # pente 4/-3\n",
"print(methode_bresenham(A, B))\n",
"print(methode_longer_inferieurement(A, B))\n",
"print(methode_longer_superieurement(A, B))\n",
"print(methode_longer_aleatoirement(A, B))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## Visualisation ? *[si le temps]*\n",
"\n",
"Ca ne devrait pas être trop compliqué :\n",
"\n",
"- il faut pouvoir donner la pente, comme un rationnel ou un flottant,\n",
"- et les points [M0,...,MN] donné avec leurs coordonnées (en général, M0=A=O=(0,0) et MN=B=(b1,b2)),\n",
"- et afficher la courbe et les pixels allumés, comme des gros rectangles."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:37:40.257693Z",
"start_time": "2021-01-24T22:37:38.432Z"
}
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"\n",
"# https://matplotlib.org/3.2.1/api/_as_gen/matplotlib.patches.Rectangle.html?highlight=rectangle#matplotlib.patches.Rectangle\n",
"from matplotlib.patches import Rectangle"
]
},
{
"cell_type": "code",
"execution_count": 288,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:57:35.050035Z",
"start_time": "2021-01-24T22:57:35.030259Z"
},
"code_folding": [
22
]
},
"outputs": [],
"source": [
"def plot_discrete_line(points=None, # liste des coordonnées [M0,...,MN]\n",
" A=None, B=None,\n",
" methodes=[], # liste de fonctions à utiliser pour calculer les points, si absents\n",
" title=\"Dessin d'une droite discrète\",\n",
" width=50, height=None,\n",
" figsize=(10,7),\n",
" linewidth=2,\n",
" fill=True,\n",
" edgecolors=['r'],\n",
" facecolors=None,\n",
" alpha=0.4,\n",
" linecolor='k',\n",
" equal=True,\n",
" pente=None,\n",
" ):\n",
" fig = plt.figure(figsize=figsize)\n",
"\n",
" if equal: plt.axis('equal')\n",
" if not facecolors: facecolors = edgecolors\n",
" if not height: height = width\n",
" \n",
" use_fake_methode = False\n",
" if not methodes:\n",
" use_fake_methode = True\n",
" def fake_methode(A, B): return points\n",
" fake_methode.__nom__ = \"Fake method XXX\"\n",
" methodes = [fake_methode]\n",
"\n",
" for i, methode in enumerate(methodes):\n",
" points = methode(A, B)\n",
" \n",
" # points in P should be ordored, but not restricted to Mi = (xi, yi) with xi=i\n",
" min_x = min(p[0] for p in points)\n",
" max_x = max(p[0] for p in points)\n",
" plt.xlim((min_x - 0.2)*width, (max_x + 1 + 0.2)*width)\n",
" min_y = min(p[1] for p in points)\n",
" max_y = max(p[1] for p in points)\n",
" plt.ylim((min_y - 0.2)*height, (max_y + 1 + 0.2)*height)\n",
"\n",
" # plot the points as big rectangles\n",
" for p in points:\n",
" x, y = p\n",
" rect = Rectangle(\n",
" (x*width, y*height),\n",
" width, height,\n",
" linewidth=linewidth,\n",
" edgecolor=edgecolors[i], facecolor=facecolors[i],\n",
" alpha=alpha, fill=fill,\n",
" )\n",
" plt.gca().add_patch(rect)\n",
" \n",
" _xs = np.linspace(min_x, max_x, 2000)\n",
" _ys = np.linspace(min_y, max_y, 2000)\n",
"\n",
" # Trick to add a legend?\n",
" plt.plot(\n",
" _xs[:2]*width, _ys[:2]*width,\n",
" color=edgecolors[i], label=methode.__nom__\n",
" )\n",
" \n",
" # plot the line\n",
" plt.plot(_xs*width, _ys*width, color=linecolor, linewidth=1+linewidth)\n",
" \n",
"\n",
" if not use_fake_methode:\n",
" plt.legend()\n",
" if title:\n",
" if pente and \"pente\" not in title:\n",
" if not isinstance(pente, str):\n",
" pente = \"{:.3g}\".format(pente)\n",
" title += \" de pente = ${}$\".format(pente)\n",
" plt.title(title)\n",
"\n",
" fig.tight_layout()\n",
" plt.show()\n",
" # return fig"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exemples manuels :"
]
},
{
"cell_type": "code",
"execution_count": 279,
"metadata": {
"ExecuteTime": {
"end_time": "2021-01-24T22:54:48.962578Z",
"start_time": "2021-01-24T22:54:48.793803Z"
}
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAlYAAAGtCAYAAADUGDpYAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAAfpUlEQVR4nO3de7Ckd13n8c/XJAQXUGTBbEgyhkgWN7i1AzVgIm42S6JcBONtJSwLE3VrUEMJrq4EtFbcBRctLruUKzosDHhBoAQkUngJI9TIyi1ogCSIjBBMQkj0EDAjOCbxt3/0M5nO5Jwz5/J0P315vaq6Tp+nn+7+Ps/pnPOepy+p1loAANi+rxp6AACARSGsAAB6IqwAAHoirAAAeiKsAAB6IqwAAHoirAAAeiKsAAB6Iqxgwqrq2qq6oIfbeX1VvXj7E/Vru3P1tX/WuO27Z5vU/VTVfavqyqr6vr5ve5X7msnHAHCUsGKpVNX1VfWVqrq9qr5YVX9aVT9SVRP7b6G19sjW2nv7vt1uW87s+3anbXz/dNt00aTvp+fb/Yck351kT1XtHL9sktszK4baxqp6TlVdVVWHq+r1075/WMuJQw8AA3hqa+3dVfW1Sf5dkv+d5FuS/OCwYy2WqjqxtXbn0HNMyvj2tdb+PskTBh5p2XwuyYsz2u9fPfAscDdHrFharbUvtdauSPK0JLur6puTpKoeWlVvraq/qarPVNWPH7lOVT2/qm7qjnh9sqouXG95d9nd/6Lvzv9UVX2sqr5UVW+uqvuuNl9VPaqq/qy7zTcnWXW9bt1WVQ8f+/4eTxkd737X2+bNzNXdz/Or6mNJ/r6qTqyqf1VV7+2OEF5bVd91zO1dX1UXVdVvJNmR5Peq6lBV/fQEZrto7Pu1fpZnVNXbuvtbqapfPs72jc93fVX9RLfupLdnw7czNvsLquq6qrqtqvYdeQwc77bWevz0sY1b1Vp7W2vtd5Os9H3bsC2tNSenpTkluT7JRass/+skP5rRPzY+kuS/JblPkrOSfDqjfxU/IskNSR7aXefMJN+41vLV7rM7/6EkD03yoCSfSPIjq8xznySfTfITSU5K8v1J7kjy4jW2qyV5+Nj3rx9fd737XW+bNztXdz9XJzkjo6MIJyU5mOSF3XUfn+T2JI9YZ/9cNHZZ37MduZ+1fpYnJPloklcmuV9GIfNtx8w6vn1H5vv5JCcneXi3zndOcns2czvHzH5NN/uDkvy/jd5W1n/8bHkbu/XfmeSLa5zeuYH/pl+c5PVD/25xcjpycsQKRj6X0R+MxyR5SGvtv7fW/rG19ukkr0lySZK7MvrjeU5VndRau7619lfrLF/Lq1prn2utfSHJ7yXZuco652b0x/R/tdbuaK39TpIPb3Mb17rf9bZ5K3O9qrV2Q2vtK93690/y0u62/zijP6RP3+DMfc92xFo/s8dmFA//tbX29621f2itvW+d7XtMklOSvKi1dri1djDJ3iT/YcLbs5nbGffL3exfSPKSjH4OG72tjTxuNz1ba+0prbUHrnF6ynG2B2aO11jByGlJvpDkG5I8tKq+OHbZCUn+pLV2sKqel+RFSR5ZVX+Y5L+ss/xza9zX58fOfzmjP+THemiSm1prbWzZZze7URu83zW3eYtz3XDM+je01v7pmPVP2+DMfc+WJFnrZ5bR0ZzPtvVfGza+fd+Q7ghOVR1ZdnKSP5/w9mzmdtaa/bPdfWz0tjbyuN3ObLAQhBVLr6oek9Ef+vdldHTlM621s1dbt7X2xiRvrKqvSfJrSX4xyTPXWr6NsW5OclpV1dgf1h1J1joS9uUk/2zs+3+R5MYN3tcNWWebtzDXeAh8LskZVfVVY3G1I8lfrnH77Zjv+57t6B2t/jP7lSQ7av0X3o/PeEOSm1tr37SBdY+s38f2bOZ2xp0xdn5HRj+frd7WEdvZxlTV7yf5t2tc/CettSdtcS4YhKcCWVpV9TVV9ZQkb0rym621j2f0OpLbuxcof3VVnVBV31xVj6mqR1TV46vq5CT/kOQrSf5preXbHO/9Se5M8uNVdVJVfW9GT1Ot5eok/7Gb94kZvdtxo9bc5h7m+mBG0ffT3foXJHlqRvt8Nbdk9Jqcic62zs/sQxkFzUur6n7dC7Qft872fSjJl6rqhWvMN6nt2cztjLusqk6vqgcl+Zkkb97GbR2xnW1Ma+1JrbX7r3FaM6pq9MaB+2Z0NOyE7mflYAGDE1Yso9+rqtsz+pf1zyR5RbqPWmit3ZXkKRm9fuQzSf42yf9N8rUZPcXz0m7Z55N8fZIXrLN8y1pr/5jke5NcmtFTlE9L8rZ1rvLcjILli0mekeR3N3Ff623ztubq1n9qkid1t/srSZ7VWvuLNa7yP5P8bI3eQfhTE5xt1Z9Zd39PzehF6H+d0VG/p62zfUfm+9drzDeR7dnM7RzjjUn+KKMXk/9VRi/s3+ptHbHlbdymn80oiC9P8p+68z/b833AptU9n74HYBFV1fVJ/nNr7d1DzwKLzBErAICeCCsAgJ54KhAAoCeOWAEA9GQm3pr64Ac/uJ155plDjwEAcFwf+chH/ra19pDVLpuJsDrzzDNz1VVXDT0GAMBxVdWa/ycMTwUCAPREWAEA9ERYAQD0RFgBAPREWAEA9ERYAQD0RFgBAPREWAEA9ERYAQD0RFgBAPREWAEA9ERYAQD0RFgBAPREWAEA9ERYAQD0RFgBAPREWAEA9OS4YVVVZ1TVe6rquqq6tqqe2y1/UVXdVFVXd6cnj13nBVV1sKo+WVVPmOQGAADMihM3sM6dSX6ytfZnVfWAJB+pqiu7y17ZWnvZ+MpVdU6SS5I8MslDk7y7qv5la+2uPgcHAJg1xw2r1trNSW7uzt9eVZ9Icto6V7k4yZtaa4eTfKaqDiZ5bJL39zAvAPNq796hJ5g9e/YMPQE928gRq7tV1ZlJHpXkg0kel+Q5VfWsJFdldFTrtoyi6wNjV7sxq4RYVe1JsidJduzYsZXZAZg3Bw4MPcHsOP/8oSdgAjYcVlV1/yRvTfK81trfVdWrk/yPJK37+vIkP7TR22ut7U2yN0l27drVNjM0AHNMUAjMBbahdwVW1UkZRdVvtdbeliSttVtaa3e11v4pyWsyerovSW5KcsbY1U/vlgEALLSNvCuwkrw2ySdaa68YW37q2Grfk+Sa7vwVSS6pqpOr6mFJzk7yof5GBgCYTRt5KvBxSZ6Z5ONVdXW37IVJnl5VOzN6KvD6JM9OktbatVX1liTXZfSOwsu8IxAAWAYbeVfg+5LUKhe9a53rvCTJS7YxFwDA3PHJ6wAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9EVYAAD0RVgAAPRFWAAA9OW5YVdUZVfWeqrquqq6tqud2yx9UVVdW1ae6r1/XLa+qelVVHayqj1XVoye9EQDMvpVDh3Ljl7889BgwURs5YnVnkp9srZ2T5Nwkl1XVOUkuT7K/tXZ2kv3d90nypCRnd6c9SV7d+9QAzJWVlZVc+MpX5oIrr8wNX/jC0OPAxJx4vBVaazcnubk7f3tVfSLJaUkuTnJBt9obkrw3yfO75b/eWmtJPlBVD6yqU7vbAVgue/cOPcHgVg4dyoWvfGU+euONSZILf+EX8vHv/M6cfMIJA08G/TtuWI2rqjOTPCrJB5OcMhZLn09ySnf+tCQ3jF3txm7ZPcKqqvZkdEQrO3bs2OzcAPPjwIGhJxjMyuHDuXD//nz0ttuSJJXkZ77v+3LyeecNOxhMyIbDqqrun+StSZ7XWvu7qrr7stZaq6q2mTture1NsjdJdu3atanrAsyd888feoKpu/tI1VhU7bv00uzet2/YwWCCNvSuwKo6KaOo+q3W2tu6xbdU1and5acmubVbflOSM8aufnq3DIAlcezTf1WVfeedl92OVLHgNvKuwEry2iSfaK29YuyiK5Ls7s7vTvKOseXP6t4deG6SL3l9FcDyWDWqdu/O7rPOGngymLyNHLF6XJJnJnl8VV3dnZ6c5KVJvr2qPpXkou77JHlXkk8nOZjkNUl+rP+xAZhFa0aVI1UsiY28K/B9GT01vpoLV1m/Jblsm3MBMGdEFfjkdQB6IKpgRFgBsC2iCo4SVgBsmaiCexJWAGyJqIJ7E1YAbJqogtUJKwA2RVTB2oQVABsmqmB9wgqADRFVcHzCCoDjElWwMcIKgHWJKtg4YQXAmkQVbI6wAmBVogo2T1gBcC+iCrZGWAFwD6IKtk5YAXA3UQXbI6wASCKqoA/CCgBRBT0RVgBLTlRBf4QVwBITVdAvYQWwpEQV9E9YASwhUQWTIawAloyogskRVgBLRFTBZAkrgCUhqmDyhBXAEhBVMB3CCmDBiSqYHmEFsMBEFUyXsAJYUKIKpk9YASwgUQXDEFYAC0ZUwXCEFcACEVUwLGEFsCBEFQxPWAEsAFEFs0FYAcw5UQWzQ1gBzDFRBbNFWAHMKVEFs0dYAcwhUQWzSVgBzBlRBbNLWAHMEVEFs01YAcwJUQWzT1gBzAFRBfNBWAHMOFEF80NYAcwwUQXzRVgBzChRBfNHWAHMIFEF80lYAcwYUQXzS1gBzBBRBfNNWAHMCFEF809YAcwAUQWLQVgBDExUweIQVgADElWwWIQVwEBEFSweYQUwAFEFi0lYAUyZqILFJawApkhUwWITVgBTIqpg8QkrgCkQVbAchBXAhK0cPiyqYEkcN6yq6nVVdWtVXTO27EVVdVNVXd2dnjx22Quq6mBVfbKqnjCpwQHmwcqhQ7lw/35RBUtiI0esXp/kiassf2VrbWd3eleSVNU5SS5J8sjuOr9SVSf0NSzAPFlZWRkdqbrttiSiCpbBicdbobV2oKrO3ODtXZzkTa21w0k+U1UHkzw2yfu3PiIwd/buHXqCwd3rNVVJ9p17bnbfcUdy4MCwwwETc9ywWsdzqupZSa5K8pOttduSnJbkA2Pr3Ngtu5eq2pNkT5Ls2LFjG2MAM2mJ42Hl8OHR039HjlQl2XfppY5UwRLYali9Osn/SNK6ry9P8kObuYHW2t4ke5Nk165dbYtzALPs/POHnmDq7j5SdWxU7ds37GDAVGzpXYGttVtaa3e11v4pyWsyerovSW5KcsbYqqd3ywAW3qofqXDeeY5UwRLZUlhV1alj335PkiPvGLwiySVVdXJVPSzJ2Uk+tL0RAWbfmp9TddZZA08GTNNxnwqsqt9OckGSB1fVjUl+LskFVbUzo6cCr0/y7CRprV1bVW9Jcl2SO5Nc1lq7ayKTA8yIdT/8c4lfawbLaCPvCnz6Kotfu876L0nyku0MBTAvfKI6MM4nrwNskagCjiWsALZAVAGrEVYAmySqgLUIK4BNEFXAeoQVwAaJKuB4hBXABogqYCOEFcBxiCpgo4QVwDpEFbAZwgpgDaIK2CxhBbAKUQVshbACOIaoArZKWAGMEVXAdggrgI6oArZLWAFEVAH9EFbA0hNVQF+EFbDURBXQJ2EFLC1RBfRNWAFLSVQBkyCsgKUjqoBJEVbAUhFVwCQJK2BpiCpg0oQVsBREFTANwgpYeKIKmBZhBSw0UQVMk7ACFpaoAqZNWAELSVQBQxBWwMIRVcBQhBWwUEQVMCRhBSwMUQUMTVgBC0FUAbNAWAFzT1QBs0JYAXNNVAGzRFgBc0tUAbNGWAFzSVQBs0hYAXNHVAGzSlgBc0VUAbNMWAFzQ1QBs05YAXNBVAHzQFgBM09UAfNCWAEzTVQB80RYATNLVAHzRlgBM0lUAfNIWAEzR1QB80pYATNFVAHzTFgBM0NUAfNOWAEzQVQBi0BYAYMTVcCiEFbAoEQVsEiEFTAYUQUsGmEFDEJUAYtIWAFTJ6qARSWsgKkSVcAiE1bA1IgqYNEJK2AqRBWwDIQVMHGiClgWwgqYKFEFLBNhBUyMqAKWjbACJmLl8GFRBSyd44ZVVb2uqm6tqmvGlj2oqq6sqk91X7+uW15V9aqqOlhVH6uqR09yeGA2rRw6lAv37xdVwNLZyBGr1yd54jHLLk+yv7V2dpL93fdJ8qQkZ3enPUle3c+YwLxYWVkZHam67bYkogpYLiceb4XW2oGqOvOYxRcnuaA7/4Yk703y/G75r7fWWpIPVNUDq+rU1trNvU0Ms2jv3qEnmAn3ek1Vkn3nnpvdd9yRHDgw7HAAU3DcsFrDKWOx9Pkkp3TnT0tyw9h6N3bL7hVWVbUno6Na2bFjxxbHgBmy5OGwcvjw6Om/I0eqkuy79FJHqoClstWwultrrVVV28L19ibZmyS7du3a9PVhJp1//tATDOLuI1XHRtW+fcMOBjBlW31X4C1VdWqSdF9v7ZbflOSMsfVO75YBC2rVj1Q47zxHqoCltNWwuiLJ7u787iTvGFv+rO7dgecm+ZLXV8HiWvNzqs46a+DJAIaxkY9b+O0k70/yiKq6sap+OMlLk3x7VX0qyUXd90nyriSfTnIwyWuS/NhEpgYG58M/Ae5tI+8KfPoaF124yrotyWXbHQqYbaIKYHU+eR3YFFEFsDZhBWyYqAJYn7ACNkRUARyfsAKOS1QBbIywAtYlqgA2TlgBaxJVAJsjrIBViSqAzRNWwL2IKoCtEVbAPYgqgK0TVsDdRBXA9ggrIImoAuiDsAJEFUBPhBUsOVEF0B9hBUtMVAH0S1jBkhJVAP0TVrCERBXAZAgrWDKiCmByhBUsEVEFMFnCCpaEqAKYPGEFS0BUAUyHsIIFJ6oApkdYwQITVQDTJaxgQYkqgOkTVrCARBXAMIQVLBhRBTAcYQULRFQBDEtYwYIQVQDDE1awAEQVwGwQVjDnRBXA7BBWMMdEFcBsEVYwp0QVwOwRVjCHRBXAbBJWMGdEFcDsElYwR0QVwGwTVjAnRBXA7BNWMAdEFcB8EFYw40QVwPwQVjDDRBXAfBFWMKNEFcD8EVYwg0QVwHwSVjBjRBXA/BJWMENEFcB8E1YwI0QVwPwTVjADRBXAYhBWMDBRBbA4hBUMSFQBLBZhBQMRVQCLR1jBAEQVwGISVjBlogpgcQkrmCJRBbDYhBVMiagCWHzCCqZAVAEsB2EFEyaqAJaHsIIJElUAy0VYwYSIKoDlI6xgAkQVwHISVtAzUQWwvIQV9EhUASy3E7dz5aq6PsntSe5KcmdrbVdVPSjJm5OcmeT6JD/QWrtte2PC7Fs5fFhUASy5Po5Y/fvW2s7W2q7u+8uT7G+tnZ1kf/c9LLSVQ4dy4f79ogpgyW3riNUaLk5yQXf+DUnem+T5E7gfhrZ379ATzISVQ4dy4YtfnI/eNjowW0n2nXtudt9xR3LgwLDDATBV2w2rluSPqqol+bXW2t4kp7TWbu4u/3ySU1a7YlXtSbInSXbs2LHNMRjMkofDyuHDoyNVR6LKkSqApbbdsPq21tpNVfX1Sa6sqr8Yv7C11rroupcuwvYmya5du1Zdhzlx/vlDTzCIu1+oPh5V+/Zl9+7dA08GwFC29Rqr1tpN3ddbk7w9yWOT3FJVpyZJ9/XW7Q4Js+Ze7/5LRkeqRBXAUttyWFXV/arqAUfOJ/mOJNckuSLJkb8uu5O8Y7tDwixZ9SMVzjvP038AbOupwFOSvL2qjtzOG1trf1BVH07ylqr64SSfTfID2x8TZsOan1N1xx0DTwbALNhyWLXWPp3k36yyfCXJhdsZCmbRuh/+ueQv4gdgxCevwwb4RHUANkJYwXGIKgA2SljBOkQVAJshrGANogqAzRJWsApRBcBWCCs4hqgCYKuEFYwRVQBsh7CCjqgCYLuEFURUAdAPYcXSE1UA9EVYsdREFQB9ElYsLVEFQN+EFUtJVAEwCcKKpSOqAJgUYcVSEVUATJKwYmmIKgAmTVixFEQVANMgrFh4ogqAaRFWLDRRBcA0CSsWlqgCYNqEFQtJVAEwBGHFwhFVAAxFWLFQRBUAQxJWLAxRBcDQhBULQVQBMAuEFXNPVAEwK4QVc01UATBLhBVzS1QBMGuEFXNJVAEwi4QVc0dUATCrhBVzRVQBMMuEFXNDVAEw64QVc0FUATAPhBUzT1QBMC+EFTNNVAEwT4QVM0tUATBvhBUzSVQBMI+EFTNHVAEwr4QVM0VUATDPhBUzQ1QBMO+EFTNBVAGwCIQVgxNVACwKYcWgRBUAi0RYMRhRBcCiEVYMQlQBsIiEFVMnqgBYVMKKqRJVACwyYcXUiCoAFp2wYipEFQDLQFgxcaIKgGUhrJgoUQXAMhFWTIyoAmDZCCsmQlQBsIyEFb0TVQAsK2FFr0QVAMtMWNEbUQXAshNW9EJUAYCwogeiCgBGhBXbsnL4sKgCgM7EwqqqnlhVn6yqg1V1+aTuh+GsHDqUC/fvF1UA0JlIWFXVCUn+T5InJTknydOr6pxJ3BfDWFlZyXe9/OV56G23JRFVAJAkJ07odh+b5GBr7dNJUlVvSnJxkusmdH9M2dOe9rT8xOc+l6ckeXiSl5x7bnbfcUdy4MDQowHAYCYVVqcluWHs+xuTfMv4ClW1J8meJNmxY8eExmBSXvayl+XZ3/qt+c2vfCUvufRSR6oAIJMLq+Nqre1NsjdJdu3a1Yaag63ZuXNnfu1P/zTXXnttnvGMZww9DgDMhEmF1U1Jzhj7/vRuGQtk586d2blz59BjAMDMmNS7Aj+c5OyqelhV3SfJJUmumNB9AQDMhIkcsWqt3VlVz0nyh0lOSPK61tq1k7gvAIBZMbHXWLXW3pXkXZO6fQCAWeOT1wEAeiKsAAB6IqwAAHoirAAAeiKsAAB6IqwAAHoirAAAeiKsAAB6IqwAAHoirAAAeiKsAAB6IqwAAHoirAAAeiKsAAB6IqwAAHoirAAAelKttaFnSFX9TZLPDj3HJjw4yd8OPcSMsC+Osi/uyf44yr44yr44yr64p3naH9/QWnvIahfMRFjNm6q6qrW2a+g5ZoF9cZR9cU/2x1H2xVH2xVH2xT0tyv7wVCAAQE+EFQBAT4TV1uwdeoAZYl8cZV/ck/1xlH1xlH1xlH1xTwuxP7zGCgCgJ45YAQD0RFgBAPREWG1CVb2oqm6qqqu705PHLntBVR2sqk9W1ROGnHNaquqJ3fYerKrLh55n2qrq+qr6ePdYuKpb9qCqurKqPtV9/bqh55yEqnpdVd1aVdeMLVt122vkVd3j5GNV9ejhJu/fGvtiKX9XVNUZVfWeqrquqq6tqud2y5f1sbHW/li6x0dV3beqPlRVH+32xc93yx9WVR/stvnNVXWfbvnJ3fcHu8vPHHQDNqO15rTBU5IXJfmpVZafk+SjSU5O8rAkf5XkhKHnnfC+OKHbzrOS3Kfb/nOGnmvK++D6JA8+ZtkvJbm8O395kl8ces4Jbfv5SR6d5JrjbXuSJyf5/SSV5NwkHxx6/insi6X8XZHk1CSP7s4/IMlfdtu8rI+NtfbH0j0+up/x/bvzJyX5YPczf0uSS7rlv5rkR7vzP5bkV7vzlyR589DbsNGTI1b9uDjJm1prh1trn0lyMMljB55p0h6b5GBr7dOttX9M8qaM9sOyuzjJG7rzb0jy3cONMjmttQNJvnDM4rW2/eIkv95GPpDkgVV16lQGnYI19sVaFvp3RWvt5tban3Xnb0/yiSSnZXkfG2vtj7Us7OOj+xkf6r49qTu1JI9P8jvd8mMfG0ceM7+T5MKqqulMuz3CavOe0x2yft3Y0zynJblhbJ0bs/5/PItgGbf5WC3JH1XVR6pqT7fslNbazd35zyc5ZZjRBrHWti/rY2Wpf1d0T908KqMjE0v/2DhmfyRL+PioqhOq6uoktya5MqMjcl9srd3ZrTK+vXfvi+7yLyX551MdeIuE1TGq6t1Vdc0qp4uTvDrJNybZmeTmJC8fclYG922ttUcneVKSy6rq/PEL2+gY9lJ+nskyb3tnqX9XVNX9k7w1yfNaa383ftkyPjZW2R9L+fhord3VWtuZ5PSMjsR907ATTcaJQw8wa1prF21kvap6TZJ3dt/elOSMsYtP75YtsmXc5ntord3Ufb21qt6e0S+KW6rq1Nbazd1TGrcOOuR0rbXtS/dYaa3dcuT8sv2uqKqTMoqI32qtva1bvLSPjdX2xzI/PpKktfbFqnpPkvMyevr3xO6o1Pj2HtkXN1bViUm+NsnKIANvkiNWm3DMc//fk+TIu4CuSHJJ9y6GhyU5O8mHpj3flH04ydndOzruk9GLC68YeKapqar7VdUDjpxP8h0ZPR6uSLK7W213kncMM+Eg1tr2K5I8q3sH2LlJvjT2tNBCWtbfFd1rYF6b5BOttVeMXbSUj4219scyPj6q6iFV9cDu/Fcn+faMXnP2niTf36127GPjyGPm+5P8cXe0c+Y5YrU5v1RVOzM6jH19kmcnSWvt2qp6S5LrktyZ5LLW2l1DDTkNrbU7q+o5Sf4wo3cIvq61du3AY03TKUne3r2W8sQkb2yt/UFVfTjJW6rqh5N8NskPDDjjxFTVbye5IMmDq+rGJD+X5KVZfdvfldG7vw4m+XKSH5z6wBO0xr64YEl/VzwuyTOTfLx7LU2SvDBL+tjI2vvj6Uv4+Dg1yRuq6oSMDuq8pbX2zqq6LsmbqurFSf48oxBN9/U3qupgRm8OuWSIobfC/9IGAKAnngoEAOiJsAIA6ImwAgDoibACAOiJsAIA6ImwAgDoibACAOjJ/wf5TbwvYsMm1AAAAABJRU5ErkJggg==\n",
"text/plain": [
"