直線生成dda演算法原理

Ⅰ 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次；

Ⅱ 生成演算法的步驟是( )

直線生成演算法中的數值/字微分分析法是一種增量計算方法。它按照斜率絕對值|k|<1和|k|>1來遞增畫描點。|k|<1時，取像素（x，（int）(y+0.5)；|k|>1時，取像素（（int）(x+0.5)，y)。

循環結構需要重復執行同一操作的結構稱為循環結構，即從某處開始，按照一定條件反復執行某一處理步驟，反復執行的處理步驟稱為循環體。循環結構中通常都有一個起循環計數作用的變數，這個變數的取值一般都包含在執行或終止循環的條件中。

演算法原理

SJT演算法，即Steinhaus–Johnson–Trotter algorithm，是一種全排列生成演算法。在該演算法中，不斷的尋找一種相鄰元素相互交換的順序，根據這種交換的順序，依次計算下一個排列。在SJT演算法中，每次循環都進行一次滿足條件的相鄰元素的交換，直到不存在滿足條件的可交換的元素，此時說明所有排列的情況均已輸出，演算法結束。

Ⅲ 分別解釋直線生成演算法DDA法、中點畫線法和Bresenham法的基本原理

DDA稱為數值微分畫線演算法，是直線生成演算法中最簡單的一種。原理相當簡單，就是最直觀的根據斜率的偏移程度，決定是以x為步進方向還是以y為步進方向。然後在相應的步進方向上，步進變數每次增加一個像素，而另一個相關坐標變數則為Yk_1=Yk+m（以x為步進變數為例，m為斜率）
假定直線斜率k在0~1之間，當前象素點為（xp,yp），則下一個象素點有兩種可選擇點P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線的交點。當M在Q的下方時，則取P2應為下一個象素點；當M在Q的上方時，則取P1為下一個象素點。這就是中點畫線法的基本原理

Bresenham：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。

大概就是這樣，預知詳細，可以參考圖形學的書籍

Ⅳ 計算機圖形學的題：已知起點A(16,-5)和終點B(-4,8)，用DDA法在A和B之間生成一段直線

樓主，你是用對稱DDA演算法還是簡單DDA演算法呢？

我用對稱DDA演算法給你做了下，答案如下，供參考（由於貼上去格式會亂，附了一張圖片）：

對稱DDA演算法

1.計算初值△x=-4-16=-20，△y=8-(-5)=13，則n=5，ε=2-n=0.03125

因此，增量分別為：ε*△x=-0.625，ε*△y=0.40625

2.按遞推公式循環計算點的坐標，並取整數顯示。

i計算坐標顯示坐標i計算坐標顯示坐標

x1y1xipyipX1y1xipyip

016.5-4.516-4175.2252.4062552

115.875-4.0937515-4184.62.812542

215.25-3.687515-3193.9753.2187533

314.625-3.2812514-2203.353.62533

414-2.87514-2212.7254.0312524

513.375-2.4687513-2222.14.437524

612.125-2.062512-2231.4754.8437514

711.5-1.6562511-1240.855.2505

810.875-1.2510-1250.2255.6562505

910.25-0.8437510026-0.46.062506

109.6-0.43759027-1.0256.46875-16

118.975-0.031258028-1.656.875-16

128.350.3758029-2.2757.28125-27

137.7250.781257030-2.97.6875-27

147.11.18757131-3.5258.09375-38

156.4751.593756132-4.158.5-48

165.85252

3.畫一張圖XY軸，將（xip，yip）標上去，描繪成一條直線即可。