dda算法

DDA(數字差分分析儀)算法 (DDA (Digital Differential Analyzer) Algorithm)

In computer graphics, the DDA algorithm is the simplest algorithm among all other line generation algorithms. Here, the DDA is an abbreviation that stands for "Digital Differential Analyzer". It is an incremental method, i.e. it works by incrementing the source coordinate points according to the values of the slope generated.

在計算機圖形學中， DDA算法是所有其他線生成算法中最簡單的算法。 在此， DDA是“數字差分分析儀”的縮寫。 這是一種增量方法，即，它根據生成的坡度值通過增加源坐標點來工作。

Hence, we can define DDA as follows,

因此，我們可以如下定義DDA，

"DDA stands for Digital Differential Analyzer. This algorithm is incremental and is used for the rasterization of lines, triangles, and polygons."

“ DDA代表數字差分分析儀。此算法是增量算法，用于線，三角形和多邊形的柵格化。”

DDA算法的工作 (Working of the DDA Algorithm)

Suppose we have to draw a line PQ with coordinates P (x1, y1) and Q (x2, y2).

假設我們必須繪制一條坐標為P(x1，y1)和Q(x2，y2)的直線PQ 。

1. First, Calculate dx = (x2 - x1) and dy = (y2 - y1)

   首先，計算dx =(x2-x1)和dy =(y2-y1)

2. Now calculate the slope m = (dy / dx)

   現在計算斜率m =(dy / dx)

3. Calculate the number of points to be plotted (i.e. n) by finding the maximum of dx and dy, i.e.?n = abs (max (dx , dy))

   通過找到dx和dy的最大值來計算要繪制的點數(即n )，即n = abs(最大值(dx，dy))

   To draw an accurate line, more number of points are required. Therefore, the maximum of the two values is used here.

   要繪制一條精確的線，需要更多的點。 因此，此處使用兩個值中的最大值。

4. Now as the n is calculated, to know by how much each source point should be incremented, calculate x_inc and y_inc as follows: x_inc = (dx / n) and y_inc = (dy / n)

   現在，當計算n時，要知道每個源點應增加多少，請按以下方式計算x _inc和y _inc ： x _inc =(dx / n)和y _inc =(dy / n)

5. Now we draw the points from P to Q. The successive points are calculated as follows: (x_next, y_next) = (x + x_inc, y + y_inc)

   現在我們將點從P畫到Q。 連續點的計算如下： (x _next ，y _next )=(x + x _inc ，y + y _inc )

   Start plotting the points from

   從開始繪制點

   P and stop when Q is reached. In case the incremented values are decimal, use the round off values.

   P并在達到Q時停止。 如果增量值為十進制，請使用四舍五入值。

Now, let us have a look at the algorithm that is followed in DDA.

現在，讓我們看一下DDA中遵循的算法。

DDA算法 (DDA Algorithm)

• Step 1: Start.

  步驟1：開始。

• Step 2: Declare x1, y1, x2, y2.

  步驟2：聲明x1，y1，x2，y2。

• Step 3: Calculate the following,

  步驟3：計算以下內容，

      dx = x2 - x1
  dy = y2 - y1
  
  

• Step 4: Calculate slope as follows,

  步驟4：按以下方式計算斜率，

      m = dy / dx
  
  

• Step 5: Calculate the no. of points (n) between x1 and x2 as follows,

  步驟5：計算編號。 x1和x2之間的點(n)如下，

      n = abs ( max ( dx , dy ) )
  
  

• Step 6: Calculate x_incand y_inc as follows,

  步驟6：按以下方式計算x _inc和y _inc ，

      xinc = (dx / n) and yinc = (dy / n)
  
  

• Step 7: Now, Initialize x = x1 and y = y1.

  步驟7：現在，初始化x = x1和y = y1。

• Step 8:

  步驟8：

      while ( x <= x2 )
  x = x + xinc
  y = y + yinc
  
  

• Step 9: Now, Plot (x,y) on the graph, and hence we get our required line between the given points.

  步驟9：現在，在圖形上繪制(x，y)，因此我們得到了給定點之間的所需線。

• Step 10: End.

  步驟10：結束。

Formula:

式：

In the entire DDA algorithm, there are three conditions and according to these conditions, the formula for calculating the coordinates is changed. These formulas are as follows,

在整個DDA算法中 ，存在三個條件，并根據這些條件更改了計算坐標的公式。 這些公式如下：

    If m < 1 :      If m > 1 :          If m = 1 :
xinc = 1        xinc = (1 / m)      xinc = 1
yinc = m        yinc = 1            yinc = 1

Example:

例：

Now let us take an example to understand the whole working of the DDA algorithm,

現在讓我們舉一個例子來了解DDA算法的整個工作原理 ，

Question: Draw a line from A(2 , 2) to B(5 , 5) using the DDA algorithm.

問題：使用DDA算法從A(2，2)到B(5，5 )畫一條線。

Solution:

解：

    Given:
x1 = 2 , y1 = 2
x2 = 5 , y2 = 6 
Calculating:    
dx  = (x2 - x1) = (5 - 2) = 3
dy  = (y2 - y1) = (6 - 2) = 4
n   = abs (max (dx , dy ) ) = abs (max (3 , 4) ) = 4
xinc = dx / n = 3/4 = 0.75
yinc = dy / n = 4 / 4 = 1

X	Y	x = round(x + xinc)	y = y + yinc
2	2	2 + 0.75 = 2.75 = 3	2 + 1 = 3
3	3	3 + 0.75 = 3.75 = 4	3 + 1 = 4
4	4	4 + 0.75 = 4.75 = 5	4 + 1 = 5
5	5	5 + 0.75 = 5.75 = 6	5 + 1 = 6

X	?	x =圓(x + x inc )	y = y + y inc
2	2	2 + 0.75 = 2.75 = 3	2 +1 = 3
3	3	3 + 0.75 = 3.75 = 4	3 +1 = 4
4	4	4 + 0.75 = 4.75 = 5	4 +1 = 5
5	5	5 + 0.75 = 5.75 = 6	5 +1 = 6

Stop here as we have reached point B.

當我們到達B點時，在此停止。

Now, Plot the points ( (2 , 2) , (3 , 3) , (4 , 4) , (5 , 5) ) on the graph and thus we get our required line from point A to point B.

現在，在圖形上繪制點((2，2)，(3、3)，(4、4)，(5、5)) ，這樣我們就得到了從點A到點B所需的線。

DDA算法的優點 (Advantages of the DDA algorithm)

Now, we will be looking at the advantages that the DDA algorithm offers over other line drawing algorithms.

現在，我們將探討DDA算法相對于其他線條繪制算法的優勢。

1. It is the simplest line generation algorithm.

   它是最簡單的線生成算法。

2. Implementation of the DDA algorithm is very easy as compared to other line generation algorithms.

   與其他線路生成算法相比，DDA算法的實現非常容易。

3. It does not use multiplication which reduces the time complexity of implementation.

   它不使用乘法來減少實現的時間復雜度。

4. It is a faster and a better method than using the direct method of the line equation: i.e. y = mx + c

   與使用線性方程式的直接方法相比，這是一種更快，更好的方法：即y = mx + c

DDA算法的缺點 (Disadvantages of the DDA algorithm)

• DDA algorithm use floating-point arithmetic as it involves the use of division in the calculation of x_inc and y_inc. This floating-point arithmetic makes the algorithm time-consuming.

  DDA算法使用浮點算法，因為它涉及在x _inc和y _inc的計算中使用除法。 這種浮點算法使算法耗時。

• The use of floating-point arithmetic decreases the accuracy of the generated points. Hence the points that we get are not accurate, i.e. they may not lie accurately on the line.

  使用浮點算法會降低生成點的準確性。 因此，我們得到的點是不準確的，即它們可能不準確地位于線上。

• As the points that we get from the DDA algorithm are not accurate, the lines generated by this algorithm are not smooth, i.e. some discontinuation and zigzag nature can be commonly seen in the lines drawn through this algorithm.

  由于我們從DDA算法獲得的點不準確，因此該算法生成的線條不平滑，即在通過該算法繪制的線條中通常可以看到一些不連續和之字形性質。

翻譯自: https://www.includehelp.com/computer-graphics/dda-digital-differential-analyzer-algorithm.aspx

dda算法