Algoritmo DDA
# Algoritmo DDA

L'algoritmo DDA (digital differential analyzer) è un algoritmo di rasterizzazione di linea.

L'algoritmo DDA parte dall'osservazione che la pendenza di una retta passante per i punti $p_{1}(x_{1},y_{1})$ e $p_{2}(x_{2},y_{2})$ è esprimibile come:

$m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}={\frac {\Delta y}{\Delta x}}$

e che

$\Delta y=m*\Delta x$

Da qui possiamo ricavare che per passare da un punto $p_{i}(x_{i},y_{i})$ ad un punto $p_{i+1}(x_{i+1},y_{i+1})$ dove $x_{i+1}=x_{i}+1$, l'aumento di $y_{i+1}$ rispetto a $y_{i}$ dovrà essere $\Delta y$ ovvero:

$y_{i+1}=y_{i}+\Delta y=y_{i}+(m*\Delta x)=y_{i}+(m*1)=y_{i}+m$

## Algoritmo

Un esempio di algoritmo può essere il seguente:

## Errori

Per grandi pendenze l'algoritmo produce uno spargimento di punti come in figura 1.

Come vediamo è presente un'operazione di arrotondamento ( round(y) ) e le operazioni sono eseguite in virgola mobile per via del valore m; tutti elementi costosi dal punto di vista computazionale.

In questo caso infatti notiamo che m ha un valore di circa 4.2, quindi per ogni incremento sull'asse x di valore 1, sull'asse y incrementeremo di 4 pixels circa. Un accorgimento per correggere questo problema è quello di invertire i parametri, ovvero non ricercheremo più la y ma la x:

$x_{i+1}=x_{i}+\Delta x=y_{i}+(1/m*\Delta y)=y_{i}+(1/m*1)=x_{i}+1/m$

In questo caso si ottiene il risultato in figura 2:

