Apri il menu principale

Algoritmo della linea di Bresenham

Algoritmo grafico usato in informatica per il tracciamento delle linee

L'algoritmo della linea di Bresenham (da alcuni chiamato algoritmo del punto medio o anche Cerchi di Bresenham) è un algoritmo di rasterizzazione di linea. Allo stato attuale è l'algoritmo più usato per la rasterizzazione di linee, soprattutto per la sua bassa richiesta di risorse computazionali.

DescrizioneModifica

Per capire l'algoritmo, semplifichiamo il problema assumendo che   sia compreso tra  .

Immaginiamo di trovarci ad un passo   dell'algoritmo, cioè abbiamo appena determinato quale pixel "accendere", per esempio  .

Ora dobbiamo determinare il prossimo pixel da "accendere", chiamiamolo  , dove  .

La situazione è quella riportata in figura 1, dove dal punto 1 (quello in verde) dobbiamo passare al punto 2 che si può trovare subito a destra, caso A, o in alto a destra, caso B.

 
Figura 1
  • Nel caso A abbiamo  ;
  • Nel caso B abbiamo  .

Prendiamo in considerazione il punto   (Figura 2), punto medio tra A e B. Se la linea da rasterizzare passa sopra, illumineremo il pixel superiore B, altrimenti il pixel inferiore A.

 
Figura 2

Per determinare se   si trova sotto o sopra la retta, consideriamo la forma esplicita dell'equazione della retta:

 

che può essere riscritta nella forma:

 

Tutti i punti appartenenti alla retta devono verificare l'equazione. Ma questa retta divide anche due semipiani, quello composto da tutti i punti per cui la formula precedente restituisce un valore positivo e quello per cui restituisce un valore negativo. Un esempio dei semipiani lo troviamo nella figura 3.

 
Figura 3

Quindi dalla formula precedente possiamo ricavare il valore decisionale  , sostituendo ad   ed   le coordinate di   (il punto medio tra A e B):

 

il quale sarà:

  •  , se il punto giace sulla retta; in questo caso possiamo scegliere in modo indifferente il punto A o il punto B;
  •  , se il punto si trova sopra la retta; in questo caso prendiamo il punto A;
  •  , se il punto si trova sotto la retta; in questo caso prendiamo il punto B.

Nell'algoritmo avremmo necessità ogni volta di sapere se   è positivo o negativo.

Ipotizziamo di aver scelto il punto A, in questo caso il nostro punto di partenza   è  , e il nostro nuovo punto medio M è  . Invece il nuovo valore di   è:

 

Proviamo a sottrarre al nuovo valore di   quello vecchio:

 

Semplificando otteniamo:

 

Quindi abbiamo modo di ricavare il nuovo valore   in modo più semplice dal vecchio, senza ogni volta rifare tutti i calcoli.

Ora dobbiamo fare l'ipotesi per il caso in cui si sia scelto il punto B. Abbiamo i nostri nuovi punti:

  •  ;
  •  ;

e il nostro nuovo valore  :

 

Ripetiamo la sottrazione:

 

Semplificando otteniamo:

 

Riassumendo, dato un valore  :

 

Non ci rimane che conoscere il valore  ; ricordandoci la formula per calcolare   e prendendo come punto  ,   ovvero un estremo della retta, abbiamo:

 

Nel passaggio abbiamo portato fuori i valori   e  . La prima parte della formula corrisponde all'equazione della retta applicata ad un punto della retta, quindi sappiamo che sarà uguale a zero. Infine ci rimane:

 

AlgoritmoModifica

Da tutte queste formule possiamo finalmente ricavare l'algoritmo: Dati due punti   e  , con coordinate (x1,y1) e (x2,y2):

DX = x2 - x1
DY = y2 - y1

//il nostro valore d0
d = - 1/2 * DX + DY

//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

while x < x2 {
       if (d >= 0) {
        d = d -DX + DY;
        y = y + 1;
        x = x + 1;
       }
       else {
        d = d + DY;
        x = x + 1;
       }
       disegna_il_punto(x, y)
}

Notiamo che l'algoritmo presenta dei numeri in virgola mobile, i quali richiedono risorse computazionali, un'idea per evitare questa precisione è quella di raddoppiare i valori di  :

DX = x2 - x1
DY = y2 - y1

//il nostro valore d0
d = - DX + 2 * DY

//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

while x < x2 {
       if (d >= 0) {
        d = d -2 * DX + 2 * DY;
        y = y + 1;
        x = x + 1;
       }
       else {
        d = d + 2 * DY;
        x = x + 1;
       }
       disegna_il_punto(x, y)
}

Abbiamo quindi ottenuto un algoritmo che lavora con numeri interi e semplice da implementare. Nel caso in cui avessimo x1>x2 allora al posto di aumentare   lo diminuiamo mentre i valori decisionali restano uguali, anche se y1>y2 i valori decisionali non variano, in quanto la retta assume pendenza di valore opposto a quello del caso y1<y2 e x1<x2, cambia solo l'incremento della   che invece di aumentare, diminuisce, e il valore decisionale resta invariato, in quanto trattiamo la retta sia se x1>x2 sia se y1>y2 come se fosse nel primo caso studiato, nel primo caso sia DX che DY sono maggiori di zero allora prenderemo il valore assoluto, di seguito ricaviamo l'algoritmo:

DX = x2 - x1
DY = y2 - y1

//per non scrivere sempre i valori assoluti cambio DY e DX con altre variabili
a=abs(DY)
b=-abs(DX)

//il nostro valore d0
d = 2*a+b
//assegna le coordinate iniziali
x = x1
y = y1
disegna_il_punto(x, y)

//s e q sono gli incrementi di x e y
s=1
q=1
if (x1>x2) q=-1
if (y1>y2) s=-1

while x < x2 {
       if (d >= 0) {
        d = 2 * (a + b) + d
        y = y + s;
        x = x + q;
       }
       else {
        d = 2 * a + d;
        x = x + q;
       }
       disegna_il_punto(x, y)
}

Con questo abbiamo ottenuto le rette con valore di  . Con valore di   dobbiamo fare delle modifiche perché |DY/DX|>1 e questo accade quando DY>DX in questo caso l'approssimazione della linea con l'algoritmo che abbiamo trovato è pessima, visto che viene trattato solo DX come loop, dobbiamo generalizzare l'algoritmo nei casi in cui possiamo avere DY>DX. Se ruotiamo la retta di 90 gradi possiamo notare che è come se dovessimo applicare lo stesso algoritmo precedente con la coordinata dei due punti da scegliere x invece che  , allora in questo caso trattiamo DY come DX e DY come DX, basta quindi scambiare DX e DY e rimanere i valori decisionali invariati, nel loop possiamo avere DX>DY oppure DY>DX ma siccome scambiamo sarà sempre DX>DY, poi nel caso in cui d>=0 avremo che entrambe le coordinate aumentano o diminuiscono di 1, quindi questo caso rimane uguale, cambia invece il caso in cui   in questo caso infatti dobbiamo decidere se aumentare solo   o solo   in base al caso che abbiamo. Nel caso normale si aumenta  , nel caso DY>DX si scambiano e si aumenta  , da questa logica possiamo ricavare l'algoritmo per linee generali che è il seguente:

swap = 0;
DX = x2 - x1;
DY = y2 - y1;

//siccome scambio DY e DX ho sempre DX>=DY allora per sapere quale coordinata occorre cambiare uso una variabile
if (abs(DX) < abs(DY)) {
   swap(DX, DY);
   swap = 1;
}

//per non scrivere sempre i valori assoluti cambio DY e DX con altre variabili
a = abs(DY);
b = -abs(DX);

//assegna le coordinate iniziali
x = x1;
y = y1;

//il nostro valore d0
d = 2 * a + b;

//s e q sono gli incrementi/decrementi di x e y
q = 1;
s = 1;
if (x1 > x2) q = -1;
if (y1 > y2) s = -1;
disegna_punto(x, y);
disegna_punto(x2, y2);
for (k = 0; k < -b; k+=1) {
   if (d > 0) {
       x= x + q; y= y + s;
       d= d + 2 * (a + b);
   }
   else {
       x = x + q;
       if (swap==1) { y = y + s; x = x - q; }
       d = d + 2 * a;
   }
   disegna_punto(x, y);
}

Altri progettiModifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica