實(shí)驗(yàn)報(bào)告Bresenham畫線算法

1、實(shí)驗(yàn)報(bào)告（Bresenham畫線算法）1、 實(shí)驗(yàn)?zāi)康母鶕?jù)Bresenham畫線算法，掌握繪制直線的程序設(shè)計(jì)方法。2、 實(shí)驗(yàn)原理 為了說明算法原理，我們首先考慮斜率非負(fù)且不超過 1 的直線的光柵化過程。設(shè)直線的起點(diǎn)坐標(biāo)為 (xs , ys)，終點(diǎn)坐標(biāo)為(xe , ye)，則直線的方程為：因此，其隱函數(shù)表示為：其中：顯然，對(duì)于直線上的點(diǎn)，F(xiàn)(x , y) 等于零；對(duì)于直線下方的點(diǎn)，F(xiàn)(x , y) 大于零；而對(duì)直線上方的點(diǎn)，F(xiàn)(x,y) 小于零。假設(shè)當(dāng)前選擇的像素點(diǎn)是 (xi , yi)，那么下一步要選擇的像素點(diǎn)可能是 NE (xi+1 , yi+1)，也可能是 E (xi+1 , yi)。選擇的

2、原則是看哪一個(gè)離直線與 x = xi+1 的交點(diǎn)最近。運(yùn)用中點(diǎn)法則，我們只需考察中點(diǎn) M 在直線的哪一側(cè)，即計(jì)算：F(M) = F(xi + 1, yi + 1/2) = a(xi + 1) + b( yi + 0.5) + c并確定其正負(fù)號(hào)。由于根據(jù)函數(shù)值 F(xi+1, yi + 1/2) 進(jìn)行判定，所以我們定義一個(gè)判定函數(shù)如下： di = 2F(xi + 1, yi + 1/2)根據(jù)定義：di = 2a(xi + 1) + 2byi + b + 2c當(dāng) d i < 0 時(shí)，M 在直線的上方，取 E 為下一個(gè)像素點(diǎn)；當(dāng) d > 0時(shí)， M 在直線的下方，取 NE 為下一個(gè)像素點(diǎn)

3、；當(dāng) d = 0時(shí)，兩者都可以選，我們約定選 E。 di 的計(jì)算需要做 4 次加法和兩次乘法。因此，為了有效地計(jì)算判定函數(shù)，我們需要建立關(guān)于 di 的遞推公式。顯然，di 的變化依賴于下一個(gè)像素點(diǎn)選的是 NE 還是 E。當(dāng) di < 0 時(shí)，下一個(gè)像素點(diǎn)是 E，那么：di+1= 2F(xi + 2, yi + 1/2) = 2a(xi + 2) + 2byi + b + 2c = di + 2a當(dāng) di > 0 時(shí)，下一個(gè)像素點(diǎn)是 NE，則：di+1= 2F(xi + 2, yi + 1 + 1/2) = 2a(xi + 2) + 2b(yi +1)+b+2c = di + 2a

4、+ 2b由此，得到計(jì)算判定函數(shù) di 的遞推公式： 因?yàn)橹本€上的第一個(gè)像素點(diǎn)就是直線的起點(diǎn) (xs, ys)，所以判定函數(shù) di 的初值為：d0 = 2a(xs + 1) + 2bys + b + 2c = 2dy - dx 故滿足條件的直線的 Bresnham 算法的步驟如下： Step 1.初始化dx = xe xs , dy = ye ys , x = xs , y = ys , d = 2dy dx； Step 2.當(dāng) x < xe 時(shí)，執(zhí)行下述操作： （1）畫像素點(diǎn) (x, y)； （2）求下一個(gè)像素點(diǎn)：x = x + 1；if (d > 0) then y = y +

5、1； （3）計(jì)算判定函數(shù) d： if (d > 0) then d = d + 2dy 2dx； else d = d 2dy； Step 3.算法結(jié)束。三、實(shí)驗(yàn)程序#include<stdio.h>#include<graphics.h>#include<math.h>#include<conio.h>#include<easyx.h>void Bresenham_line(int xs,int ys,int xe,int ye,int c)int dx=abs(xe-xs),dy=abs(ye-ys),i,x=xs,y=ys

6、;int twoDX=2*dx,twoDY=2*dy,p=2*dy-dx;int s1,s2,interchange=0,temp;if (xe-xs>=0)s1=1;elses1=-1;if(ye-ys>=0)s2=1;elses2=-1;if(dy>dx) temp=dx;dx=dy;dy=temp;interchange=1;for (i=0;i<=dx;i+)putpixel(x,y,c); if(p>0)if(interchange)x+=s1;elsey+=s2;p-=twoDX;if(interchange)y+=s2;elsex+=s1; p+=twoDY;void main() int x1=60,y1=88,x2=345,y2=789,c=GREEN;int dx,dy,n,k,f;int x,y;int gdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode," ");Bresenham_line(x1,y1,x2,y2,c);getch();closegraph();四、測試結(jié)果x1=60,y1=88,x2=345,y2=789,c=GREEN，