Algoritmo di rasterizzazione di linea

Da Wikipedia, l'enciclopedia libera.

Un algoritmo di rasterizzazione di linea è un algoritmo grafico che si occupa di approssimare una linea o un segmento in una rappresentazione grafica discreta. Esempi di rappresentazioni grafiche discrete possono essere il monitor, composto da migliaia di pixel, o una stampa, con migliaia di punti. La rappresentazione su queste "superfici" richiede un'approssimazione, naturalmente in casi non banali.

In rappresentazioni non discrete, e quindi continue, questo lavoro non si presenta. Esempi di rappresentazioni grafiche continue sono gli oscilloscopi.

Un esempio del problema si può vedere nella figura 0:

Figura 0.

Nello sfondo si vede una griglia, che rappresenta i pixel di un'immagine. Il segmento rosso (dal punto p1 al punto p2) è il segmento che noi vorremmo rasterizzare. Nel lato destro vediamo un esempio di rasterizzazione. Abbiamo evidenziato in nero i pixel che si dovrebbero illuminare per visualizzare il segmento dal punto p1 al punto p2.

Un semplice algoritmo di rasterizzazione di linea[modifica | modifica wikitesto]

Dati due punti p1 e p2, con coordinate (x1,y1) e (x2,y2), possiamo usare il seguente algoritmo:

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

Nel nostro caso abbiamo semplificato l'operazione assumendo che i punti siano ordinati, ovvero che e . L'algoritmo funziona bene con (figura 1.), ma diventa piuttosto lento nei computer, per via dei calcoli in virgola mobile.

Figura 1.

Se abbiamo , i punti della linea diventano "sparsi", come mostrato in figura 2.

Figura 2.

Nel caso limite di viene disegnato un solo punto.

Elenco di algoritmi di rasterizzazione di linee[modifica | modifica wikitesto]

La lista non vuole essere completa:

Rasterizzazione di poligono[modifica | modifica wikitesto]

L'algoritmo di rasterizzazione di poligono è un algoritmo di rasterizzazione che si occupa di convertire un poligono definito attraverso i suoi vertici in un'immagine raster (o bitmap).

Il problema più semplice è quello di convertire un poligono vuoto, ovvero nel quale sono definiti solo i lati. In questo caso si può fare un uso ricorsivo di un algoritmo di rasterizzazione di linea, per ogni lato del poligono.

Il problema si complica nel caso di poligoni pieni. Nella figura 1 possiamo vedere alcuni esempi di poligono:

Figura 1.

In questi casi abbiamo a disposizione i seguenti algoritmi:

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