Š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.

turbo c++ lejupielāde

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+1ir
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+1uz 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=yi
di+1=di+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_beigaskā 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.

lateksa matrica

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: