⑴ 直線掃描演算法(個人總結,僅供參考)
直線掃描演算法主要包含三種演算法,DDA演算法、中點畫線演算法、Bresenham直線演算法。
這三種演算法都要事先要確定兩個端點(起點和終點),從起點開始每次走一步,每走一步畫一個點,直至到達終點。
這個前提也比較好理解,因為如果朝斜率大的方向走,可能沒走幾步就走完了,那畫出來的直線就是離散的。
以下我們宏隱只討論朝x方向移動的情況。(y方向的情況是一樣的)
DDA演算法實際上是根據 斜截式直線方程 來畫的。
但這么做實際上是比較消耗性能的,因為斜截式方程, 它涉及到了乘法運算 。因此我們需要通過 增量思想 對它進行優化。
這樣轉換後,我們就可以根據當前的位置來找到下一步的位置,且每次計算只需要進行一次 浮點的加法運算 ,一次四捨五入取整即蔽歷廳可。
中點畫線演算法實際上是根據 一般式直線方程 來畫的。它是通過判斷中點在直線的下方還是上方,來決定下一步的坐標位置。
但這樣也是非常消耗性能的,把中點帶入F(x, y)中,會涉及到2個乘法,4個加法。我們依然可以通過增量的方式來對它進行優化。
這樣我們就優化到每次只需要一次 整數加法 即可,且還不需要四捨五入。因此它要更優於DDA演算法。
Breseham演算法是通過比較d(交點與交點下方最近的點的距離)來進行選擇的。d每次按照k的大小增加。
但這么做依舊和DDA演算法一樣,會涉及到浮點數k的加法。我們可以通過 換元的方式 對它進行下優化。
這樣就能使得每次進行一次或兩次的 整數加法運算 ,不需要四捨五入。效率高於DDA,低於中點畫線演算法。
但Bresenham演算法不依賴直線方程,使得它能有更寬泛爛中的適用范圍。