Bresenham 算法

1965 年，Bresenham 为数字绘图仪开发了一种绘制直线的算法，该算法同样使用于光栅扫描显示器，被称为 Bresenham 算法。

原理

算法的目标是选择表示直线的最佳光栅位置。Bresenhan 算法在主位移方向上每次递增一个单位。另一个方向的增量为 0 或 1，取决于理想直线于最近网格点的距离，这一距离称为误差项，误差项用 d 表示。

在这里插入图片描述

当 $x$ 方向递增一个单位，有 $d = d + k$ ; 则

$y_{i+1} = \begin{cases} y_i + 1; &\quad d \geq 0.5\\ y_i &\quad d < 0.5 \end{cases}$
误差项初始值 $d_0 = 0$ ，如果 $\geq 0.5$ ， $y$ 方向递增一个单位并且将 $d$ 减 1.

在这里插入图片描述
消除 0.5 的影响

令 $e = d - 0.5$ . 当 $x$ 方向走一步，有 $e = e + k$ , 则

$y_{i+1} = \begin{cases} y_i + 1; &\quad e \geq 0\\ y_i &\quad e < 0.5 \end{cases}$

$e_0 = -0.5$ , 如果 $\geq 0$ , 则 $e = e - 1$

在这里插入图片描述

消除浮点数的影响，斜率和 $e$ , 进行整数化

当 $\leq k \leq 1$ ， $\Delta x$ 为正
$\Delta x e = 2 \Delta x (d-0.5) = -\Delta x + 2 \Delta x d$
初始值 $e_0 = -\Delta x$
当 x 方向走一步，有 $\Delta y$

如果 $\geq 0$ 有

$\Delta x (e-1) = 2 \Delta x e - 2 \Delta x \\ e -= 2 \Delta x$

算法

设置像素点的颜色
读入直线的两个端点坐标
取 $e$ 的初始值为 $e_0 = -0.5$
从起点开始，沿着 $x$ 轴方向每递增一个单位，有 $\Delta y$
当 $\geq 0$ 时，下一个像素更新为 $x_i + 1, y_i + 1)$ , 同时将 $e$ 更新为 $\Delta x$ , 否则，下一个像素更为 $x_i + 1, y_i +1)$
绘制像素点，执行 $x + +$ 操作到终点

void BresenhamLine(CDC* pDC, CPoint P0, CPoint P1)
{
	COLORREF crColor = RGB(0, 0, 0);
	int dx = P1.x - P0.x;
	int dy = P1.y - P0.y;
	int e = - dx;
	for (int x=P0.x, y=P0.y; x < P1.x; x++) {
		pDC->SetPixelV(x, y, crColor);
		e += 2 * dy;
		if (e >= 0) {
			y++;
			e -= 2 * dx;
		}
	}
}