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₁'(X₁',E₁'), quindi seleziona i pixel successivi mentre lavoriamo fino alla notte, una posizione di pixel alla volta nella direzione orizzontale verso P₂'(X₂',E₂').

Una volta inserito un pixel, scegli in qualsiasi passaggio

Il pixel successivo è

1. O quello alla sua destra (limite inferiore per la linea)
2. 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₁',P₂'.

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

metodi stringa in Java

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

metodi di arraylist

Quando (s-t)<0 ⟹ s < t< p>

Il pixel più vicino è S

Quando (s-t) ≧0 ⟹ s

Il pixel più vicino è T

Questa differenza è
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Sostituendo m con 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

Dove c= 2△y+△x (2b-1)

Possiamo scrivere la variabile decisionale d_io+1per il prossimo slip on
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)

Poiché x_(i+1)=x_io+1, abbiamo
D_io+1+d_io=2△y.(x_io+1-x_io)- 2△x(y_io+1-E_io)

Casi speciali

Se il pixel scelto è in alto, il pixel T (cioè d_io≧0)⟹ e_io+1=y_io+1
D_io+1=d_io+2△y-2△x

Se il pixel scelto si trova nel pixel inferiore T (ad esempio, d_io<0)⟹ y_{io+1=yio
Dio+1=dio+2△a}

Infine calcoliamo d₁
D₁=△x[2m(x₁+1)+2b-2y₁-1]
D₁=△x[2(mx₁+a-a₁)+2m-1]

Dal mx₁+a-a_io=0 e m = , abbiamo
D₁=2△y-△x

Vantaggio:

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.

Svantaggio:

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.

Java comparabile

Algoritmo della linea di Bresenham:

Passo 1: Avvia algoritmo

Passo 2: Dichiarare la variabile x₁,X₂,E₁,E₂,d,i₁,io₂,dx,dy

Passaggio 3: Immettere il valore di x₁,E₁,X₂,E₂
Dove x₁,E₁sono le coordinate del punto di partenza
E x₂,E₂sono le coordinate del punto finale

Passaggio 4: Calcola dx = x₂-X₁
Calcola dy = y₂-E₁
Calcola i₁=2*tu
Calcola i₂=2*(dy-dx)
Calcola d=i₁-dx

Passaggio 5: Considera (x, y) come punto di partenza e x_FINEcome massimo valore possibile di x.
Se dx<0
Allora x = x₂
y = y₂
X_FINE=x₁
Se dx > 0
Allora x = x₁
y = y₁
X_FINE=x₂

Passaggio 6: Genera punto alle coordinate (x,y).

10 di 100,00

Passaggio 7: Controlla se viene generata l'intera riga.
Se x > = x_FINE
Fermare.

Passaggio 8: Calcola le coordinate del pixel successivo
Se d<0
Allora d = d + i₁
Se d ≧ 0
Allora d = d + i₂
Incremento y = y + 1

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
E₁=1
X₂=8
E₂=5
dx=x₂-X₁=8-1=7
tu=sì₂-E₁=5-1=4
IO₁=2* ∆y=2*4=8
IO₂=2*(∆y-∆x)=2*(4-7)=-6
d = io₁-∆x=8-7=1

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; } 

Produzione:

Distinguere tra l'algoritmo DDA e l'algoritmo della linea di Bresenham: