直线生成算法--Bresenham法
直线生成算法——Bresenham 法
最近的研究涉及在像素图上作直线，自己也不想花时间摸索，于是在网上找到了Bresenham 的直线生成算法，讲得清晰明了，但是算法上有些问题，我进行了改进和移植，下面讲解Bresenham 的直线生成算法时也是参考这篇博文。
1. 算法简介
图1
算法思想：图1中，连接M 点和N 点的直线经过点B ，由于是像素图，所以实际上B 点应该由A 点或者C 点代替。当B 点更靠近A 点时，选择点A （x+1,y+1）；当B 点更靠近C 点时，选择点C （x+1,y）。 因此，当ε+m
时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点，这里ε为累加误差，表达式为： 式中：表示在第n 次计算时的值，表示在第n+1次计算时的值；m 就是直线的
斜率。
由于斜率m 的值有正有负，有可能为0，也可能为∞，为了避免分别讨论这些情况， 将上述公式两边都乘以dx, 并将ε*dx用ξ表示，则有
式中：表示在第n 次计算时的值，表示在第n+1次计算时的值；dx 为起点和终点横坐标之差，dy 为起点和终点纵坐标之差。
还需说明一点，由直线斜率的定义
故
值得注意的是，现在我们只考虑dx > dy， 且x ，y 的增量均为正的情况，但实际上有
8种不同的情况（但是算法思想不变），如图2所示
如图2
2. 算法程序 前文提到的那篇博文提出了一种方法，能将这8种情况都考虑，很巧妙。但是实际应用时发现程序运行结果不是完全对，多次检查之后将程序进行了修改。
修改后的算法VB 程序如下
‘****************************************************************************
Type mypos ' 自定义数据类型
x As Integer
y As Integer
End Type
‘**************************************************************************** Function Bresenham(arr() As mypos, x1, y1, x2, y2)
Dim x!, y!, dx!, dy!, ux%, uy%, eps!
Dim cnt%
ReDim arr(100)
dx = x2 - x1
dy = y2 - y1
If dx >= 0 Then ux = 1
If dx
If dy >= 0 Then uy = 1 If dy
x = x1 y = y1
eps = 0 dx = Abs(dx): dy = Abs(dy)
cnt = 0
If dx >= dy Then
For x = x1 To x2 Step ux cnt = cnt + 1 If 2 * (eps + dy)
eps = eps + dy
arr(cnt).x = x
arr(cnt).y = y Else
eps = eps + dy - dx
If cnt >= 2 Then y = y + uy 'cnt大于2才执行y = y + uy，即排除起始坐标点，否则造成错误结果
arr(cnt).x = x
arr(cnt).y = y
End If
Next x
Else
For y = y1 To y2 Step uy
cnt = cnt + 1
If 2 * (eps + dx)
eps = eps + dx
arr(cnt).x = x
arr(cnt).y = y Else
eps = eps + dx - dy
If cnt >= 2 Then x = x + ux 'cnt大于2才执行x = x + ux，即排除起始坐标点，否则造成错误结果
arr(cnt).x = x arr(cnt).y = y
End If
Next y
End If
arr(0).x = cnt’记录元素个数
End Function
如果大家有不同看法，还希望共同讨论
3. 程序运行结果（VB+ OpenGL）
图
3
图4
绘制y=x，0≤x≤10，图3是原程序运行结果，图4时修改后的程序运行结果，原程序运行得到的起点是（0,1），但实际应该是（0,0）
图
5
图6
绘制直线[第1个坐标为起点，第2个坐标为终点]
（5,5）-（15,15）、（5,10）-（15,15）、（5,15）-（15,15）、（5,20）-（15,15）、（5,25）-（15,15）；
（25,5）-（15,15）、（25,10）-（15,15）、（25,15）-（15,15）、（25,20）-（15,15）、（25,25）-（15,15）；
（5,5）-（15,15）、（10,5）-（15,15）、（15,5）-（15,15）、（20,5）-（15,15）、（25,5）-（15,15）；
（5,25）-（15,15）、（10,25）-（15,15）、（15,25）-（15,15）、（20,25）-（15,15）、（25,25）-（15,15）；
图5是原程序运行结果，图6是修改后的程序运行结果