中点画线算法

一、原理

已知直线的一般式方程：

​ $F(x,y)=0$， 即$Ax+By+C=0$

其中：

• $A=-(\Delta y)$
• $B=(\Delta x)$
• $C=-B(\Delta x)$

如图：

代入m，当$x_m,y_m$取不同值时，函数$F(x_m,y_m)$的取值可以分三种情况，

• $F(x_m,y_m)=0$，m点在直线上
• $F(x_m,y_m)<0$，m点在直线下方
• $F(x_m,y_m)>0$，m点在直线上方

二、推导

1. 以$0\le |k|\le 1$来讨论:

   如图：

   可以看出每次在x方向上加1，y方向上加1或不变需要判断。

2. 通过仔细观察，发现:

   • 当M在Q的下方时，则$P_u$ 离直线近，应为下一个象素点;

   • 当M在Q的上方，应取$P_d$ 为下一点。

3. 利用中点画线的基本原理

   将M带入代入理想直线方程，可得
   $$F(x_m,y_m)=A{x}_m+B{y}_m+C$$
   令$d_i=F(x_m,y_m)$

   则有：$d_i=F(x_i+1,y_i+0.5)=A(x_i+1)+B(y_i+0.5)+C$

   有三种情况：

   • 当d = 0 时： M在直线上，选$p_d$或$p_u$均可；
   • 当d > 0 时： M在Q上方，应取$p_d$；
   • 当d < 0 时： M在Q下方，应取$p_u$。

   d的值决定了y的值：

   ​ $d_i=A(x_i+1)+B(y_i+0.5)+C$

$$y_{i+1}=\{\begin{array}{ll}{y}_i+1,& (d_i<0)\\ y_i,& (d_i\ge 0)\end{array}$$ ​

三、优化

1. 分析计算量

   为了求出d值，需要两个乘法，四个加法，且有浮点数运算。

2. 提高运算效率

   因为d是x,y的线性函数，采用增量计算是可行的。

   $d_{i+1}=d_i+增量$

3. 计算增量

   • 计算$d_0$

     $d_0=F(x_{M_0},y_{M_0})$

     ​ $=F(x_i,y_i+0.5)$

     ​ $=A(x_i+1)+B(y_i+0.5)+C$

   • 计算$d_1$

     如图：
     

     $d_1=F(x_{M_1},y_{M_1})$

     ​ $=F(x_i+2,y_i+1.5)$

     ​ $=A(x_i+2)+B(y_i+1.5)+C$

     ​ $=A(x_i+1)+B(y_i+0.5)+C+A+B$

     ​ $=d_0+A+B$

   • 计算$d_2$

     如图：
     

     $d_2=F(x_{M_2},y_{M_2})$

     ​ $=F(x_i+2,y_i+0.5)$

     ​ $=A(x_i+2)+B(y_i+0.5)+C$

     ​ $=A(x_i+1)+B(y_i+0.5)+C+A$

     ​ $=d_0+A$

   • 计算d的初始值$d_0$

     因为直线的第一个像素$P_0(x_0,y_0)$在直线上，即$A(x_0)+B(y_0)+C=0$，因此相应的d的初始值计算如下：

     $d_0=F(x_0,y_0+0.5)$

     ​ $=A(x_0+1)+B(y_0+0.5)+C$

     ​ $=A(x_0)+B(y_0)+C+A+0.5B$

     ​ $=A+0.5B$

   • 综上可得：
     $d_0=A+0.5B$

$$d_{i+1}=\{\begin{array}{ll}{d}_i+A+B,& (d_i<0)\\ d_i+A,& (d_i\ge 0)\end{array}$$ ​

至此，中点算法至少可以和DDA算法一样好。

4. 摆脱浮点运算

   用2d代替d来摆脱浮点运算，写出仅包含整数运算的算法。这样，中点生成直线的算法提高到整数加法，优于DDA算法。

   即：

$$d_{i+1}=\{\begin{array}{ll}{d}_i+2(A+B),& (d_i<0)\\ d_i+2A,& (d_i\ge 0)\end{array}$$ ​
$$d_0=2A+B$$