1、2.1.1 生成直線的生成直線的 DDA 算法算法數值微分法即 DDA 法(Digital Differential Analyzer)，是一種基于直線的微分方程來生成直線的方法。一、直線 DDA 算法描述：設(x1，y1)和(x2，y2)分別為所求直線的起點和終點坐標，由直線的微分方程得= m =直線的斜率(21)可通過計算由 x 方向的增量x 引起 y 的改變來生成直線：xi+1=xi+x(22)yi+1=yi+y=yi+xm(23)也可通過計算由 y 方向的增量y 引起 x 的改變來生成直線：yi+1=yi+y(24)xi+1=xi+x=xi+y/m(25)式(22)至(25)是遞推的。

2、二、直線 DDA 算法思想：選定 x2x1和 y2y1中較大者作為步進方向(假設 x2x1較大)，取該方向上的增量為一個象素單位(x=1)，然后利用式(21)計算另一個方向的增量(y=xm=m)。通過遞推公式(22)至(25)，把每次計算出的(xi+1，yi+1)經取整后送到顯示器輸出，則得到掃描轉換后的直線。之所以取 x2x1和 y2y1中較大者作為步進方向，是考慮沿著線段分布的象素應均勻，這在下圖中可看出。另外，算法實現中還應注意直線的生成方向，以決定x 及y 是取正值還是負值。三、直線 DDA 算法實現：1、已知直線的兩端點坐標：(x1，y1)，(x2，y2)2、已知畫線的顏色：colo

3、r3、計算兩個方向的變化量：dx=x2x1dy=y2y14、求出兩個方向最大變化量的絕對值：steps=max(|dx|，|dy|)5、計算兩個方向的增量(考慮了生成方向)：xin=dx/stepsyin=dy/steps6、設置初始象素坐標：x=x1,y=y17、用循環實現直線的繪制：for(i=1；i0)?static_cast(fNum+0.5):static_cast(fNum-0.5)/*!*brief DDA 畫線函數*param pDCin窗口 DC*param BeginPtin直線起點*param EndPtin直線終點*param LineCorin直線顏色*return

4、無*/void CDrawMsg:DDA_DrawLine(CDC *pDC,CPoint &BeginPt,CPoint &EndPt,COLORREFLineCor)long YDis = (EndPt.y - BeginPt.y);long XDis = (EndPt.x-BeginPt.x);long MaxStep = max(abs(XDis),abs(YDis); / 步進的步數float fXUnitLen = 1.0f;/ X 方向的單位步進float fYUnitLen = 1.0f;/ Y 方向的單位步進fYUnitLen = static_cast(YD

5、is)/static_cast(MaxStep);fXUnitLen = static_cast(XDis)/static_cast(MaxStep);/ 設置起點像素顏色pDC-SetPixel(BeginPt.x,BeginPt.y,LineCor);float x = static_cast(BeginPt.x);float y = static_cast(BeginPt.y);/ 循環步進for (long i = 1;iSetPixel(FloatToInteger(x),FloatToInteger(y),LineCor);2.1.2 生成生成直線直線的的Bresenham算法算法

6、從上面介紹的DDA 算法可以看到，由于在循環中涉及實型數據的加減運算，因此直線的生成速度較慢。在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來生成直線的有兩種 Bresenham 算法思想，它們各自從不同角度介紹了Bresenham 算法思想，得出的誤差判別式都是一樣的。二、直線 Bresenham 算法思想之一：由于顯示直線的象素點只能取整數值坐標，可以假設直線上第 i 個象素點坐標為(xi，yi)，它是直線上點(xi，yi)的最佳近似，并且 xi=xi(假設 m1），如下圖所示。那么，直線上下一個象素點的可能位置是(xi+1，yi)或(xi+1，yi+1)。由圖中可以知道，在 x=xi+1 處，直線上點的 y 值是方法。一、直線Bresenham 算法描述：它也是采用遞推步進的辦法，令每次最大變化方向的坐標步進一個象素，同時另一個方向的坐標依據誤差判別式的符號來決定是否也要步進一個象素。我們首先討論m=y/x，當0m1 且 x1x2時的 Bresenham 算法。從 DDA 直線算法可知這些