Algoritmul de linie al lui Bresenham
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 1 '(X 1 ',și 1 '), 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 2 '(X 2 ',și 2 ').
Odată ce un pixel a intrat, alegeți la orice pas
Următorul pixel este
- Fie cel din dreapta sa (limita inferioară pentru linie)
- 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 1 ',P 2 '.
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
Coordonatele y reale ale dreptei la x = x i+1 este
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 Înlocuind m cu Unde c= 2△y+△x (2b-1) Putem scrie variabila de decizie d i+1 pentru următoarea alunecare Deoarece x_(i+1)=x i +1, avem Cazuri speciale Dacă pixelul ales este în partea de sus a pixelului T (adică d i ≧0)⟹ și i+1 =y i +1 Dacă pixelul ales este în partea de jos a pixelului T (adică d i <0)⟹ y i+1=y i În final, calculăm d 1 Din moment ce mx 1 +b-y i =0 și m = 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. 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. Pasul 1: Porniți algoritmul Pasul 2: Declarați variabila x 1 ,X 2 ,și 1 ,și 2 ,d,i 1 ,i 2 ,dx,dy Pasul 3: Introduceți valoarea lui x 1 ,și 1 ,X 2 ,și 2 Pasul 4: Calculați dx = x 2 -X 1 Pasul 5: Considerați (x, y) ca punct de plecare și x Sfârşit ca valoare maximă posibilă a lui x. Pasul 6: Generați punctul la coordonatele (x,y). Pasul 7: Verificați dacă este generată întreaga linie. Pasul 8: Calculați coordonatele următorului pixel 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 =1 Ieșire:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
ș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
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 )
d i+1 +d i =2△y.(x i +1-x i )- 2△x(y i+1 -și i )
d i+1 =d i +2△y-2△x
d i+1 =d i +2△y
d 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
d 1 =△x[2(mx 1 +b-y 1 )+2m-1] , avem
d 1 =2△y-△x Avantaj:
Dezavantaj:
Algoritmul liniei lui Bresenham:
Unde x 1 ,și 1 sunt coordonatele punctului de plecare
Și x 2 ,și 2 sunt coordonatele punctului final
Calculați dy = y 2 -și 1
Calculați i 1 =2*tu
Calculați i 2 =2*(dy-dx)
Calculați d=i 1 -dx
Dacă dx <0
Atunci x = x 2
y = y 2
X Sfârşit =x 1
Dacă dx > 0
Atunci x = x 1
y = y 1
X Sfârşit =x 2
Dacă x > = x Sfârşit
Stop.
Dacă d <0
Atunci d = d + i 1
Dacă d ≧ 0
Atunci d = d + i 2
Crește y = y + 1
și 1 =1
X 2 =8
și 2 =5
dx= x 2 -X 1 =8-1=7
tu=y 2 -și 1 =5-1=4
eu 1 =2* ∆y=2*4=8
eu 2 =2*(∆y-∆x)=2*(4-7)=-6
d = I 1 -∆x=8-7=1
X și d=d+I 1 sau eu 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 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; } 
Faceți diferența dintre algoritmul DDA și algoritmul linie al lui Bresenham:
Algoritmul DDA Algoritmul de linie al lui Bresenham 1. Algoritmul DDA utilizează virgulă mobilă, adică aritmetica reală. 1. Algoritmul lui Bresenham folosește punctul fix, adică aritmetica întregului 2. Algoritmii DDA utilizează operarea înmulțirii și împărțirii 2.Algoritmul de linie al lui Bresenham folosește doar operația de scădere și adunare 3. Algoritmul DDA este mai lent decât Algoritmul de linie al lui Bresenham în desenul liniei, deoarece folosește aritmetică reală (operație în virgulă mobilă) 3. Algoritmul lui Bresenham este mai rapid decât algoritmul DDA în linie, deoarece implică doar adunarea și scăderea în calculul său și folosește doar aritmetică cu numere întregi. 4. Algoritmul DDA nu este precis și eficient ca algoritmul de linie a lui Bresenham. 4. Algoritmul de linie al lui Bresenham este mai precis și mai eficient la algoritmul DDA. 5. Algoritmul DDA poate desena cercuri și curbe, dar nu sunt precise ca algoritmul de linie a lui Bresenham 5. Algoritmul de linie al lui Bresenham poate desena cercuri și curbe cu mai multă precizie decât algoritmul DDA.
