实验报告(Bresenham画线算法)

实验报告（Bresenham画线算法）1、 实验目的根据Bresenham画线算法，掌握绘制直线的程序设计方法。2、 实验原理 为了说明算法原理，我们首先考虑斜率非负且不超过 1 的直线的光栅化过程。设直线的起点坐标为 (xs , ys)，终点坐标为(xe , ye)，则直线的方程为：因此，其隐函数表示为：其中：显然，对于直线上的点，F(x , y) 等于零；对于直线下方的点，F(x , y) 大于零；而对直线上方的点，F(x,y) 小于零。假设当前选择的像素点是 (xi , yi)，那么下一步要选择的像素点可能是 NE (xi+1 , yi+1)，也可能是 E (xi+1 , yi)。选择的原则是看哪一个离直线与 x = xi+1 的交点最近。运用中点法则，我们只需考察中点 M 在直线的哪一侧，即计算：F(M) = F(xi + 1, yi + 1/2) = a(xi + 1) + b( yi + 0.5) + c并确定其正负号。由于根据函数值 F(xi+1, yi + 1/2) 进行判定，所以我们定义一个判定函数如下： di = 2F(xi + 1, yi + 1/2)根据定义：di = 2a(xi + 1) + 2byi + b + 2c当 d i 0时， M 在直线的下方，取 NE 为下一个像素点；当 d = 0时，两者都可以选，我们约定选 E。 di 的计算需要做 4 次加法和两次乘法。因此，为了有效地计算判定函数，我们需要建立关于 di 的递推公式。显然，di 的变化依赖于下一个像素点选的是 NE 还是 E。当 di 0 时，下一个像素点是 NE，则：di+1= 2F(xi + 2, yi + 1 + 1/2) = 2a(xi + 2) + 2b(yi +1)+b+2c = di + 2a + 2b由此，得到计算判定函数 di 的递推公式： 因为直线上的第一个像素点就是直线的起点 (xs, ys)，所以判定函数 di 的初值为：d0 = 2a(xs + 1) + 2bys + b + 2c = 2dy - dx 故满足条件的直线的 Bresnham 算法的步骤如下： Step 1.初始化dx = xe xs , dy = ye ys , x = xs , y = ys , d = 2dy dx； Step 2.当 x 0) then y = y + 1； （3）计算判定函数 d： if (d 0) then d = d + 2dy 2dx； else d = d 2dy； Step 3.算法结束。三、实验程序#include#include#include#include#includevoid Bresenham_line(int xs,int ys,int xe,int ye,int c)int dx=abs(xe-xs),dy=abs(ye-ys),i,x=xs,y=ys;int twoDX=2*dx,twoDY=2*dy,p=2*dy-dx;int s1,s2,interchange=0,temp;if (xe-xs=0)s1=1;elses1=-1;if(ye-ys=0)s2=1;elses2=-1;if(dydx) temp=dx;dx=dy;dy=temp;interchange=1;for (i=0;i0)if(interchange)x+=s1;elsey+=s2;p-=twoDX;if(interchange)y+=s2;elsex+=s1; p+=twoDY;void main() int x1=60,y1=88,x2=345,y2=789,c=GREEN;int dx,dy,n,k,f;int x,y;int gdriver,gmode;gdriver=DETECT;initgraph(&gdriver,&gmode, );Bresenham_line(x1,y1,x2,y2,c);getch();closegraph();四、测试结果x1=60,y1=88,x2=345,y2=789,c=GREEN，则得图如下示：5、 实验总结本次实