Algoritmo della linea di Bresenham
Questo algoritmo viene utilizzato per convertire la scansione di una linea. È stato sviluppato da Bresenham. È un metodo efficiente perché prevede solo operazioni di addizione, sottrazione e moltiplicazione di numeri interi. Queste operazioni possono essere eseguite molto rapidamente in modo che le linee possano essere generate rapidamente.
In questo metodo, il pixel successivo selezionato è quello che ha la distanza minore dalla linea reale.
Il metodo funziona come segue:
Assumi un pixel P 1 '(X 1 ',E 1 '), quindi seleziona i pixel successivi mentre lavoriamo fino alla notte, una posizione di pixel alla volta nella direzione orizzontale verso P 2 '(X 2 ',E 2 ').
Una volta inserito un pixel, scegli in qualsiasi passaggio
Il pixel successivo è
- O quello alla sua destra (limite inferiore per la linea)
- Uno in alto a destra e in alto (limite superiore per la linea)
La linea viene approssimata meglio da quei pixel che cadono alla minima distanza dal percorso tra P 1 ',P 2 '.
Per sceglie quello successivo tra il pixel inferiore S e il pixel superiore T.
Se si sceglie S
Abbiamo x io+1 =x io +1 e y io+1 =y io
Se si sceglie T
Abbiamo x io+1 =x io +1 e y io+1 =y io +1
Le coordinate y effettive della linea in x = x io+1 È
y=mx io+1 +b
La distanza da S alla linea effettiva nella direzione y
s = aa io
La distanza da T alla linea effettiva nella direzione y
t = (y io +1)-y
Consideriamo ora la differenza tra questi 2 valori di distanza
s - t
Quando (s-t) <0 ⟹ s < t < p>
Il pixel più vicino è S
Quando (s-t) ≧0 ⟹ s Il pixel più vicino è T Questa differenza è Sostituendo m con Dove c= 2△y+△x (2b-1) Possiamo scrivere la variabile decisionale d io+1 per il prossimo slip on Poiché x_(i+1)=x io +1, abbiamo Casi speciali Se il pixel scelto è in alto, il pixel T (cioè d io ≧0)⟹ e io+1 =y io +1 Se il pixel scelto si trova nel pixel inferiore T (ad esempio, d io <0)⟹ y io+1=y io Infine calcoliamo d 1 Dal mx 1 +a-a io =0 e m = 1. Implica solo l'aritmetica dei numeri interi, quindi è semplice. 2. Evita la generazione di punti duplicati. 3. Può essere implementato utilizzando l'hardware perché non utilizza moltiplicazioni e divisioni. 4. È più veloce rispetto a DDA (Digital Differential Analyser) perché non prevede calcoli in virgola mobile come l'algoritmo DDA. 1. Questo algoritmo è pensato solo per il disegno di linee di base. L'inizializzazione non fa parte dell'algoritmo delle linee di Bresenham. Quindi, per disegnare linee morbide, dovresti esaminare un algoritmo diverso. Passo 1: Avvia algoritmo Passo 2: Dichiarare la variabile x 1 ,X 2 ,E 1 ,E 2 ,d,i 1 ,io 2 ,dx,dy Passaggio 3: Immettere il valore di x 1 ,E 1 ,X 2 ,E 2 Passaggio 4: Calcola dx = x 2 -X 1 Passaggio 5: Considera (x, y) come punto di partenza e x FINE come massimo valore possibile di x. Passaggio 6: Genera punto alle coordinate (x,y). Passaggio 7: Controlla se viene generata l'intera riga. Passaggio 8: Calcola le coordinate del pixel successivo Passaggio 9: Incremento x = x + 1 Passaggio 10: Disegna un punto delle ultime coordinate (x, y). Passaggio 11: Vai al passaggio 7 Passaggio 12: Fine dell'algoritmo Esempio: Le posizioni iniziale e finale della linea sono (1, 1) e (8, 5). Trova punti intermedi. Soluzione: X 1 =1 Produzione:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
e introducendo la variabile decisionale
D io =△x (s-t)
D io =△x(2 (X io +1)+2b-2y io -1)
=2△xy io -2△y-1△x.2b-2y io △x-△x
D io =2△y.x io -2△x.a io +c
D io+1 =2△y.x io+1 -2△x.a io+1 +c
D io+1 -D io =2△y.(x io+1 -X io )- 2△x(y io+1 -E io )
D io+1 +d io =2△y.(x io +1-x io )- 2△x(y io+1 -E io )
D io+1 =d io +2△y-2△x
D io+1 =d io +2△a
D 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
D 1 =△x[2(mx 1 +a-a 1 )+2m-1] , abbiamo
D 1 =2△y-△x Vantaggio:
Svantaggio:
Algoritmo della linea di Bresenham:
Dove x 1 ,E 1 sono le coordinate del punto di partenza
E x 2 ,E 2 sono le coordinate del punto finale
Calcola dy = y 2 -E 1
Calcola i 1 =2*tu
Calcola i 2 =2*(dy-dx)
Calcola d=i 1 -dx
Se dx <0
Allora x = x 2
y = y 2
X FINE =x 1
Se dx > 0
Allora x = x 1
y = y 1
X FINE =x 2
Se x > = x FINE
Fermare.
Se d <0
Allora d = d + i 1
Se d ≧ 0
Allora d = d + i 2
Incremento y = y + 1
E 1 =1
X 2 =8
E 2 =5
dx=x 2 -X 1 =8-1=7
tu=sì 2 -E 1 =5-1=4
IO 1 =2* ∆y=2*4=8
IO 2 =2*(∆y-∆x)=2*(4-7)=-6
d = io 1 -∆x=8-7=1
X E d=d+I 1 o io 2 1 1 d+I 2 =1+(-6)=-5 2 2 d+I 1 =-5+8=3 3 2 d+I 2 =3+(-6)=-3 4 3 d+I 1 =-3+8=5 5 3 d+I 2 =5+(-6)=-1 6 4 d+I 1 =-1+8=7 7 4 d+I 2 =7+(-6)=1 8 5 Programma per implementare l'algoritmo di disegno al tratto di Bresenham:
#include #include void drawline(int x0, int y0, int x1, int y1) { int dx, dy, p, x, y; dx=x1-x0; dy=y1-y0; x=x0; y=y0; p=2*dy-dx; while(x=0) { putpixel(x,y,7); y=y+1; p=p+2*dy-2*dx; } else { putpixel(x,y,7); p=p+2*dy;} x=x+1; } } int main() { int gdriver=DETECT, gmode, error, x0, y0, x1, y1; initgraph(&gdriver, &gmode, 'c:\turboc3\bgi'); printf('Enter co-ordinates of first point: '); scanf('%d%d', &x0, &y0); printf('Enter co-ordinates of second point: '); scanf('%d%d', &x1, &y1); drawline(x0, y0, x1, y1); return 0; } 
Distinguere tra l'algoritmo DDA e l'algoritmo della linea di Bresenham:
Algoritmo DDA Algoritmo della linea di Bresenham 1. L'algoritmo DDA utilizza la virgola mobile, ovvero l'aritmetica reale. 1. L'algoritmo della linea di Bresenham utilizza il punto fisso, ovvero l'aritmetica dei numeri interi 2. Gli algoritmi DDA utilizzano la moltiplicazione e la divisione nelle sue operazioni 2.L'algoritmo della linea di Bresenham utilizza solo la sottrazione e l'addizione 3. L'algoritmo DDA è lento rispetto all'algoritmo Line di Bresenham nel disegno al tratto perché utilizza l'aritmetica reale (operazione in virgola mobile) 3. L'algoritmo di Bresenham è più veloce dell'algoritmo DDA in linea perché prevede solo addizioni e sottrazioni nel calcolo e utilizza solo l'aritmetica dei numeri interi. 4. L'algoritmo DDA non è accurato ed efficiente come l'algoritmo della linea di Bresenham. 4. L'algoritmo della linea di Bresenham è più accurato ed efficiente nell'algoritmo DDA. 5.L'algoritmo DDA può disegnare cerchi e curve ma non è accurato come l'algoritmo della linea di Bresenham 5. L'algoritmo della linea di Bresenham può disegnare cerchi e curve con maggiore precisione dell'algoritmo DDA.
