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₁'(x₁',i₁'), zatim odaberite sljedeće piksele dok radimo na našem svibnju do noći, položaj po jedan piksel u vodoravnom smjeru prema P₂'(x₂',i₂').

Nakon ulaska piksela odaberite bilo koji korak

Sljedeći piksel je

1. Ili onaj s njegove desne strane (donja granica za liniju)
2. 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₁',P₂'.

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+1je
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
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Zamjena m sa 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

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

regresijski izraz u Javi

Možemo napisati varijablu odluke d_i+1za sljedeći slip on
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)

Budući da je x_(i+1)=x_ja+1, imamo
d_i+1+d_ja=2△y.(x_ja+1-x_ja)- 2△x(y_i+1-i_ja)

Posebni slučajevi

Ako je odabrani piksel na vrhu piksel T (tj. d_ja≧0)⟹ i_i+1=y_ja+1
d_i+1=d_ja+2△y-2△x

Ako je odabrani piksel na dnu piksel T (tj. d_ja<0)⟹ y_{i+1=yja
di+1=dja+2△g}

Na kraju izračunavamo d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-g₁)+2m-1]

Budući da je mx₁+b-g_ja=0 i m = , imamo
d₁=2△y-△x

Prednost:

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.

Hendikep:

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.

k algoritam klasteriranja

Algoritam Bresenhamove linije:

Korak 1: Pokreni algoritam

Korak 2: Deklarirajte varijablu x₁,x₂,i₁,i₂,d,i₁,i₂,dx,dy

3. korak: Unesite vrijednost x₁,i₁,x₂,i₂
Gdje je x₁,i₁su koordinate početne točke
i x₂,i₂su koordinate završne točke

Korak 4: Izračunajte dx = x₂-x₁
Izračunajte dy = y₂-i₁
Izračunajte i₁=2*ti
Izračunajte i₂=2*(dy-dx)
Izračunajte d=i₁-dx

Korak 5: Uzmite (x, y) kao početnu točku i x_krajkao najveću moguću vrijednost x.
Ako dx<0
Tada je x = x₂
y = y₂
x_kraj=x₁
Ako je dx > 0
Tada je x = x₁
y = y₁
x_kraj=x₂

Korak 6: Generirajte točku na (x,y) koordinatama.

Korak 7: Provjerite je li generirana cijela linija.
Ako je x > = x_kraj
Stop.

Korak 8: Izračunajte koordinate sljedećeg piksela
Ako d<0
Tada je d = d + i₁
Ako je d ≧ 0
Tada je d = d + i₂
Povećaj y = y + 1

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
i₁=1
x₂=8
i₂=5
dx= x₂-x₁=8-1=7
ti=y₂-i₁=5-1=4
ja₁=2* ∆y=2*4=8
ja₂=2*(∆y-∆x)=2*(4-7)=-6
d = ja₁-∆x=8-7=1

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

Izlaz:

Napravite razliku između DDA algoritma i Bresenhamovog linijskog algoritma: