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+1On
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

estetyt yhteystiedot

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+1seuraavaa 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=yi
di+1=di+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

tcp ja ip malli

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_loppukuin 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ä: