详述Bresenham线生成算法

给定直线的起始点和结束点，在显示设备上绘制该线段是计算机图形学中最基本的操作之一。本文将介绍的 Bresenham Line Drawing Algorithm 即为执行该操作的其中一个较为优化的算法。

计算机显示设备是由一个个像素组成的，该算法的目的即为“点亮”由起始像素点

(x0​,x0​) 至结束像素点

(x1​,y1​) 的线段上的像素点，当分辨率足够大，像素点足够小，看起来就会像一条直线。

举例：

为简化后续讨论，设置如下限定条件：

1. 起始点在结束点左下方；
2. 
   $x_0<x_1$

   x0​<x1​ 且

   $y_0<=y_1$

   y0​<=y1​ ；

3. 线段的斜率
   $0\le k\le 1$

   0≤k≤1 ；

4. 对于区间
   $[x_0,x_1]$

   [x0​,x1​] 内的所有

   $x$

   x ，该位置仅存在一个像素点。

设置以上限定条件之后，我们可以得到一个十分粗糙的算法：

def easyway(x0,y0,x1,y1):
  m = (y2-y1)/(x2-x1)
  for x in range(x0, x1+1, 1):
    # find y (integer)
    y = round(mx+b)
    colorify(x,y)
复制代码

该算法是可行的，但在循环的每一步都需要计算

mx+b，执行速度较慢，因此，我们需要寻找一个快速得到

y 值的方法。

推导

由于线段的斜率在0到1之间，因此对于点

(xk​,yk​) ，下个点只可能是

(xk​+1,yk​) 或

(xk​+1,yk​+1) ，其中

k 表示横坐标

x 移动的次数，如图所示。

因此，我们需要从

yk​ 和

yk​+1 中获取离线段较近的值，假设直线方程为

y=mx+b ，设

y 为直线上实际的值，

d1​(k) 和

d2​(k) 分别为距离

yk​ 和

yk​+1 的距离，则有：

比较

d1​(k) 和

d2​(k) 的值，即可判断下个点的具体位置：

1. 若
   $d_1(k) \le d_2(k)$

   d1​(k)≤d2​(k) ，认为下个点应为

   $(x_k+1, y_k)$

   (xk​+1,yk​)

2. 反之，认为下个点应为
   $(x_k+1, y_k+1)$

   (xk​+1,yk​+1)

因此，我们只需要判断

d1​(k)−d2​(k) 的正负性即可：

同时，我们有：

b=y0​−mx0​

m=x1​−x0​y1​−y0​​=dxdy​

因此，进一步简化得到：

其中

c=2dxdy​+2y0​−2dxdy​−1 。

设

p(k)=d1​(k)−d2​(k)，则:

对

p(k+1) 推导如下：

所以：

因此：

1. 当
   $p_k \le 0$

   pk​≤0 即

   $d_1(k) \le d_2(k)$

   d1​(k)≤d2​(k) 时，

   $y_{k+1} = y_k$

   yk+1​=yk​，则

   $p(k+1) = p(k)+2\frac{dy}{dx}$

   p(k+1)=p(k)+2dxdy​

2. 反之，
   $p(k+1) = p(k) + 2\frac{dy}{dx}-2$

   p(k+1)=p(k)+2dxdy​−2

因此，综合以上，我们的代码即为:

def pk(x0,y0,x1,y1):
  dy = y1-y0
  dx = x1-x0
  p = 2*dy/dx - 1

  base_increment = 2*dy/dx
  colorify(x0,y0)
  while x0 <= x1:
    x0 += 1
    if p > 0:
      y0 += 1
      p -= 2
    p += base_increment
    colorify(x0,y0)
复制代码

整数化

上述算法仍然涉及浮点数的计算，下面我们考虑如何彻底取消浮点相关操作。

观察

p(k) 的表达式，涉及浮点操作的仅为

dxdy​，因此，考虑将等式两侧同乘

dx，注意

dx>0，因此

P(k) 与

p(k) 正负性相同，有：

同样的：

1. 当
   $P_k \le 0$

   Pk​≤0 即

   $d_1(k) \le d_2(k)$

   d1​(k)≤d2​(k) 时，

   $y_{k+1} = y_k$

   yk+1​=yk​，则

   $P(k+1) = P(k)+2dy$

   P(k+1)=P(k)+2dy

2. 反之，
   $P(k+1) = P(k) + 2dy-2dx$

   P(k+1)=P(k)+2dy−2dx

代码即变为：

def pk(x0,y0,x1,y1):
  dy = y1-y0
  dx = x1-x0
  p = 2*dy - dx

  base_increment = 2*dy
  colorify(x0,y0)
  while x0 <= x1:
    x0 += 1
    if p > 0:
      y0 += 1
      p -= 2*dx
    
    p += base_increment
    colorify(x0,y0)
复制代码

一般化

之前的讨论是基于文首给出的限定条件的：

1. 起始点在结束点左下方；
2. 
   $x_0<x_1$

   x0​<x1​ 且

   $y_0<=y_1$

   y0​<=y1​ ；

3. 线段的斜率
   $0\le k\le 1$

   0≤k≤1 ；

4. 对于区间
   $[x_0,x_1]$

   [x0​,x1​] 内的所有

   $x$

   x ，该位置仅存在一个像素点。

下面我们将该算法一般化。

垂直线

当

x0​=x1​ 时，线段的斜率不存在，此时只需要使纵坐标

y 每次递增单位长度，然后染色即可。

if dx == 0:
  while y1!=y2:
    y1 += stepy
    colorify(x1,y1)
复制代码

dy<0, dx<0

当 dy<0 时，如下图：

此时我们将点

(x1​,y1​) 映射为

(x1​,y1′​)，其中虚线为两条线段的垂直平分线，那么

y1′​−y0​=y0​−y1​，接着我们对虚线上侧的线段按上述算法计算需要绘制的点即可，但在实际绘制时，对需要递增

y 的情况，我们递减

y，则可以对称的绘制出原需要绘制的直线。

同理，当 dx < 0 时，如下图：

同样的，此时我们将点

(x1​,y1​) 映射为

(x1′​,y1​)，其中虚线为两条线段的垂直平分线，那么

x1′​−x0​=x0​−x1​，接着我们对虚线右侧的线段按上述算法计算需要绘制的点即可，但在实际绘制时，对需要递增

x 的情况，我们递减

x，则可以对称的绘制出原需要绘制的直线。

当 dx 和 dy 均小于0时，需要对原线段作两次变换。

dx = x1-x0
dy = y1-y0
if dy < 0:
    dy = -dy
    stepy = -1
else:
    stepy = 1

if dx < 0:
    dx = -dx
    stepx = -1
else:
    stepx = 1

#  ....

while x0 != x1:
    x0 += stepx

    if p >= 0:
        y0 += stepy
        # ....
    
    # ....

# ....
复制代码

m > 1

当直线斜率大于 1 时，即 dy>dx，原直线方程为

y=mx+b ，可以变换为

x=m1​y−mb​，则

m1​<1，因此只需要对该新直线应用上述算法即可。

Put it together

def bresenham(p1,p2):
    x0, y0 = p1
    x1, y1 = p2
    dx = x1-x0
    dy = y1-y0
    if dy < 0:
        dy = -dy
        stepy = -1
    else:
        stepy = 1

    if dx < 0:
        dx = -dx
        stepx = -1
    else:
        stepx = 1
    dy <<= 1
    dx <<= 1
    colorify(x0, y0)
    if dx == 0:
        while y0 != y1:
            y0 += stepy
            colorify(x0, y0)
    if dx > dy:
        fraction = dy-(dx >> 1)
        while x0 != x1:
            x0 += stepx

            if fraction >= 0:
                y0 += stepy
                fraction -= dx

            fraction += dy
            colorify(x0, y0)
    else:
        fraction = dx - (dy >> 1)
        while y0 != y1:
            if fraction >= 0:
                x0 += stepx
                fraction -= dy
            y0 += stepy
            fraction += dx
            colorify(x0, y0)
复制代码

时间复杂度为

O(x2​−x1​)，空间复杂度为

O(1)

实际应用

使用 python 中的 matplotlib 模块对该算法进行可视化。

(1,1) -> (2,10)：

(1,1) -> (10,1)：

(10,8) -> (1,1)：

源码

github

参考

csustan.csustan.edu/~tom/Lectur…

en.wikipedia.org/wiki/Bresen…