1 前言
下面的画线和画圆算法了解其思想就行，我保证就算你现在看会了，以后想写算法还是要回来再看一遍资料。所以算法这种东西会用就可以了！
2 Bresenham直线算法(任意斜率)
2.1 算法产生原因
在一张白纸上绘制一个线段只需要2个点连接即可得到。但在oled屏幕上却很难，因为oled屏幕是由一个一个的led灯组成的点阵组成的。如下图，每一个白块都是一个led灯，当我们绘制一条直线时，就需要判断在这条直线上，需要点亮哪些灯来模拟这条直线。
2.2 Bresenham直线算法原理
如下图是对Bresenham直线算法的总结。假设我们要绘制如上图中所示直线f(x,y)，它的起点在(xk,yk)，上图中的每一个圆圈是一个led灯。
为了简化理解，我们的起点和终点都是整数，并且直线的斜率为0 < m < 1 。所以毫无疑问，我们首先点亮(xk,yk)这个led灯。
那么下一个led灯，我们应该点亮哪一个呢？观察上图可以很容易发现，我们应该点亮(xk+1,yk)和(xk+1,yk+1)中的一个，那究竟选择哪个呢？一个很朴素的想法是，谁在y方向上距离直线最近，那就点亮谁。这个想法也正是Bresenham直线算法的思想。
既然已经可以确定思路了，那我们下一步就可以尝试使用数学公式来表示这个过程了。
现在我们可以想象一下，对于上图，直线与(xk+1,yk)和(xk+1,yk+1)连线的交点，如果在线段一半的上面，那么就应该选择点亮(xk+1,yk+1)，否则点亮(xk+1,yk)。
那么，我们只需要将中点坐标(xk+1,yk+1/2)坐标带入直线函数f(x,y)中:
如果f(xk+1,yk+1/2)>0，则说明直线的交点在(xk+1,yk+1/2)的下面，此时需要点亮(xk+1,yk);
如果f(xk+1,yk+1/2) < 0，则说明直线的交点在(xk+1,yk+1/2)的上面，此时需要点亮(xk+1,yk+1);
至此布雷森汉姆直线算法最核心的思想就讲完了。
2.3 进一步探索布雷森汉姆直线算法
上面我们使用的是中点的方法，我们稍加修改换一种表示(实际上也没有很大的变化，它的核心思想依然是判断距离)。
上图中红色的线，是我们想要绘制的线，它的斜率是 0 < m< 1 ，现在考虑在x点，直线对应纵轴的值为y+ϵ。
很明显
y+ϵ < y+0.5 所以(x,y)点距离直线更近，所以把该点点亮。一旦选择了(x,y)点，那么此时到直线就产生了误差：ϵ。
那么当我们绘制下一个点时，其横坐标是x+1，它对应的纵坐标是y+m+ϵ
斜率为m的直线，x增加1，那么y增加m
此时，直线在x+1时对应的纵坐标为:y+ϵ+m
同样执行如下判断：
y+ϵ+m > y+0.5 那么很明显，此时我们需要点亮(x+1,y+1)对应的灯。
此时误差就变成了：
ϵnew=(y+ϵ+m)−(y+1)如果咱们再往后计算，此时横轴到达了x+2，纵轴到达了y+1，同样的进行如下判断：
y+1+ϵ < sub>new+m < y+1+0.5 所以，需要点亮(x+2,y+1)对应的灯。
以上分别从直观和数学上对布雷森汉姆直线算法进行介绍，不知道你是否明白了，其实它本身非常简单，一定要记住的它的核心思想: 离谁近，就选谁。
以上过程的伪代码形式如下：
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs (error) ≥ 0.5 then
y := y + 1
error := error - 1.02.4 任意方向画线
上面介绍的布雷森汉姆直线算法，是在第一象限，并且斜率0 < m < 1时的情况。如果超过了这个限制，那么上面的过程就不能直接应用了，必须要做一些改进。
咱们可以来看一下面临的问题：
(1) 反方向
(2) 斜率为负
(3) 综合所有情况
所以，最终需要该算法能完成整个平面任意方式绘制直线。
如下是对该算法的实现，没做优化，所以代码略显冗余。
void paint_draw_slope_line(uint16_t xstart, uint16_t ystart, uint16_t xend, uint16_t yend,
uint16_t color, DOT_PIXEL line_width, LINE_STYLE line_style){
uint16_t temp = 0;
uint16_t xpoint = xstart;
uint16_t ypoint = ystart;
//算出2点间距离，确保值为非负值（abs函数是获取绝对值）
int dx = (int)xend - (int)xstart >= 0 ? xend - xstart : xstart - xend; // 算出两点距离
int dy = (int)yend - (int)ystart >= 0 ? yend - ystart : ystart - yend;
if(dy>dx)//为真证明斜率绝对值大于1，主要以y轴方向递增
{
temp = xstart; //x,y值互换
xstart = ystart;
ystart = temp;
temp = 0;
}
if(xstart >xend)//为真，说明起点大于终点，交换方向
{
temp = xstart;
xstart = xend;
xend = temp;
temp = 0;
temp = ystart;
ystart = yend;
yend = temp;
temp = 0;
}
uint16_t delta_x = xend -xstart;//上面换算判断，这步xend一定大于xstart
uint16_t delta_y = (int)yend - (int)ystart >= 0 ? yend - ystart : ystart - yend;
uint16_t error = 0; //误差量
uint16_t delta_error = delta_x/delta_y;//斜率
uint16_t yk = ystart; //保存初值
uint16_t y_step = 0; //设置初始步长
if(ystart < yend)
{
y_step = 1;
}else{
y_step = -1;
}
for(uint16_t xk = xstart; xk <= xend; xk++)
{
if(dy>dx)
{
paint_draw_point(yk, xk, color, line_width, DOT_FILL_AROUND);
}else{
paint_draw_point(xk, yk, color, line_width, DOT_FILL_AROUND);
}
error = error +delta_error;
if(error >= 0.5)
{
yk=yk+y_step;
error = error -1;
}
}
}3 Bresenham中点画圆算法
3.1 算法简介
Bresenham画圆算法又称中点画圆算法，与Bresenham 直线算法一样，其基本的方法是利用判别变量来判断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆 心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。
为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。
显然，我们只需要知道了圆上的一个点的坐标 (x, y) ，利用八对称性，我们马上就能得到另外七个对称点的坐标。
和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆，如下图。
3.2 公式推导
考虑圆心在原点，半径为R的圆在第一象限内的八分之一圆弧，从点（0, R）到点（R’ , R’ ）顺时针方向确定这段圆弧。假定某点Pi(xi, yi)已经是该圆弧上最接近实际圆弧的点，那么Pi的下一个点只可能是正右方的P1或右下方的P2两者之一，如下图所示：
构造判别函数：
F(x,y）= x2 + y2 – R2
当F(x,y)=0，表示点在圆上，当F(x,y)>0，表示点在圆外，当F(x,y)< 0，表示点在圆内。如果M是P1和P2的中点，则M的坐标是（xi + 1, yi – 0.5），当F（xi + 1, yi – 0.5）< 0时，M点在圆内，说明P1点离实际圆弧更近，应该取P1作为圆的下一个点。同理分析，当F（xi + 1, yi – 0.5）> 0时，P2离实际圆弧更近，应取P2作为下一个点。当F（xi + 1, yi – 0.5）= 0时，P1和P2都可以作为圆的下一个点，算法约定取P2作为下一个点。
现在将M点坐标（xi + 1, yi – 0.5）带入判别函数F(x, y），得到判别式d：
d = F（xi + 1, yi – 0.5）= (xi + 1)2 + (yi – 0.5)2 – R2
若d < 0，则取P1为下一个点，此时P1的下一个点的判别式为：
d’ = F（xi + 2, yi – 0.5）= (xi + 2)2 + (yi – 0.5)2 – R2
展开后将d带入可得到判别式的递推关系：
d’ = d + 2xi + 3
若d > 0，则取P2为下一个点，此时P2的下一个点的判别式为：
d’ = F（xi + 2, yi – 1.5）= (xi + 2)2 + (yi – 1.5)2 – R2
展开后将d带入可得到判别式的递推关系：
d’ = d + 2(xi – yi) + 5
特别的，在第一个象限的第一个点（0, R）时，可以推倒出判别式d的初始值d0：
d0 = F(1, R – 0.5) = 1 – (R – 0.5)2 – R2 = 1.25 – R
实际使用时我采用的误差算法是luckfox官方代码中的算法。
3.3 函数实现
下面的程序是我结合教程和自己的理解重写的画圆算法：
void paint_draw_circle(uint16_t x_center, uint16_t y_center, uint16_t radius,
uint16_t color, DOT_PIXEL line_width, DRAW_FILL draw_fill)
{
if (x_center > 128 || y_center > 64)
{
Debug("超出正常显示范围\r\n");
return;
}
// 画一个圆从（0,r）处作为一个起点
int16_t xcurrent, ycurrent;
xcurrent = 0;
ycurrent = radius;
// 累计误差，判断下一个点的位置
int16_t esp = 3 - (radius << 1);
// 画一个空心圆
while (xcurrent <= ycurrent)
{
paint_draw_point(x_center + xcurrent, y_center + ycurrent, color, line_width, DOT_FILL_AROUND); // 1
paint_draw_point(x_center - xcurrent, y_center + ycurrent, color, line_width, DOT_FILL_AROUND); // 2
paint_draw_point(x_center - ycurrent, y_center + xcurrent, color, line_width, DOT_FILL_AROUND); // 3
paint_draw_point(x_center - ycurrent, y_center - xcurrent, color, line_width, DOT_FILL_AROUND); // 4
paint_draw_point(x_center - xcurrent, y_center - ycurrent, color, line_width, DOT_FILL_AROUND); // 5
paint_draw_point(x_center + xcurrent, y_center - ycurrent, color, line_width, DOT_FILL_AROUND); // 6
paint_draw_point(x_center + ycurrent, y_center - xcurrent, color, line_width, DOT_FILL_AROUND); // 7
paint_draw_point(x_center + ycurrent, y_center + xcurrent, color, line_width, DOT_FILL_AROUND); // 0
if (esp <0)
{
esp += 4 * xcurrent + 6;
}
else
{
esp += 10 + 4 * (xcurrent - ycurrent);
ycurrent--;
}
xcurrent++;
}
}4 总结
这是我查阅很多资料找出的最好理解的解释了，这再看不会可以回家卖烤红薯去了。