Bresenham算法是图形学非常经典的光栅线生成算法，可用于显示直线、圆以及其他曲线。这里通过算法画直线过程，了解其工作原理。
问题描述
已知线段2端点\((x_0, y_0) (x_e, y_e)\)，屏幕上画出该直线段。
由于屏幕是通过像素点显示的，只能通过像素点所在的整数坐标近似代表直线上点的位置。那么，该用什么点画出直线呢？这就是Bresenham算法要解决的问题。
Bresenham算法
假设线段对应直线方程：
\begin{equation}
y = mx + b
\end{equation}
因为线段2端点在直线上，所以，
线段x、y坐标变化：
斜率m、截距b：
Bresenham算法是按变化大的轴（x轴或y轴）逐像素绘制线段。
1. 先讨论斜率m：0 < m < 1
如果现在画到了第k个像素点，位置\((x_k,y_k)\)，那么第k+1个点\((x_{k+1},y_{k+1})\)在哪？
因为0 < m < 1，所以\(∆x>∆y\)，可按x轴逐次递增绘制像素点，\(x_{k+1}=x_k+1\)；
因为直线斜率m > 0且连续，所以y是递增的，\(y_{k+1}\)取值只能是\(y_k或y_k+1\)。
因此，第k+1个点有2个选择：\((x_k+1,y_k ) or (x_k+1,y_k+1)\)
Bresenham算法根据哪个像素点到直线距离更近，就选择哪个点。然而，为了方便计算，算法并没有求点到直线的垂直距离，而是比较y轴或x轴方向偏移。
根据(1)，直线在\(x_{k+1}\)位置的y值（理论值）：
\begin{equation}
y=mx_{k+1}+b=m(x_k+1)+b
\end{equation}
记2个备选点\(y_k, y_k+1\)到直线的竖直偏移分别为\(d_{low}, d_{upper}\)，有：
\begin{equation}
\begin{aligned}
d_{low} & = y-y_k \\
& = m(x_k+1)+b-y_k
\end{aligned}
\end{equation}
\begin{equation}
\begin{aligned}
d_{upper} & = (y_k+1)-y \\
& = y_k+1-m(x_k+1)-b
\end{aligned}
\end{equation}
这里利用了m范围：0 < m < 1，有\(d_{low} > 0, d_{upper} > 0\)
如果\(y_k\)距离直线更近，即\(d_{low} < d_{upper}\)，k+1点就选择\(y_k\)；
否则，\(y_k+1\)距离更近，即\(d_{low} ≥ d_{upper}\)，k+1点选择\(y_k+1\)。
要判断哪个点距离更近，将(3)(4)做差值：