直线的生成算法 BresenHam

线条绘制算法是一种用于在离散视觉媒体上显示线段的方法

设直线的从起点$x_1, y_1$到终点$x_2,y_2$,直线可以表示方程$y = kx + b$

假定直线的点是位于第一象限，并且斜率是大于 0 小于 1 的，这这种情况下，当直线光栅化时，$x$每次都是自增 1,而相应的$y$的增量是小于 1 的，为了光栅化，当$x_i$增加 1 时，y 只能是$y_i$或者$y_i + 1$两个位置之一

$y_i$或者$y_i + 1$的位置选择的原则是有精确值$y$与$y_i$和$y_i + 1$的距离$d_1$和$d_2$的大小而定的，计算公式如下

$$y = kx_i + 1 + b \\d_1 = y - y_i \\d_2 = y_i + 1 - y$$

如果$d_1 - d_2 > 0$,则选择$yi + 1$, 否则选择$y_i$,因此算法的关键在与简便的求出$d_1 - d_2$的符号，
$$d_1 - d_2 = 2y - 2y_i -1 = 2mx_i + 1 - 2y_i + 2b -1 \tag{1}$$
$$m = \frac{y_2 - y_1}{x_2 - x_1} \tag{2}$$
令$\Delta x =x_2 - x_1$, $\Delta y =y_2 - y_1$
将2式带入1式
$$\Delta xd_1 - d_2 = 2x_i\Delta y - 2y_i\Delta x + 2\Delta y + \Delta x2b-1 \tag{3}$$

由于已经假定直线的 2 个端点都是在第一象限，并且斜率是大于 0 小于 1 的,所以$\Delta x$大于 0,因此$\Delta xd_1 - d_2$依然可以用作符号判断

令$P_i = \Delta xd_1 - d_2$
则 3 式表示为
$$P_i = 2x_i\Delta y - 2y_i\Delta x + 2\Delta y + \Delta x2b-1 \tag{4}$$

$$P_{i+1} = 2x_{i+1}\Delta y - 2y_{i+1}\Delta x + 2\Delta y + \Delta x2b-1$$
$$P_{i+1} - P_i = 2\Delta y - 2\Delta xy_{i + 1} - y_i \tag{5}$$

综合所述,针对上述条件下的直线 BresenHam 算法思想如下

1. 绘制第一个点 计算$\Delta x, \Delta y, P_0 = 2\Delta y - 1$
2. 求下个位置$x_{i+1} = x_i + 1$若$P_i > 0$则取$y_{i+1}$否则$y_i$
3. 绘制
4. 求下一个误差,若$P_i > 0$则取$P_i+ 1 = P_i + 2\Delta y - 2 \Delta x$否则$P_i+ 1 = P_i + 2\Delta y$
5. 判断是否需要终止，否则执行2、3、4

当斜率的绝对值大于1时，将x和y，dx,dy进行对换

代码实现

请参考直线的生成算法_BresenHam