algorithme 1

principe

C'est l'équation paramètrique d'une droite que l'on utilise ici.

On commence à se placer sur (x1;y1). Ensuite, on trace le point puis on incrémente x de 1 et y du coefficient directeur de la droite. Pour finir, on répète l'opération jusqu'à atteindre x2.

algorithme

L'algorithme est le suivant :

 
initialiser x avec x1
initialiser y avec y1
debut:
Tracer le point (x,y)
Incrémente x de 1
Incrémenter y de deltaY / deltaX
Si x < x2 alors aller à debut
 

critique

- utilisation de flottants (deltaY/deltaX)
Le traitement des flottants est plus long que celui des entiers
- dans (x,y), y n'est pas un entier
y incrémenté de deltaY/deltaX
 

algorithme 2

principe

On crée une nouvelle variable err. Elle sera incrémentée de deltaY/deltaX et y sera incrémentée que lorque err sera supérieure à 0,5.

Ce principe se nomme algorithme de Bresenham. On reste sur la même ligne tant que l'erreur est inférieure à 0,5.
Ce principe peut être utilisé non seulement pour tracer une droite mais aussi pour tracer un cercle ou une ellipse.

algorithme

 
; algorithme 1
x = x1
y = y1
debut:
draw (x,y)
x += 1
y += deltaY / deltaX
cmp x,x2
jl debut
 

devient

 
; algorithme 2
x = x1
y = y1
k = deltaY / deltaX
err = 0
boucle = x2 - x1
debut:
draw (x,y)
x += 1
err += k
if err > 0.5
  y += 1
  err -= 1
dec boucle
jnz debut
 

algorithme 3

principe

Le principe est de tranformer l'algorithme pour qu'il n'utilise que des entiers.

algorithme

 
deltaY/deltaX
0.5
1
 

devient

 
2*deltaY/deltaX
1
2
 

devient

 
2*deltaY
deltaX
2*deltaX
 

 

 
; algorithme 3
x = x1
y = y1
k = 2*deltaY
err = 0
boucle = x2 - x1
debut:
draw (x,y)
x += 1
err += k
if err > deltaX
  y += 1
  err -= 2*deltaX
dec boucle
jnz debut
 

algorithme 4

principe

Le principe de ce nouvel algorithme est,dans la boucle, de na plus comparer err à 0.5 mais à 0.

explications

Pour pouvoir comparer err à 0, on va soustraire deltaX à err. Cela donne :

 
err > deltaX
est équivalent à
err - deltaX > 0
 

Pour ne pas effectuer err - deltaX à chaque boucle, on va opérer la soustraction directement au moment d'initialiser err. err sera donc initialisée à -deltaX.

algorithme

 
; algorithme 4
x = x1
y = y1
k = 2*deltaY
err = -deltaX
boucle = x2 - x1
debut:
draw (x,y)
x += 1
err += k
if err > 0
  y += 1
  err -= 2*deltaX
dec boucle
jnz debut
 

algorithme 5

principe

On peut remarquer que dans l'algorithme précédent, err est incrémenté 1 ou 2 fois. On va réduire ce nombre à 1.

algorithme

 
; algorithme 5
x = x1
y = y1
err = 2*deltaY-deltaX
boucle = x2 - x1
debut:
draw (x,y)
x += 1
if err > 0
  y += 1
  err += 2*deltaY-2*deltaX
else
  err += 2*deltaY
dec boucle
jnz debut
 

algorithme 6

principe

Dans la boucle err est influencée par 2*deltaY-2*deltaX et 2*deltaY. On remarque un facteur commun 2 dans ces 2 constantes. On va donc l'éliminer, ce qui permettra d'économiser 1 bit dans les registres du processeur.

algorithme

 
; algorithme 6
x = x1
y = y1
err = 2*deltaY-deltaX
boucle = x2 - x1
debut:
draw (x,y)
x += 1
if err > 0
  y += 1
  err += deltaY-deltaX
else
  err += deltaY
dec boucle
jnz debut
 

remarques

Les algorithmes décrits précédemment supposent que x2>x1, que y2>y1, et que deltaX>deltaY.

Dans le cas où deltaX>deltaY, il faut inverser les axes.

Dans le cas où x2<x1, il faut échanger (x1,y1) avec (x2,y2).

Dans le cas où y2>y1, dans la boucle, il faut décrémenter y au lieu de l'incrémenter.