一、???????????? 算法原理簡(jiǎn)介：

算法原理的詳細(xì)描述及部分實(shí)現(xiàn)可參考：

http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

?

Fig.1?

假設(shè)以(x, y)為繪制起點(diǎn)，一般情況下的直觀想法是先求m = dy /dx（即x每增加1， y的增量），然后逐步遞增x, 設(shè)新的點(diǎn)為x1 = x + j, 則y1 = round(y + j * m)。可以看到，這個(gè)過程涉及大量的浮點(diǎn)運(yùn)算，效率上是比較低的（特別是在嵌入式應(yīng)用中，DSP可以一周期內(nèi)完成2次乘法，一次浮點(diǎn)卻要上百個(gè)周期）。

?????? 下面，我們來看一下Bresenham算法，如Fig. 1,(x, y +ε)的下一個(gè)點(diǎn)為(x, y + ε + m)，這里ε為累加誤差。可以看出，當(dāng)ε+m < 0.5時(shí)，繪制(x + 1, y)點(diǎn)，否則繪制(x + 1, y + 1)點(diǎn)。每次繪制后，ε將更新為新值：

??????????? ε = ε + m ,如果(ε + m) <０.５ (或表示為2*(ε + m) < 1)

??????????? ε = ε + m – 1, 其他情況

??? 將上述公式都乘以dx, 并將ε*dx用新符號(hào)ξ表示，可得

??????????? ξ = ξ + dy, 如果2*(ξ + dy) < dx

??????????? ξ = ξ + dy – dx, 其他情況

??? 可以看到，此時(shí)運(yùn)算已經(jīng)全變?yōu)檎麛?shù)了。以下為算法的偽代碼：

??????????? ξ ← 0, y ← y1

??????????? For x ← x1 to x2 do

??????????????? Plot Point at (x, y)

??????????????? If (2(ξ + dy) < dx)

??????????????????? ξ ←ξ + dy

??????????????? Else

??????????????????? y ← y + 1,ξ ←ξ + dy – dx

??????????????? End If

??????????? End For

二、???????????? 算法的注意點(diǎn)：

?

?

Fig. 2

??? 在實(shí)際應(yīng)用中，我們會(huì)發(fā)現(xiàn)，當(dāng)dy > dx或出現(xiàn)Fig.2 右圖情況時(shí)時(shí)，便得不到想要的結(jié)果，這是由于我們只考慮dx > dy， 且x, y的增量均為正的情況所致。經(jīng)過分析，需要考慮8種不同的情況，如Fig. 3所示：

?當(dāng)然，如果直接在算法中對(duì)8種情況分別枚舉， 那重復(fù)代碼便會(huì)顯得十分臃腫，因此在設(shè)計(jì)算法時(shí)必須充分考慮上述各種情況的共性，后面將給出考慮了所有情況的實(shí)現(xiàn)代碼。

三、???????????? 算法的實(shí)現(xiàn)

?

以下代碼的測(cè)試是利用Opencv 2.0進(jìn)行的,根據(jù)需要，只要稍微修改代碼便能適應(yīng)不同環(huán)境

?

//Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/
void DrawLine(IplImage *img, int x1, int y1, int x2, int y2) {int dx = x2 - x1;int dy = y2 - y1;int ux = ((dx > 0) << 1) - 1;//x的增量方向，取或-1int uy = ((dy > 0) << 1) - 1;//y的增量方向，取或-1int x = x1, y = y1, eps;//eps為累加誤差 eps = 0;dx = abs(dx); dy = abs(dy); if (dx > dy) {for (x = x1; x != x2; x += ux){SetPixel(img, x, y);eps += dy;if ((eps << 1) >= dx){y += uy; eps -= dx;}}}else{for (y = y1; y != y2; y += uy){SetPixel(img, x, y);eps += dx;if ((eps << 1) >= dy){x += ux; eps -= dy;}}} }

四、???????????? 測(cè)試結(jié)果

五、???????????? 進(jìn)一步可能的改進(jìn)

設(shè)(x1, y1)為起點(diǎn),(x2, y2)為終點(diǎn)，取中點(diǎn)(x1 + x2)/2, (y1 +y2)/2，然后從兩個(gè)端點(diǎn)同時(shí)向中點(diǎn)生長(zhǎng)，這種并行運(yùn)算可以提高一定的效率。

原文地址：http://www.cnblogs.com/pheye/archive/2010/08/14/1799803.html

?

總結(jié)

以上是生活随笔為你收集整理的【转】Bresenham快速画直线算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。