直线中点算法

中点算法是基于隐函数方程设计的，使用像素网格中点来判断如何选取距离理想直线最近的像素点，直线的中点算法不仅与 Bresenham 算法产生同样的像素点集，二期还可以推广到圆和椭圆。

原理

直线的隐函数表示

$$F(x,y)=y?kx?b=0$$
理想直线将平面划分成三个区域
对于直线上的点， $F(x, y) = 0 $
对于直线上方的点，$F(x,y)>0$
对于直线下方的点，$F(x,y)<0$

中点误差项

$$d_i=F(x_i+1,y_i+0.5)=y_i+0.5?k(x_i+1)?b$$

$$y_{i+1}=\{\begin{array}{ll}{y}_i+1& d_i<0\\ y_i& d_i\ge 0\end{array}$$

中点误差项的递推公式

• 当 $d_i<0$ ， 下一步进行判断的中点为 $M_u(x_i+2，y_i+1.5)$ ， 中点的误差项的递推公式为

$$d_{i+1}=d_i+1?k$$

上一步选择 $P_u$ 后，中点误差项的增量为 $1?k$

• 当 $d_i\ge 0$ 时，下一步进行判断的中点为 $M_d(x_i+2,y_i+0.5)$ 中点的误差项的递推公式为
  

$$d_{i+1}=d_i?k$$
上一步选择 $P_d$ 后，中点误差项的增量为 $?k$

中点误差项的初始值

直线的起点坐标扫描转换后的像素为 $P_0(x_0,y_0)$ .从像素 $P_0$ 出发沿着主位移 $x$ 方向的递增一个单位，第一个参与判断的中点是 $M(x_0+1,y_0+0.5)$。 代入中点误差项计算公式， $d$ 的初始值为

$$d_0=0.5?k$$

算法

• 设置像素点的颜色
• 读入直线的两个端点坐标
• 计算中点误差项的初始值 $d$
• 当 $d<0$ 时， $d$ 的增量为 $1?k$， 当 $d\ge 0$ 时， $d的增量为?k$
• 根据每一步中点误差项的值，选择像素点并绘制出来

void MidPointLine(CDC* pDC, CPoint P0, CPoint P1) {
	COLORREF crColor = RGB(0, 0, 0);
	double k, d;
	int dx = P1.x - P0.x;
	int dy = P1.y - P1.y;
	k = double (dy) / dx;
	d = 0.5 -k;
	double inColorUp = 1 - k;
	double inColorDown = -k;
	for (int x=P0.x, y= P0.y; x <P1.x; x++) {
		pDC->SetPixelV(x, y, crColor)
		if (d <0) {
			y++;
			d += inColorUp;
		}
		else {
			d += inColorDown; 
		}
	}  	
}

总结

中点算法是一种浮点数算法，现在的计算机做浮点数运算和整数运算一样快
中点算法设计巧妙，不需要取证操作
中点算法同样适用于绘制圆和椭圆

参考 《计算几何算法与实现》孔令德