Table of Contents

Titre de l'oral : « Comment dessiner des droites sur un écran d'ordinateur ? »

Texte d'oral de modélisation, agrég maths option D "Droite Discrète" (public 2012 D5)

Voir : cette page et ce texte (public2012-D5.pdf) : 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.

Introduction

Donner un petit discours d'introduction :

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é. 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. [faire un dessin au tableau]

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. On pose $\alpha=b2/b1 \in \mathbb{R} \cup \{\pm\infty\}$ la pente de cette droite.

Comme on le voit, si la courbe est un cas particulier très facile, il n'y a pas de difficultés particulières. Les cas faciles sont les courbes horizontales, de pente $1$ ou verticales, soit $\alpha \in \{0,1,\infty\}$. Dans les autres cas, la pente est toujours rationnelle, mais en général elle ne sera pas entière. 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.

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 (par convention, le point de référence des pixels est le point en bas à gauche)

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.

Plan : voir table des matières pour le détail. [écrire au tableau]

Tracé de droites, formalisation

AU TABLEAU

Formalisation, et hypothèses

Présentation du problème

TODO

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.

Généralisation au delà de ces hypothèses ?

Trois méthodes différentes : algorithmes, implémentations, exemples

Implémentation de l'exercice de programmation

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.

É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<b1, a2≤b2 et que la pente $\alpha$ de la droite est inférieure à 1. La sortie du programme sera la liste des couples (xi,yi) des points représentant le segment.

Un bidouillage avec Python : un "wrapper" qui gère les symétries, pour ne pas avoir à les coder plusieurs fois

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.

Maintenant on peut écrire la méthode de Bresenham, en gérant uniquement le cas qui nous arrange :

Exemples : deux premiers quadrants, deux premières demi-droites

Autres exemples : six autre premiers quadrants, deux autres demi-droites

On fera ces autres exemples quand on aura les deux autres méthodes.

Deux autres méthodes

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.

Longer au plus près inférieurement

Longer au plus près supérieurement

Une dernière méthode ?

On peut aussi longer la droite aléatoirement, en prenant inférieurement ou supérieurement uniformément au hasard. Cela n'a pas d'intérêt particulier, mais c'est rapide à écrire alors autant le faire :

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 :

Exemples : deux premiers quadrants, deux premières demi-droites

Autres exemples : six autre premiers quadrants, deux autres demi-droites

On fera ces autres exemples quand on aura les deux autres méthodes.

TODO fix this bug?


Visualisation ? [si le temps]

Ca ne devrait pas être trop compliqué :

Exemples manuels :

On peut évidemment dessiner des droites avec une pente qui ne vérifie pas $0 < \alpha < 1$ :

Comparaison graphique des trois méthodes :

On va prendre les exemples précédents, et les afficher dans la même figure :

Meilleur visualisation avec quatre sous-figures ?

Pas le temps, mais il serait plus approprié de montrer les quatres méthodes m1/m2/m3/m4 comme ça : [ m1 | m2 ] [ m3 | m4 ]

Avec plt.subplots(2,2) ce ne serait pas trop difficile

Un exemple :