Tätä algoritmia käytetään viivan skannaukseen. Sen on kehittänyt Bresenham. Se on tehokas menetelmä, koska se sisältää vain kokonaislukujen yhteenlasku-, vähennys- ja kertolaskuoperaatioita. Nämä toiminnot voidaan suorittaa erittäin nopeasti, joten rivit voidaan luoda nopeasti.

Tässä menetelmässä seuraavaksi valittu pikseli on se, jolla on pienin etäisyys todellisesta viivasta.

Menetelmä toimii seuraavasti:

Oletetaan pikseli P ₁ '(x ₁ ',ja ₁ '), valitse sitten seuraavat pikselit työskennellessämme toukokuusta yöhön, yksi pikselin sijainti kerrallaan vaakasuunnassa kohti P ₂ '(x ₂ ',ja ₂ ').

Kerran pikseli valitse missä tahansa vaiheessa

Seuraava pikseli on

1. Joko sen oikealla puolella oleva (linjan alaraja)
2. Yksi yläreuna on oikea ja ylöspäin (linjan yläraja)

Viiva on parhaiten approksimoitu niiden pikselien avulla, jotka putoavat vähiten etäisyydelle P:n välisestä polusta ₁ ',P ₂ '.

To valitsee seuraavan alimman pikselin S ja ylimmän pikselin T väliltä.
Jos S valitaan
Meillä on x _i+1 =x _i +1 ja y _i+1 =y _i
Jos T valitaan
Meillä on x _i+1 =x _i +1 ja y _i+1 =y _i +1

Suoran todelliset y-koordinaatit kohdassa x = x _i+1 On
y = mx _i+1 +b

Etäisyys pisteestä S todelliseen linjaan y-suunnassa
s = y-y _i

Etäisyys pisteestä T todelliseen suoraan y-suunnassa
t = (y _i +1)-y

Mieti nyt näiden kahden etäisyysarvon eroa
s - t

Milloin (s-t) <0 ⟹ s < t < p>

Lähin pikseli on S

Kun (s-t) ≧0 ⟹ s

Lähin pikseli on T

Tämä ero on
s-t = (y-yi)-[(yi+1)-y]
= 2v - 2yi -1

Korvaa m:lla ja esittelemme päätösmuuttujan
d _i =△x (s-t)
d _i =△x (2 (x _i +1)+2b-2v _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

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

Voimme kirjoittaa päätösmuuttujan d _i+1 seuraavaa lipsahdusta varten
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 -ja _i )

Koska x_(i+1)=x _i +1, meillä on
d _i+1 +d _i =2△y.(x _i +1-x _i )- 2△x(y _i+1 -ja _i )

Erikoistapaukset

Jos valittu pikseli on ylimmässä kuvapisteessä T (eli d _i ≧0)⟹ ja _i+1 =y _i +1
d _i+1 =d _i +2△y-2△x

Jos valittu pikseli on alapikselissä T (eli d _i <0)⟹ y _{i+1=y i
d i+1 =d i +2△v}

Lopuksi lasketaan d ₁
d ₁ =△x[2m(x ₁ +1)+2b-2v ₁ -1]
d ₁ =△x[2(mx ₁ +b-y ₁ )+2m-1]

Koska mx ₁ +b-y _i =0 ja m = , meillä on
d ₁ =2△y-△x

Etu:

1. Se sisältää vain kokonaislukuaritmetiikkaa, joten se on yksinkertainen.

2. Se välttää kaksoispisteiden luomisen.

3. Se voidaan toteuttaa laitteistolla, koska se ei käytä kerto- ja jakolaskua.

4. Se on nopeampi verrattuna DDA:han (Digital Differential Analyzer), koska se ei sisällä liukulukuja, kuten DDA-algoritmi.

Haitta:

1. Tämä algoritmi on tarkoitettu vain perusviivan piirtämiseen Alustus ei ole osa Bresenhamin viivaalgoritmia. Joten piirtääksesi sileitä viivoja, sinun pitäisi haluta tarkastella erilaista algoritmia.

Bresenhamin linja-algoritmi:

Vaihe 1: Aloita algoritmi

Vaihe2: Ilmoita muuttuja x ₁ ,x ₂ ,ja ₁ ,ja ₂ ,d,i ₁ ,i ₂ ,dx,dy

Vaihe 3: Syötä x:n arvo ₁ ,ja ₁ ,x ₂ ,ja ₂
Missä x ₁ ,ja ₁ ovat lähtöpisteen koordinaatit
Ja x ₂ ,ja ₂ ovat loppupisteen koordinaatit

Vaihe 4: Laske dx = x ₂ -x ₁
Laske dy = y ₂ -ja ₁
Laske i ₁ =2*sinä
Laske i ₂ =2*(dy-dx)
Laske d=i ₁ -dx

Vaihe 5: Otetaan (x, y) aloituspisteeksi ja x _loppu kuin suurin mahdollinen x:n arvo.
Jos dx <0
Sitten x = x ₂
y = y ₂
x _loppu =x ₁
Jos dx > 0
Sitten x = x ₁
y = y ₁
x _loppu =x ₂

Vaihe 6: Luo piste (x,y)-koordinaateissa.

Vaihe 7: Tarkista, onko koko rivi luotu.
Jos x > = x _loppu
Lopettaa.

Vaihe 8: Laske seuraavan pikselin koordinaatit
Jos d <0
Sitten d = d + i ₁
Jos d ≧ 0
Sitten d = d + i ₂
Kasvata y = y + 1

Vaihe 9: Kasvata x = x + 1

Vaihe 10: Piirrä viimeisimpien (x, y) koordinaattien piste

Vaihe 11: Siirry vaiheeseen 7

Vaihe 12: Algoritmin loppu

Esimerkki: Viivan aloitus- ja loppupisteet ovat (1, 1) ja (8, 5). Etsi välipisteitä.

Ratkaisu: x ₁ =1
ja ₁ =1
x ₂ =8
ja ₂ =5
dx = x ₂ -x ₁ =8-1=7
sinä=y ₂ -ja ₁ =5-1=4
minä ₁ =2* ∆y=2*4=8
minä ₂ =2*(∆y-∆x)=2*(4-7)=-6
d = I ₁ -∆x=8-7=1

Ohjelma Bresenhamin viivapiirtoalgoritmin toteuttamiseksi:

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

Lähtö:

Tee ero DDA-algoritmin ja Bresenhamin linja-algoritmin välillä: