Bresenham的算法畫直線

./基于VC++6.0的Bresenham算法畫直線一．Bresenham算法概述：Bresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域使用最廣泛的直線掃描轉(zhuǎn)換方法。過各行、各列像素中心構(gòu)造一組虛擬網(wǎng)格線,按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線各垂直網(wǎng)格線的交點(diǎn),然后確定該列像素中與此交點(diǎn)最近的像素。該算法的優(yōu)點(diǎn)在于可以采用增量計(jì)算,使得對(duì)于每一列,只要檢查一個(gè)誤差項(xiàng)的符號(hào),就可以確定該列所求的像素。二．Bresenham算法原理：由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo),可以假設(shè)直線上第i個(gè)象素點(diǎn)坐標(biāo)為<xi,yi>,它是直線上點(diǎn)<xi,yi>的最佳近似,并且xi=xi<假設(shè)m<1,如下圖所示。那么,直線上下一個(gè)象素點(diǎn)的可能位置是<xi+1,yi>或<xi+1,yi+1>。由圖中可以知道,在x=xi+1處,直線上點(diǎn)的y值是y=m<xi+1>+b,該點(diǎn)離象素點(diǎn)<xi+1,yi>和象素點(diǎn)<xi+1,yi+1>的距離分別是d1和d2：d1=y-yi=m<xi+1>+b-yi<1－8>d2=<yi+1>-y=<yi+1>-m<xi+1>-b<1－9>這兩個(gè)距離差是d1-d2=2m<xi+1>-2yi＋2b-1<1－10>我們來分析公式<1-10>：<1>當(dāng)此值為正時(shí),d1>d2,說明直線上理論點(diǎn)離<xi+1,yi+1>象素較近,下一個(gè)象素點(diǎn)應(yīng)取<xi+1,yi+1>。<2>當(dāng)此值為負(fù)時(shí),d1<d2,說明直線上理論點(diǎn)離<xi+1,yi>象素較近,則下一個(gè)象素點(diǎn)應(yīng)取<xi+1,yi>。<3>當(dāng)此值為零時(shí),說明直線上理論點(diǎn)離上、下兩個(gè)象素點(diǎn)的距離相等,取哪個(gè)點(diǎn)都行,假設(shè)算法規(guī)定這種情況下取<xi+1,yi+1>作為下一個(gè)象素點(diǎn)。因此只要利用<d1-d2>的符號(hào)就可以決定下一個(gè)象素點(diǎn)的選擇。為此,我們進(jìn)一步定義一個(gè)新的判別式：pi=△x×<d1-d2>=2△y·xi-2△x·yi+c<1－11>式<1-11>中的△x=<x2-x1>>0,因此pi與<d1-d2>有相同的符號(hào)；這里△y=y2-y1,m=△y/△x；c=2△y+△x<2b-1>。下面對(duì)式<1-11>作進(jìn)一步處理,以便得出誤差判別遞推公式并消除常數(shù)c。將式<2-11>中的下標(biāo)i改寫成i+1,得到：pi+1=2△y·xi+1-2△x·yi+1+c<1－12>將式<2-12>減去<2-11>,并利用xi+1=xi+1,可得：pi+1=pi+2△y-2△x·<yi+1-yi><1－13>再假設(shè)直線的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo),即滿足：y1=mx1+b<1－14>由式<1-11>和式<1-14>得到p1的初始值：p1=2△y-△x<1－15>這樣,我們可利用誤差判別變量,得到如下算法表示：初始p1=2△y-△x<1－16>當(dāng)pi≥0時(shí)：yi+1=yi+1,xi+1=xi+1,pi+1=pi+2<△y-△x>否則：yi+1=yi,xi+1=xi+1,pi+1=pi+2△y從式<1-16>可以看出,第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個(gè)端點(diǎn)坐標(biāo)分量差△x和△y有關(guān),運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算,而乘2可利用算術(shù)左移一位來完成,因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。三．用VC++6.0中的MFC來實(shí)現(xiàn)Bresenham直線算法實(shí)現(xiàn)步驟：1建立MFC程序：2選擇單個(gè)文件：3接下來step2~step5一直點(diǎn)擊NEXT：4step6點(diǎn)擊Finished后出現(xiàn)以下界面點(diǎn)擊OK5選則Resource中的Menu雙擊后,添加繪圖按鈕,并建立繪圖的下鼠按鈕命名為bresenham算法畫直線6建好后點(diǎn)擊中的View下屬菜單ClassWizard.7雙擊中的,再將Classname中換成再雙擊中的COMMAND,彈出框后點(diǎn)擊OK.會(huì)在下方圖中多出陰影部分的容。8再點(diǎn)擊EditCode在此處添加你的程序代碼然后編譯。四程序：CDC*pDC=GetDC<>;CPointPtBegin<80,130>;//起始點(diǎn)CPointPtEnd<320,370>;//終止點(diǎn)ints1,s2,interchange;doubleX=PtBegin.x;doubleY=PtBegin.y;doubledeltax,deltay,f,Temp;deltax=abs<PtEnd.x-PtBegin.x>;deltay=abs<PtEnd.y-PtBegin.y>;if<PtBegin.x-PtBegin.x>=0>s1=1;elses1=-1;if<PtEnd.y-PtBegin.y>=0>s2=1;elses2=-1;f=2*deltay-deltax;if<deltay>deltax>{Temp=deltax;deltax=deltay;deltay=Temp;interchange=1;}elseinterchange=0;for<inti=1;i<=<deltax+deltay>;i++>{ if<f>=0> { if<interchange==1>X+=s1; elseY+=s2; pDC->SetPixel<int<X>,int<Y>,RGB<0,50,250>>; f=f-2*deltax;} else { if<interchang