数值微分法（DDA）详解

数值微分法（$DDA$DDA）

一、原理

1. 假定直线的起点、终点分别为：$(x_0,y_0)$(x0​,y0​)，$(x_1,y_1)$(x1​,y1​)，且都为整数。
   
   则过端点$P_0 (x_0, y_0)$P0​(x0​,y0​)，$P_1(x_1, y_1)$P1​(x1​,y1​)的直线段$L:y=kx+b$L:y=kx+b，直线斜率为：
   $k=\frac{y_1-y_0}{x_1-x_0}\ (x_1\neq x_0)$k=x1​−x0​y1​−y0​​ (x1​​=x0​)

2. 假设$x$x已知，即从$x$x的起$x_0$x0​开始，沿$x$x方向前进一个像素（步长= 1)，可以计算出相应的y值。因为像素的坐标是整数，所以y值还要进行取整处理：
   $y=round(y)$y=round(y)

3. $DDA$DDA算法就是一个增量算法，即在一个迭代算法中，如果每一步的$x$x、$y$y值是用前一步的值加上一个增量来获得，则称为增量算法。

4. 这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

二、计算

$\begin{aligned} y_{i+1} &= kx_{i+1}+b \\ &=k(x_i+\Delta x)+b\\ &=kx_i+b+\Delta x\\ &= y_i+k\Delta x\\ \end{aligned} \\$yi+1​​=kxi+1​+b=k(xi​+Δx)+b=kxi​+b+Δx=yi​+kΔx​

• 当$x$x每递增$1$1，$y$y递增$k$k(即直线斜率)，即当$x_{i+1}=x_i+1$xi+1​=xi​+1时，$y_{i+1}=y_i+k$yi+1​=yi​+k；
• 取整：$y_{i+1}= round(y_i+k+0.5)$yi+1​=round(yi​+k+0.5)；
• 注意上述分析的算法仅适用于$|k|≤1$∣k∣≤1的情形。在这种情况下，$x$x每增加$1$1，$y$y最多增加$1$1。
• 当$|k|\geq 1$∣k∣≥1时，$y$y每增加$1$1，$x$x增加$\frac{1}{k}$k1​，之后同理。

三、举例

写出下列直线段$P_0(0,0)\to P_1(5,2)$P0​(0,0)→P1​(5,2)所经过实际坐标。

1. 判断$k$k值，决定使用谁为增量
   $k=\frac{2-0}{5-0}=0.4<1$k=5−02−0​=0.4<1，使用$x$x为增量，步长为$1$1。
2. 计算
   $\begin{aligned} x_{i+1}&=x_i+1\\ y_{i+1}&=y_i+0.4 \end{aligned}$xi+1​yi+1​​=xi​+1=yi​+0.4​
   即：当$x_{i+1}=x_i+1$xi+1​=xi​+1时，$y_{i+1}=y_i+0.4$yi+1​=yi​+0.4

3. 结果
   经过如下5个坐标：
   $P_0(0,0)、P_1(1,0)、P_2(2,1)、P_3(3,1)、P_4(4,2)、P_5(5,2)$P0​(0,0)、P1​(1,0)、P2​(2,1)、P3​(3,1)、P4​(4,2)、P5​(5,2)