dda直線演算法-ag真人国际官网

ⅰ dda法生成直線的基本原理是什麼為什麼說bersenham畫圓的演算法效率較高

dda演算法主要是根據直線公式y = kx b來推導出來的，其關鍵之處在於如何設定單位步進，即一個方向的步進為單位步進，另一個方向的步進必然是小於1。演算法的具體思路如下：
1. 輸入直線的起點、終點；
2. 計算x方向的間距：△x和y方向的間距：△y。
3. 確定單位步進，取maxsteps = max（△x，△y）; 若△x>=△y，則x方向的步進為單位步進，x方向步進一個單位，y方向步進△y/maxsteps;否則相反。
4. 設置第一個點的像素值
5. 令循環初始值為1，循環次數為maxsteps，定義變數x,y，執行以下計算：
a. x增加一個單位步進，y增加一個單位步進
b. 設置位置為（x,y）的像素值

bresenham演算法是dda演算法畫線演算法的一種改進演算法。本質上它也是採取了步進的思想。不過它比dda演算法作了優化，避免了步進時浮點數運算，同時為選取符合直線方程的點提供了一個好思路。首先通過直線的斜率確定了在x方向進行單位步進還是y方向進行單位步進：當斜率k的絕對值|k|<1時，在x方向進行單位步進；當斜率k的絕對值|k|>1時，在y方向進行單位步進。
1. 輸入線段的起點和終點。
2. 判斷線段的斜率是否存在（即起點和終點的x坐標是否相同），若相同，即斜率不存在，
只需計算y方向的單位步進（△y 1次），x方向的坐標保持不變即可繪制直線。
3. 計算線段的斜率k，分為下面幾種情況處理
a. k等於0，即線段平行於x軸，即程序只需計算x方向的單位步進，y方向的值不變
b. |k|等於1，即線段的x方向的單位步進和y方向的單位步進一樣，皆為1。直接循環△x次計算x和y坐標。
4. 根據輸入的起點和終點的x、y坐標值的大小決定x方向和y方向的單位步進是1還是-1
6. 畫出第一個點。
7. 若|k| <1，設m =0,計算p0，如果pm>0，下一個要繪制的點為（xm 單位步進，ym），
pm 1 = pm -2*△y;
否則要繪制的點為（xm 單位步進，ym 單位步進）
pm 1 = pm 2*△x-2*△y；
8. 重復執行第七步△x-1次；
9. 若|k| <1，設m =0,計算q0，如果qm>0，下一個要繪制的點為（xm，ym 單位步進），
pm 1 = pm -2*△x;
否則要繪制的點為（xm 單位步進，ym 單位步進）
pm 1 = pm 2*△y-2*△x；
10. 重復執行第9步△y-1次；