采用增量思想的DDA算法,直观、易实现,每计算一个象素坐标,只需计算一个加法。
(1)改进效率。这个算法每步只做一个加法,能否再提高效率?
一般情况下k与y都是小数,而且每一步运算都要对y进行四舍五入后取整。
唯一改进的途径是把浮点运算变成整数加法!
(2)第二个思路是从直线方程类型做文章
而直线的方程有许多类型,如两点式、一般式等。如用其它的直线方程来表示这条直线会不会有出人意料的效果?
中点画线法
F(x,y) =0 直线的一般式方程:Ax+By+C=0
其中A=Y1-Y2
B=X2-X1
C=X1Y2-X2Y1
对于直线上的点: F(x,y)=0
对于直线上方的点: F(x,y)>>0
对于直线下方的点: F(x,y)<0
每次在最大位移方向上走一步,而另一个方向是走步还是不走步要取决于中点误差项的判断.
假定:0≤|k|≤1。因此,每次在x方向上加1,y方向上加1或不变需要判断。
设U点为(xi+1,yi+1),D为(xi+1,yi),M(xi+1,yi+0.5)
当M在Q的下方,则u 离直线近,应为下一个象素点, 当M在Q的上方,应取d 为下一点.
如何判断Q在M的上方还是下方?
把M代入理想直线方程:
di=A(xi+1)+B(yi+0.5)+C
当d<0时,M在Q下方,取U
当d>0时,M在Q上方,取D
当d=0时,M在Q上,取UD均可(一般取D)
用增量计算提高运算效率
d0=A+0.5B
d1=d0+A+B d0<0
d1=d0+A d0>=0
y=y+1 d<0
y=y d>=0
可以用2d代替d来摆脱浮点运算,写出仅包含整数运算的算法。
当-1<k<0时的情况
推导过程如下:
第二个点应该是(5,0)
结论如下: d0=-A+0.5B
d1=d0-A+B d0<0
d1=d0-A d0>=0
也可以用2d来摆脱浮点运算
当1<k时的情况
推导过程如下:
注意:倒置后上下位置发生变化,因此x的取值和d的后续取值都发生变化
结论如下: d0=0.5A+B
d1=d0+A+B d0>0
d1=d0+B d0<=0
x=x d<=0
x=x+1 d>0
也可以用2d来摆脱浮点运算
当k<-1时的情况
推导过程如下:
下面的坐标应该是(3,0),从y0开始减。
结论如下: d0=0.5A-B
d1=d0+A-B d0<0
d1=d0-B d0>=0
也可以用2d来摆脱浮点运算