【附源码】布雷森汉姆直线算法(bresenham‘s line algorithm)

一点儿也不萌的萌萌

18374人浏览 · 2021-07-16 15:40:40

一点儿也不萌的萌萌 · 2021-07-16 15:40:40 发布

1.布雷森汉姆直线算法简介

我们在纸上画直线时，只需要定一个起点和终点，然后把两点连接起来就是一条直线，你将会得到一条笔直的直线。

但是，这个简单的过程，在计算机上却并不容易。首先计算机的屏幕是一个一个的离散的led。如下图，每一个白块都是一个灯管，当我们绘制一条直线时，就需要判断在这条直线上，需要点亮哪些灯管来模拟这条直线。
在这里插入图片描述
布雷森汉姆直线算法就是为了解决这样的问题。

2.算法流程

2.1 直观理解布雷森汉姆直线算法

在这里插入图片描述
我们现在正式开始进入布雷森汉姆直线算法的探索。假设我们要绘制如上图中所示直线 $f (x, y)$ ，它的起点在 $x_k, y_k)$ ，上图中的每一个圆圈是一个led灯。

在介绍布雷森汉姆直线算法时，为了简化理解，我们的起点和终点都是整数，并且直线的斜率为 $0 < m < 1$ 。所以毫无疑问，我们首先点亮 $x_k, y_k)$ 这个led灯。

那么下一个led灯，我们应该点亮哪一个呢？观察上图可以很容易发现，我们应该点亮 $x_k+1, y_k)$ 和 $x_k+1, y_k+1)$ 中的一个，那究竟选择哪个呢？一个很朴素的想法是，谁在 $y$ 方向上距离直线最近，那就点亮谁。这个想法也正是布雷森汉姆直线算法的思想。

既然已经可以确定思路了，那我们下一步就可以尝试使用数学公式来表示这个过程了。

网上有很多博客介绍了很多不一样的表示方法，我在这里采用维基百科上的表示方法，我觉得也是很容易理解的。

现在我们可以想象一下，对于上图，直线与 $x_k+1, y_k)$ 和 $x_k+1, y_k+1)$ 连线的交点，如果在线段一半的上面，那么就应该选择点亮 $x_k+1, y_k+1)$ ，否则点亮 $x_k+1, y_k)$ 。

那么，我们只需要将中点坐标 $(xk+1,yk+12)(x_k+1, y_k+\frac{1}{2})$ 坐标带入直线函数 $f (x, y)$ 中:

如果 $f(xk+1,yk+12)>0f(x_k+1, y_k+\frac{1}{2}) > 0$ ，则说明直线的交点在 $(xk+1,yk+12)(x_k+1, y_k+\frac{1}{2})$ 的下面，此时需要点亮 $x_k+1, y_k)$ ;
如果 $f(xk+1,yk+12)<0f(x_k+1, y_k+\frac{1}{2}) < 0$ ，则说明直线的交点在 $(xk+1,yk+12)(x_k+1, y_k+\frac{1}{2})$ 的上面，此时需要点亮 $x_k+1, y_k+1)$ ;

还记得这个结论吗？在直线上部区域的点 $f (x, y) < 0$ ，在直线下部区域的点 $f (x, y) > 0$ 。

这就是布雷森汉姆直线算法最核心的思想。

2.2 进一步探索布雷森汉姆直线算法

上面我们使用的是中点的方法，我们稍加修改换一种表示(实际上也没有很大的变化，它的核心思想依然是判断距离)。

我们继续探索。
在这里插入图片描述
上图中红色的线，是我们想要绘制的线，它的斜率是 $0 < m < 1$ ，现在考虑在 $x$ 点，直线对应纵轴的值为 $y+ϵy+\epsilon$ 。

很明显 $y+\epsilon < y+0.5$

所以 $(x, y)$ 点距离直线更近，所以把该点点亮。一旦选择了 $(x, y)$ 点，那么此时到直线就产生了误差： $ϵ\epsilon$

那么当我们绘制下一个点时，其横坐标是 $x + 1$ ，它对应的纵坐标是 $y+m+ϵy+m+\epsilon$

斜率为m的直线，x增加1，那么y增加m

此时，直线在 $x + 1$ 时对应的纵坐标为: $y+ϵ+my+\epsilon+m$

同样执行如下判断： $y+\epsilon+m > y+0.5$
那么很明显，此时我们需要点亮 $(x + 1, y + 1)$ 对应的灯。

此时误差就变成了： $\epsilon_{new} = (y+\epsilon+m) - (y+1)$

如果咱们再往后计算，此时横轴到达了 $x + 2$ ，纵轴到达了 $y + 1$ ，同样的进行如下判断： $y+1+\epsilon_{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.0

2.3 面临的问题

上面介绍的布雷森汉姆直线算法，是在第一象限，并且斜率 $0 < m < 1$ 时的情况。如果超过了这个限制，那么上面的过程就不能直接应用了，必须要做一些改进。

咱们可以来看一下面临的问题：

(1) 反方向
在这里插入图片描述
(2) 斜率为负
(3) 综合所有情况

所以，最终需要该算法能完成整个平面任意方式绘制直线。

对于这些情况可以按照2.2所述的过程进行探索，并不难理解。

3. 代码实现

from matplotlib import pyplot as plt
from matplotlib.pyplot import MultipleLocator


def line(x0, y0, x1, y1):
    x = []
    y = []
    steep = abs(y1 - y0) > abs(x1 - x0)
    if steep:  # 如果为真，说明斜率绝对值大于1，则主要以y方向递增
        x0, y0 = y0, x0
        x1, y1 = y1, x1

    if x0 > x1:  # 如果为真，说明起点大于终点，此时则交换方向
        x0, x1 = x1, x0
        y0, y1 = y1, y0

    delta_x = x1 - x0
    delta_y = abs(y1 - y0)
    error = 0
    delta_error = delta_y / delta_x
    yk = y0

    if y0 < y1:
        y_step = 1
    else:
        y_step = -1

    for xk in range(x0, x1):
        if steep:
            x.append(yk)
            y.append(xk)
        else:
            x.append(xk)
            y.append(yk)

        error = error + delta_error
        if error >= 0.5:
            yk = yk + y_step
            error = error - 1.0
    return x, y


if __name__ == '__main__':
    x, y = line(30, 30, 4, -20)

    plt.xlim((-30, 30))
    plt.ylim((-30, 30))
    plt.grid()
    plt.plot(x, y)

    y_major_locator = MultipleLocator(1)
    x_major_locator = MultipleLocator(1)
    ax = plt.gca()
    ax.xaxis.set_major_locator(x_major_locator)
    ax.yaxis.set_major_locator(y_major_locator)
    plt.show()