Algorithme de Bresenham
Tracé de segment sur grille de pixels
Enonce
Implémenter bresenham(x0, y0, x1, y1) qui retourne la liste de couples (x, y) des pixels traversés par le segment.
⚠ Contrainte : Aucune opération flottante, aucun /. Doit fonctionner pour toutes les directions (8 octants), y compris segments verticaux et pentes négatives.
Signature attendue
def bresenham(x0: int, y0: int, x1: int, y1: int) -> list:Exemples
bresenham(0, 0, 5, 0)→[(0,0),(1,0),(2,0),(3,0),(4,0),(5,0)]bresenham(0, 0, 4, 4)→[(0,0),(1,1),(2,2),(3,3),(4,4)]bresenham(0, 0, 6, 3)→[(0,0),(1,0),(2,1),(3,1),(4,2),(5,2),(6,3)]
📖 Rappel de cours
Tracer un segment entre $(x_0,y_0)$ et $(x_1,y_1)$ sur une grille de pixels nécessite de choisir, à chaque colonne, quel pixel allumer. La méthode naïve avec division flottante est lente et imprécise.
Idée de Bresenham (1965) :
Maintenir une erreur entière qui mesure l'écart entre le segment idéal et le pixel choisi. À chaque pas en $x$, on incrémente $y$ uniquement si l'erreur dépasse un seuil. Aucun flottant, aucune division.
Utilisé partout : rendu typographique, traçage CAO, rasterisation GPU.
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.