Bresenham vonalalgoritmusa
Ez az algoritmus egy vonal letapogatására szolgál. Bresenham fejlesztette ki. Ez egy hatékony módszer, mert csak egész számok összeadását, kivonását és szorzási műveleteit tartalmazza. Ezek a műveletek nagyon gyorsan végrehajthatók, így a vonalak gyorsan generálhatók.
Ennél a módszernél a következő képpont az lesz, amelyiknek a legkisebb távolsága van a valódi vonaltól.
A módszer a következőképpen működik:
Tételezzünk fel egy P pixelt 1 '(x 1 ',és 1 '), majd válasszuk ki a következő képpontokat, ahogy májustól éjszakáig dolgozunk, egy-egy pixel pozícióban vízszintes irányban P felé 2 '(x 2 ',és 2 ').
Ha egy pixel van, bármelyik lépésben választhat
A következő pixel az
- Vagy a tőle jobbra eső (a vonal alsó korlátja)
- Az egyik jobbra fent és felfelé (a vonal felső határa)
A vonalat azokkal a képpontokkal lehet a legjobban közelíteni, amelyek a legkisebb távolságra esnek a P közötti útvonaltól 1 ', P 2 '.
A To kiválasztja a következőt az alsó S pixel és a felső T pixel között.
Ha S-t választjuk
Nekünk x van i+1 =x én +1 és y i+1 =y én
Ha T választja
Nekünk x van i+1 =x én +1 és y i+1 =y én +1
Az x = x pontban lévő egyenes tényleges y koordinátái i+1 van
y=mx i+1 +b
Az S-től a tényleges egyenesig mért távolság y irányban
s = y-y én
A távolság T-től a tényleges egyenesig y irányban
t = (y én +1)-y
Most nézzük meg a különbséget a két távolságérték között
utca
Mikor (s-t) <0 ⟹ s < t < p>
A legközelebbi pixel az S
Amikor (s-t) ≧0 ⟹ s A legközelebbi pixel a T Ez a különbség az m-t helyettesítve ahol c= 2△y+△x (2b-1) Felírhatjuk a d döntési változót i+1 a következő csúszáshoz Mivel x_(i+1)=x én +1, megvan Különleges esetek Ha a kiválasztott pixel a felső T pixelnél van (azaz d én ≧0)⟹ és i+1 =y én +1 Ha a kiválasztott pixel az alsó T pixelben van (azaz d én <0)⟹ y i+1=y én Végül kiszámoljuk d 1 Mivel mx 1 +b-y én =0 és m = 1. Csak egész számot tartalmaz, tehát egyszerű. 2. Elkerüli az ismétlődő pontok generálását. 3. Hardverrel megvalósítható, mert nem használ szorzást és osztást. 4. Gyorsabb a DDA-hoz (Digital Differential Analyzer) képest, mivel nem tartalmaz olyan lebegőpontos számításokat, mint a DDA algoritmus. 1. Ez az algoritmus csak alapvető vonalvezetésre szolgál. Az inicializálás nem része a Bresenham-féle vonalalgoritmusnak. Tehát a sima vonalak rajzolásához érdemes egy másik algoritmust megvizsgálni. 1. lépés: Algoritmus indítása 2. lépés: Az x változó deklarálása 1 ,x 2 ,és 1 ,és 2 ,d,i 1 ,én 2 ,dx,dy 3. lépés: Adja meg x értékét 1 ,és 1 ,x 2 ,és 2 4. lépés: Számítsd ki dx = x 2 -x 1 5. lépés: Tekintsük (x, y) kezdőpontnak és x-nek vége mint lehetséges x maximális értéke. 6. lépés: Pont generálása (x,y) koordinátákon. 7. lépés: Ellenőrizze, hogy létrejött-e a teljes sor. 8. lépés: Számítsa ki a következő pixel koordinátáit 9. lépés: Növekedés x = x + 1 10. lépés: Rajzolj egy pontot a legújabb (x, y) koordinátákkal 11. lépés: Folytassa a 7. lépéssel 12. lépés: Algoritmus vége Példa: A sor kezdő és végpontja (1, 1) és (8, 5). Keresse meg a közbenső pontokat. Megoldás: x 1 =1 Kimenet:
s-t = (y-yi)-[(yi+1)-y]
= 2y - 2yi -1 
és döntési változó bevezetése
d én =△x (s-t)
d én =△x (2 (x én +1)+2b-2y én -1)
=2△xy én -2△y-1△x.2b-2y én △x-△x
d én =2△y.x én -2△x.y én +c
d i+1 =2△y.x i+1 -2△x.y i+1 +c
d i+1 -d én =2△y.(x i+1 -x én )- 2△x(y i+1 -és én )
d i+1 +d én =2△y.(x én +1-x én )- 2△x(y i+1 -és én )
d i+1 =d én +2△y-2△x
d i+1 =d én +2△y
d 1 =△x[2m(x 1 +1)+2b-2y 1 -1]
d 1 =△x[2(mx 1 +b-y 1 )+2m-1] , nekünk van
d 1 =2△y-△x Előny:
Hátrány:
Bresenham vonal algoritmusa:
Ahol x 1 ,és 1 a kezdőpont koordinátái
És x 2 ,és 2 a végpont koordinátái
Számítsa ki dy = y 2 -és 1
Számítsa ki az i 1 =2*te
Számítsa ki az i 2 =2*(dy-dx)
Számítsd ki d=i 1 -dx
Ha dx <0
Ekkor x = x 2
y = y 2
x vége =x 1
Ha dx > 0
Ekkor x = x 1
y = y 1
x vége =x 2
Ha x > = x vége
Állj meg.
Ha d <0
Ekkor d = d + i 1
Ha d ≧ 0
Ekkor d = d + i 2
Növekedés y = y + 1
és 1 =1
x 2 =8
és 2 =5
dx= x 2 -x 1 =8-1=7
te=y 2 -és 1 =5-1=4
én 1 =2* ∆y=2*4=8
én 2 =2*(∆y-∆x)=2*(4-7)=-6
d = I 1 -∆x=8-7=1
x és d=d+I 1 vagy én 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 a Bresenham-féle vonalrajzolási algoritmus megvalósításához:
#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; } 
Tegyen különbséget a DDA algoritmus és a Bresenham-féle vonalalgoritmus között:
DDA algoritmus Bresenham vonalalgoritmusa 1. A DDA algoritmus lebegőpontos, azaz valós aritmetikát használ. 1. A Bresenham-féle vonalalgoritmus fix pontot, azaz egész számot használ 2. A DDA algoritmusok szorzást és osztást használnak a működéséhez 2. A Bresenham-féle vonalalgoritmus csak a kivonást és az összeadást használja 3. A DDA algoritmus lassabb, mint a Bresenham-féle vonalalgoritmus a vonalrajzolásban, mert valós aritmetikát használ (lebegőpontos művelet) 3. A Bresenham-algoritmus gyorsabb, mint a DDA-algoritmus, mivel csak összeadást és kivonást tartalmaz a számításban, és csak egész számokat használ. 4. A DDA algoritmus nem pontos és nem hatékony, mint a Bresenham-féle vonalalgoritmus. 4. A Bresenham-féle vonalalgoritmus pontosabb és hatékonyabb a DDA algoritmusnál. 5. A DDA algoritmus képes köröket és görbéket rajzolni, de nem pontos, mint a Bresenham-féle vonalalgoritmus 5. A Bresenham-féle vonalalgoritmus pontosabban tud kört és görbéket rajzolni, mint a DDA algoritmus.
