Bresenhamov riadkový algoritmus
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 1 '(X 1 ',a 1 '), potom vyberte nasledujúce pixely, ako pracujeme, až do noci, po jednom pixeli v horizontálnom smere smerom k P 2 '(X 2 ',a 2 ').
Keď je pixel vložený, vyberte si v ktoromkoľvek kroku
Ďalší pixel je
- Buď ten napravo (dolná hranica pre riadok)
- 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 1 ',P 2 '.
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
Skutočné súradnice y čiary v bode x = x i+1 je
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 Nahradenie m za Kde c= 2△y+△x (2b-1) Rozhodovaciu premennú d môžeme zapísať i+1 na ďalšie pošmyknutie Pretože x_(i+1)=x i +1, máme Špeciálne prípady Ak je vybraný pixel na hornom pixeli T (t.j. d i ≧0)⟹ a i+1 =y i +1 Ak je zvolený pixel na spodnom pixeli T (t.j. d i <0)⟹ y i+1=y i Nakoniec vypočítame d 1 Od mx 1 +b-y i =0 a m = 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. 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. Krok 1: Spustite algoritmus Krok 2: Deklarujte premennú x 1 ,X 2 a 1 a 2 ,d,i 1 ,i 2 ,dx,dy Krok 3: Zadajte hodnotu x 1 a 1 ,X 2 a 2 Krok 4: Vypočítajte dx = x 2 -X 1 Krok 5: Uvažujme (x, y) ako východiskový bod a x koniec ako maximálna možná hodnota x. Krok 6: Vygenerujte bod na (x,y) súradniciach. Krok 7: Skontrolujte, či sa generuje celý riadok. Krok 8: Vypočítajte súradnice nasledujúceho pixelu 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 =1 Výkon:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
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
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 )
d i+1 +d i =2△y.(x i +1-x i )- 2△x(y i+1 -a i )
d i+1 =d i +2△y-2△x
d i+1 =d i +2△r
d 1 =△x[2m(x 1 +1)+2b-2r 1 -1]
d 1 =△x[2(mx 1 +b-y 1 )+2m-1] , máme
d 1 =2△y-△x Výhoda:
Nevýhoda:
Bresenhamov riadkový algoritmus:
Kde x 1 a 1 sú súradnice východiskového bodu
A x 2 a 2 sú súradnice koncového bodu
Vypočítajte dy = y 2 -a 1
Vypočítajte i 1 = 2*vy
Vypočítajte i 2 =2*(dy-dx)
Vypočítajte d=i 1 -dx
Ak dx <0
Potom x = x 2
y = y 2
X koniec =x 1
Ak dx > 0
Potom x = x 1
y = y 1
X koniec =x 2
Ak x > = x koniec
Stop.
Ak d <0
Potom d = d + i 1
Ak d ≧ 0
Potom d = d + i 2
Prírastok y = y + 1
a 1 =1
X 2 =8
a 2 =5
dx = x 2 -X 1 = 8-1 = 7
ty=y 2 -a 1 = 5-1 = 4
ja 1 =2* ∆y=2*4=8
ja 2 =2*(∆y-∆x)=2*(4-7)=-6
d = I 1 -∆x=8-7=1
X a d = d + I 1 alebo ja 2 1 1 d+I 2 =1+(-6)=-5 2 2 d+I 1 =-5+8=3 3 2 d+I 2 =3+(-6)=-3 4 3 d+I 1 =-3+8=5 5 3 d+I 2 =5+(-6)=-1 6 4 d+I 1 =-1+8=7 7 4 d+I 2 =7+(-6)=1 8 5 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; } 
Rozdiel medzi algoritmom DDA a algoritmom Bresenham's Line:
Algoritmus DDA Bresenhamov riadkový algoritmus 1. Algoritmus DDA používa plávajúcu desatinnú čiarku, t. j. skutočnú aritmetiku. 1. Bresenhamov riadkový algoritmus používa pevný bod, t. j. celočíselnú aritmetiku 2. Algoritmy DDA využívajú na svoju činnosť násobenie a delenie 2. Bresenham's Line Algorithm používa iba odčítanie a sčítanie 3. Algoritmus DDA je pri kreslení čiar pomalý ako Bresenhamov Line Algorithm, pretože používa skutočnú aritmetiku (operácia s pohyblivou rádovou čiarkou) 3. Bresenhamov algoritmus je rýchlejší ako algoritmus DDA v rade, pretože vo výpočte zahŕňa iba sčítanie a odčítanie a používa iba aritmetiku celého čísla. 4. Algoritmus DDA nie je presný a efektívny ako Bresenham's Line Algorithm. 4. Bresenhamov Line Algorithm je presnejší a efektívnejší v DDA Algorithm. 5. Algoritmus DDA môže kresliť kruh a krivky, ale nie sú presné ako Bresenhamov lineárny algoritmus 5. Bresenham's Line Algorithm dokáže kresliť kruh a krivky presnejšie ako algoritmus DDA.
