Bresenham直线演算法的最佳化
发布网友
发布时间：2022-05-24 21:00
共1个回答
热心网友
时间：2023-11-01 23:10
以上的程序有一个问题：电脑处理浮点运算的速度比较慢，而error与deltaerr的计算是浮点运算。此外，error的值经过多次浮点数加法之后，可能有累积误差。使用整数运算可令算法更快、更准确。只要将所有以上的分数数值乘以deltax，我们就可以用整数来表示它们。唯一的问题是程序中的常数0.5—我们可以透过改变error的初始方法，以及将error的计算由递增改为递减来解决。新的程序如下：
function line(x0, x1, y0, y1)
boolean steep := abs(y1 - y0) > abs(x1 - x0)
if steep then
swap(x0, y0)
swap(x1, y1)
if x0 > x1 then
swap(x0, x1)
swap(y0, y1)
int deltax := x1 - x0
int deltay := abs(y1 - y0)
int error := deltax / 2
int ystep
int y := y0
if y0 < y1 then ystep := 1 else ystep := -1
for x from x0 to x1
if steep then plot(y,x) else plot(x,y)
error := error - deltay
if error < 0 then
y := y + ystep
error := error + deltax
[编辑] 历史
Jack E. Bresenham于1962年在IBM发明了此算法。据他本人表示，他于1963年在丹佛举行的美国计算机协会全国大会上发表了该算法，论文则登载于1965年的《IBM系统期刊》 (IBM Systems Journal) 之中。[1]Bresenham直线算法其后被修改为能够画圆，修改后的算法有时被称为“Bresenham画圆算法”或中点画圆算法。
