TechCodeview

Denna algoritm används för att skanna omvandling av en linje. Det utvecklades av Bresenham. Det är en effektiv metod eftersom den endast involverar heltalsaddition, subtraktioner och multiplikationsoperationer. Dessa operationer kan utföras mycket snabbt så linjer kan genereras snabbt.

I denna metod är nästa pixel som väljs den som har det minsta avståndet från den sanna linjen.

Metoden fungerar enligt följande:

Antag en pixel P₁'(x₁',och₁'), välj sedan efterföljande pixlar medan vi arbetar vår maj till natten, en pixelposition åt gången i horisontell riktning mot P₂'(x₂',och₂').

Välj en gång en pixel i vilket steg som helst

Nästa pixel är

1. Antingen den till höger (nedre gräns för linjen)
2. En överst till höger och uppåt (övre gräns för linjen)

Linjen uppskattas bäst av de pixlar som faller minst avstånd från banan mellan P₁',P₂'.

För att välja nästa mellan den nedre pixeln S och den översta pixeln T.
Om S väljs
Vi har x_i+1=x_i+1 och y_i+1=y_i
Om T väljs
Vi har x_i+1=x_i+1 och y_i+1=y_i+1

Linjens faktiska y-koordinater vid x = x_i+1är
y=mx_i+1+b

Avståndet från S till den faktiska linjen i y-riktning
s = å-å_i

Avståndet från T till den faktiska linjen i y-riktning
t = (y_i+1)-y

Tänk nu på skillnaden mellan dessa 2 avståndsvärden
s - t

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

Den närmaste pixeln är S

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

Den närmaste pixeln är T

Denna skillnad är
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Ersätter m med och införa beslutsvariabel
d_i=△x (s-t)
d_i=△x (2 (x_i+1)+2b-2y_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

Där c= 2△y+△x (2b-1)

Vi kan skriva beslutsvariabeln d_i+1för nästa slip on
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-och_i)

Eftersom x_(i+1)=x_i+1, det har vi
d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-och_i)

Speciella fall

Om den valda pixeln är på den översta pixeln T (d.v.s_i≧0)⟹ och_i+1=y_i+1
d_i+1=d_i+2△y-2△x

Om den valda pixeln är på den nedre pixeln T (d.v.s_i<0)⟹ y_{i+1=yi
di+1=di+2△y}

Slutligen beräknar vi d₁
d₁=△x[2m(x₁+1)+2b-2y₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

Sedan mx₁+b-y_i=0 och m = , vi har
d₁=2△y-△x

Fördel:

1. Det involverar bara heltalsaritmetik, så det är enkelt.

2. Det undviker generering av dubbla punkter.

3. Det kan implementeras med hjälp av hårdvara eftersom det inte använder multiplikation och division.

4. Det är snabbare jämfört med DDA (Digital Differential Analyzer) eftersom det inte involverar flyttalsberäkningar som DDA Algorithm.

Nackdel:

1. Denna algoritm är endast avsedd för grundläggande linjeritning. Initiering är inte en del av Bresenhams linjealgoritm. Så för att rita jämna linjer bör du titta på en annan algoritm.

Bresenhams linjealgoritm:

Steg 1: Starta algoritm

Steg 2: Deklarera variabel x₁,x₂,och₁,och₂,d,i₁, jag₂,dx,dy

Steg 3: Ange värdet på x₁,och₁,x₂,och₂
Där x₁,och₁är startpunktens koordinater
Och x₂,och₂är koordinater för slutpunkten

sortera arraylist

Steg 4: Beräkna dx = x₂-x₁
Beräkna dy = y₂-och₁
Beräkna i₁=2*du
Beräkna i₂=2*(dy-dx)
Beräkna d=i₁-dx

Steg 5: Betrakta (x, y) som utgångspunkt och x_slutetsom högsta möjliga värde på x.
Om dx<0
Då är x = x₂
y = y₂
x_slutet=x₁
Om dx > 0
Då är x = x₁
y = y₁
x_slutet=x₂

Steg 6: Generera punkt vid (x,y)koordinater.

Steg 7: Kontrollera om hela linjen genereras.
Om x > = x_slutet
Sluta.

Steg 8: Beräkna koordinaterna för nästa pixel
Om d<0
Då d = d + i₁
Om d ≧ 0
Då d = d + i₂
Öka y = y + 1

Steg 9: Öka x = x + 1

Steg 10: Rita en punkt med de senaste (x, y) koordinaterna

Steg 11: Gå till steg 7

Steg 12: Slut på algoritm

Exempel: Linjens start- och slutposition är (1, 1) och (8, 5). Hitta mellanpunkter.

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

Program för att implementera Bresenhams linjeritningsalgoritm:

 #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:

Skilja mellan DDA-algoritmen och Bresenhams linjealgoritm: