Šis algoritms tiek izmantots līnijas skenēšanai. To izstrādāja Bresenham. Tā ir efektīva metode, jo tā ietver tikai veselu skaitļu saskaitīšanu, atņemšanu un reizināšanas darbības. Šīs darbības var veikt ļoti ātri, tāpēc līnijas var ātri ģenerēt.

Izmantojot šo metodi, nākamais atlasītais pikselis ir tas, kuram ir vismazākais attālums no patiesās līnijas.

Metode darbojas šādi:

Pieņemsim pikseli P ₁ '(x ₁ ',un ₁ '), pēc tam atlasiet nākamos pikseļus, strādājot no maija līdz naktij, pa vienam pikseļa stāvoklim horizontālā virzienā virzienā uz P ₂ '(x ₂ ',un ₂ ').

Kad pikselis ir ievadīts, izvēlieties jebkurā solī

Nākamais pikselis ir

1. Vai nu pa labi (līnijas apakšējā robeža)
2. Viena augšdaļa ir pa labi un uz augšu (līnijas augšējā robeža)

Līniju vislabāk tuvināt pēc tiem pikseļiem, kas atrodas vismazākajā attālumā no ceļa starp P ₁ ', P ₂ '.

To izvēlas nākamo starp apakšējo pikseļu S un augšējo pikseļu T.
Ja izvēlēts S
Mums ir x _i+1 =x _i +1 un y _i+1 =y _i
Ja izvēlēts T
Mums ir x _i+1 =x _i +1 un y _i+1 =y _i +1

Taisnes faktiskās y koordinātas pie x = x _i+1 ir
y=mx _i+1 +b

Attālums no S līdz faktiskajai līnijai y virzienā
s = y-y _i

Attālums no T līdz faktiskajai līnijai y virzienā
t = (y _i +1)-y

Tagad apsveriet atšķirību starp šīm divām attāluma vērtībām
s - t

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

Tuvākais pikselis ir S

Kad (s-t) ≧0 ⟹ s

Tuvākais pikselis ir T

Šī atšķirība ir
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Aizstājot m ar un ieviešot lēmumu mainīgo
d _i =△x (s-t)
d _i =△x (2 (x _i +1)+2b-2g _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

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

Varam uzrakstīt lēmuma mainīgo d _i+1 uz nākamo slīdēšanu
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 -un _i )

Tā kā x_(i+1)=x _i +1, mums ir
d _i+1 +d _i =2△y.(x _i +1-x _i )- 2△x(y _i+1 -un _i )

Īpaši gadījumi

Ja izvēlētais pikselis atrodas augšējā pikselī T (t.i., d _i ≧0)⟹ un _i+1 =y _i +1
d _i+1 =d _i +2△y-2△x

Ja izvēlētais pikselis atrodas apakšējā pikselī T (t.i., d _i <0)⟹ y _{i+1=y i
d i+1 =d i +2△ g}

Visbeidzot, mēs aprēķinām d ₁
d ₁ =△x[2m(x ₁ +1)+2b-2g ₁ -1]
d ₁ =△x[2(mx ₁ +b-y ₁ )+2m-1]

Kopš mx ₁ +b-y _i =0 un m = , mums ir
d ₁ =2△y-△x

Priekšrocība:

1. Tas ietver tikai veselu skaitļu aritmētiku, tāpēc tas ir vienkāršs.

2. Tas ļauj izvairīties no punktu dublikātu ģenerēšanas.

3. To var ieviest, izmantojot aparatūru, jo tajā netiek izmantota reizināšana un dalīšana.

4. Tas ir ātrāks salīdzinājumā ar DDA (digitālo diferenciālo analizatoru), jo tas neietver peldošā komata aprēķinus, piemēram, DDA algoritmu.

Trūkums:

1. Šis algoritms ir paredzēts tikai pamata līniju zīmēšanai Inicializēšana nav daļa no Bresenhemas līniju algoritma. Tātad, lai zīmētu gludas līnijas, jums vajadzētu izpētīt citu algoritmu.

Bresenhemas līnijas algoritms:

1. darbība: Sākt algoritmu

2. darbība: Deklarē mainīgo x ₁ ,x ₂ ,un ₁ ,un ₂ ,d,i ₁ ,t.i ₂ ,dx,dy

3. darbība: Ievadiet x vērtību ₁ ,un ₁ ,x ₂ ,un ₂
Kur x ₁ ,un ₁ ir sākuma punkta koordinātas
Un x ₂ ,un ₂ ir beigu punkta koordinātas

4. darbība: Aprēķināt dx = x ₂ -x ₁
Aprēķināt dy = y ₂ -un ₁
Aprēķināt i ₁ =2*tu
Aprēķināt i ₂ =2*(dy-dx)
Aprēķināt d=i ₁ -dx

5. darbība: Apsveriet (x, y) par sākuma punktu un x _beigas kā maksimālo iespējamo x vērtību.
Ja dx <0
Tad x = x ₂
y = y ₂
x _beigas =x ₁
Ja dx > 0
Tad x = x ₁
y = y ₁
x _beigas =x ₂

6. darbība: Ģenerēt punktu pie (x,y) koordinātām.

7. darbība: Pārbaudiet, vai ir izveidota visa rinda.
Ja x > = x _beigas
Stop.

8. darbība: Aprēķināt nākamā pikseļa koordinātas
Ja d <0
Tad d = d + i ₁
Ja d ≧ 0
Tad d = d + i ₂
Palieliniet y = y + 1

9. darbība: Palieliniet x = x + 1

10. darbība: Uzzīmējiet pēdējo (x, y) koordinātu punktu

11. darbība: Pārejiet uz 7. darbību

12. darbība: Algoritma beigas

Piemērs: Līnijas sākuma un beigu pozīcija ir (1, 1) un (8, 5). Atrodiet starppunktus.

Risinājums: x ₁ =1
un ₁ =1
x ₂ =8
un ₂ =5
dx = x ₂ -x ₁ =8-1=7
tu=y ₂ -un ₁ =5-1=4
es ₁ =2* ∆y=2*4=8
es ₂ =2*(∆y-∆x)=2*(4-7)=-6
d = I ₁ -∆x=8-7=1

Programma Bresenhemas līniju zīmēšanas algoritma ieviešanai:

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

Izvade:

Atšķiriet DDA algoritmu un Brezenhemas līnijas algoritmu: