Bresenhamo linijos algoritmas
Šis algoritmas naudojamas nuskaitymui konvertuojant eilutę. Jį sukūrė Bresenhamas. Tai efektyvus metodas, nes jis apima tik sveikųjų skaičių sudėjimo, atimties ir daugybos operacijas. Šios operacijos gali būti atliekamos labai greitai, todėl greitai galima sukurti linijas.
Taikant šį metodą, kitas pasirenkamas taškas, turintis mažiausią atstumą nuo tikrosios linijos.
Metodas veikia taip:
Tarkime, pikselis P 1 '(x 1 ', ir 1 '), tada pasirinkite tolesnius pikselius, kai dirbame nuo gegužės iki nakties, po vieną pikselio padėtį horizontalia kryptimi link P 2 '(x 2 ', ir 2 ').
Kai tik pikselis, pasirinkite bet kuriuo žingsniu
Kitas pikselis yra
- Dešinėje esanti (apatinė eilutės riba)
- Vienas viršuje yra dešinėn ir aukštyn (viršutinė eilutės riba)
Liniją geriausiai apytiksliai nustato tie pikseliai, kurie mažiausią atstumą nukrenta nuo kelio tarp P 1 ', P 2 “.
Norėdami pasirinkti kitą tarp apatinio taško S ir viršutinio pikselio T.
Jei pasirinktas S
Mes turime x aš+1 =x i +1 ir y aš+1 =y i
Jei pasirinktas T
Mes turime x aš+1 =x i +1 ir y aš+1 =y i +1
Tiesės, esančios x = x, tikrosios y koordinatės aš+1 yra
y=mx aš+1 +b
Atstumas nuo S iki tikrosios linijos y kryptimi
s = y-y i
Atstumas nuo T iki tikrosios linijos y kryptimi
t = (y i +1)-y
Dabar apsvarstykite skirtumą tarp šių dviejų atstumo verčių
s - t
Kada (s-t) <0 ⟹ s < t < p>
Artimiausias pikselis yra S
Kai (s-t) ≧0 ⟹ s Artimiausias pikselis yra T Šis skirtumas yra Pakeičiant m kur c = 2△y+△x (2b-1) Galime parašyti sprendimo kintamąjį d aš+1 už kitą slydimą Kadangi x_(i+1)=x i +1, turime Ypatingi atvejai Jei pasirinktas pikselis yra viršutiniame pikselyje T (t. y. d i ≧0)⟹ ir aš+1 =y i +1 Jei pasirinktas pikselis yra apatiniame pikselyje T (t. y. d i <0)⟹ y i+1=y i Galiausiai apskaičiuojame d 1 Nuo mx 1 +b-y i =0 ir m = 1. Ji apima tik sveikųjų skaičių aritmetiką, todėl ji yra paprasta. 2. Taip išvengiama pasikartojančių taškų generavimo. 3. Jis gali būti įgyvendintas naudojant techninę įrangą, nes nenaudoja daugybos ir dalybos. 4. Jis yra greitesnis, palyginti su DDA (skaitmeniniu diferencialiniu analizatoriumi), nes neapima slankiojo kablelio skaičiavimų, tokių kaip DDA algoritmas. 1. Šis algoritmas skirtas tik pagrindiniam linijų braižymui Inicijuoti nėra Bresenhamo linijų algoritmo dalis. Taigi, norėdami nubrėžti lygias linijas, turėtumėte pažvelgti į kitą algoritmą. 1 žingsnis: Pradėti algoritmą 2 žingsnis: Deklaruoti kintamąjį x 1 ,x 2 , ir 1 , ir 2 ,d,i 1 ,t.y 2 ,dx,dy 3 veiksmas: Įveskite x reikšmę 1 , ir 1 ,x 2 , ir 2 4 veiksmas: Apskaičiuokite dx = x 2 -x 1 5 veiksmas: Apsvarstykite (x, y) kaip pradžios tašką ir x galas kaip didžiausia galima x reikšmė. 6 veiksmas: Sukurkite tašką (x,y) koordinatėse. 7 veiksmas: Patikrinkite, ar sugeneruota visa eilutė. 8 veiksmas: Apskaičiuokite kito pikselio koordinates 9 veiksmas: Padidinkite x = x + 1 10 veiksmas: Nubrėžkite naujausių (x, y) koordinačių tašką 11 veiksmas: Eikite į 7 veiksmą 12 veiksmas: Algoritmo pabaiga Pavyzdys: Linijos pradžios ir pabaigos padėtis yra (1, 1) ir (8, 5). Raskite tarpinius taškus. Sprendimas: x 1 =1 Išvestis:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
ir įvedant sprendimo kintamąjį
d i =△x (s-t)
d i =△x (2 (x i +1)+2b-2m 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 aš+1 =2△y.x aš+1 -2△x.y aš+1 +c
d aš+1 -d i =2△y.(x aš+1 -x i )- 2△x(y aš+1 - ir i )
d aš+1 +d i =2△y.(x i +1-x i )- 2△x(y aš+1 - ir i )
d aš+1 =d i +2△y-2△x
d aš+1 =d i +2△m
d 1 =△x[2m(x 1 +1)+2b-2m 1 -1]
d 1 =△x[2(mx 1 +b-y 1 )+2m-1] , mes turime
d 1 =2△y-△x Privalumas:
Trūkumas:
Bresenhamo linijos algoritmas:
Kur x 1 , ir 1 yra pradinio taško koordinatės
Ir x 2 , ir 2 yra pabaigos taško koordinatės
Apskaičiuokite dy = y 2 - ir 1
Apskaičiuokite i 1 =2*tu
Apskaičiuokite i 2 =2*(dy-dx)
Apskaičiuokite d=i 1 -dx
Jei dx <0
Tada x = x 2
y = y 2
x galas =x 1
Jei dx > 0
Tada x = x 1
y = y 1
x galas =x 2
Jei x > = x galas
Sustabdyti.
Jei d <0
Tada d = d + i 1
Jei d ≧ 0
Tada d = d + i 2
Padidinkite y = y + 1
ir 1 =1
x 2 =8
ir 2 =5
dx = x 2 -x 1 =8-1=7
tu=y 2 - ir 1 =5-1=4
aš 1 =2* ∆y=2*4=8
aš 2 =2*(∆y-∆x)=2*(4-7)=-6
d = I 1 -∆x=8-7=1
x ir d=d+I 1 ar aš 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 Programa, skirta įgyvendinti Bresenhamo linijų braižymo algoritmą:
#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; } 
Atskirkite DDA algoritmą nuo Bresenhamo linijos algoritmo:
DDA algoritmas Bresenhamo linijos algoritmas 1. DDA algoritmas naudoja slankųjį kablelį, t. y. tikrąją aritmetiką. 1. Bresenhamo linijos algoritmas naudoja fiksuotąjį tašką, t. y. sveikųjų skaičių aritmetiką 2. DDA algoritmai naudoja daugybos ir padalijimo operacijas 2. Bresenhamo linijos algoritmas naudoja tik atimtį ir sudėjimą 3. DDA algoritmas yra lėtesnis už Bresenhamo linijinį algoritmą, nes jis naudoja tikrą aritmetiką (slankiojo kablelio operacija) 3. Bresenhamo algoritmas yra greitesnis nei DDA algoritmas, nes skaičiuojant naudojamas tik sudėjimas ir atėmimas ir naudojama tik sveikųjų skaičių aritmetika. 4. DDA algoritmas nėra tikslus ir efektyvus kaip Bresenhamo linijos algoritmas. 4. Bresenhamo linijos algoritmas yra tikslesnis ir efektyvesnis naudojant DDA algoritmą. 5.DDA algoritmas gali nubrėžti apskritimą ir kreives, bet nėra tikslus kaip Bresenhamo linijos algoritmas 5. Bresenhamo linijos algoritmas gali nubrėžti apskritimą ir kreives tiksliau nei DDA algoritmas.
