Denne algoritmen brukes til å konvertere en linje. Den ble utviklet av Bresenham. Det er en effektiv metode fordi den bare involverer heltallsaddisjon, subtraksjoner og multiplikasjonsoperasjoner. Disse operasjonene kan utføres veldig raskt slik at linjer kan genereres raskt.

I denne metoden er neste piksel valgt den som har minst avstand fra sann linje.

Metoden fungerer som følger:

Anta en piksel P ₁ '(x ₁ ',og ₁ '), velg deretter påfølgende piksler mens vi jobber vår mai til natten, én pikselposisjon om gangen i horisontal retning mot P ₂ '(x ₂ ',og ₂ ').

Velg en gang en piksel i hvilket som helst trinn

Neste piksel er

1. Enten den til høyre (nedre grense for linjen)
2. En øverst til høyre og oppover (øvre grense for linjen)

Linjen tilnærmes best av de pikslene som faller minst avstand fra banen mellom P ₁ ',P ₂ '.

To velger den neste mellom den nederste piksel S og topppiksel T.
Hvis S velges
Vi har x _i+1 =x _Jeg +1 og y _i+1 =y _Jeg
Hvis T velges
Vi har x _i+1 =x _Jeg +1 og y _i+1 =y _Jeg +1

De faktiske y-koordinatene til linjen ved x = x _i+1 er
y=mx _i+1 +b

Avstanden fra S til den faktiske linjen i y-retning
s = å-å _Jeg

Avstanden fra T til den faktiske linjen i y-retning
t = (y _Jeg +1)-y

Vurder nå forskjellen mellom disse 2 avstandsverdiene
s - t

Når (s-t) <0 ⟹ s < t < p>

Den nærmeste pikselen er S

Når (s-t) ≧0 ⟹ s

Den nærmeste pikselen er T

Denne forskjellen er
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Erstatter m med og introdusere beslutningsvariabel
d _Jeg =△x (s-t)
d _Jeg =△x (2 (x _Jeg +1)+2b-2y _Jeg -1)
=2△xy _Jeg -2△y-1△x.2b-2y _Jeg △x-△x
d _Jeg =2△y.x _Jeg -2△x.y _Jeg +c

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

Vi kan skrive beslutningsvariabelen d _i+1 for neste slip on
d _i+1 =2△y.x _i+1 -2△x.y _i+1 +c
d _i+1 -d _Jeg =2△y.(x _i+1 -x _Jeg )- 2△x(y _i+1 -og _Jeg )

Siden x_(i+1)=x _Jeg +1, det har vi
d _i+1 +d _Jeg =2△y.(x _Jeg +1-x _Jeg )- 2△x(y _i+1 -og _Jeg )

Spesielle tilfeller

Hvis valgt piksel er på topppiksel T (dvs. d _Jeg ≧0)⟹ og _i+1 =y _Jeg +1
d _i+1 =d _Jeg +2△y-2△x

Hvis valgt piksel er nederst piksel T (dvs. d _Jeg <0)⟹ y _{i+1=y Jeg
d i+1 =d Jeg +2△y}

Til slutt beregner vi d ₁
d ₁ =△x[2m(x ₁ +1)+2b-2y ₁ -1]
d ₁ =△x[2(mx ₁ +b-y ₁ )+2m-1]

Siden mx ₁ +b-y _Jeg =0 og m = , vi har
d ₁ =2△y-△x

Fordel:

1. Det involverer bare heltallsaritmetikk, så det er enkelt.

2. Det unngår generering av dupliserte punkter.

3. Det kan implementeres ved hjelp av maskinvare fordi det ikke bruker multiplikasjon og divisjon.

4. Det er raskere sammenlignet med DDA (Digital Differential Analyzer) fordi det ikke involverer flytepunktberegninger som DDA-algoritmen.

Ulempe:

1. Denne algoritmen er kun ment for grunnleggende linjetegning Initialisering er ikke en del av Bresenhams linjealgoritme. Så for å tegne jevne linjer, bør du se nærmere på en annen algoritme.

Bresenhams linjealgoritme:

Trinn 1: Start algoritme

Steg 2: Deklarer variabel x ₁ ,x ₂ ,og ₁ ,og ₂ ,d,i ₁ ,Jeg ₂ ,dx,dy

Trinn 3: Skriv inn verdien av x ₁ ,og ₁ ,x ₂ ,og ₂
Hvor x ₁ ,og ₁ er koordinater for utgangspunktet
Og x ₂ ,og ₂ er koordinatene til sluttpunktet

Trinn 4: Regn ut dx = x ₂ -x ₁
Regn ut dy = y ₂ -og ₁
Beregn i ₁ =2*du
Beregn i ₂ =2*(dy-dx)
Regn ut d=i ₁ -dx

Trinn 5: Betrakt (x, y) som utgangspunkt og x _slutt som maksimal mulig verdi av x.
Hvis dx <0
Da er x = x ₂
y = y ₂
x _slutt =x ₁
Hvis dx > 0
Da er x = x ₁
y = y ₁
x _slutt =x ₂

Trinn 6: Generer punkt ved (x,y)koordinater.

Trinn 7: Sjekk om hele linjen er generert.
Hvis x > = x _slutt
Stoppe.

Trinn 8: Beregn koordinatene til neste piksel
Hvis d <0
Da er d = d + i ₁
Hvis d ≧ 0
Da er d = d + i ₂
Øk y = y + 1

Trinn 9: Øk x = x + 1

Trinn 10: Tegn et punkt med siste (x, y) koordinater

Trinn 11: Gå til trinn 7

Trinn 12: Slutt på algoritmen

Eksempel: Start- og sluttposisjonen til linjen er (1, 1) og (8, 5). Finn mellompunkter.

Løsning: x ₁ =1
og ₁ =1
x ₂ =8
og ₂ =5
dx= x ₂ -x ₁ =8-1=7
du=y ₂ -og ₁ =5-1=4
Jeg ₁ =2* ∆y=2*4=8
Jeg ₂ =2*(∆y-∆x)=2*(4-7)=-6
d = I ₁ -∆x=8-7=1

Program for å implementere Bresenhams linjetegningsalgoritme:

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

Produksjon:

Skille mellom DDA Algorithm og Bresenhams Line Algorithm: