直線的中點Bresenham算法

摘要：直線Bresenham算法的基本原理是采取對整型參量的符號進行檢測，整型參量的值正比于兩像素與實際線段之間的偏移。直線的中點Bresenham算法是依據下一個點可能出現的兩個點的中間點處在直線的位置來判斷下一個點的取舍。

關鍵詞：Bresenham算法；斜率；誤差項

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2011)04-0825-02

The Bresenham Algorithm of Center Point of Straight Line

WANG Fang， WANG Zheng-lan

(Commanding Institute of Engineer Corps， Xuzhou 221004， China)

Abstract: The basic principle of the Bresenham algorithm of center point of straight line Adopts carries on the examination to the trueing parameter mark， the trueing parameter value is in proportion to two picture elements and actual line segment displacements. The Bresenham algorithm of center point of the straight line is two spot intermediate points which the basis next spot possibly appears occupies the straight line position judgment next spot choices.

Key words: Bresenham algorithm; slope; error term

1 直線Bresenham算法

設直線從起點(x1，y1)到終點(x2，y2)。直線可表示為方程y=mx+b，|m|≤1，其中

沿線路徑的像素位置由以單位x間距的取樣來決定，從給定線段的左端點(x1，y1)開始，逐步處理每個后繼列（x位置），并在掃描線y值最接近線段的像素上繪出一點。圖1顯示了這個過程的第k步，用d1和d2來標識兩個候選像素與線段數學路徑的垂直偏移。

那么，兩個候選像素與線段數學路徑的垂直偏移分別為：

其中：xk+1=xk+1，yk+1= yk+1

這兩個分離點的差分為：

d1-d2=2m(xk+1)-2yk+2b-1

如果d1d2，那么yk+1處的像素比yk的像素更接近于線段，此時選擇較高像素(xk+1，yk+1)。

2 中點Bresenham算法

將直線方程轉換為：

該直線方程將平面分為三個區域：

對于直線上的點，F(x，y)=0；

對于直線上方的點，F(x，y)>0；

對于直線下方的點，F(x，y)<0。

假設|m|≤1，在第k步，點P(xi，yi)，下一個像素可能取的點為Pu(xi+1，yi+1)，Pd(xi+1，yi)，由可以求出Pu，Pd的中心點M的坐標為(xi+1，yi+0.5)。

判別式：，則有

當d<0，誤差項的遞推

當d≥0，誤差項的遞推

初始值的計算：

0≤k≤1時Bresenham算法的步驟為：

1) 輸入直線的兩端點p0(x0，y0)和p1(x1，y1)；

2) 計算初始值x、y，d=0.5-k，x=x0、y=y0；

3) 繪制點(x，y)。判斷d的符號；若d<0，則(x，y)更新為(x+1，y+1)，d更新為d+1-k。

否則(x，y)更新為(x+1，y)，d更新為d-k。

4)當直線沒有畫完時，重復步驟3。否則結束。

3 改進中點Bresenham算法

用2d△x代替d：

1) 輸入直線的兩端點P0(x0，y0)和P1(x1，y1)；

2) 計算初始值x、y，d=△x-2△y，x=x0、y=y0；

3) 繪制點(x，y)，判斷d的符號；若d<0，則(x，y)更新為(x+1，y+1)，d更新為 d+2△x-2△y；

否則(x，y)更新為(x+1，y)， d更新為d-2△y。

4) 當直線沒有畫完時，重復步驟3。否則結束。

4 結束語

中點Bresenham算法是直線Bresenham的改進，改進的算法不必計算直線的斜率，不用做除法，不用浮點數，只用整數，而且改進的算法運算速度很快，并且適于用硬件實現。

參考文獻：

[1] 孫正興，周良.計算機圖形學基礎教程[M].北京:清華大學出版社，2004.

[2] 潘云鶴，董金祥.計算機圖形學—原理、方法及應用[M].北京:高等教育出版社，2003.

[3] 陳傳波，陸楓.計算機圖形學基礎[M].北京:電子工業出版社，2002.

[4] 孫家廣.計算機圖形學[M].3版.北京:清華大學出版社，1999.

[5] 唐澤圣.計算機圖形學基礎[M].北京:清華大學出版社，1995.

[6] Hearn D，Baker M P.Computer Graphics (C Version)[M].Prentice Hall，1997.