Acest algoritm este utilizat pentru scanarea conversiei unei linii. A fost dezvoltat de Bresenham. Este o metodă eficientă deoarece implică doar operații de adunare, scădere și înmulțire a întregului. Aceste operațiuni pot fi efectuate foarte rapid, astfel încât liniile pot fi generate rapid.

În această metodă, următorul pixel selectat este cel care are cea mai mică distanță față de linia adevărată.

Metoda funcționează după cum urmează:

Să presupunem un pixel P₁'(X₁',și₁'), apoi selectați pixelii următori pe măsură ce lucrăm până la noapte, câte o poziție de pixel pe rând în direcția orizontală spre P₂'(X₂',și₂').

Odată ce un pixel a intrat, alegeți la orice pas

Următorul pixel este

1. Fie cel din dreapta sa (limita inferioară pentru linie)
2. Unul sus, în dreapta și în sus (limită superioară pentru linie)

Linia este cel mai bine aproximată de acei pixeli care se încadrează la cea mai mică distanță de la calea dintre P₁',P₂'.

Pentru a alege următorul dintre pixelul de jos S și pixelul de sus T.
Dacă se alege S
Avem x_i+1=x_i+1 și y_i+1=y_i
Dacă se alege T
Avem x_i+1=x_i+1 și y_i+1=y_i+1

metode string în java

Coordonatele y reale ale dreptei la x = x_i+1este
y=mx_i+1+b

Distanța de la S la linia reală în direcția y
s = y-y_i

Distanța de la T la linia reală în direcția y
t = (y_i+1)-y

Acum luați în considerare diferența dintre aceste 2 valori ale distanței
s - t

Când (s-t)<0 ⟹ s < t< p>

Cel mai apropiat pixel este S

Când (s-t) ≧0 ⟹ s

Cel mai apropiat pixel este T

Această diferență este
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Înlocuind m cu și introducerea variabilei de decizie
d_i=△x (s-t)
d_i=△x (2 (X_i+1)+2b-2y_i-1)
=2△xy_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.y_i+c

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

Putem scrie variabila de decizie d_i+1pentru următoarea alunecare
d_i+1=2△y.x_i+1-2△x.y_i+1+c
d_i+1-d_i=2△y.(x_i+1-X_i)- 2△x(y_i+1-și_i)

Deoarece x_(i+1)=x_i+1, avem
d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-și_i)

Cazuri speciale

np.unic

Dacă pixelul ales este în partea de sus a pixelului T (adică d_i≧0)⟹ și_i+1=y_i+1
d_i+1=d_i+2△y-2△x

Dacă pixelul ales este în partea de jos a pixelului T (adică d_i<0)⟹ y_{i+1=yi
di+1=di+2△y}

În final, calculăm d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

Din moment ce mx₁+b-y_i=0 și m = , avem
d₁=2△y-△x

Avantaj:

1. Implică doar aritmetica întregi, deci este simplă.

2. Evită generarea de puncte duplicat.

3. Poate fi implementat folosind hardware deoarece nu folosește înmulțirea și împărțirea.

4. Este mai rapid în comparație cu DDA (Digital Differential Analyzer) deoarece nu implică calcule în virgulă mobilă, cum ar fi algoritmul DDA.

Dezavantaj:

1. Acest algoritm este destinat numai desenului de linie de bază. Inițializarea nu face parte din algoritmul de linie al lui Bresenham. Așadar, pentru a desena linii netede, ar trebui să vă uitați la un alt algoritm.

Algoritmul liniei lui Bresenham:

Pasul 1: Porniți algoritmul

Pasul 2: Declarați variabila x₁,X₂,și₁,și₂,d,i₁,i₂,dx,dy

inițializator de dicționar c#

Pasul 3: Introduceți valoarea lui x₁,și₁,X₂,și₂
Unde x₁,și₁sunt coordonatele punctului de plecare
Și x₂,și₂sunt coordonatele punctului final

Pasul 4: Calculați dx = x₂-X₁
Calculați dy = y₂-și₁
Calculați i₁=2*tu
Calculați i₂=2*(dy-dx)
Calculați d=i₁-dx

Pasul 5: Considerați (x, y) ca punct de plecare și x_Sfârşitca valoare maximă posibilă a lui x.
Dacă dx<0
Atunci x = x₂
y = y₂
X_Sfârşit=x₁
Dacă dx > 0
Atunci x = x₁
y = y₁
X_Sfârşit=x₂

Pasul 6: Generați punctul la coordonatele (x,y).

Pasul 7: Verificați dacă este generată întreaga linie.
Dacă x > = x_Sfârşit
Stop.

Pasul 8: Calculați coordonatele următorului pixel
Dacă d<0
Atunci d = d + i₁
Dacă d ≧ 0
Atunci d = d + i₂
Crește y = y + 1

Pasul 9: Creșteți x = x + 1

Pasul 10: Desenați un punct cu ultimele coordonate (x, y).

Pasul 11: Treceți la pasul 7

Pasul 12: Sfârșitul algoritmului

Exemplu: Poziția de început și de sfârșit a liniei sunt (1, 1) și (8, 5). Găsiți puncte intermediare.

Soluţie: X₁=1
și₁=1
X₂=8
și₂=5
dx= x₂-X₁=8-1=7
tu=y₂-și₁=5-1=4
eu₁=2* ∆y=2*4=8
eu₂=2*(∆y-∆x)=2*(4-7)=-6
d = I₁-∆x=8-7=1

Program pentru implementarea algoritmului de desen al lui 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; } 

Ieșire:

Faceți diferența dintre algoritmul DDA și algoritmul linie al lui Bresenham: