Algoritmul Bresenham de trasare a unei linii

>        Algoritmul Bresenham de trasare a unei linii este un algoritm ce determină care puncte dintr-un raster n-dimensional trebuie aprinse pentru a forma o aproximaţie a unei linii drepte între două puncte date. Acest algoritm este folosit pentru a trasa linii pe ecranele calculatoarelor, folosind doar adunarea numerelor întregi, scădere şi schimbare de bit, operaţii rapide pe calculatoarele din zilele noastre. Este unul dintre primii algoritmi apărut în domeniul graficii pe calculator.

        Printr-o mică modificare, algoritmul original pentru trasarea unei linii poate fii folosit şi pentru a trasa cercuri. De asemenea, se poate rezolva cu operaţii aritmetice simple, ecuaţiile pătratice şi expresiile trigonometrice pot fii evitate sau sparte recursiv în bucăţi mai mici.

        Proprietăţiile menţionate fac din acest algoritm unul foarte important, fiind folosit în plottere, în chipurile plăcilor grafice moderne şi în multe librarii grafice a diverselor aplicatii de pe piaţă, fiind foarte simplu, este implementat direct în firmware-ul acestor dispozitive.

Algoritmul

        Se foloseşte convenţia următoare: coordonatele pixelilor cresc în direcţiile jos şi dreapta şi că centrul pixelilor are coordonate numere întregi. Capetele liniei sunt pixelii aflaţi la coordonatele (x0, y0) şi (x1, y1), unde primele coordinate din pereche reprezintă coloana, celelalte linia.

        Algoritmul este iniţial prezentat doar pentru octantul unde segmentul se deplasează în jos şi spre dreapta (x0≤x1 and y0≤y1 ) , şi proiecţia sa orizontală x1−x0 este mai lungă decât proiecţia verticală y1−y0 (în alte cuvinte, linia are o pantă mai mică decât 1 şi mai mare decât 0). În acest octant, pentru fiecare coloană x între x0 şi x1, este exact o linie y (calculată de algoritm) ce conţine un pixel din linie, în timp ce fiecare linie din intervalul y0 şi y1 conţine mai mulţi pixeli rasterizaţi.

        Algoritmul Bresenham alege acel y număr întreg ce corespunde centrului pixelului care este cel mai aproape de y-ul ideal (fracţional) pentru acelaşi x. Pentru coloane succesive, y poate rămâne acelaşi sau poate creşte cu 1. Ecuaţia generală a unei drepte este dată de formula:

        De vreme ce cunoaştem coloana x, linia pixelului, y, este dată de rotunjirea la cel mai apropiat întreg a următoarei formule:

        Panta (y1 − y0)/(x1 − x0) depinde numai de coordonatele de sfârşit şi poate fii precalculată, şi y-ul ideal pentru valori întregi successive ale lui x poate fii calculat pornind de la y0 şi adunând repetat panta.

        În practică, algoritmul poate avea o mică eroare a cărei valoare este cuprinsă în intervalul −0.5 şi 0.5: distanţa verticală dintre y-ul rotunjit şi cel exact pentru x-ul current. De fiecare dată când x este mărit, eroare este mărită prin adunarea pantei la eroare; dacă depăşeşte 0.5, y–ul este mărit cu 1 şi eroarea este scăzută cu 1.

Generalizarea algoritmului

        Prima versiune a algoritmului trasa doar linii care coboară spre dreapta. De accea algoritmul a fost modificat pentru a trasa linii în orice direcţie. Prima modificare a fost facută pentru a permite trasarea liniilor care coboară spre stânga. Pentru asta s-a schimbat punctele iniţiale, dacă x0 > x1. Pentru a trasa liniile care ascend către marginea superioară a ecranului, se verifică dacă y0 ≥ y1; dacă e adevarat, y scade cu 1 în loc să crească cu 1. Pentru a trasa linii cu o pantă mai abruptă , ne folosim de faptul că o linie abruptă poate fii oglindită de-a lungul liniei y=x pentru a obţine o linie cu o pantă mai mică. Pentru asta se schimbă variabilele x şi y între ele, inclusiv schimbarea parametrilor funcţiei plot. Pseudocodul unui astfel de program arată cam aşa :

function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     real error := 0
     real deltaerr := deltay / deltax
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltaerr
         if error = 0.5 then
             y := y + ystep
             error := error - 1.0

Exemplu de program in C

#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <math.h>
#include <dos.h>

void Bresenham(int x1, int y1, int x2, int y2)
 {
     int pas;
     int dx, dy, incE, incNE, d, x, y;
      // inverseaza daca  x1 > x2
     if (x1 > x2)
       Bresenham(x2, y2, x1, y1);
     dx = x2 - x1;
     dy = y2 - y1;
     if (dy < 0)
     {
  pas = -1;
  dy = -dy;
     }
     else
      pas = 1;
     incE = 2 * dy;
     incNE = 2 * dy - 2 * dx;
     d = 2 * dy - dx;
     y = y1;
     // pune pixeli
     for (x = x1; x <= x2; x++)
     {
  putpixel(x,y,3);
  if (d <= 0)  d += incE;
   else
   {
      d += incNE;
      y += pas;
  }
     }
 }

void main(void)
{
   int gdriver = DETECT, gmode, errorcode;
   int xmax, ymax,y,x;
   initgraph(&gdriver,&gmode,"");
   errorcode = graphresult();
   if (errorcode != grOk)
    {
      printf("Graphics error: %sn", grapherrormsg(errorcode));
      printf("Press any key to halt:");
      getch();
      exit(1);
    }
xmax = getmaxx();  ymax = getmaxy();
Bresenham(0,ymax/2,xmax,ymax/2);
Bresenham(xmax/2,0,xmax,ymax);
getch();closegraph();clrscr();
}