Table of Contents

• 1  Titre de l'oral : « Comment dessiner des droites sur un écran d'ordinateur ? »
  • 1.1  Texte d'oral de modélisation, agrég maths option D "Droite Discrète" (public 2012 D5)
  • 1.2  Introduction
• 2  Tracé de droites, formalisation
  • 2.1  Formalisation, et hypothèses
  • 2.2  Présentation du problème
  • 2.3  Généralisation au delà de ces hypothèses ?
• 3  Trois méthodes différentes : algorithmes, implémentations, exemples
  • 3.1  Implémentation de l'exercice de programmation
    • 3.1.1  Un bidouillage avec Python : un "wrapper" qui gère les symétries, pour ne pas avoir à les coder plusieurs fois
    • 3.1.2  Exemples : deux premiers quadrants, deux premières demi-droites
    • 3.1.3  Autres exemples : six autre premiers quadrants, deux autres demi-droites
  • 3.2  Deux autres méthodes
    • 3.2.1  Longer au plus près inférieurement
    • 3.2.2  Longer au plus près supérieurement
    • 3.2.3  Une dernière méthode ?
    • 3.2.4  Exemples : deux premiers quadrants, deux premières demi-droites
    • 3.2.5  Autres exemples : six autre premiers quadrants, deux autres demi-droites
  • 3.3  Visualisation ? [si le temps]
    • 3.3.1  Exemples manuels :
    • 3.3.2  Comparaison graphique des trois méthodes :
    • 3.3.3  Meilleur visualisation avec quatre sous-figures ?
• 4  Conclusion de l'oral
  • 4.1  Autres pistes :

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.

• Auteur : Lilian Besson
• Écrit en Python 3
• License : MIT Licensed
• Date : 25/01/2021 (j'avais écrit une solution en OCaml en 2014)

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]

• I) Introduction
• II) Tracé de droites, formalisation
• III) Trois méthodes différentes : algorithmes, implémentations, exemples [visualisation si le temps ?]
• IV) Mathématiques des droites discrètes
• V) Mots binaires
• VI) Liens entre les (pentes) rationnels et les mots binaires [si le temps ?]
• VII) Conclusion et ouvertures

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.

• Avant 2019, il fallait absolument implémenter l'exercice demandé, et éventuellement faire plus ;
• 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.

É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.

def gerersymetrie(nom=""):
    def decorator(f):
        def g(A, B):
            a1, a2 = int(A[0]), int(A[1])
            b1, b2 = int(B[0]), int(B[1])
            # on commence à traiter les symétries

            if a1 == b1:
                # il faut renvoyer une droite verticale, facile à faire
                if b2 < a2:
                    print(f"{nom} (avant symétries) avec une pente = -oo")
                    return g(B, A)
                # OK maintenant b2 >= a2
                print(f"{nom} (avant symétries) avec une pente = +oo")
                points = [
                    (a1, a2 + i) for i in range(b2 - a2 + 1)
                    # droite verticale, même x, y change
                ]
                return points

            pente = float(b2-a2) / float(b1-a1)

            if a1 > b1:  # cas facile !
                print(f"{nom} (avant symétries) avec une pente = {pente}")
                return g(B, A)

            # OK maintenant a1 < b1
            # vérification des hypothèses 1/2
            assert a1 < b1, f"Erreur : {nom} demande a1 = {a1} < a2 = {b1}."

            if pente > 1:  # cas plus difficile, il faudra calculer une symétrie
                # --> i) symétrie % axe horizontal
                Bx = [B[1], B[0]]
                print(f"{nom} (avant symétries) avec une pente = {pente}")
                points = g(A, Bx)
                # <-- i) symétrie % droite {(x,x)}
                points = [ (y, x) for (x,y) in points ]
                return points

            if a2 > b2:  # cas plus difficile, il faudra calculer une symétrie
                Ax = [0,0]
                # --> i) translation =>
                Bx = [b1 - a1, b2 - a2]
                # --> --> ii) symétrie % axe horizontal
                Bxx = [Bx[0], -Bx[1]]
                print(f"{nom} (avant symétries) avec une pente = {pente}")
                points = g(Ax, Bxx)
                # <-- <-- ii) symétrie % axe horizontal
                points = [ (x, -y) for (x,y) in points ]
                # <-- i) translation <=
                points = [ (x + a1, y + a2) for (x,y) in points ]
                return points
            
            # cas de base, on propage
            return f(A, B)

        if f.__doc__:
            g.__doc__ = f.__doc__
        g.__nom__ = nom
        # maintenant on a un wrapper g(A,B) qui gère les symétries
        return g
    # et voilà on a un decorateur
    return decorator

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

# cette ligne fait que la fonction finale va gérer les symétries !
@gerersymetrie(nom="Méthode de Bresenham")
def methode_bresenham(A, B):
    """ Méthode de Bresenham.
    
    - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)
      N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical

    - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,
      et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :
      a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)
    """
    a1, a2 = int(A[0]), int(A[1])
    b1, b2 = int(B[0]), int(B[1])

    pente = float(b2-a2) / float(b1-a1)

    # vérification des hypothèses 2/2
    assert 0 <= pente <= 1, f"Erreur : la méthode de Bresenham demande 0 <= pente = {pente} <= 1."
    print(f"Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1")

    points = []
    points.append(A)    # premier point A

    nombre_point = b1 - a1  # c'est le n du texte
    pente_normalise = b2 - a2  # le m du texte = b2-a2, c'est la pente normalisée alpha*n
    xi = int(a1)
    yi = int(a2)
    ei = 0
    
    for i in range(1, nombre_point):
        xi += 1

        # cette partie spécifique à Bresenham, et change selon les trois méthodes
        if 2 * ( ei + pente_normalise ) <= nombre_point:
            ei += pente_normalise
            yi += 0  # inutile, juste pour le montrer
        else:
            ei += pente_normalise - nombre_point
            yi += 1

        points.append((xi, yi))
    
    # et dernier point B
    points.append(B)
    return points

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

• Avec une pente $\alpha=1$, tous les yi += O/1 seront yi += 1 :

A = (0, 0)
B = (4, 4)  # pente 1
print(methode_bresenham(A, B))

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]

• Avec une pente $\alpha=0$, tous les yi += O/1 seront yi += 0 :

A = (0, 0)
B = (4, 0)  # pente 0
print(methode_bresenham(A, B))

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]

• Avec une pente $0 < \alpha < 1$, tous les yi += O/1 suivent la méthode de Bresenham :

A = (0, 0)
B = (4, 3)  # pente 3/4
print(methode_bresenham(A, B))

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3)]

• Avec une pente $1 < \alpha < +\infty$, ce sont maintenant les yi += 1 mais les xi += O/1 qui suivent la méthode de Bresenham :

A = (0, 0)
B = (3, 4)  # pente 4/3
print(methode_bresenham(A, B))

Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 1), (1, 2), (2, 3), (3, 4)]

• Avec une pente $\alpha = -\infty$, ce sont maintenant les yi += 1 et tous les xi += O/1 sont des += 1 :

A = (0, 0)
B = (0, 4)  # pente +infini
print(methode_bresenham(A, B))

Méthode de Bresenham (avant symétries) avec une pente = +oo
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]

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.

from math import floor, ceil

Longer au plus près inférieurement

@gerersymetrie(nom="Méthode de longer au plus près inférieurement")
def methode_longer_inferieurement(A, B):
    """ Méthode de longer au plus près inférieurement.
    
    - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)
      N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical

    - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,
      et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :
      a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)
    """
    a1, a2 = int(A[0]), int(A[1])
    b1, b2 = int(B[0]), int(B[1])

    pente = float(b2-a2) / float(b1-a1)

    # vérification des hypothèses 2/2
    assert 0 <= pente <= 1, f"Erreur : la méthode de longer au plus près inférieurement demande 0 <= pente = {pente} <= 1."
    print(f"Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1")

    points = []
    points.append(A)    # premier point A

    nombre_point = b1 - a1  # c'est le n du texte
    pente_normalise = b2 - a2  # le m du texte = b2-a2, c'est la pente normalisée alpha*n
    xi = int(a1)
    yi = int(a2)
    ei = 0
    
    for i in range(1, nombre_point):
        xi += 1
        # cette partie est spécifique à cette méthode
        yi = floor(a2 + pente*i)

        points.append((xi, yi))
    
    # et dernier point B
    points.append(B)
    return points

Longer au plus près supérieurement

@gerersymetrie(nom="Méthode de longer au plus près supérieurement")
def methode_longer_superieurement(A, B):
    """ Méthode de longer au plus près supérieurement.
    
    - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)
      N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical

    - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,
      et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :
      a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)
    """
    a1, a2 = int(A[0]), int(A[1])
    b1, b2 = int(B[0]), int(B[1])

    pente = float(b2-a2) / float(b1-a1)

    # vérification des hypothèses 2/2
    assert 0 <= pente <= 1, f"Erreur : la méthode de longer au plus près supérieurement demande 0 <= pente = {pente} <= 1."
    print(f"Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1")

    points = []
    points.append(A)    # premier point A

    nombre_point = b1 - a1  # c'est le n du texte
    pente_normalise = b2 - a2  # le m du texte = b2-a2, c'est la pente normalisée alpha*n
    xi = int(a1)
    yi = int(a2)
    ei = 0
    
    for i in range(1, nombre_point):
        xi += 1
        # cette partie est spécifique à cette méthode
        yi = ceil(a2 + pente*i)

        points.append((xi, yi))
    
    # et dernier point B
    points.append(B)
    return points

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 :

import random

[ random.randint(0, 1) for _ in range(20) ]

[0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0]

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 :

@gerersymetrie(nom="Méthode de longer aléatoirement")
def methode_longer_aleatoirement(A, B):
    """ Méthode de longer aléatoirement.
    
    - Si N = |A B| longueur du segment, cette fonction tourne en temps O(N) et en mémoire O(N)
      N = max(n, m) avec m = |b2 - a2| et n = |b1 - a1| nb de déplacement sur l'axe horizontal/vertical

    - Fonctionne dans tous les cas, supporte les huit quadrants, les quatre demi-droites,
      et le cas spécial A==B, en exploitant les symétries et se ramener au cas de base :
      a1 < b1, b2 <= a2 (pente = (b2-a2)/(b1-a1) = alpha, 0 <= alpha <= 1)
    """
    a1, a2 = int(A[0]), int(A[1])
    b1, b2 = int(B[0]), int(B[1])

    pente = float(b2-a2) / float(b1-a1)

    # vérification des hypothèses 2/2
    assert 0 <= pente <= 1, f"Erreur : la méthode de longer aléatoirement demande 0 <= pente = {pente} <= 1."
    print(f"Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = {pente} <= 1")

    points = []
    points.append(A)    # premier point A

    nombre_point = b1 - a1  # c'est le n du texte
    pente_normalise = b2 - a2  # le m du texte = b2-a2, c'est la pente normalisée alpha*n
    xi = int(a1)
    yi = int(a2)
    ei = 0
    
    for i in range(1, nombre_point):
        xi += 1
        # cette partie est spécifique à cette méthode
        if random.randint(0, 1) == 0:
            yi = floor(a2 + pente*i)
        else:
            yi = ceil(a2 + pente*i)
        # écrire cela est aussi possible
        # yi += random.randint(0, 1)  # TODO

        points.append((xi, yi))
    
    # et dernier point B
    points.append(B)
    return points

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

• Avec une pente $\alpha=1$, tous les yi += O/1 seront yi += 1 :

A = (0, 0)
B = (4, 4)  # pente 1
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]

• Avec une pente $\alpha=0$, tous les yi += O/1 seront yi += 0 :

A = (0, 0)
B = (4, 0)  # pente 0
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]

• Avec une pente $0 < \alpha < 1$, tous les yi += O/1 suivent la méthode choisie :

A = (0, 0)
B = (4, 3)  # pente 3/4
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 0), (2, 1), (3, 2), (4, 3)]
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3)]
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 0), (2, 2), (3, 3), (4, 3)]

• Avec une pente $1 < \alpha < +\infty$, ce sont maintenant les yi += 1 mais les xi += O/1 qui suivent la méthode choisie :

A = (0, 0)
B = (3, 4)  # pente 4/3
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (0, 1), (1, 2), (2, 3), (3, 4)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]
Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 1), (2, 2), (3, 3), (3, 4)]

• Avec une pente $\alpha = -\infty$, ce sont maintenant les yi += 1 et tous les xi += O/1 sont des += 1 :

A = (0, 0)
B = (0, 4)  # pente +infini
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de longer au plus près inférieurement (avant symétries) avec une pente = +oo
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = +oo
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]
Méthode de longer aléatoirement (avant symétries) avec une pente = +oo
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]

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

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

• Quadrant #3, b1 < a1 mais b2 > a2 et b2 >= b1 :

A = (0, 0)
B = (-3, 4)  # pente -4/3
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333
Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333
Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-3, 4), (-2, 3), (-2, 2), (-1, 1), (0, 0)]
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-3, 4), (-3, 3), (-2, 2), (-1, 1), (0, 0)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-3, 4), (-2, 3), (-1, 2), (0, 1), (0, 0)]
Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-3, 4), (-2, 3), (-2, 2), (-1, 1), (0, 0)]

• Quadrant #4, b1 < a1 mais b2 > a2 et b2 < b1 :

A = (0, 0)
B = (-4, 3)  # pente -3/4
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de Bresenham (avant symétries) avec une pente = -0.75
Méthode de Bresenham (avant symétries) avec une pente = -0.75
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, 3), (-3, 2), (-2, 2), (-1, 1), (0, 0)]
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, 3), (-3, 3), (-2, 2), (-1, 1), (0, 0)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, 3), (-3, 2), (-2, 1), (-1, 0), (0, 0)]
Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75
Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, 3), (-3, 2), (-2, 2), (-1, 1), (0, 0)]

• Quadrant #5 :

A = (0, 0)
B = (-4, -3)  # pente -3/-4
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de Bresenham (avant symétries) avec une pente = 0.75
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, -3), (-3, -2), (-2, -2), (-1, -1), (0, 0)]
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 0.75
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, -3), (-3, -3), (-2, -2), (-1, -1), (0, 0)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 0.75
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, -3), (-3, -2), (-2, -1), (-1, 0), (0, 0)]
Méthode de longer aléatoirement (avant symétries) avec une pente = 0.75
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(-4, -3), (-3, -2), (-2, -2), (-1, -1), (0, 0)]

• Quadrant #6 :

A = (0, 0)
B = (-3, -4)  # pente -4/-3
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

TODO fix this bug?

• Quadrant #7 :

A = (0, 0)
B = (3, -4)  # pente 3/-4
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de Bresenham (avant symétries) avec une pente = -1.3333333333333333
Méthode de Bresenham (avant symétries) avec une pente = 1.3333333333333333
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, -1), (1, -2), (2, -3), (3, -4)]
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (0, -1), (1, -2), (2, -3), (3, -4)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, -1), (2, -2), (3, -3), (3, -4)]
Méthode de longer aléatoirement (avant symétries) avec une pente = -1.3333333333333333
Méthode de longer aléatoirement (avant symétries) avec une pente = 1.3333333333333333
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (0, -1), (2, -2), (3, -3), (3, -4)]

• Quadrant #8 :

A = (0, 0)
B = (4, -3)  # pente 4/-3
print(methode_bresenham(A, B))
print(methode_longer_inferieurement(A, B))
print(methode_longer_superieurement(A, B))
print(methode_longer_aleatoirement(A, B))

Méthode de Bresenham (avant symétries) avec une pente = -0.75
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, -1), (2, -1), (3, -2), (4, -3)]
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 0), (2, -1), (3, -2), (4, -3)]
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -0.75
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, -1), (2, -2), (3, -3), (4, -3)]
Méthode de longer aléatoirement (avant symétries) avec une pente = -0.75
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.75 <= 1
[(0, 0), (1, 0), (2, -2), (3, -3), (4, -3)]

---

Visualisation ? [si le temps]

Ca ne devrait pas être trop compliqué :

• il faut pouvoir donner la pente, comme un rationnel ou un flottant,
• et les points [M0,...,MN] donné avec leurs coordonnées (en général, M0=A=O=(0,0) et MN=B=(b1,b2)),
• et afficher la courbe et les pixels allumés, comme des gros rectangles.

import matplotlib.pyplot as plt

# https://matplotlib.org/3.2.1/api/_as_gen/matplotlib.patches.Rectangle.html?highlight=rectangle#matplotlib.patches.Rectangle
from matplotlib.patches import Rectangle

def plot_discrete_line(points=None,  # liste des coordonnées [M0,...,MN]
                       A=None, B=None,
                       methodes=[],  # liste de fonctions à utiliser pour calculer les points, si absents
                       title="Dessin d'une droite discrète",
                       width=50, height=None,
                       figsize=(10,7),
                       linewidth=2,
                       fill=True,
                       edgecolors=['r'],
                       facecolors=None,
                       alpha=0.4,
                       linecolor='k',
                       equal=True,
                       pente=None,
                      ):
    fig = plt.figure(figsize=figsize)

    if equal: plt.axis('equal')
    if not facecolors: facecolors = edgecolors
    if not height: height = width
        
    use_fake_methode = False
    if not methodes:
        use_fake_methode = True
        def fake_methode(A, B): return points
        fake_methode.__nom__ = "Fake method XXX"
        methodes = [fake_methode]

    for i, methode in enumerate(methodes):
        points = methode(A, B)
    
        # points in P should be ordored, but not restricted to Mi = (xi, yi) with xi=i
        min_x = min(p[0] for p in points)
        max_x = max(p[0] for p in points)
        plt.xlim((min_x - 0.2)*width, (max_x + 1 + 0.2)*width)
        min_y = min(p[1] for p in points)
        max_y = max(p[1] for p in points)
        plt.ylim((min_y - 0.2)*height, (max_y + 1 + 0.2)*height)

        # plot the points as big rectangles
        for p in points:
            x, y = p
            rect = Rectangle(
                (x*width, y*height),
                width, height,
                linewidth=linewidth,
                edgecolor=edgecolors[i], facecolor=facecolors[i],
                alpha=alpha, fill=fill,
            )
            plt.gca().add_patch(rect)
        
        _xs = np.linspace(min_x, max_x, 2000)
        _ys = np.linspace(min_y, max_y, 2000)

        # Trick to add a legend?
        plt.plot(
            _xs[:2]*width, _ys[:2]*width,
            color=edgecolors[i], label=methode.__nom__
        )
        
        # plot the line
        plt.plot(_xs*width, _ys*width, color=linecolor, linewidth=1+linewidth)
        

    if not use_fake_methode:
        plt.legend()
    if title:
        if pente and "pente" not in title:
            if not isinstance(pente, str):
                pente = "{:.3g}".format(pente)
            title += " de pente = ${}$".format(pente)
        plt.title(title)

    fig.tight_layout()
    plt.show()
    # return fig

Exemples manuels :

points = [ (0,0), (1,1), (2,2), (3,3), (4,4) ]

plot_discrete_line(points, pente=1.0)

points = [ (0,0), (1,0), (2,1), (3,1), (4,2), (5,2) ]

plot_discrete_line(points, pente=0.5)

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

points = [ (0,0), (0,1), (1,2), (1,3), (2,4), (2,5) ]

plot_discrete_line(points, pente=2)

Comparaison graphique des trois méthodes :

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

methodes = [
    methode_bresenham,
    methode_longer_inferieurement,
    methode_longer_superieurement,
    methode_longer_aleatoirement
]

• Avec une pente $\alpha=1$, tous les yi += O/1 seront yi += 1 :

A = (0, 0)
B = (20, 20)  # pente 1
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_discrete_line(A=A, B=B, pente=pente,
                   methodes=methodes,
                   edgecolors=['red', 'blue', 'orange', 'purple']
)

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 1.0 <= 1

• Avec une pente $\alpha=0$, tous les yi += O/1 seront yi += 0 :

A = (0, 0)
B = (20, 0)  # pente 0
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_discrete_line(A=A, B=B, pente=pente,
                   methodes=methodes,
                   edgecolors=['red', 'blue', 'orange', 'purple']
)

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.0 <= 1

• Avec une pente $0 < \alpha < 1$, tous les yi += O/1 suivent la méthode de Bresenham :

A = (0, 0)
B = (20, 7)  # pente 7/20
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_discrete_line(A=A, B=B, pente=pente,
                   methodes=methodes,
                   edgecolors=['red', 'blue', 'orange', 'purple']
)

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1

A = (0, 0)
B = (7, 20)  # pente 20/7
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_discrete_line(A=A, B=B, pente=pente,
                   methodes=methodes,
                   edgecolors=['red', 'blue', 'orange', 'purple']
)

Méthode de Bresenham (avant symétries) avec une pente = 2.857142857142857
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer aléatoirement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1

• Avec une pente $\alpha = +\infty$, ce sont maintenant les yi += 1 et tous les xi += O/1 sont des += 1 :

A = (0, 0)
B = (0, 7)  # pente +infini
print(methode_bresenham(A, B))
pente = '+oo'
plot_discrete_line(A=A, B=B, pente=pente,
                   methodes=methodes,
                   edgecolors=['red', 'blue', 'orange', 'purple']
)

Méthode de Bresenham (avant symétries) avec une pente = +oo
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7)]
Méthode de Bresenham (avant symétries) avec une pente = +oo
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = +oo
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = +oo
Méthode de longer aléatoirement (avant symétries) avec une pente = +oo

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

nos_4_methodes = [
    methode_bresenham,
    methode_longer_aleatoirement,
    methode_longer_inferieurement,
    methode_longer_superieurement,
]

def plot_4_differents_methods(A=None, B=None,
                       title="Dessin d'une droite discrète",
                       width=50, height=None,
                       figsize=(20,14),
                       linewidth=2,
                       fill=True,
                       methodes=nos_4_methodes,
                       edgecolors=['red', 'blue', 'orange', 'purple'],
                       facecolors=None,
                       alpha=0.4,
                       linecolor='k',
                       equal=True,
                       pente=None,
                      ):
    fig, axs = plt.subplots(2, 2, figsize=figsize)

    if not facecolors: facecolors = edgecolors
    if not height: height = width
        
    use_fake_methode = False
    if not methodes:
        use_fake_methode = True
        def fake_methode(A, B): return points
        fake_methode.__nom__ = "Fake method XXX"
        methodes = [fake_methode]

    i_x_axis = 0
    j_y_axis = 0
    for i, methode in enumerate(methodes):
        points = methode(A, B)
        ax = axs[i_x_axis, j_y_axis]
        if equal: ax.set_aspect('equal')
    
        # points in P should be ordored, but not restricted to Mi = (xi, yi) with xi=i
        min_x = min(p[0] for p in points)
        max_x = max(p[0] for p in points)
        # plt.xlim((min_x - 0.2)*width, (max_x + 1 + 0.2)*width)
        min_y = min(p[1] for p in points)
        max_y = max(p[1] for p in points)
        # plt.ylim((min_y - 0.2)*height, (max_y + 1 + 0.2)*height)
        
        _xs = np.linspace(min_x, max_x, 2000)
        _ys = np.linspace(min_y, max_y, 2000)

        # Trick to add a legend?
        ax.plot(
            _xs[:2]*width, _ys[:2]*width,
            color=edgecolors[i], label=methode.__nom__
        )
        
        # plot the line
        ax.plot(_xs*width, _ys*width, color=linecolor, linewidth=1+linewidth)

        # plot the points as big rectangles
        for p in points:
            x, y = p
            rect = Rectangle(
                (x*width, y*height),
                width, height,
                linewidth=linewidth,
                edgecolor=edgecolors[i], facecolor=facecolors[i],
                alpha=alpha, fill=fill,
            )
            ax.add_patch(rect)
        
        i_x_axis = (i_x_axis + 1) % 2
        if i_x_axis == 1:
            j_y_axis = (j_y_axis + 1) % 2

        if not use_fake_methode:
            ax.legend()
        if not title:
            title = methode.nom
        if title:
            if pente and "pente" not in title:
                if not isinstance(pente, str):
                    pente = "{:.5g}".format(pente)
                title += " de pente = ${}$".format(pente)
            ax.set_title(title)

    plt.show()
    # return fig

Un exemple :

A = (0, 0)
B = (20, 7)  # pente 7/20
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_4_differents_methods(A=A, B=B, pente=pente)

Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1

A = (0, 0)
B = (7, 20)  # pente 20/7
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_4_differents_methods(A=A, B=B, pente=pente)

Méthode de Bresenham (avant symétries) avec une pente = 2.857142857142857
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer aléatoirement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1

A = (0, 0)
B = (-7, 20)  # pente 20/-7
pente = (B[1] - A[1]) / (B[0] - A[0])
plot_4_differents_methods(A=A, B=B, pente=pente)

Méthode de Bresenham (avant symétries) avec une pente = -2.857142857142857
Méthode de Bresenham (avant symétries) avec une pente = -2.857142857142857
Méthode de Bresenham (avant symétries) avec une pente = 2.857142857142857
Méthode de Bresenham (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer aléatoirement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer aléatoirement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer aléatoirement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer aléatoirement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer au plus près inférieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près inférieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = -2.857142857142857
Méthode de longer au plus près supérieurement (avant symétries) avec une pente = 2.857142857142857
Méthode de longer au plus près supérieurement (après symétries éventuelles) avec une pente 0 <= pente = 0.35 <= 1

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

TODO si le temps:

• corriger dessin de la courbe noire en cas de symétries

---

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 :

• DONE généraliser à tous les cas d'une droite : verticale, horizontale, et les sept autre quadrants (ici, seulement $0 < \alpha < 1$ et $a_2 \leq b_2$) ;

• DONE écrire une fonction permettant de visualiser cette méthode de Bresenham, et les autres méthodes, par exemple avec ipythonblocks (pratique mais pas possible le jour J des oraux), ou avec matplotlib (ce sera un peu plus long, mais disponible le jour J) ;

• TODO généraliser l'algorithme à un cercle, par exemple, ou d'autres figures dont on connaît des équations et qu'on peut chercher à vouloir longer au plus près inférieurement, supérieurement, ou de façon hybride à la Bresenham ;

• TODO pour s'éloigner davantage du problème de tracés de droite, on peut implémenter des choses concernant les mots binaires (ultimement) périodiques (abbrégés en mbup) :

  • représentation d'un mbup, affichage ;
  • vérification qu'un mot binaire est bien équilibré : est-ce seulement possible, sachant que Déf.5 porte sur un mot infini ?
  • transformation d'un mbup en une droite discrète (§6) $\sigma \mapsto (M_0,\dots,M_n)$ ;
  • mot binaire up associé à un rationnel, et inversement : est-ce facile d'écrire deux fonctions qui effectuent ces transformations, par exemple $\frac{2}{3} \leftrightarrow (011)^\omega$ ?