Tento algoritmus sa používa na konverziu skenovania riadku. Vyvinul ho Bresenham. Je to efektívna metóda, pretože zahŕňa iba operácie sčítania, odčítania a násobenia celých čísel. Tieto operácie môžu byť vykonávané veľmi rýchlo, takže čiary môžu byť generované rýchlo.

Pri tejto metóde sa vyberie ďalší pixel, ktorý má najmenšiu vzdialenosť od skutočnej čiary.

Metóda funguje nasledovne:

Predpokladajme, že pixel P₁'(X₁',a₁'), potom vyberte nasledujúce pixely, ako pracujeme, až do noci, po jednom pixeli v horizontálnom smere smerom k P₂'(X₂',a₂').

Keď je pixel vložený, vyberte si v ktoromkoľvek kroku

Ďalší pixel je

1. Buď ten napravo (dolná hranica pre riadok)
2. Jeden hore vpravo a hore (horná hranica pre riadok)

Čiara je najlepšie aproximovaná tými pixelmi, ktoré spadajú najmenšiu vzdialenosť od cesty medzi P₁',P₂'.

Ak chcete vybrať ďalší medzi spodným pixelom S a horným pixelom T.
Ak sa zvolí S
Máme x_i+1=x_i+1 a y_i+1=y_i
Ak sa zvolí T
Máme x_i+1=x_i+1 a y_i+1=y_i+1

programovacie vzory java

Skutočné súradnice y čiary v bode x = x_i+1je
y=mx_i+1+b

Vzdialenosť od S k skutočnej čiare v smere y
s = y-y_i

Vzdialenosť od T k skutočnej čiare v smere y
t = (y_i+1)-y

Teraz zvážte rozdiel medzi týmito 2 hodnotami vzdialenosti
s - t

Keď (s-t)<0 ⟹ s < t< p>

Najbližší pixel je S

Keď (s-t) ≧0 ⟹ s

Najbližší pixel je T

Tento rozdiel je
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1

Nahradenie m za a zavedenie rozhodovacej premennej
d_i=△x (s-t)
d_i=△x (2 (X_i+1)+2b-2r_i-1)
= 2△xy_i-2△y-1△x.2b-2y_i△x-△x
d_i=2△y.x_i-2△x.r_i+c

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

Rozhodovaciu premennú d môžeme zapísať_i+1na ďalšie pošmyknutie
d_i+1=2△y.x_i+1-2△x.r_i+1+c
d_i+1-d_i=2△y.(x_i+1-X_i)- 2△x(y_i+1-a_i)

Pretože x_(i+1)=x_i+1, máme
d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-a_i)

Špeciálne prípady

Neena Gupta

Ak je vybraný pixel na hornom pixeli T (t.j. d_i≧0)⟹ a_i+1=y_i+1
d_i+1=d_i+2△y-2△x

Ak je zvolený pixel na spodnom pixeli T (t.j. d_i<0)⟹ y_{i+1=yi
di+1=di+2△r}

Nakoniec vypočítame d₁
d₁=△x[2m(x₁+1)+2b-2r₁-1]
d₁=△x[2(mx₁+b-y₁)+2m-1]

Od mx₁+b-y_i=0 a m = , máme
d₁=2△y-△x

Výhoda:

1. Zahŕňa iba celočíselnú aritmetiku, takže je to jednoduché.

2. Vyhne sa vytváraniu duplicitných bodov.

3. Môže byť implementovaný pomocou hardvéru, pretože nepoužíva násobenie a delenie.

4. Je rýchlejší v porovnaní s DDA (digitálny diferenciálny analyzátor), pretože nezahŕňa výpočty s pohyblivou rádovou čiarkou ako algoritmus DDA.

Nevýhoda:

1. Tento algoritmus je určený len pre základné kreslenie čiar Inicializácia nie je súčasťou Bresenhamovho čiarového algoritmu. Ak chcete nakresliť hladké čiary, mali by ste sa pozrieť na iný algoritmus.

Bresenhamov riadkový algoritmus:

Krok 1: Spustite algoritmus

Krok 2: Deklarujte premennú x₁,X₂a₁a₂,d,i₁,i₂,dx,dy

reťazec v c++

Krok 3: Zadajte hodnotu x₁a₁,X₂a₂
Kde x₁a₁sú súradnice východiskového bodu
A x₂a₂sú súradnice koncového bodu

Krok 4: Vypočítajte dx = x₂-X₁
Vypočítajte dy = y₂-a₁
Vypočítajte i₁= 2*vy
Vypočítajte i₂=2*(dy-dx)
Vypočítajte d=i₁-dx

Krok 5: Uvažujme (x, y) ako východiskový bod a x_koniecako maximálna možná hodnota x.
Ak dx<0
Potom x = x₂
y = y₂
X_koniec=x₁
Ak dx > 0
Potom x = x₁
y = y₁
X_koniec=x₂

Krok 6: Vygenerujte bod na (x,y) súradniciach.

Krok 7: Skontrolujte, či sa generuje celý riadok.
Ak x > = x_koniec
Stop.

Krok 8: Vypočítajte súradnice nasledujúceho pixelu
Ak d<0
Potom d = d + i₁
Ak d ≧ 0
Potom d = d + i₂
Prírastok y = y + 1

Krok 9: Prírastok x = x + 1

Krok 10: Nakreslite bod najnovších (x, y) súradníc

Krok 11: Prejdite na krok 7

Krok 12: Koniec Algoritmu

Príklad: Počiatočná a koncová poloha riadku sú (1, 1) a (8, 5). Nájdite medziľahlé body.

Riešenie: X₁=1
a₁=1
X₂=8
a₂=5
dx = x₂-X₁= 8-1 = 7
ty=y₂-a₁= 5-1 = 4
ja₁=2* ∆y=2*4=8
ja₂=2*(∆y-∆x)=2*(4-7)=-6
d = I₁-∆x=8-7=1

Program na implementáciu Bresenhamovho algoritmu kreslenia čiar:

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

Výkon:

Rozdiel medzi algoritmom DDA a algoritmom Bresenham's Line: