直線生成算法

1、直線生成算法Bresenham法最近的研究涉及在像素圖上作直線，自己也不想花時間摸索，于是在網(wǎng)上找到了 Bresenham的直線生成算法，有一篇博客講得清晰明了，但是算法上有些問題，我進(jìn)行了改 進(jìn)和移植，下面講解Bresenham的直線生成算法時也是參考這篇博文。1.算法簡介圖1算法思想：圖1中，連接M點(diǎn)和N點(diǎn)的直線經(jīng)過點(diǎn)B，由于是像素圖，所以實(shí)際上B 點(diǎn)應(yīng)該由A點(diǎn)或者C點(diǎn)代替。當(dāng)B點(diǎn)更靠近A點(diǎn)時，選擇點(diǎn)A（x+1,y+1）；當(dāng)B點(diǎn)更靠近 C點(diǎn)時，選擇點(diǎn)C（x+1,y）。因此，當(dāng)+m 0.5時，繪制（x + 1, y）點(diǎn)，否則繪制0 + 1, y + 1）點(diǎn)，這里為累加誤差， 表達(dá)式為：部+二

2、:-姬 +海,如果姬 +m + m- 1,其他式中： ：表示在第n次計算時的值，廠i-表示在第n+1次計算時的值；m就是直線的 斜率。由于斜率m的值有正有負(fù)，有可能為0，也可能為8,為了避免分別討論這些情況， 將上述公式兩邊都乘以dx,并將*dx用g表示，則有二卜+ 即，如果 + dy） dy,且x, y的增量均為正的情況，但實(shí)際上有8 值得注意的是，現(xiàn)在我們只考慮dx dy,且x, y的增量均為正的情況，但實(shí)際上有8 種不同的情況（但是算法思想不變），如圖2所示叼 叼1 771 OOIII始 就I叼 叼尤1 771 O01 m 771 OO尤1 叼0 771 = 0 Then ux = 1I

3、f dx = 0 Then uy = 1If dy = dy ThenFor x = x1 To x2 Step ux cnt = cnt + 1If 2 * (eps + dy) = 2 Then y = y + uy cnt大于2才執(zhí)行y = y + uy，即排除起始 坐標(biāo)點(diǎn)，否則造成錯誤結(jié)果arr(cnt).x = xarr(cnt).y = yEnd IfNext xElseFor y = y1 To y2 Step uy cnt = cnt + 1If 2 * (eps + dx) = 2 Then x = x + ux cnt大于2才執(zhí)行x = x + ux，即排除起始 坐標(biāo)點(diǎn)，否

4、則造成錯誤結(jié)果arr(cnt).x = xarr(cnt).y = yEnd IfNext yEnd Ifarr(0).x = cn記錄元素個數(shù)End Function如果大家有不同看法，還希望共同討論3.程序運(yùn)行結(jié)果(VB+ OpenGL)原程序運(yùn)繪制y=x, 0 x10圖3是原程序運(yùn)行結(jié)果，圖4時修改后的程序運(yùn)行結(jié)果， 行得到的起點(diǎn)是（0,1），但實(shí)際應(yīng)該是（0,0）原程序運(yùn)圖5圖6繪制直線第1個坐標(biāo)為起點(diǎn)，第2個坐標(biāo)為終點(diǎn)- (15,15)、(5,10) - (15,15)、(5,15) - (15,15)、(5,20) - (15,15)、(5,25)- (15,15)；- (15,15)、(25,10) - (15,15)、(25,15) - (15,15)、(25,20) - (15,15)、(25,25) -(15,15)；- (15,15)、(10,5) - (15,15)、(15,5) - (15,15)、(20,5) - (15,15)、(25,5)- (15,15)；(5,25) - (15,15)、(10,25) - (15,15)、(15,