Denne algoritme bruges til at scanne konvertering af en linje. Det blev udviklet af Bresenham. Det er en effektiv metode, fordi den kun involverer heltalsaddition, subtraktioner og multiplikationsoperationer. Disse operationer kan udføres meget hurtigt, så linjer kan genereres hurtigt.

I denne metode er den næste valgte pixel den, der har den mindste afstand fra den sande linje.

Metoden fungerer som følger:

Antag en pixel P₁'(x₁',og₁'), vælg derefter efterfølgende pixels, mens vi arbejder os mod natten, en pixelposition ad gangen i vandret retning mod P₂'(x₂',og₂').

eksempel på brugernavn

Vælg en gang en pixel i ethvert trin

Den næste pixel er

1. Enten den til højre (nedre grænse for linjen)
2. Den ene øverst til højre og op (øvre grænse for linjen)

Linjen tilnærmes bedst af de pixels, der falder mindst fra stien mellem P₁',P₂'.

To vælger den næste mellem den nederste pixel S og den øverste pixel T.
Hvis S er valgt
Vi har x_i+1=x_jeg+1 og y_i+1=y_jeg
Hvis T er valgt
Vi har x_i+1=x_jeg+1 og y_i+1=y_jeg+1

De faktiske y-koordinater for linjen ved x = x_i+1er
y=mx_i+1+b

Afstanden fra S til den faktiske linje i y-retningen
s = y-y_jeg

Afstanden fra T til den faktiske linje i y-retningen
t = (y_jeg+1)-y

Overvej nu forskellen mellem disse 2 afstandsværdier
s - t

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

Den nærmeste pixel er S

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

Den nærmeste pixel er T

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

Erstatter m ved og introduktion af 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 få aktuel tid

Vi kan skrive beslutningsvariablen d_i+1til næste 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)

Da 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)

Særlige tilfælde

Hvis den valgte pixel er på den øverste pixel T (dvs_jeg≧0)⟹ og_i+1=y_jeg+1
d_i+1=d_jeg+2△y-2△x

Hvis den valgte pixel er ved den nederste pixel T (dvs_jeg<0)⟹ y_{i+1=yjeg
di+1=djeg+2△y}

Til sidst 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 kun heltals aritmetik, så det er enkelt.

2. Det undgår generering af duplikerede punkter.

3. Det kan implementeres ved hjælp af hardware, fordi det ikke bruger multiplikation og division.

4. Det er hurtigere sammenlignet med DDA (Digital Differential Analyzer), fordi det ikke involverer flydende kommaberegninger som DDA Algorithm.

Ulempe:

1. Denne algoritme er kun beregnet til grundlæggende linjetegning. Initialisering er ikke en del af Bresenhams linjealgoritme. Så for at tegne glatte linjer, bør du undersøge en anden algoritme.

Bresenhams linjealgoritme:

Trin 1: Start algoritme

Trin 2: Erklær variabel x₁,x₂,og₁,og₂,d,i₁,jeg₂,dx,dy

Trin 3: Indtast værdien af ​​x₁,og₁,x₂,og₂
Hvor x₁,og₁er koordinater for udgangspunktet
Og x₂,og₂er koordinater for slutpunktet

Trin 4: Beregn dx = x₂-x₁
Beregn dy = y₂-og₁
Beregn i₁=2*dig
Beregn i₂=2*(dy-dx)
Beregn d=i₁-dx

okse vs tyr

Trin 5: Betragt (x, y) som udgangspunkt og x_endesom maksimalt mulig værdi af x.
Hvis dx<0
Så er x = x₂
y = y₂
x_ende=x₁
Hvis dx > 0
Så er x = x₁
y = y₁
x_ende=x₂

latex skriftstørrelse

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

Trin 7: Tjek om hele linjen er genereret.
Hvis x > = x_ende
Hold op.

Trin 8: Beregn koordinaterne for den næste pixel
Hvis d<0
Så er d = d + i₁
Hvis d ≧ 0
Så er d = d + i₂
Forøg y = y + 1

Trin 9: Forøg x = x + 1

Trin 10: Tegn et punkt med de seneste (x, y) koordinater

Trin 11: Gå til trin 7

Trin 12: Slut på algoritme

Eksempel: Linjens start- og slutposition er (1, 1) og (8, 5). Find mellempunkter.

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 til implementering af 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; } 

Produktion:

Forskel mellem DDA-algoritmen og Bresenhams linjealgoritme: