写在前面

应用场景：Bresenham算法是图象图形学中的经典算法，在图形渲染、图像画线都会用到它，非常非常著名。

特点：原理简单（思想很伟大），计算高效，没有浮点型运算，很适合在硬件实现。

这样一个经典、强大的算法还是十分值得学习和记录的！

算法原理

从数学的角度，建立一个坐标系，当我们在坐标系中画一条线时，这条线上的值（坐标的连续的）；但是计算机中的图像是以一个一个像素组成的，是一个又一个的小格子，那么在图像上已知起点和终点画一条线，这条线就是由一个一个格子组成的，Bresenham算法就是去不断地寻找离“这条线”最近的格子（像素），然后画出线段，如下图：

Bresenham直线算法示意

 

图片来自：https://oldj.net/blog/2010/08/27/bresenham-algorithm

那么如何找离线最近的点呢？且看下图：

假设黑色（xi,yi）为 线段的起点，黑色的D点为经过该线的下一点，这时有两个像素点选择：（xi+1,yi+1）、（xi+1,yi），这两个点距离黑色D点的距离分别为d2、d1，通过比较d2和d1大小就可确定选取哪一点作为线段的下一个点。如d1大，说明距离(xi+1,yi)(x_i + 1, y_i)(xi​+1,yi​)更远，要描实(xi+1,yi+1)(x_i + 1, y_i + 1)(xi​+1,yi​+1)。相反同理。

算法推导

算法具体推导请看：https://blog.csdn.net/sinat_41104353/article/details/82858375

注意： 上面的博客的推导中只考虑了斜率 k 在 0 到 1 之间，也就是说只只能画0~45°的线。

如果想要画0~360度的线，就需要考虑他们的共性所在，具体可参考：https://zhuanlan.zhihu.com/p/106155534

 

c++实现

#include <iostream>
#include <stdio.h>
 
#define H 16     //触摸框宽度
#define W 16
using namespace std;
unsigned short Array[H][W];
 
void Bresenham(unsigned short x1, unsigned short y1, unsigned short x2, unsigned short y2, unsigned short(*array)[W]){
 
	int dx = abs(x2 - x1);
 
	int dy = abs(y2 - y1);
 
	bool is_great_than_45_degree = false;
 
	if (dx <= dy)
	{
		// 大于45度
		// Y 方向上变化速率快于 X 方向上变化速率，选择在 Y 方向上迭代，在每次迭代中计算 X 轴上变化；
		is_great_than_45_degree = true;
	}
 
	int fx = (x2 - x1) > 0 ? 1 : -1;
	int fy = (y2 - y1) > 0 ? 1 : -1;
	
	if (dy == 0)//0°
		fy = 0;
	if (dx == 0)//90°
		fx = 0;
 
	int ix = x1;
	int iy = y1;
	int p1 = 2 * dy - dx; //小于等于45°
	int p2 = 2 * dx - dy; //大于45°
if (is_great_than_45_degree){
		while (iy != y2){
			//Array[num - iy - 1][ix] = 0;
			*(*(array + (H- iy - 1)) + ix) = 1;
			//p2>0
			if (p2 > 0){
				p2 += 2 * (dx - dy);
				ix += fx;
			}
			else{
				p2 += 2*dx;
			}
			iy += fy;
			//Array[num - iy - 1][ix] = 0;
			*(*(array + (H - iy - 1)) + ix) = 1;
		}
	}
	else{
		while (ix != x2){
			//Array[num - iy - 1][ix] = 0;
			*(*(array + (H - iy - 1)) + ix) = 1;
			//p1>0
			if (p1 > 0){
				p1 += 2 * (dy - dx);
				iy += fy;
			}
			else{
				p1 += 2 * dy;
			}
			ix += fx;
			//Array[num - iy - 1][ix] = 0;
			*(*(array + (H - iy - 1)) + ix) = 1;
		}
	}
}
 
 
 
void main(){
	memset(Array, 0, H*W);
	unsigned short (*arr)[W] = Array;
	Bresenham(15, 15, 0, 5, arr);
	for (int i = 0; i < H; ++i){
		for (int j = 0; j < W; ++j){
			cout << int(Array[i][j]) << " ";
		}
		cout << endl;
	}
	system("pause");
}

效果

为1的就是所画的线段

 

参考：

https://www.cnblogs.com/pheye/archive/2010/08/14/1799803.html

https://www.cnblogs.com/pheye/archive/2010/08/14/1799803.html

https://blog.csdn.net/sinat_41104353/article/details/82858375