Coding - Algoritmo per le linee di Brensenham 1

Alessandra Peroni

Algoritmo per le linee di Brensenham

Una tecnica che il computer usa per sapere se un pixel deve essere colorato è l’Algoritmo per le linee di

Brensenham.

Qui l’algoritmo in forma semplificata.

Tratto da http://csunplugged.org/wp-content/uploads/2014/12/Lines.pdf

Per linee con ∆y < ∆x

Siano date le coordinate X,Y di due punti I e F, dove I (inizio) è il punto di partenza e F (fine) quello di arrivo.

Regole

Si colora 1 pixel per ogni colonna.

Si determina se andare SU o GIU di una riga:

Si va a destra o a sinistra a seconda della posizione relativa di I e F.

Se pendenza positiva (dal basso all’alto), vado SU

Se pendenza negativa (dall’alto al basso), vado GIU

Si determina se andare a destra o a sinistra:

Si va a destra o a sinistra a seconda della posizione relativa di I e F.

Coding - Algoritmo per le linee di Brensenham 2

Alessandra Peroni

Procedimento

Su un foglio scrivere

le coordinate dei punti I e F

il valore SU o GIU determinato

il valore SIN o DX determinato

Determinare e scrivere i tre valori:

A = 2 x (valore assoluto della differenza tra le coordinate Y dei punti)

B = A - 2 x (valore assoluto della differenza tra le coordinate X dei punti)

P = A - (valore assoluto della differenza tra le coordinate X dei punti)

Riempi il primo pixel I.

Per ogni posizione lungo l’asse X, fai:

- se P < 0 allora colora il pixel nella prossima colonna DX o SIN e sulla stessa riga. Poi calcola P= P + A

- se P >=0 allora colora il pixel nella prossima colonna DX o SIN e sulla riga SU o GIU. Poi calcola P= P + B

Ricomincia da finché raggiungi la fine della linea F.

Esercizi

Provare a tracciare le seguenti linee:

I(18,6) e F(11,3)

I(5,14) e F(11,11)

I(17,13) e F(10,17)

I(2,3) e F(11,8)

Coding - Algoritmo per le linee di Brensenham 3

Alessandra Peroni

Per linee con ∆y > ∆x

Siano date le coordinate (X,Y) di due punti I e F, dove I (inizio) è il punto di partenza e F (fine) quello di

arrivo.

Regole

Si colora 1 pixel per ogni riga.

Si determina se andare SU o GIU di una riga:

Si va a destra o a sinistra a seconda della posizione relativa di I e F.

Se pendenza positiva (dal basso all’alto), vado SU

Se pendenza negativa (dall’alto al basso), vado GIU

Si determina se andare a destra o a sinistra:

Si va a destra o a sinistra a seconda della posizione relativa di I e F.

Coding - Algoritmo per le linee di Brensenham 4

Alessandra Peroni

Procedimento

Su un foglio scrivere

le coordinate dei punti I e F

il valore SU o GIU determinato

il valore SIN o DX determinato

Determinare e scrivere i tre valori:

A = 2 x (valore assoluto della differenza tra le coordinate X dei punti)

B = A - 2 x (valore assoluto della differenza tra le coordinate Y dei punti)

P = A - (valore assoluto della differenza tra le coordinate Y dei punti)

Riempi il primo pixel I.

Per ogni posizione lungo l’asse Y, fai:

- se P < 0 allora colora il pixel nella prossima riga SU o GIU e sulla stessa colonna. Poi calcola P= P + A

- se P >=0 allora colora il pixel nella prossima riga SU o GIU e sulla colonna DX o SIN. Poi calcola P= P + B

Ricomincia da finché raggiungi la fine della linea F.

Esercizi

Provare a tracciare le seguenti linee:

I(2,9) e F(5,16)

I(8,16) e F(12,9)

Coding - Algoritmo per le linee di Brensenham 5

Alessandra Peroni