Bresenham-Algorithmus

Der Bresenham-Algorithmus ist ein Verfahren, um beim Umwandeln von Vektorgrafik in Pixelgrafik zwei Punkte gerade miteinander zu verbinden. Zu Zeiten, als sich Microsoft Windows und X-Windows (X11) noch nicht in dem Maße durchgesetzt hatten wie heute, gab es viele Enthusiasten, die ihre eigene Grafik-Unterprogrammbibliothek entwickelt haben, um direkt auf die Grafik-Hardware (z.B. VGA-Karte) zuzugreifen und dort Diagramme oder andere technische Darstellungen auszugeben. Dabei war der Bresenham-Algorithmus das wichtigste Hilfsmittel. Seine Bedeutung ist bis heute ungebrochen, auch wenn man ihn nur noch selten selbst programmieren muss, denn er ist in den Grafik-Libraries oder Teilen des Betriebssystems enthalten, mit denen man Vektorgrafik programmiert. Als selbsterklärendes Beispiel folgt der Quellcode eines entsprechenden Unterprogramms in C, worin der Caller dafür verantwortlich ist, dass die Koordinaten-Arrays ausreichend groß dimensioniert sind.

void gbham(int xstart,int ystart,int xend,int yend,int *npix,int *xpix,int *ypix)
/*--------------------------------------------------------------
 * Bresenham's algorithm: line drawing on pixel devices.
 *
 * input parameters:
 *    int xstart,ystart     = coordinates of beginning of line
 *    int xend,yend         = coordinates of ending of line
 *
 * output parameters:
 *    int *npix             = number of pixels
 *    int xpix[i],ypix[i]   = coordinates of i-th pixel
 *---------------------------------------------------------------
 */
 {
     int x,y,t,dist,xerr,yerr,dx,dy,incx,incy;

/* compute the distance in both directions */
     dx=xend-xstart;
     dy=yend-ystart;

/* compute the sign of the increment in both directions */
     if(dx<0)
        {
        incx= -1;
        dx= -dx;
        }
     else
        incx = dx ? 1 : 0;
     if(dy<0)
        {
        incy= -1;
        dy= -dy;
        }
     else
        incy = dy ? 1 : 0;

/* determine which distance is larger */
     dist = (dx>dy)?dx:dy;

/* initilaizations before loop */
     x=xstart;
     y=ystart;
     xerr=dx;
     yerr=dy;

/* compute the pixels */
     for(t=0; t<dist; ++t)
        {
        xpix[t]=x;
        ypix[t]=y;
        xerr += dx;
        yerr += dy;
        if(xerr>dist)
           {
           xerr -= dist;
           x += incx;
           }
        if(yerr>dist)
           {
           yerr -= dist;
           y += incy;
           }
        }
     *npix=dist+1;
     xpix[dist]=xend;
     ypix[dist]=yend;
     } /* gbham() */