Ta algoritem se uporablja za skeniranje pretvorbe vrstice. Razvil ga je Bresenham. Je učinkovita metoda, ker vključuje samo celoštevilske operacije seštevanja, odštevanja in množenja. Te operacije je mogoče izvesti zelo hitro, tako da je mogoče hitro ustvariti vrstice.

Pri tej metodi je naslednji izbrani piksel tisti, ki je najmanj oddaljen od prave črte.

Metoda deluje na naslednji način:

Predpostavimo slikovno piko P₁'(x₁',in₁'), nato izberite naslednje slikovne pike, ko delamo do noči, eno slikovno piko naenkrat v vodoravni smeri proti P₂'(x₂',in₂').

Ko je piksel vstavljen, izberite na katerem koli koraku

Naslednji piksel je

1. Bodisi tista na njegovi desni (spodnja meja za črto)
2. Eden zgoraj desno in navzgor (zgornja meja za črto)

Črto najbolje približajo tiste slikovne pike, ki so najmanj oddaljene od poti med P₁',P₂'.

Izbere naslednjo med spodnjo slikovno piko S in zgornjo slikovno piko T.
Če je izbran S
Imamo x_i+1=x_jaz+1 in y_i+1=y_jaz
Če je izbran T
Imamo x_i+1=x_jaz+1 in y_i+1=y_jaz+1

Dejanske koordinate y premice pri x = x_i+1je
y=mx_i+1+b

Razdalja od S do dejanske črte v smeri y
s = y-y_jaz

Razdalja od T do dejanske črte v smeri y
t = (y_jaz+1)-y

Zdaj razmislite o razliki med tema dvema vrednostma razdalje
s - t

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

Najbližji piksel je S

Ko je (s-t) ≧0 ⟹ s

Najbližji piksel je T

Ta razlika je
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Zamenjava m z in uvedbo odločitvene spremenljivke
d_jaz=△x (s-t)
d_jaz=△x (2 (x_jaz+1)+2b-2y_jaz-1)
=2△xy_jaz-2△y-1△x.2b-2y_jaz△x-△x
d_jaz=2△y.x_jaz-2△x.y_jaz+c

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

Odločitveno spremenljivko lahko zapišemo d_i+1za naslednji zdrs naprej
d_i+1=2△y.x_i+1-2△x.y_i+1+c
d_i+1-d_jaz=2△y.(x_i+1-x_jaz)- 2△x(y_i+1-in_jaz)

Ker je x_(i+1)=x_jaz+1, imamo
d_i+1+d_jaz=2△y.(x_jaz+1-x_jaz)- 2△x(y_i+1-in_jaz)

chmod 755

Posebni primeri

Če je izbrani piksel na vrhu, je piksel T (tj. d_jaz≧0)⟹ in_i+1=y_jaz+1
d_i+1=d_jaz+2△y-2△x

Če je izbrana slikovna pika na dnu slikovne pike T (tj. d_jaz<0)⟹ y_{i+1=yjaz
di+1=djaz+2△y}

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

Ker je mx₁+b-y_jaz=0 in m = , imamo
d₁=2△y-△x

Prednost:

1. Vključuje samo aritmetiko celih števil, zato je preprosta.

2. Izogne ​​se ustvarjanju podvojenih točk.

3. Lahko se izvede s strojno opremo, ker ne uporablja množenja in deljenja.

4. Je hitrejši v primerjavi z DDA (digitalni diferencialni analizator), ker ne vključuje izračunov s plavajočo vejico, kot je algoritem DDA.

Slabost:

1. Ta algoritem je namenjen le osnovnemu risanju črt. Inicializacija ni del Bresenhamovega algoritma črt. Torej, če želite risati gladke črte, bi morali pogledati v drug algoritem.

Algoritem Bresenhamove črte:

Korak 1: Zaženi algoritem

2. korak: Deklarirajte spremenljivko x₁,x₂,in₁,in₂,d,i₁,jaz₂,dx,dy

java dvojno v niz

3. korak: Vnesite vrednost x₁,in₁,x₂,in₂
Kjer je x₁,in₁so koordinate začetne točke
In x₂,in₂so koordinate končne točke

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

5. korak: Upoštevajte (x, y) kot izhodišče in x_koneckot največjo možno vrednost x.
Če dx<0
Potem je x = x₂
y = y₂
x_konec=x₁
Če je dx > 0
Potem je x = x₁
y = y₁
x_konec=x₂

6. korak: Ustvari točko na (x,y) koordinatah.

7. korak: Preverite, ali je ustvarjena cela vrstica.
Če je x > = x_konec
Stop.

8. korak: Izračunajte koordinate naslednje piksle
Če d<0
Potem je d = d + i₁
Če je d ≧ 0
Potem je d = d + i₂
Povečaj y = y + 1

9. korak: Povečaj x = x + 1

10. korak: Narišite točko zadnje (x, y) koordinate

11. korak: Pojdite na 7. korak

12. korak: Konec algoritma

primer: Začetni in končni položaj črte sta (1, 1) in (8, 5). Poiščite vmesne točke.

rešitev: x₁=1
in₁=1
x₂=8
in₂=5
dx= x₂-x₁=8-1=7
ti=y₂-in₁=5-1=4
jaz₁=2* ∆y=2*4=8
jaz₂=2*(∆y-∆x)=2*(4-7)=-6
d = jaz₁-∆x=8-7=1

Program za implementacijo Bresenhamovega algoritma za risanje črt:

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

Izhod:

Razlikujte med algoritmom DDA in algoritmom Bresenhamove črte: