?

最近作業在做 graphics driver 涉及到 Bresenham 畫線以及畫圓算法，以防自己忘記了總結一些知識點以及源碼。

?所有代碼的輸入參數類型都是 unsinged int?

• Bresenham 直線算法

在給出直線兩個端點（x1, y1) 和 (x2, y2) 的情況下，選取 (x1, y1) 作為起始點， 依次確認相應的像素點。選取哪個端點作為起點是沒有關系的，因為線段并不存在方向這一說，只是和斜率有關系，下面會提到。

?

以點 (x_i, y_i) 為例，以 y 為步進單位， (x_i,?y_i) 的下一個像素點為?(x_i+1,?y_i+1) 和 (x_i+1,?y_i) 中的一個點，那么為了確認到底應該選哪一個點，這時就要比較垂直距離 d1 和 d2 的關系。設直線的方程為 y = kx + b，其中 k=Δy/Δx,?Δy = abs(y2 - y1),?Δx = abs(x2 - x1)。此時

，?，?

接下來可以得到

在上面這個表達式中，可以發現我們涉及到了除法運算，為了消除除法運算可能引入的誤差，在等式兩邊同時乘 Δx， 并命名為一個新的變量

?

其中c是最終化簡得到的總的常數。此時 pi 和（d1 - d2) 同號，我們可以根據 pi 的正負來判斷下一個像素點的位置：

?當 pi > 0 時， d1 > d2，，?

?當 pi <= 0 時，d1 <= d2，，?

?

由于直線起點為 (x1, y1)， 那么將起點坐標帶入 p 的表達式后可以得出 p1 的值：

， 其中?， 化簡得?

以上為 Bresenham 算法的基本思想，由于我們只討論了步進單位為 y 的情況，也就是說以上情況中我們能得到的直線最大斜率為 1（也就是說上述過程都是在討論?Δx > Δy 的情況）。那么對于直線斜率小于等于 1 的情況， 只需要把步進單位改成 x 就可以了。

以下為源代碼：

可以直接定義 void 類型，不用返回值。

?

• Bresenham 畫圓算法

圓形算法和直線算法思想差不多，都是根據前一個像素點來選取后一個像素點的位置。由于圓的對稱性，在得到圓上的一個點的同時，相當于我們同時得到了圓上互相對稱的八個點，可以看下圖理解一下 （坐標軸我忘畫了嘻嘻嘻）

?

和直線算法同理，在點 (x_i, y_i) 的基礎上，在 (x_i+1,?y_i+1) 和(x_i+1,?y_i) 中確定下一個像素點，那么按理說還是應該比較 d1 和 d2 的大小，但是這倆值并不好求（涉及到浮點數運算 blablabla），所以在這里做一個近似，令 d1 = d3 = |AC|, d2 = d4 = |BD|,?，?。 同樣的引入一個變量 p 來表示差值?，情況如下：

當 pi > 0 時，選取點 (x_i+1,?y_i+1)，?

當 pi <= 0 時， 選取點?(x_i+1,?y_i)，?

?

將起始點設為 (0, r)，

根據圓的八分對稱性，先設置八個部分的坐標值（圓心可以任意選取）， 這部分可以單獨寫一個函數也可以和畫圓合并。代碼如下：

如果想要對圓進行填充，可以選取外接正方形，判斷正方形內的像素點是否在圓內來填充，也可以用 Bresenham 法畫 n 個圓來填充， 由于我用第二種方法填充有部分像素點填不滿，所以就先放第一種方法的代碼：

?

轉載于:https://www.cnblogs.com/molly77/p/10556259.html

總結

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

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