Bresenham直线算法

此算法用于扫描转换一条线。它由Bresenham开发。这是一种有效的方法，因为它只涉及整数加法、减法和乘法运算。这些运算可以非常快速地执行，因此可以快速生成线条。

在这个方法中，下一个选择的像素是距离真实线最近的像素。

该方法的工作原理如下

假设一个像素P₁'(x₁',y₁')，然后选择后续像素，当我们从左到右工作时，一次一个像素位置在水平方向朝向P₂'(x₂',y₂')。

在任何步骤中选择一个像素后

下一个像素是

1. 要么是它右边的那个（线的下界）
2. 要么是它右上方的那个（线的上界）

该线最好由那些与P₁'和P₂'之间的路径距离最小的像素来近似。

为了选择底部像素S和顶部像素T之间的下一个像素。
            如果选择S
            那么 x_i+1=x_i+1       并且       y_i+1=y_i
            如果选择T
            那么 x_i+1=x_i+1       并且       y_i+1=y_i+1

在x = x_i+1处，线的实际y坐标为
            y=mx_i+1+b

从S到y方向上实际线的距离
            s = y-y_i

从T到y方向上实际线的距离
            t = (y_i+1)-y

现在考虑这两个距离值之间的差异
            s - t

当 (s-t) <0 ⟹ s < t

最接近的像素是S

当 (s-t) ≥0 ⟹ s < t

最接近的像素是T

这个差异是
            s-t = (y-yi)-[(yi+1)-y]
                    = 2y - 2yi -1

用代替m并引入决策变量
                d_i=△x (s-t)
                d_i=△x (2 (x_i+1)+2b-2y_i-1)
                        =2△xy_i-2△y-1△x.2b-2y_i△x-△x
                d_i=2△y.x_i-2△x.y_i+c

其中 c= 2△y+△x (2b-1)

我们可以写出下一个滑动上的决策变量d_i+1
                d_i+1=2△y.x_i+1-2△x.y_i+1+c
                d_i+1-d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-y_i)

由于x_(i+1)=x_i+1，我们有
                d_i+1+d_i=2△y.(x_i+1-x_i)- 2△x(y_i+1-y_i)

特殊情况

如果选择的像素在顶部像素T (i.e., d_i≥0)⟹ y_i+1=y_i+1
                d_i+1=d_i+2△y-2△x

如果选择的像素在底部像素T (i.e., d_i<0)⟹ y_i+1=y_i
                d_i+1=d_i+2△y

最后，我们计算d₁
                d₁=△x[2m(x₁+1)+2b-2y₁-1]
                d₁=△x[2(mx₁+b-y₁)+2m-1]

Since mx₁+b-y_i=0 and m = , we have
                d₁=2△y-△x

优点

1. 它只涉及整数运算，因此很简单。

2. 它避免了重复点的生成。

3. 它可以使用硬件实现，因为它不使用乘法和除法。

4. 与DDA（数字微分分析器）相比，它更快，因为它不涉及像DDA算法这样的浮点计算。

缺点

1. 此算法仅适用于基本直线绘制。初始化不是Bresenham直线算法的一部分。因此，要绘制平滑的线条，您应该考虑使用不同的算法。

Bresenham直线算法

步骤1： 开始算法

步骤2： 声明变量 x₁,x₂,y₁,y₂,d,i₁,i₂,dx,dy

步骤3： 输入x₁,y₁,x₂,y₂的值
                其中x₁,y₁是起始点的坐标
                并且x₂,y₂是结束点的坐标

步骤4： 计算 dx = x₂-x₁
                计算 dy = y₂-y₁
                计算 i₁=2*dy
                计算 i₂=2*(dy-dx)
                计算 d=i₁-dx

步骤5： 将(x, y)视为起点，x_end视为x的最大可能值。
                如果 dx < 0
                        那么 x = x₂
                        y = y₂
                          x_end=x₁
                如果 dx > 0
                    那么 x = x₁
                y = y₁
                        x_end=x₂

步骤6： 在(x,y)坐标处生成点。

步骤7： 检查是否生成了整条线。
                如果 x > = x_end
                停止。

步骤8： 计算下一个像素的坐标
                如果 d < 0
                    那么 d = d + i₁
                如果 d ≥ 0
            那么 d = d + i₂
                递增 y = y + 1

步骤9： 递增 x = x + 1

步骤10： 绘制最新(x, y)坐标的点

步骤11： 转到步骤 7

步骤12： 算法结束

示例： 线的起始和结束位置是 (1, 1) 和 (8, 5)。找到中间点。

解决方案： x₁=1
                y₁=1
                x₂=8
                y₂=5
                dx= x₂-x₁=8-1=7
                dy=y₂-y₁=5-1=4
                I₁=2* ∆y=2*4=8
                I₂=2*(∆y-∆x)=2*(4-7)=-6
                d = I₁-∆x=8-7=1

实现Bresenham直线绘制算法的程序

输出

区分DDA算法和Bresenham直线算法