直线绘制算法-中点画线法

article/2025/3/1 6:58:29

之前讲过用数值积分法(DDA)进行直线逼近，通过 $int(y_{i}+0.5)$ 向下取整获取目标像素点。计算过程中每一次都需要加0.5这一浮点数，浮点数运算效率相比整数运算效率低的多，因此需要对此进行改进。

一.中点画线法

直线方程式通过一般式表示： $F(x,y)=Ax+By+C=0$ ，调整A、B参数为整数，且B为正整数。

点在直线上方则 $F(x,y)>0$ ，点在直线直线下方则 $F(x,y)<0$ ，点在直线上则 $F(x,y)=0$

前提条件k∈[0,1]，且 $P(x_{i},y_{i})$ 坐标已经确定。接下来需要判断下一个点是取点 $P_{d}(x_{i}+1,y_{i})$ 还是取点 $P_{u}(x_{i}+1,y_{i}+1)$ 。判断的依据是看 $P_{d}$ 和 $P_{u}$ 的中点 $M(x_{i}+1,y_{i}+0.5)$ 位于直线上方还是下方，若位于直线上方则取 $P_{d}$ 点，位于直线下方则取 $P_{u}$ 点，正好位于直线上则任取均可。

$d=F(x_{i}+1,y_{i}+0.5)=A(x_{i}+1)+B(y_{i}+0.5)+C$

$y=\left\{\begin{matrix} y+1 & (d<0)\\ y& (d\geqslant 0) \end{matrix}\right.$

由上述可知，d的正负决定下一个像素点是进1还是保持不变。接下来考虑d的递推关系，共分为两种情况。

1. $d_{0}\geqslant 0$ ，即中点 $M_{0}$ 位于直线上方，下一个像素点选择为 $P_{d}$

$d_{0}=F(x_{i}+1,y_{i}+0.5)=A(x_{i}+1)+B(y_{i}+0.5)+C$

$d_{1}=F(x_{i}+2,y_{i}+0.5)=A(x_{i}+2)+B(y_{i}+0.5)+C=d_{0}+A$

2. $d_{0}<0$ ，即中点 $M_{0}$ 位于直线下方，下一个像素点选择为 $P_{u}$

$d_{0}=F(x_{i}+1,y_{i}+0.5)=A(x_{i}+1)+B(y_{i}+0.5)+C$

$d_{1}=F(x_{i}+2,y_{i}+1.5)=A(x_{i}+2)+B(y_{i}+1.5)+C=d_{0}+A+B$

至此，d的增量关系已经确定，最后只需要确定 $d_{0}$ 的初值即可。已知P点为线段起点，则初始值 $d_{0}$ 可求。

$d_{0}=F(x_{i}+1,y_{i}+0.5)=A(x_{i}+1)+B(y_{i}+0.5)+C$

$=Ax_{0}+By_{0}+C+A+0.5B=A+0.5B$

总结：

$d_{0}=A+0.5B$

$d_{new}=\left\{\begin{matrix} d_{old}+A+B & (d<0)\\ d_{old}+A& (d\geqslant 0) \end{matrix}\right.$ $y=\left\{\begin{matrix} y+1 & (d<0)\\ y& (d\geqslant 0) \end{matrix}\right.$