在位图上画直线

Wed Feb 18, 2015

在显示器上画出的各种图形中，直线是最简单的一种。这里说的直线，有确定的起点和终点；数学家也许更愿意称其为线段。

画直线是如此的简单，以至于人们也许已经忽略了它也是逐个像素点绘制出来的，而把它当作一种原子的操作。我也是如此认为，直到昨天一位同学谈他的计算机图形学课程时，说到了这个问题。

于是我尝试用自己的知识来解决这个问题。显示器上的直线和数学上的线段最明显的差别是，前者是由有限个点构成的，而后者不是。所以，显示器上的直线只是一种近似，而我要使得这种近似的效果尽量好。

为了简化问题，假设显示器显示的是一幅单色的位图。我想到的做法是这样的：

画完一个点后，在其周围的点中，找到距离给定直线最近的点，然后画这个点。
重复第2步，直到画了终点为止。

这个做法看上去应该没有问题，只有一些细节部分需要考虑。

点到直线距离

首先要考虑的是，怎样确定一个点到给定直线的距离最近？平面解析几何给出了点(x0,y0)到直线Ax+By+C=0的距离公式： d=|Ax0+By0+C|A2+B2

给出的是两个端点，而距离公式中使用的是直线方程，其中的3个待定系数需要求解。根据直线的两点式方程，过(x1,y1),(x2,y2)的直线方程为 (y1−y2)x−(x1−x2)y+x1y2−x2y1=0

如果给出第3个点(x3,y3)，则该点到直线的距离 d=|(y1−y2)x3−(x1−x2)y3+x1y2−x2y1|(y1−y2)2+(x1−x2)2 看上去有些复杂。实际上，对于给定的直线而言，式中的分母是常数，因此无需计算，只需比较分子的大小即可。而分子 |(y1−y2)x3−(x1−x2)y3+x1y2−x2y1|=||y11y21|x3−|x11x21|y3+|x1y1x2y2||=|det(x1y11x2y21x3y31)|

是一个非常好记的形式。

画线的方向

上文使用两个端点确定了直线的方程，但是仍然有一个细节值得注意：画完起点以后，面向终点和背离终点的两个方向都存在一个到直线距离最短的点，因此必须做出取舍。有两种办法处理这个问题。

把所有对称的情况化归到一种最基本的情况，在这种情况里（比方说），斜率永远在[0,1]区间里，而起点是左下角的那个点。这样的话，枚举所谓“周围的点”，只要枚举两个点：右边的点和右上角的点。

单调性限制

这种做法在编程中更加方便。其原理是，限制所画的各点的坐标是单调变化的，其单调的方向由给定的两点的相对位置而定。

Talk is cheap, show me your code.

#include <stdlib.h>

typedef void *Bitmap; /* 位图类型(代码中未给出实现) */
extern void set_pixel(Bitmap b, int x, int y, int color);
/* 把位图b的(x, y)坐标设置为color颜色 */
extern void is_pixel(Bitmap b, int x, int y);
/* 检查坐标(x, y)是否在位图b的范围内 */

static
int crossp3(int x1, int y1, int x2, int y2, int x3, int y3)
{
	return x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2);
}

void line(Bitmap b, int x1, int y1, int x2, int y2)
{
	int x, y, xx, yy;
	int dxmin, dymin;

	dxmin = (x1 < x2) ? 0 : -1;
	dymin = (y1 < y2) ? 0 : -1;
	x = x1;
	y = y1;
	for (;;) {
		int xx, yy, dx, dy, x3, y3;
		int crossp, min_crossp = INT_MAX;

		set_pixel(b, x, y, 1);
		if (x == x2 && y == y2)
			break;
		for (dx = dxmin; dx <= dxmin+1; dx++) {
			for (dy = dymin; dy <= dymin+1; dy++) {
				if (!dx && !dy)
					continue;
				if (!is_pixel(b, x3 = x+dx, y3 = y+dy))
					continue;
				crossp = abs(crossp3(x1, y1, x2, y2, x3, y3));
				if (crossp < min_crossp) {
					min_crossp = crossp;
					xx = x3;
					yy = y3;
				}
			}
		}
		x = xx;
		y = yy;
	}
}

在位图上画直线