Algorithmique de
base de l'Infographie

RETOUR

On donne l'algorithme de Bresenham. Cet algorithme permet de tracer sur un écran raster le segment de droite allant du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf).

void ligne(int xi,int yi,int xf,int yf) {t xf,int yf) {
  int x = xi ;
  int y = yi ;
  int dx = xf - xi ;
  int dy = yf - yi ;
  int cumul = dx / 2 ;
  allume_pixel(x,y) ;
  for ( x = xi+1 ; x <= xf ; x++ ) {
    cumul += dy ;
    if ( cumul >= dx ) {
      cumul -= dx ;
      y += 1 ; }
    allume_pixel(x,y) ; }
}

Question : Prouver que le dernier pixel tracé est bien le pixel de coordonnées (xf,yf).

Solution

Le dernier pixel allumé a pour coordonnées (xf,yf) car dx/2+dy*dx est la valeur totale de ce qui a été accumulé dans cumul au cours de l'exécution.
-> = dy est le nombre de fois où y a été incrémenté de 1.
-> L’ordonnée du dernier pixel allumé est yi + dy = yf.

Par ailleurs, la dernière valeur de cumul est égale à dx/2