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 :

Bon c'était clairement trop long, inutile et impossible le jour même.

TODO si le temps:


Conclusion de l'oral

Donner une conclusion, scientifique et aussi personnelle, en 2-4 minutes.

Blabla TODO

Cela peut aussi s'appliquer en dehors des écrans, par exemple les mosaïques ou la broderie subissent les mêmes contraintes de dessins sur un support quadrillé et "pixelisé", et donc les méthodes mises au point sur le premier problème pourraient être aussi utilisées dans ces pratiques artistiques. On peut même imaginer qu'un artist mosaïste durant l'Antiquité Romaine suivant ce genre de méthodes de "longer au plus près inférieurement", sans même y réfléchir formellement.

[si le temps]

Une question en ouverture : et si on passe en 3D, est-ce beaucoup plus compliqué ? Mon intuition dit que oui ! Et il s'ajoute aussi la difficulté de savoir quel support est utilisé pour représenter un objet en 3D. L'analogie la plus simple sera de jouer avec des briques de Légo, qui pourraient se fixer dans les six directions (aux sommets du cube actuel). Même si ce serait intéressant de généraliser notre modélisation et les méthodes développées pour le tracé de courbes, du 2D à la 3D, je peine à voir ce qu'on pourrait généraliser pour la partie plus mathématiques liées au mots binaires.

Autres pistes :