Algoritmo DDA

Da Wikipedia, l'enciclopedia libera.

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 e è esprimibile come:

e che

Da qui possiamo ricavare che per passare da un punto ad un punto dove , l'aumento di rispetto a dovrà essere ovvero:

Algoritmo[modifica | modifica wikitesto]

Un esempio di algoritmo può essere il seguente:

dx = x2 - x1;
dy = y2 - y1;
m  = dy / dx;
y = y1;
for x from x1 to x2 {
        y = y + m;
        disegna_il_punto(x, round(y) );
}

Errori[modifica | modifica wikitesto]

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

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:

In questo caso si ottiene il risultato in figura 2:

Figura 2.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica