Voir la source de Algorithme de tracé de segment de Bresenham

{{Sources|date=janvier 2015}}
[[image:Bresenham_line.png|right|300px|Illustration de l'algorithme de Bresenham]]
L’'''algorithme de tracé de segment de Bresenham''' est un [[Algorithmique|algorithme]] développé par [[Jack E. Bresenham]] en {{date-|mai 1962}}, alors qu’il travaillait dans un laboratoire informatique d’[[International Business Machines Corporation|IBM]] et cherchait à piloter un traceur attaché à une console texte. Cet algorithme a été présenté à la convention de l’[[Association for Computing Machinery|ACM]] en [[1963]], puis publié en 1965 dans la revue ''IBM Systems Journal''.

L’algorithme détermine quels sont les points d’un plan discret qui doivent être tracés afin de former une approximation de [[Segment (mathématiques)|segment de droite]] entre deux points donnés. Cet algorithme est souvent utilisé pour dessiner des segments de droites sur l’écran d’un ordinateur ou une image calculée pour l’impression. Il est considéré comme l’un des premiers algorithmes découverts dans le domaine de la [[synthèse d'image]] <ref>{{Ouvrage|langue=fr|auteur1=James D. Foley|titre=Introduction à l'infographie|lieu=Paris|éditeur=Addison-Wesley France|année=|date=mai 1995|pages totales=573|isbn=978-2-87908-058-1|isbn10=2-87908-058-4|bnf=37480856|passage=p.76 à 84}}</ref>.

== Utilisations ==
Le principe du calcul est largement documenté et a depuis été repris pour tracer de façon incrémentale n’importe quelle courbe [[conique]] ([[cercle]], [[Ellipse (mathématiques)|ellipse]], [[arc de cercle|arc]], [[parabole]], [[Hyperbole (mathématiques)|hyperbole]]) ou [[courbe de Bézier|courbes de Bézier]] grâce aux propriétés de leur [[fonction polynomiale]] de définition, dont les [[dérivée]]s permettent de calculer les orientations de segments élémentaires avec de simples opérations entières. On peut même l’adapter à l’approximation de courbes dont on ne connaît qu’un [[développement limité]] (dont on ne prendra que les premiers termes de faible degré), utilisable avec une bonne précision sur un domaine suffisant par rapport à la résolution ([[sinusoïde]]s, [[Fonction exponentielle|exponentielle]]s, [[Puissance (mathématiques élémentaires)|puissances]] non entières).

L’algorithme est également facilement adaptable au calcul de courbes et surfaces dans un espace discret de plus de 2 dimensions (notamment pour le pilotage de machines-outils). Même en deux dimensions seulement, on peut discrétiser avec cet algorithme une courbe avec une fonction de lissage prenant en compte l’erreur commise entre deux points candidats afin d’ajuster leur couleur, l’erreur incrémentale étant convertible en coefficient de transparence, ce qui permet de conserver la graisse (épaisseur visuelle) d’une courbe tout en limitant l’effet d’escalier ([[crénelage]]).

Cet algorithme intervient aussi dans le lissage de rendus de [[Texture (image de synthèse)|textures]] 2D appliquées sur des surfaces d’une scène 3D où la texture subit des réductions ou agrandissements. On l’emploie aussi pour le lissage d’agrandissements photographiques, ou pour l’interpolation de couleurs intermédiaires sur une échelle discrète.{{Clr}}

== Explication de l’algorithme de base dans le premier octant ==
[[Image:Bresenham.svg|right|300px|thumb|Illustration du résultat de l’algorithme de tracé de segment de Bresenham.]]
La ligne est tracée entre deux points (''x''<sub>1</sub>, ''y''<sub>1</sub>) et (''x''<sub>2</sub>, ''y''<sub>2</sub>), où chaque paire indique la colonne et la rangée, respectivement, croissant vers la droite et le bas. On supposera au départ que notre segment descend vers le bas et la droite, et que la distance horizontale ''x''<sub>2</sub>–''x''<sub>1</sub> excède la distance verticale ''y''<sub>2</sub>–''y''<sub>1</sub> (c’est-à-dire que le segment a une pente comprise entre 0 et -1). Notre but est, pour chaque colonne ''x'' entre ''x''<sub>1</sub> et ''x''<sub>2</sub>, d’identifier la rangée ''y'' dans cette colonne qui est la plus proche du segment idéal et de tracer un [[pixel]] en (''x'', ''y'').

=== Détermination des ordonnées ===
Il s'agit maintenant de déterminer quel pixel est le plus proche de la droite pour une colonne donnée. La formule générale d’une droite entre les deux points est donnée par :

: <math>y - y_1 = \frac{y_2 - y_1}{x_2 -x_1} \cdot \left(x - x_1\right)</math>. &nbsp; (1)

Puisque la colonne <math>\dot{x}</math> est connue, la rangée <math>\dot{y}</math> du pixel le plus proche de l’ordonnée exacte du point d’abscisse <math>x = \dot{x}</math> sur la droite est donnée en arrondissant cette ordonnée {{mvar|y}} à l’entier le plus proche :

: <math>\dot{y} = \left\lfloor \frac{y_2 - y_1}{x_2 - x_1} \cdot \left(\dot{x} - x_1\right) + y_1 + 0,5 \right\rfloor</math>. &nbsp; (2)

La valeur 0,5 dans le membre de droite est une approximation des coordonnées (le point est au milieu du carré).

Cependant, le calcul explicite de cette valeur pour chaque colonne <math>\dot{x}</math> est coûteux. Or <math>\left(\dot{x}, \dot{y}\right)</math> commence en <math>(x_1, y_1)\ </math>, et que chaque fois qu'on ajoute 1 à l'abscisse, on ajoute la valeur constante <math>e_{(1,0)} = \frac{y_2 - y_1}{x_2 - x_1}</math> à la valeur de l’ordonnée {{mvar|y}} du point de la droite correspondant. Cette valeur est la pente de la droite, et en vertu de notre hypothèse initiale, elle est comprise entre 0 et -1. Après l’arrondi, pour chaque colonne <math>\dot{x}</math>, on utilise donc soit la valeur <math>\dot{y}</math> précédente (ordonnée du pixel d'abscisse <math>\dot{x}-1</math>), soit cette valeur augmentée de 1.

On peut décider laquelle de ces deux valeurs prendre en conservant une ''valeur d’erreur'' qui représente la distance verticale entre la valeur <math>\dot{y}</math> courante et la valeur {{mvar|y}} exacte pour la droite à l’abscisse <math>x = \dot{x}</math> courante. Au départ cette valeur d’erreur ''e'' est nulle et chaque fois qu'on incrémente <math>\dot{x}</math>, on augmente la valeur d’erreur par la valeur de pente ci-dessus. Chaque fois que l’erreur dépasse 0,5, la droite est devenue plus proche de la valeur <math>\dot{y}</math> suivante, aussi on ajoute 1 à <math>\dot{y}</math> en retranchant simultanément 1,0 à l’erreur ''e''.

La procédure ressemble à ceci, en supposant que <code>tracerPixel(''x'', ''y'')</code> est une primitive graphique traçant le pixel de rangée ''x'' et de colonne {{mvar|y}} ; exprimé en [[pseudo-code]], l’algorithme de base est :
 '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''x'', ''y'', ''dx'', ''dy'' ;
   '''déclarer''' '''rationnel''' ''e'', ''e''<sub>(1,0)</sub>, ''e''<sub>(0,1)</sub> ;  ''// valeur d’erreur et incréments''
   ''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub> ;
   ''dx'' ← ''x''<sub>2</sub> - ''x''<sub>1</sub> ;
   ''y'' ← ''y''<sub>1</sub> ;  ''// rangée initiale''
   ''e'' ← 0,0 ;  ''// valeur d’erreur initiale''
   ''e''<sub>(1,0)</sub> ← ''dy'' / ''dx'' ;
   ''e''<sub>(0,1)</sub> ← -1.0 ;
   '''pour''' ''x'' '''variant de''' ''x''<sub>1</sub> '''jusqu’à''' ''x''<sub>2</sub> '''par incrément de''' 1 '''faire'''
     tracerPixel(''x'', ''y'') ;
     '''si''' (''e'' ←  ''e'' + ''e''<sub>(1,0)</sub>) ≥ 0,5 '''alors'''  ''// erreur pour le pixel suivant de même rangée''
       ''y'' ←  ''y'' + 1 ;  ''// choisir plutôt le pixel suivant dans la rangée supérieure''
       ''e'' ←  ''e'' + ''e''<sub>(0,1)</sub> ;  ''// ajuste l’erreur commise dans cette nouvelle rangée''
     '''fin si''' ;
   '''fin pour''' ;
 '''fin procédure''' ;

=== Amélioration de l’algorithme pour le calcul avec des entiers ===
Le problème avec cet algorithme simple est que les microprocesseurs d’ordinateur sont relativement lents dans le calcul sur des nombres en [[virgule flottante]] (et la représentation suggérée ci-dessus sous forme de nombres rationnels pour ''e'' et ''e''<sub>(1,0)</sub> est nettement plus complexe et non nativement prise en charge par les processeurs ce qui augmente le nombre d’instructions pour travailler sur de tels nombres) ; de plus, les erreurs d’approximation du nombre flottant ''e''<sub>(1,0)</sub> s’accumulent à chaque addition de ''e''<sub>(1,0)</sub> dans ''e''. Travailler avec uniquement des entiers permettrait un calcul à la fois plus exact et plus rapide.

La première astuce est de remarquer d’abord qu’on peut remplacer ''e'' par ''e''–0,5, ce qui permet de ne tester que le signe de la valeur d’erreur au lieu de comparer deux rationnels, le test de proximité par rapport à la droite exacte revient alors à savoir lequel des deux pixels candidats se situe en dessous de la droite exacte parallèle dont les ordonnées sont augmentées de 0,5, et de remplacer l’arrondi de la formule (1) ci-dessus à l’entier le plus proche par un arrondi à l’entier égal ou inférieur avec cette nouvelle droite, ce qui ne change effectivement pas la formule (2) ci-dessus, mais ''e'' représentera l’erreur commise lors de l'approximation de cette seconde droite par les pixels tracés :
 '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''x'', ''y'', ''dx'', ''dy'' ;
   '''déclarer''' '''rationnel''' ''e'', ''e''<sub>(1,0)</sub>, ''e''<sub>(0,1)</sub> ;  ''// valeur d’erreur et incréments''
   ''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub> ;
   ''dx'' ← ''x''<sub>2</sub> - ''x''<sub>1</sub> ;
   ''y'' ← ''y''<sub>1</sub> ;  ''// rangée initiale''
   ''e'' ← -0,5 ;  ''// valeur d’erreur initiale''
   ''e''<sub>(1,0)</sub> ← ''dy'' / ''dx'' ;
   ''e''<sub>(0,1)</sub> ← -1.0 ;
   '''pour''' ''x'' '''variant de''' ''x''<sub>1</sub> '''jusqu’à''' ''x''<sub>2</sub> '''par incrément de''' 1 '''faire'''
     tracerPixel(''x'', ''y'') ;
     '''si''' (''e'' ← ''e'' + ''e''<sub>(1,0)</sub>) ≥ 0 '''alors'''  ''// erreur pour le pixel suivant de même rangée''
       ''y'' ← ''y'' + 1 ;  ''// choisir plutôt le pixel suivant dans la rangée supérieure''
       ''e'' ← ''e'' + ''e''<sub>(0,1)</sub> ;  ''// ajuste l’erreur commise dans cette nouvelle rangée''
     '''fin si''' ;
   '''fin pour''' ;
 '''fin procédure''' ;

Ensuite en multipliant tous les rationnels ci-dessus par ''dx'', le calcul ne demande plus d’incréments rationnels (ce qui élimine l'accumulation d'erreurs d’approximation des flottants). Cependant la valeur initiale de ''e''= –0,5×''dx'' n’est pas encore entière, même si ses incréments sont entiers.
 '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''x'', ''y'', ''dx'', ''dy'' ;
   '''déclarer''' '''rationnel''' ''e'' ; ''// valeur d’erreur''
   '''déclarer''' '''entier''' ''e''<sub>(1,0)</sub>, ''e''<sub>(0,1)</sub> ;  ''// incréments''
   ''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub> ;
   ''dx'' ← ''x''<sub>2</sub> - ''x''<sub>1</sub> ;
   ''y'' ← ''y''<sub>1</sub> ;  ''// rangée initiale''
   ''e'' ← -0,5 × ''dx'' ;  ''// valeur d’erreur initiale''
   ''e''<sub>(1,0)</sub> ←  ''dy'' ;
   ''e''<sub>(0,1)</sub> ← -''dx'' ;
   '''pour''' ''x'' '''variant de''' ''x''<sub>1</sub> '''jusqu’à''' ''x''<sub>2</sub> '''par incrément de''' 1 '''faire'''
     tracerPixel(''x'', ''y'') ;
     '''si''' (''e'' ← ''e'' + ''e''<sub>(1,0)</sub>) ≥ 0 '''alors'''  ''// erreur pour le pixel suivant de même rangée''
       ''y'' ← ''y'' + 1 ;  ''// choisir plutôt le pixel suivant dans la rangée supérieure''
       ''e'' ← ''e'' + ''e''<sub>(0,1)</sub> ;  ''// ajuste l’erreur commise dans cette nouvelle rangée''
     '''fin si''' ;
   '''fin pour''' ;
 '''fin procédure''' ;

Toutefois en doublant ''e'' (et les valeurs de ses incréments), cela ne change rien au test de son signe : ''e'' représentera alors la distance par rapport à la droite exacte d’ordonnées augmentées de 0,5, cette distance étant multipliée par le facteur constant positif 2×''dy'' (ce qui ne change pas le signe de la valeur d’erreur testée). La valeur de pente utilisée comme incrément de ''e'' étant aussi multipliée par le même facteur devient simplement 2×''dy'', sa valeur initiale devient –''dx'', le second décrément conditionnel devient 2×''dx'' (que l’on peut aussi précalculer). L’algorithme devient alors :
 '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''x'', ''y'', ''dx'', ''dy'' ;
   '''déclarer''' '''entier''' ''e'' ; ''// valeur d’erreur''
   '''déclarer''' '''entier''' ''e''<sub>(1,0)</sub>, ''e''<sub>(0,1)</sub> ;  ''// incréments''
   ''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub> ;
   ''dx'' ← ''x''<sub>2</sub> - ''x''<sub>1</sub> ;
   ''y'' ← ''y''<sub>1</sub> ;  ''// rangée initiale''
   ''e'' ← -''dx'' ;  ''// valeur d’erreur initiale''
   ''e''<sub>(1,0)</sub> ←  ''dy'' × 2 ;
   ''e''<sub>(0,1)</sub> ← -''dx'' × 2;
   '''pour''' ''x'' '''variant de''' ''x''<sub>1</sub> '''jusqu’à''' ''x''<sub>2</sub> '''par incrément  de''' 1 '''faire'''
     tracerPixel(''x'', ''y'') ;
     '''si''' (''e'' ← ''e'' + ''e''<sub>(1,0)</sub>) ≥ 0 '''alors'''  ''// erreur pour le pixel suivant de même rangée''
       ''y'' ← ''y'' + 1 ;  ''// choisir plutôt le pixel suivant dans la rangée supérieure''
       ''e'' ← ''e'' + ''e''<sub>(0,1)</sub> ;  ''// ajuste l’erreur commise dans cette nouvelle rangée''
     '''fin si''' ;
   '''fin pour''' ;
 '''fin procédure''' ;

[[Fichier:Tracé de segment avec l'algorithme de Bresenham.gif|alt=Tracé de segment avec l'algorithme de Bresenham (exemple animé, avec de plus en plus de carrés)|centré|vignette|346x346px|Un exemple de tracé de segments avec l'algorithme de Bresenham, en une animation avec de plus en plus de carrés et toujours la même pente.]]

=== Réduction des variables et simplifications ===
On pourra enfin changer le signe de ''e'' en testant le signe opposé, puis réduire le nombre de variables, en constatant que ''x1'' et ''y1'' ci-dessus ne sont plus utilisés dès que l’erreur initiale et les incréments sont calculés ; il suffit de changer aussi le signe des incréments et décréments :
 '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''dx'', ''dy'' ;
   '''déclarer''' '''entier''' ''e'' ; ''// valeur d’erreur''
   ''e''  ← ''x''<sub>2</sub> - ''x''<sub>1</sub> ;        ''// -e<sub>(0,1)</sub>''
   ''dx'' ← ''e'' × 2 ;          ''// -e<sub>(0,1)</sub>''
   ''dy'' ← (''y''<sub>2</sub> - ''y''<sub>1</sub>) × 2 ;  ''// e<sub>(1,0)</sub>''
   '''tant que''' ''x''<sub>1</sub> ≤ ''x''<sub>2</sub> '''faire'''
     tracerPixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
     ''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1 ;  ''// colonne du pixel suivant''
     '''si''' (''e'' ← ''e'' - ''dy'') ≤ 0 '''alors'''  ''// erreur pour le pixel suivant de même rangée''
       ''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1 ;  ''// choisir plutôt le pixel suivant dans la rangée supérieure''
       ''e'' ← ''e'' + ''dx'' ;  ''// ajuste l’erreur commise dans cette nouvelle rangée''
     '''fin si''' ;
   '''fin faire''' ;
   ''// Le pixel final (x<sub>2</sub>, y<sub>2</sub>) n’est '''pas''' tracé.''
 '''fin procédure''' ;

Cet algorithme est optimal et suffisant pour tracer tout vecteur horizontal diagonal ou oblique dans le premier octant, de colonnes et rangées croissantes. Si le [[langage de programmation]] le permet, les deux [[Variable locale|variables locales]] déclarées ''x'' et ''y'' peuvent être remplacées par réutilisation des variables ''x''<sub>1</sub> et ''y''<sub>1</sub> des paramètres. Ce cas est traité ci-dessus.

Toutefois il faut remarquer dans l’algorithme ci-dessus que le test du signe de ''e'' peut aussi bien inclure l’égalité avec zéro ou ne pas l’inclure. Cela correspond au fait que les deux pixels suivants candidats sont équidistants de la droite exacte. Si on choisit un déplacement diagonal le deuxième point suivant sera toujours obtenu par un déplacement horizontal ; si on choisit un déplacement horizontal le deuxième point suivant sera toujours obtenu par un déplacement diagonal. Si on inversait la direction du vecteur, les pixels choisis seraient inversés donc différents, et on devra en tenir compte si on souhaite un recouvrement exact des pixels de deux vecteurs obliques de sens opposés, lors de la généralisation de l’algorithme à des vecteurs obliques de directions quelconques (ce cas ne peut pas se produire pour le tracé de vecteurs horizontaux, verticaux ou diagonaux).

== Algorithme général optimisé ==
La généralisation de l’algorithme de base au tracé de vecteurs de direction quelconque est obtenue par simple symétrie.

L’algorithme est ici développé et optimisé dans chacun des huit octants. Toutefois, afin de s’assurer que les mêmes pixels seront toujours tracés pour deux vecteurs identiques mais de direction opposée, on inversera les cas limites où un déplacement diagonal est à égalité avec un déplacement droit, en choissant la diagonale quand le vecteur est orienté vers la gauche (abscisses décroissantes) plutôt que vers la droite (abscisses croissantes) comme dans le cas simplifié ci-dessus :

 
 
  '''procédure''' tracerSegment('''entier''' ''x''<sub>1</sub>, '''entier''' ''y''<sub>1</sub>, '''entier''' ''x''<sub>2</sub>, '''entier''' ''y''<sub>2</sub>) '''est'''
   '''déclarer''' '''entier''' ''dx'', ''dy'';
   
   '''si''' (''dx'' ← ''x<sub>2</sub>'' - ''x<sub>1</sub>'') ≠ 0 '''alors'''
     '''si''' ''dx'' &gt; 0 '''alors'''
       '''si''' (''dy'' ← ''y<sub>2</sub>'' - ''y<sub>1</sub>'') ≠ 0 '''alors'''
         '''si''' ''dy'' &gt; 0 '''alors'''
           ''// vecteur oblique dans le {{1er}} quadrant''
           
           '''si''' ''dx'' ≥ ''dy'' '''alors'''
             ''// vecteur diagonal ou oblique proche de l’horizontale, dans le {{1er|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ;  ''// e est positif''
             '''boucle sans fin'''  ''// déplacements horizontaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' - ''dy'') &lt; 0 '''alors'''
                 ''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dx'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''sinon'''
             ''// vecteur oblique proche de la verticale, dans le {{2nd}} octant''
             '''déclarer''' '''entier''' ''e'' ;
             ''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ;  ''// e est positif''
             '''boucle sans fin'''  ''// déplacements verticaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' - ''dx'') &lt; 0 '''alors'''
                 ''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dy'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''fin si''' ;
           
         '''sinon'''  ''// dy &lt; 0 (et dx &gt; 0)''
           ''// vecteur oblique dans le {{4e|quadrant}}''
           
           '''si''' ''dx'' ≥ -''dy'' '''alors'''
             ''// vecteur diagonal ou oblique proche de l’horizontale, dans le {{8e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ;  ''// e est positif''
             '''boucle sans fin'''  ''// déplacements horizontaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' + ''dy'') &lt; 0 '''alors'''
                 ''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dx'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''sinon'''  ''// vecteur oblique proche de la verticale, dans le {{7e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ;  ''// e est négatif''
             '''boucle sans fin'''  ''// déplacements verticaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' + ''dx'') &gt; 0 '''alors'''
                 ''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dy'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''fin si''' ;
           
         '''fin si''' ;
       '''sinon'''  ''// dy = 0 (et dx &gt; 0)''
         
         ''// vecteur horizontal vers la droite''
         '''répéter'''
           tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
         '''jusqu’à ce que''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> + 1) = ''x<sub>2</sub>'' ;
         
       '''fin si''' ;
     '''sinon'''  ''// dx &lt; 0''
       '''si''' (''dy'' ← ''y<sub>2</sub>'' - ''y<sub>1</sub>'') ≠ 0 '''alors'''
         '''si''' ''dy'' &gt; 0 '''alors'''
           ''// vecteur oblique dans le {{2nd}} quadrant''
           
           '''si''' -''dx'' ≥ ''dy'' '''alors'''
             ''// vecteur diagonal ou oblique proche de l’horizontale, dans le {{4e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ;  ''// e est négatif''
             '''boucle sans fin'''  ''// déplacements horizontaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' + ''dy'') ≥ 0 '''alors'''
                 ''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dx'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''sinon'''
             ''// vecteur oblique proche de la verticale, dans le {{3e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ;  ''// e est positif''
             '''boucle sans fin'''  ''// déplacements verticaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' + ''dx'') ≤ 0 '''alors'''
                 ''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dy'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''fin si''' ;
           
         '''sinon'''  ''// dy &lt; 0 (et dx &lt; 0)''
           ''// vecteur oblique dans le {{3e|quadrant}}''
           
           '''si''' ''dx'' ≤ ''dy'' '''alors'''
             ''// vecteur diagonal ou oblique proche de l’horizontale, dans le {{5e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dx'' ← (e ← ''dx'') × 2 ; ''dy'' ← ''dy'' × 2 ;  ''// e est négatif''
             '''boucle sans fin'''  ''// déplacements horizontaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' - ''dy'') ≥ 0 '''alors'''
                 ''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dx'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''sinon'''  ''// vecteur oblique proche de la verticale, dans le {{6e|octant}}''
             '''déclarer''' '''entier''' ''e'' ;
             ''dy'' ← (e ← ''dy'') × 2 ; ''dx'' ← ''dx'' × 2 ;  ''// e est négatif''
             '''boucle sans fin'''  ''// déplacements verticaux''
               tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
               '''interrompre boucle si''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
               '''si''' (''e'' ← ''e'' - ''dx'') ≥ 0 '''alors'''
                 ''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1 ;  ''// déplacement diagonal''
                 ''e'' ← ''e'' + ''dy'' ;
               '''fin si''' ;
             '''fin boucle''' ;
           '''fin si''' ;
           
         '''fin si''' ;
       '''sinon'''  ''// dy = 0 (et dx &lt; 0)''
         
         ''// vecteur horizontal vers la gauche''
         '''répéter'''
           tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
         '''jusqu’à ce que''' (''x''<sub>1</sub> ← ''x''<sub>1</sub> - 1) = ''x<sub>2</sub>'' ;
         
       '''fin si''' ;
     '''fin si''' ;
   '''sinon'''  ''// dx = 0''
     '''si''' (''dy'' ← ''y''<sub>2</sub> - ''y''<sub>1</sub>) ≠ 0 '''alors'''
       '''si''' ''dy'' &gt; 0 '''alors'''
         
         ''// vecteur vertical croissant''
         '''répéter'''
           tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
         '''jusqu’à ce que''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> + 1) = ''y<sub>2</sub>'' ;
         
       '''sinon'''  ''// dy &lt; 0 (et dx = 0)''
         
         ''// vecteur vertical décroissant''
         '''répéter'''
           tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>) ;
         '''jusqu’à ce que''' (''y''<sub>1</sub> ← ''y''<sub>1</sub> - 1) = ''y<sub>2</sub>'' ;
         
       '''fin si''' ;
     '''fin si''' ;
   '''fin si''' ;
   ''// le pixel final (x<sub>2</sub>, y<sub>2</sub>) n’est pas tracé.''
 '''fin procédure''' ;

Notes :
* Ci-dessus, les affectations sont parfois regroupées au sein des expressions qui en réutilisent la valeur affectée. Si le langage utilisé ne le permet pas, il suffit d'effectuer les affectations internes dans des instructions d’affectation préalables séparées, et de relire cette variable dans l’expression contenante.
* Les primitives graphiques '''tracePixel(''x''<sub>1</sub>, ''y''<sub>1</sub>)''' sont regroupées ci-dessus pour tracer dans la boucle interne des segments horizontaux (cas du premier octant ci-dessus) ou verticaux (second octant), et peuvent être regroupées en un seul appel (il suffit de compter le nombre de passages dans la boucle interne, et d’effectuer le tracé de segment horizontal (ou vertical) en sortie de cette boucle.

== Références ==
{{références}}
* {{article|langue=en|auteur1=[[Jack E. Bresenham]]|nom1=Bresenham|prénom=Jack E.|titre=Algorithm for computer control of a digital plotter| périodique=IBM Systems Journal| jour=1| mois=janvier| année=1965| volume=4| numéro=1| pages=25–30| doi=10.1147/sj.41.0025| lire en ligne=http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf}}

== Articles connexes ==
* [[Algorithme de tracé d'arc de cercle de Bresenham]]
* [[Algorithme de tracé de cercle d'Andres]]
* [[Algorithme de tracé de segment de Xiaolin Wu]], version avec [[anticrénelage]]

{{Portail|informatique théorique|Imagerie numérique}}

[[Catégorie:Algorithme d'infographie|Brensenham]]