DDA算法和Bresenham算法

本文結構如下：

• 1、DDA算法
• 2、Bresenham算法
• 3、代碼實現核心部分

1、DDA算法

DDA算法是計算機圖形學中最簡單的繪制直線算法。其主要思想是由直線公式y = kx + b推導出來的。
我們已知直線段兩個端點P₀(x₀,y₀)和P₁(x₁,y₁)，就能求出 k 和 b 。

在k，b均求出的條件下，只要知道一個x值，我們就能計算出一個y值。如果x的步進為1（x每次加1，即x = x +1），那么y的步進就為k+b；同樣知道一個y值也能計算出x值，此時y的步進為1，x的步進為(1-b)/k。根據計算出的x值和y值，向下取整，得到坐標(x’,y’)，并在(x’,y’)處繪制直線段上的一點。

為進一步簡化計算，通常可令b取0，將起點看作(0,0)。設當前點為(x_i, y_i)則用DDA算法求解(x_i+1，y_i+1)的計算公式可以概括為：

• x_i+1 = x_i + xStep (1)
• y_i+1 = y_i + yStep (2)

我們一般通過計算 Δx 和 Δy 來確定xStep和yStep：

• 如果 Δx > Δy ，說明x軸的最大差值大于y軸的最大差值，x軸方向為步進的主方向，xStep = 1，yStep = k；
• 如果 Δy> Δx，說明y軸的最大差值大于x軸的最大差值，y軸方向為步進的主方向，yStep = 1，xStep = 1 / k。

根據這個公式，就能通過(x_i，y_i)迭代計算出(x_i+1、y_i+1)，然后在坐標系中繪制計算出的(x,y)坐標點。

2、Bresenham算法

Bresenham算法也是一種計算機圖形學中常見的繪制直線的算法，其本質思想也是步進的思想，但由于避免了浮點運算，相當于DDA算法的一種改進算法。

設直線的斜率為k，當|k| <=1時，x方向為主步進方向；當|k| >1時，y方向為主步進方向。現以|k| <1時為例，推導Bresenham算法的原理。

Bresenham算法直線繪制示意圖
圖片來自：http://st251256589.blog.163.com/blog/static/16487644920114112817666/

圖中繪制了一條直線，藍色點表示該直線上的點，紅色點表示光柵下繪制的點。
假設當前點是(x_i,y_i)
- 如果int(y_i+0.5) = y_i，則在點(x_i, round(y_i))處繪制.
- 如果int(y_i+0.5) = y_i + 1，則在點(x_i, round(y_i)+1)處繪制。

上述邏輯可簡述為：當x方向是主要步進方向時，以每一小格的中點為界，如果當前的y_i在中點(圖中紅色短線)下方，則y取round(y_i); 如果當前的y_i在中點上方，則y取rund(y_i)+1。

引用部分：現考慮這種方法的誤差，因為直線的起始點在像素中心，所以誤差項d的初值d₀＝0。x下標每增加1，d的值相應遞增。直線的斜率值k，即d＝d＋k。一旦d≥1，就把它減去1，這樣保證d在0、1之間。當d≥0.5時，最接近于當前像素的右上方像素（x+1,y+1）而當d<0.5時，更接近于右方像素(x+1,y）為方便計算，令e＝d-0.5，e的初值為-0.5，增量為k。當e≥0時，取當前像素（x_i，y_i）的右上方像素（x+1,y+1），而當e<0時，更接近于右方像素(x+1,y）可以改用整數以避免除法。由于算法中只用到誤差項的符號，因此可作如下替換：
e₁ = 2e * Δx。

參考：
http://blog.csdn.net/xdg_blog/article/details/52848891
http://www.cnblogs.com/weiweishuo/archive/2013/03/11/2954443.html

3、代碼實現

1、DDA算法

void CGView::DrawDDALine(int startx,int starty, int endx, int endy) { CDC* pDC = GetDC();DrawStandLine(pDC);//繪制標準直線int x0 = startx; int y0 = starty ;int x1 = endx; int y1 = endy; int color=RGB(255,0,0);int x; float dx,dy,y,k;dx = x1-x0, dy = y1-y0;k = dy / dx,y = y0;int x2 = startx; int y2 = endx;for(x = x0;x <= x1;x++){ //(20,360)是坐標軸的起點x2 = 20 + x * 30; //30是坐標軸的單位刻度pDC->Ellipse( x2 - 5, y2 - 5, x2 + 5, y2 + 5 );y = k * x + k;y = (int)(y+0.5);y2 = 360 - y * 30;} }

2、Bresenham算法

void CGView::DrawBresenham(int startx,int starty, int endx, int endy) {CDC* pDC = GetDC();DrawStandLine(pDC);//繪制標準直線int x0, y0, x1, y1;x0 = startx; y0 =starty;x1 = endx; y1 = endy;int x, y, dx, dy; dx = x1-x0, dy = y1- y0; x = x0;y = y0;double k = dy / dx;//如果 >1，則y方向是主要步進方向，需要轉換坐標系方向if(abs(k)>1){Swap(startx,starty,endx,endy);}int e = -dx; int x2 = 20, y2 = 360; //(20,360)是坐標軸的起點for (int x=x0; x<=x1; x++){ pDC->Ellipse( x2 - 5, y2 - 5, x2 + 5, y2 + 5 );x2 += 30;e += 2 * dy;if (e > 0){ y++;y2 -= 30; //30是坐標軸的單位刻度e -= 2*dx;}} }

兩種算法的運行結果情況如下圖所示，從圖中可已看出，兩種算法都能繪制出直線段，但是在細節稍有不同，當x=4時，DDA算法的y值為3，而Bresenham的算法y為2。在不過從效率上看，由于Bresenham避免了浮點運算，所以效率更高。

本文參考了網上的資料，包括圖片、文字等。在文中均給出了鏈接。時間太久了，代碼已經找不到出處了。如有疏漏，請指出。

總結

以上是生活随笔為你收集整理的DDA算法和Bresenham算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。