# Algoritmo della linea di Bresenham

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.

## Descrizione

Per capire l'algoritmo, semplifichiamo il problema assumendo che $m={\frac {\Delta y}{\Delta x}}$ sia compreso tra $0<m<1$.
Immaginiamo di trovarci ad un passo $i$ dell'algoritmo, cioè abbiamo appena determinato quale pixel "accendere", per esempio $p_{1}(x_{1},y_{1})$.
Ora dobbiamo determinare il prossimo pixel da "accendere", chiamiamolo $p_{2}(x_{2},y_{2})$, dove $x_{2}=x_{1}+1$.
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.
* Nel caso A abbiamo $y_{2}=y_{1}$;
* Nel caso B abbiamo $y_{2}=y_{1}+1$.
Prendiamo in considerazione il punto $M(x_{1}+1,y_{1}+{1 \over 2})$ (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.
Per determinare se $M$ si trova sotto o sopra la retta, consideriamo la forma esplicita dell'equazione della retta:
$y={\frac {\Delta y}{\Delta x}}\cdot x+q$
che può essere riscritta nella forma:
$-\Delta x\cdot y+\Delta y\cdot x+\Delta x\cdot q=0$
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.
Quindi dalla formula precedente possiamo ricavare il valore decisionale $d$, sostituendo ad $x$ ed $y$ le coordinate di $M(x_{1}+1,y_{1}+1/2)$ (il punto medio tra A e B):
$d=-\Delta x\cdot y_{M}+\Delta y\cdot x_{M}+\Delta x\cdot q$
il quale sarà:
* $d=0$, se il punto giace sulla retta; in questo caso possiamo scegliere in modo indifferente il punto A o il punto B;
* $d<0$, se il punto si trova sopra la retta; in questo caso prendiamo il punto A;
* $d>0$, se il punto si trova sotto la retta; in questo caso prendiamo il punto B.
Nell'algoritmo avremmo necessità ogni volta di sapere se $d$ è positivo o negativo.
Ipotizziamo di aver scelto il punto A, in questo caso il nostro punto di partenza $p$ è $p(x_{1}+1,y_{1})$, e il nostro nuovo punto medio M è $M(x_{1}+2,y_{1}+{1 \over 2})$. Invece il nuovo valore di $d$ è:
$d_{new}=-\Delta x\cdot y_{M}+\Delta y\cdot x_{M}+\Delta x\cdot q=-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q$
Proviamo a sottrarre al nuovo valore di $d$ quello vecchio:
$d_{new}-d_{old}=-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q-\left(-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+1)+\Delta x\cdot q\right)$
Semplificando otteniamo:
$d_{new}-d_{old}=\Delta y$
Quindi abbiamo modo di ricavare il nuovo valore $d$ 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:
* $p(x_{1}+1,y_{1}+1)$;
* $M(x_{1}+2,y_{1}+1+{1 \over 2})=M(x_{1}+2,y_{1}+{3 \over 2})$;
e il nostro nuovo valore $d$:
$d_{new}=-\Delta x\cdot \left(y_{1}+{\frac {3}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q$
Ripetiamo la sottrazione:
$d_{new}-d_{old}=-\Delta x\cdot \left(y_{1}+{\frac {3}{2}}\right)+\Delta y\cdot (x_{1}+2)+\Delta x\cdot q-\left(-\Delta x\cdot \left(y_{1}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{1}+1)+\Delta x\cdot q\right)$
Semplificando otteniamo:
$d_{new}-d_{old}=-\Delta x+\Delta y$
Riassumendo, dato un valore $d_{i}$:
$d_{i+1}=\left\{{\begin{matrix}d_{i}-\Delta x+\Delta y,&{\mbox{se }}d_{i}>0\\d_{i}+\Delta y,&{\mbox{se }}d_{i}<0\end{matrix}}\right.$
Non ci rimane che conoscere il valore $d_{0}$; ricordandoci la formula per calcolare $d$ e prendendo come punto $p$, $p_{0}(x_{0},y_{0})$ ovvero un estremo della retta, abbiamo:
$d=-\Delta x\cdot \left(y_{0}+{\frac {1}{2}}\right)+\Delta y\cdot (x_{0}+1)+\Delta x\cdot q=-\Delta x\cdot y_{0}+\Delta y\cdot x_{0}+\Delta x\cdot q+\left(-{\frac {\Delta x}{2}}+\Delta y\right)$
Nel passaggio abbiamo portato fuori i valori $+1/2$ e $+1$. 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:
$d_{0}=-{\frac {\Delta x}{2}}+\Delta y$

## Algoritmo

Da tutte queste formule possiamo finalmente ricavare l'algoritmo: Dati due punti $p_{1}$ e $p_{2}$, con coordinate (x$_1$,y$_1$) e (x$_2$,y$_2$):
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 $d$:
Abbiamo quindi ottenuto un algoritmo che lavora con numeri interi e semplice da implementare. Nel caso in cui avessimo x$_1$>x$_2$ allora al posto di aumentare $x$ lo diminuiamo mentre i valori decisionali restano uguali, anche se y$_1$>y$_2$ i valori decisionali non variano, in quanto la retta assume pendenza di valore opposto a quello del caso y$_1$<y$_2$ e x$_1$<x$_2$, cambia solo l'incremento della $y$ che invece di aumentare, diminuisce, e il valore decisionale resta invariato, in quanto trattiamo la retta sia se x$_1$>x$_2$ sia se y$_1$>y$_2$ 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:
Con questo abbiamo ottenuto le rette con valore di $|m|<1$. Con valore di $|m|>1$ 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 $y$, 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 $d<0$ in questo caso infatti dobbiamo decidere se aumentare solo $x$ o solo $y$ in base al caso che abbiamo. Nel caso normale si aumenta $x$, nel caso DY>DX si scambiano e si aumenta $y$, da questa logica possiamo ricavare l'algoritmo per linee generali che è il seguente: