P, Q \in \mathbb{Z}^2

Problème: étant donné deux points P et Q de coordonnées entières, afficher le segment de droite PQ. C'est à dire, déterminer les pixels approximant le segment et donnant l'impression visuelle.

Rappel: Droite de pente k passant par un point M_0 = \left(x_0 \atop y_0 \right) et de vecteur directeur \vec{v}=\left(u \atop v\right).

• y=kx+b
• b=y₀ - k * x₀ = l'ordonnée en x₀

Droite de pente k passant par P=\left( x_1 \atop x_2 \right), Q=\left(x_2 \atop y_2\right)

AfficheSegmentFloat( P point, Q point, c code_couleur){
  delta_x = Q.x - P.x;
  delta_y = Q.y - P.y;
  if (delta_x==0) pente=0 else pente=delta_y/delta_x;
  decalage = P.y - pente * P.x;
/* on suppose que le segment a une pente entre 0 et 1 et on affiche un pixel par colonne */
  if (delta_x >0 && delta_x >= delta_y){
    for (x=P.x, x<=Q.x, 1) 
      {
      y = round(x * pente + decalage);
      AffichePixel(x,y);
      }
  }
}

Lorsque la pente est de 1 à + infini on affiche un pixel par ligne.

• on peut améliorer cet algorithme en travaillant de manière incrémentale

  y_{k+1} = \frac{\Delta y}{\Delta x}\left(x+1\right) + c = \frac{\Delta y}{\Delta x}\cdot + c + \frac{\Delta y}{\Delta x} = y_{k} + \frac{\Delta y}{\Delta x}

; et en utilisant l'arithmétique entière, mais comment faire?

L'idée fondamentale est qu'à chaque transition de x_c à x_c+1=x_c+1 dans le premier octant, on choisit entre y_c+1=y_c (on ne change pas de ligne) et y_c+1=y_c+1 (on change de ligne). Il convient de trouver une bonne règle pour prendre cette décision à chaque x.

La préconisation est de prendre le pixel dont le décalage (ou distance) vertical de la vraie ligne est le (ou la) moindre.

• pour y_c : d1=m(x_c+1)+b-y_c
• pour y_c+1 : d2=y_c +1 - m(x_c+1)-b
• Si D=d1-d2 est positive, d2 est moindre et on choisit y_c+1
• Si D=d1-d2 est négative, d1 est moindre et on choisit y_c
• Or, si on développe D et multiplie par \Delta x >0 puisqu'on est dans le premier octant par hypothèse,

  \begin{eqnarray}D & =& d1-d2\\ & = & \left[\frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c\right] - \left[y_c+1 -\frac{\Delta y}{\Delta x}\left(x_c + 1\right)-b \right] \\ & = & \frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c - y_c-1 +\frac{\Delta y}{\Delta x}\left(x_c + 1\right)+b \\ & = & 2\times\left[\frac{\Delta y}{\Delta x}\left(x_c + 1\right) + b - y_c \right] -1 \\ d_c=\Delta x \times D & = & 2\times\left[\Delta y\left(x_c + 1\right) + b\times\Delta x - y_c \times\Delta x\right] -\Delta x \end{eqnarray}
• Notons que presque tous ces termes sont des entiers puisque x_1,y_1,x_2,y_2 sont des entiers; mais b?
• Calcul incrémentale de d_c+1:
  • si d_c < 0, d₁ < d₂ et on choisit y_c. Donc d_{c+1} = 2\Delta y \left(x_c + 1 + 1\right) - 2 y_c \Delta x - \Delta x +2b\Delta x = d_c + 2\Delta y
  • di d_c >0, d₁ > d₂ et on choisit y_c+1. Donc d_{c+1} = 2\Delta y \left(x_c + 1 + 1\right) - 2 (y_c +1) \Delta x - \Delta x +2b\Delta x = d_c + 2\Delta y - 2\Delta x

Au premier pas, la valeur initiale de d_c est calculée:

x=x1;y=y1;
delta_x = x2 - x1; delta_y = y2 - y1;
d = 2*delta_y - delta_x;
incr1 = -2* delta_x;
incr2 = 2*delta_y;
for (i=0; i<=delta_x; i++) {
  AffichePixel(x,y,couleur);
  if (d>= 0) {y=y+1;d=d+incr1;}  
  x=x+1;
  d=d+incr2;

1. Reste à généraliser cet algorithme aux autres octants en TP
2. il est incrémental et en entiers (donc rapide) mais il est dur de calculer les intersections avec d'autres figures, ou même de “deviner” si un pixel est allumé ou non sans dérouler l'algorithme! Bonne nouvelle : il existe une “droite arithmétique” passant par les mêmes P et Q et les points de cette droite sont ceux du segment discret 8-connexe obtenus par l'algorithme de Bresenham.

La droite arithmétique passant par P=\left(x_1,y_1\right), Q=\left(x_2,y_2\right) avec \left(\Delta x = x_2 - x_1 \gt 0\right)\quad \& \quad \left(\Delta y = y_2-y_1\geq 0\right) \quad \& \quad \left(\Delta y \leq \Delta x\right) est \displaystyle \left\{ \left(x,y\right)\in\mathbb{Z}^2 | y=y_1+\lfloor \frac{\left(x-x_1\right)\Delta y + \frac{\Delta x}{2}}{\Delta x}\rfloor\right\}

Précondition : premier octant (comme d'hab)

delta_x = Q.x - P.x; delta_y = Q.y - P.y;
r = floor(delta_x/2);
y = y1;
pour x = x1 à x2 par 1 faire
  afficher (x,y,couleur);
  r=r+delta_y;
  if (r>= delta_x) {y=y+1; r=r-delta_x;}