Bresenhamov linijski algoritam
Ovaj se algoritam koristi za skeniranje pretvaranja linije. Razvio ga je Bresenham. To je učinkovita metoda jer uključuje samo cjelobrojne operacije zbrajanja, oduzimanja i množenja. Ove se operacije mogu izvesti vrlo brzo tako da se linije mogu brzo generirati.
U ovoj metodi, sljedeći odabrani piksel je onaj koji ima najmanju udaljenost od prave linije.
Metoda funkcionira na sljedeći način:
Pretpostavimo piksel P 1 '(x 1 ',i 1 '), zatim odaberite sljedeće piksele dok radimo na našem svibnju do noći, položaj po jedan piksel u vodoravnom smjeru prema P 2 '(x 2 ',i 2 ').
Nakon ulaska piksela odaberite bilo koji korak
Sljedeći piksel je
- Ili onaj s njegove desne strane (donja granica za liniju)
- Jedan je gore desno i gore (gornja granica za liniju)
Linija se najbolje aproksimira onim pikselima koji padaju na najmanju udaljenost od putanje između P 1 ',P 2 '.
Za odabir sljedećeg između donjeg piksela S i gornjeg piksela T.
Ako se izabere S
Imamo x i+1 =x ja +1 i y i+1 =y ja
Ako se izabere T
Imamo x i+1 =x ja +1 i y i+1 =y ja +1
Stvarne y koordinate pravca na x = x i+1 je
y=mx i+1 +b
Udaljenost od S do stvarne linije u smjeru y
s = y-y ja
Udaljenost od T do stvarne crte u smjeru y
t = (y ja +1)-y
Sada razmotrite razliku između ove dvije vrijednosti udaljenosti
s - t
Kada (s-t) <0 ⟹ s < t < p>
Najbliži piksel je S
Kada je (s-t) ≧0 ⟹ s Najbliži piksel je T Ova razlika je Zamjena m sa Gdje je c= 2△y+△x (2b-1) Možemo napisati varijablu odluke d i+1 za sljedeći slip on Budući da je x_(i+1)=x ja +1, imamo Posebni slučajevi Ako je odabrani piksel na vrhu piksel T (tj. d ja ≧0)⟹ i i+1 =y ja +1 Ako je odabrani piksel na dnu piksel T (tj. d ja <0)⟹ y i+1=y ja Na kraju izračunavamo d 1 Budući da je mx 1 +b-g ja =0 i m = 1. Uključuje samo cjelobrojnu aritmetiku, tako da je jednostavan. 2. Izbjegava stvaranje duplih točaka. 3. Može se implementirati pomoću hardvera jer ne koristi množenje i dijeljenje. 4. Brži je u usporedbi s DDA (Digitalni diferencijalni analizator) jer ne uključuje izračune s pomičnim zarezom poput DDA algoritma. 1. Ovaj algoritam je namijenjen samo za osnovno crtanje linija. Inicijalizacija nije dio Bresenhamovog algoritma linija. Dakle, da biste crtali glatke linije, trebali biste potražiti drugačiji algoritam. Korak 1: Pokreni algoritam Korak 2: Deklarirajte varijablu x 1 ,x 2 ,i 1 ,i 2 ,d,i 1 ,i 2 ,dx,dy 3. korak: Unesite vrijednost x 1 ,i 1 ,x 2 ,i 2 Korak 4: Izračunajte dx = x 2 -x 1 Korak 5: Uzmite (x, y) kao početnu točku i x kraj kao najveću moguću vrijednost x. Korak 6: Generirajte točku na (x,y) koordinatama. Korak 7: Provjerite je li generirana cijela linija. Korak 8: Izračunajte koordinate sljedećeg piksela Korak 9: Povećaj x = x + 1 Korak 10: Nacrtajte točku najnovijih (x, y) koordinata Korak 11: Idite na korak 7 Korak 12: Kraj algoritma Primjer: Početna i završna pozicija linije su (1, 1) i (8, 5). Pronađite međutočke. Riješenje: x 1 =1 Izlaz:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
i uvođenje varijable odlučivanja
d ja =△x (s-t)
d ja =△x (2 (x ja +1)+2b-2y ja -1)
=2△xy ja -2△y-1△x.2b-2y ja △x-△x
d ja =2△y.x ja -2△x.y ja +c
d i+1 =2△y.x i+1 -2△x.y i+1 +c
d i+1 -d ja =2△y.(x i+1 -x ja )- 2△x(y i+1 -i ja )
d i+1 +d ja =2△y.(x ja +1-x ja )- 2△x(y i+1 -i ja )
d i+1 =d ja +2△y-2△x
d i+1 =d ja +2△g
d 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
d 1 =△x[2(mx 1 +b-g 1 )+2m-1] , imamo
d 1 =2△y-△x Prednost:
Hendikep:
Algoritam Bresenhamove linije:
Gdje je x 1 ,i 1 su koordinate početne točke
i x 2 ,i 2 su koordinate završne točke
Izračunajte dy = y 2 -i 1
Izračunajte i 1 =2*ti
Izračunajte i 2 =2*(dy-dx)
Izračunajte d=i 1 -dx
Ako dx <0
Tada je x = x 2
y = y 2
x kraj =x 1
Ako je dx > 0
Tada je x = x 1
y = y 1
x kraj =x 2
Ako je x > = x kraj
Stop.
Ako d <0
Tada je d = d + i 1
Ako je d ≧ 0
Tada je d = d + i 2
Povećaj y = y + 1
i 1 =1
x 2 =8
i 2 =5
dx= x 2 -x 1 =8-1=7
ti=y 2 -i 1 =5-1=4
ja 1 =2* ∆y=2*4=8
ja 2 =2*(∆y-∆x)=2*(4-7)=-6
d = ja 1 -∆x=8-7=1
x i d=d+I 1 ili ja 2 1 1 d+ja 2 =1+(-6)=-5 2 2 d+ja 1 =-5+8=3 3 2 d+ja 2 =3+(-6)=-3 4 3 d+ja 1 =-3+8=5 5 3 d+ja 2 =5+(-6)=-1 6 4 d+ja 1 =-1+8=7 7 4 d+ja 2 =7+(-6)=1 8 5 Program za implementaciju Bresenhamovog algoritma crtanja linija:
#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; } 
Napravite razliku između DDA algoritma i Bresenhamovog linijskog algoritma:
DDA algoritam Bresenhamov linijski algoritam 1. DDA algoritam koristi pokretni zarez, tj. stvarnu aritmetiku. 1. Bresenhamov linijski algoritam koristi fiksnu točku, tj. aritmetiku cijelog broja 2. DDA algoritmi koriste množenje i dijeljenje 2.Bresenhamov linijski algoritam koristi samo oduzimanje i zbrajanje 3. DDA algoritam je sporiji od Bresenhamovog linijskog algoritma u crtanju linija jer koristi stvarnu aritmetiku (operacija s pomičnim zarezom) 3. Bresenhamov algoritam je brži od DDA algoritma jer uključuje samo zbrajanje i oduzimanje u svom izračunu i koristi samo aritmetiku cijelog broja. 4. DDA algoritam nije točan i učinkovit kao Bresenhamov linijski algoritam. 4. Bresenhamov linijski algoritam točniji je i učinkovitiji kod DDA algoritma. 5. DDA algoritam može nacrtati krug i krivulje, ali nije točan kao Bresenhamov linijski algoritam 5. Bresenhamov linijski algoritam može crtati krug i krivulje točnije od DDA algoritma.
