直线生成算法——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 < 0.5时，绘制(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 < 0 Then ux = -1
If dy >= 0 Then uy = 1
If dy < 0 Then uy = -1
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) < dx Then
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) < dy Then
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是修改后的程序运行结果。