Severity: Notice
Message: Undefined offset: 1
Filename: infosekolah/leftmenudasboard.php
Line Number: 33
Line Number: 34
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 ) {\displaystyle p_{1}(x_{1},y_{1})} e p 2 ( x 2 , y 2 ) {\displaystyle p_{2}(x_{2},y_{2})} è esprimibile come:
m = y 2 − y 1 x 2 − x 1 = Δ y Δ x {\displaystyle m={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}={\frac {\Delta y}{\Delta x}}}
e che
Δ y = m ∗ Δ x {\displaystyle \Delta y=m*\Delta x}
Da qui possiamo ricavare che per passare da un punto p i ( x i , y i ) {\displaystyle p_{i}(x_{i},y_{i})} ad un punto p i + 1 ( x i + 1 , y i + 1 ) {\displaystyle p_{i+1}(x_{i+1},y_{i+1})} dove x i + 1 = x i + 1 {\displaystyle x_{i+1}=x_{i}+1} , l'aumento di y i + 1 {\displaystyle y_{i+1}} rispetto a y i {\displaystyle y_{i}} dovrà essere Δ y {\displaystyle \Delta y} ovvero:
y i + 1 = y i + Δ y = y i + ( m ∗ Δ x ) = y i + ( m ∗ 1 ) = y i + m {\displaystyle y_{i+1}=y_{i}+\Delta y=y_{i}+(m*\Delta x)=y_{i}+(m*1)=y_{i}+m}
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) ); }
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.
round(y)
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 + Δ x = y i + ( 1 / m ∗ Δ y ) = y i + ( 1 / m ∗ 1 ) = x i + 1 / m {\displaystyle 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:
