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₂').

eksempel på brukernavn

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+1er
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)

java konvertere char til streng

Vi kan skrive beslutningsvariabelen d_i+1for 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=yJeg
di+1=dJeg+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

css-kanten

Trinn 5: Betrakt (x, y) som utgangspunkt og x_sluttsom 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₂

latex skriftstørrelse

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: