Bresenham 画线算法推导过程

今天复习这个算法的时候，有一点没有立马反应过来，故特此记此篇博客作为备忘。

描点原理

原理就是描实距离D点最近的那个点，距离的判断通过比较d1和d2的大小来确定。d1大，说明距离$(x_i+1,y_i)$更远，要描实$(x_i+1,y_i+1)$。相反同理。

需要说明的是此图将横线和竖线的交点看作像素点。

不妨假设直线方程为 y = kx + b ，其斜率 k 在 0 到 1 之间，并且 $x_2>x_1$。
于是我们可以有上图这样一条直线。设在第 i 步已经确定第 i 个像素点是 $(x_i,y_i)$，现在看第 i+1 步如何确定第 i+1 个像素点的位置：

我们不妨假设 D(x, y) 其中 $x=x_i+1$
$d_1=y-y_i=k(x_i+1)+b-y_i$
$d_2=y_i+1-y=(y_i+1)-k(x_i+1)-b$

• $d_1>d_2$，下一个像素点取$(x_i+1,y_i+1)$
• $d_1<d_2$，下一个像素点取$(x_i+1,y_i)$
• $d_1=d_2$，取两个像素点中的任意一个

我们知道判断 $d_1和d_2$ 大小可以通过作差来得出。
$d_1-d_2=2k(x_i+1)-2y_i+2b-1$，其中的 k 值为 $\frac{\Delta y}{\Delta x}$，其中 $\Delta x$ 为 $x_2-x_1$，$\Delta y$ 为 $y_2-y_1$。

用 $p_i$ 代替 $d_1-d_2$

这里有个问题是，k 值是通过除法得出来的，我们知道计算机计算除法都是不精确的，所以这里，我们要做一点处理，来避免除法运算。这里，我们做的是两边同乘 $\Delta x$
$\Delta x(d_1-d_2)=2\Delta y(x_i+1)-\Delta x\cdot 2y_i+\Delta x\cdot (2b-1)$

由于 $\Delta x$ 在我们假设的时候就是大于0的，于是 $d_1-d_2$ 的符号并不会因此而改变，于是我们不妨假设 $p_i=\Delta x(d_1-d_2)$。
$p_i=2\Delta y(x_i+1)-\Delta x\cdot 2y_i+\Delta x\cdot (2b-1)$
我们将其中不变的一部分提取出来，并用常数 c 来代替：
$p_i=2\Delta y\cdot x_i-2\Delta x\cdot y_i+c$
这样，我们就可以通过判断 $p_i$ 的正负来判断是描哪个点。

1. $p_i⩾0$，即 $d_1⩾d_2$，选取右边的点，此时 $y_{i+1}=y_i+1$
2. $p_i<0$，即 $d_1<d_2$， 选取右上的点，此时 $y_{i+1}=y_i$

$p_i$ 递推

当然，我们仅仅知道一个 $p_i$ 是不够的，我们得进一步的递推下去：
$p_{i+1}=2\Delta y\cdot x_{i+1}-2\Delta x\cdot y_{i+1}+c$
这里的 $p_{i+1}$ 代表下下一个描点的判别式。

通过做一个减法，我们可以得出 $p_{i+1}和p_i$ 之间的数值关系：
$p_{i+1}-p_i=2\Delta y-2\Delta x(y_{i+1}-y_i)$

于是我们可以得出下面结论：

1. $p_i⩾0$，应取 $y_{i+1}=y_i+1$, 带入得 $p_{i+1}=p_i+2(\Delta y-\Delta x)$
2. $p_i<0$，应取 $y_{i+1}=y_i$ , 带入得 $p_{i+1}=p_i+2\Delta y$

我们通过 $p_i$ 的正负选出下个点，然后判断 $p_i$ 和 $p_{i+1}$ 的关系，以此来求出 $p_{i+1}$ 的值。再通过 $p_{i+1}$ 的正负选出下个点，然后推出 $p_{i+1}$ 和 $p_{i+2}$ 的关系。

如何确定 $p_1$ 呢？

$x_1=x_1$， $y_1=\frac{\Delta y}{\Delta x}{x}_1+b$ => $\Delta x\cdot y_1=\Delta y\cdot x_1+\Delta x\cdot b$

在 $p_i$ 的公式中，不妨令 i = 1，有：
$p_i=2\Delta y(x_i+1)-\Delta x\cdot 2y_i+\Delta x\cdot (2b-1)$
$p_1=2\Delta y(x_1+1)-\Delta x\cdot 2y_1+\Delta x\cdot (2b-1)$
将刚才推导出来的式子带入化简得：
$p_1=2\Delta y-\Delta x$

程序代码

void BresenhamLine(int x1, int y1, int x2, int y2)
{
	int x, y, dx, dy, p;  //dx和dy是Δx和Δy
	x = x1;
	y = y1;
	
	dx = x2 - x1;
	dy = y2 - y1;
	
	p = 2*dy - dx;
	for (; x <= x2; x++) {
		SetPixel(x, y);
		if (p > 0) {
			y++;
			p += 2*(dy-dx);
		} else {
			p += 2*dy;
		}
	}
}