Bresenham直线算法个人理解

​最近在学习野火的单片机的电容屏，顺便学习了一下屏幕的显示原理等内容，到了往屏幕中显示图像的时候遇到了一个算法，下面是我自己学习的一些笔记，该文章只是个人理解以及算法的简单实现，同时我在实现这个算法的时候并没有很好的考虑到算法的复杂度等条件，因此可能我自己算法的代码会相当的愚蠢，具体有什么可以改进以及错误，请各位大佬们指出。

在纸张上，给出任意的一个起点和终点，要求我们画出一条连接他们的直线，这在显示中相当简单，但是如果在一个一个像素中画一条直线就相对困难，例如我们在屏幕上斜着画一条线，我们就很贵相对困难，因为像素是行列排列的，并没有斜着的部分。

屏幕像素原理：

就像上图中的，屏幕中的像素是像一个表格一样，每个像素都是有指定大小的像素格子，而每个格子中都有相应的像素值，这个像素值是有关RGB三种颜色的具体表示数值，我们通过这些格子以及格子中的像素值，就能显示各种图像

但是如果我们想要显示的是直线的话，就会比较困难，因此我们需要使用到计算机图形学的Bresenham直线算法，这个算法具体的作用就是：计算在屏幕上的一个像素点到另一个像素点之间画一条直线时下一个需要赋予像素值的像素的位置

直线方程

众所周知，一条直线可以使用一条方程来表示，也就是说每条线段之间都能使用来进行表示，并且直线上的点都在直线上，因此如果我们知道了直线的k、b，我们就能知道线段上的任何点

因此重点就是知道直线的斜率（k）以及截距（b）。

而当我们想要在屏幕上的一个点到另一个点之间画一条直线，我们就可以线通过这两个像素点的坐标值先将斜率k以及截距b计算出来，然后我们就可通过这条直线方程来计算出两个点之间的任意一个点

如下图

我们可以计算出蓝色直线的斜率以及偏置，并计算出直线在x轴的每个整数位处的y的值，为了解释清楚我们进一步的将图更改一下，我们就是用图片的左下角区域来讲解一下我对这个算法的理解

算法的在干啥

我们将上面的图更改一下，更改如下图所示：

y取值理解图

我们画出了黑色的辅助线，我们可以将粗黑色线框起来的一个个矩形看作一个一个的像素点，而算法实际在做的其实就是判断直线上面的点应该在哪个像素中显示出来

我们上面的这个例子中蓝线是（10， 8）以及（1，1）两个像素点所要表示的直线，通过计算我们可以算出当前直线的

然后我们将计算到的斜率k并选取蓝色直线上的任意一个点（这里我们带入的是(1，1)）带入以下的式子中求得截距b为：

我们通过最简单的程序验证以下：

def evaluation(x1, x2, y1, y2)
    k = (y2 - y1) / (x2 - x1)               # 斜率
    b = y1 - k * x1
    print(f"{k}, {b}")

if __name__ == "__main__":
    evaluation(10, 1, 8, 1)

>>>
0.7777777777777778, 0.22222222222222232

验证正确我们继续

求出斜率k以及截距b过后，我们就可求出任何在直线上的点，但是我们使用的是像素，像素不会有浮点数，因此我们的x只需要使用整数即可

因此可以看到上面的 y取值理解图 都是直接使用整数作为输入x的，因此我们直接将整数1-3作为x输入到算式中，结果如蓝色直线所示，当x=1时，y的取值应该为

很明显当x=1时，y的值也为1，最接近1号像素点，因此1号像素点将会用于显示直线

而当x=2时，y的取值为：，此时y的值处于y轴的整数的1和2之间，也就是要么在像素2中显示，要么在像素3中显示，但是由于此时的y值更加接近整数2，因此算法将会选择像素3进行显示。

后面的值以此类推，都是通过输入x得出y，最后判断y的值离哪个y轴的整数值越近，那么就选择哪个像素作为显示

基本的原理就是这样，我们使用下面的代码进行实现一下这个算法：

python版本实现

import matplotlib.pyplot as plt
import numpy as np
import cv2

def draw_grid(res_list):              # 使用数组来将大概的像素图画出来
    array1 = np.zeros((max(res_list)+1, len(res_list)))
    i=0
    for j in res_list:              
        array1[-j, i] = 255
        i+=1
    print(array1)
    plt.yticks([])
    plt.xticks([])
    plt.imshow(array1, cmap="gray", interpolation='nearest')
    plt.show()

    
def logging(func):  
    def wrapper(x1, x2, y1, y2):
        res_list = func(x1, x2, y1, y2)
        draw_grid(res_list)
    return wrapper

@logging
def bresenham(x1, x2, y1, y2):
    k = (y2 - y1) / (x2 - x1)               # 斜率
    b = y1 - k * x1
    res_list = list()
    if x1 > x2:
        x_1 = x2
        x_2 = x1
    elif x1 == x2:
        x_1 = x1
        x_2 = x2
    else:
        x_1 = x1
        x_2 = x2

    for x in range(x_1, x_2+1, 1):
        y = k * x + b
        print(y)
        if ( y % 1 ) > 0.5:
            res_list.append(int(y)+1)
        elif ( y % 1 ) <= 0.5:
            res_list.append(int(y))
    return res_list


if __name__ == "__main__":
    bresenham(10, 1, 8, 1)

最后的结果为：

我们再来看这个结果的左下角两个像素，正如我们上面所推断的，最终算法会使用像素1以及像素3进行显示。

C++版本实现

/**
* @brief	计算出像素屏幕中两点之间的直线上的某个点所在的像素位置
* @param	x1: 第一个点的x坐标
* @param	x2: 第二个点的x坐标
* @param	y1: 第一个点的y坐标
* @param	y2: 第二个点的y坐标
*/

float* bresenham(float x1, float x2, float y1, float y2)
{
	float k = (y2 - y1) / (x2 - x1);
	float b = y1 - k * x1;
	float x_2 = ((x2 - x1) > 0) ? x2 : x1;
	float x_1 = ((x2 - x1) > 0) ? x1 : x2;
	int index = 0;
	float* ptr = new float[(x_2 - x_1 + 1)];					// 动态传入最终数组的大小
	for (float x = x_1; x < (x_2 + 1); x+=1)
	{
		std::cout << (k * x + b) << std::endl;
		float c = fmodf(k * x + b, 1) > 0.5 ? ceil(k * x + b) : floor(k * x + b);
		std::cout << c << std::endl;
		ptr[index] = c;
		index+=1;
	}
	return ptr;
}

int main(void)
{
	float* res_ptr = bresenham(10, 1, 8, 1);
	delete[] res_ptr;											// 释放堆空间指针

	return 0;
}

C版本实现

#include <stdio.h>
#include <math.h>

void ILI9806G_DrawLine( float usX1, float usX2, float usY1, float usY2 )
{
	float usK = ((float)usY2-(float)usY1)/((float)usX2-(float)usX1);				// 求出线段的斜率
	float usB = usY1-usK*usX1;							// 求出线段的截距
	printf("usK is %.2f\n", usK);
	printf("usB is %.2f\n", usB);

	if (usX1 > usX2)
	{
		float med_value = 0.;
		med_value = usX1;
		usX1 = usX2;
		usX2 = med_value;
	}
	
	for (float x=usX1; x<=usX2; x++)
	{
		float curr_Y = 0.;									      // 初始化像素值
		curr_Y = usK * x + usB;
		printf("\ncurr_Y shang is %.2f\t", curr_Y);
		if (fmodf(curr_Y, 1) > 0.5 )
		{
			printf("curr_Y’s value is %d\n", (int)(curr_Y+1));    
            // 这里的printf只用于占位
            // 这里可以替换成其他的功能函数用于接收算法的返回值
		}
		else
		{
		    printf("curr_Y’s value is %d\n", (int)curr_Y);
		}
	}
}

最后输出的结果都是一样的，实验成功

然后我们直接把写好的算法代码放到我们的stm32例程文件中，进行烧写实验

心心念念的直线就出来了，实验成功。

注意

在实现算法的过程中，我发现C与C++的取余%号由于只能用于两个int类型的数据，因此我们不得不使用其他的取余方法，而具体我使用了math.h头文件的fmodf函数进行取余