Bresenham中点画线算法

《Bresenham中点画线算法》由会员分享，可在线阅读，更多相关《Bresenham中点画线算法（15页珍藏版）》请在装配图网上搜索。

1、word先标明这自etails/6295714直线扫描算法之-bresenham改良算法(任何斜率，任何方向)by zxx图形学神马的全都是数学，看来以后我不能搞这个，伤脑筋，所以先把我现在懂得先记录下来吧。不过呢，我的水平实在有限，对于算法这种东西实在难以说明白，请大家包涵。书上讲的实在是太过简略，所以这里我把一些简单的推导过程都记录下来：1.重温bresenham未改良算法斜率在0-1之间的直线我想要记录的是bresenham改良算法，所以在讲解改良算法之前，我先用一个简单的例子说明一下未改良算法的思想：这是一个斜率k在0-1之间的一条直线，我就用斜率为0-1之间的直线来重温：首先，如图1

2、所示，假设x列的像素已定，其坐标为x，y，那么下一个坐标一定是：x+1，y+1或者x+1，y。而是哪一个取决于d的值，如果那么就是x+1，y+1，如果d=1时，就让d减一，这样就保证了d在0-1之间。当d0.5,下一个点取x+1，y+1当d0，下一个点取x+1，y+1当e0使用这个替换以后，我们就可以消除除法和小数了，这里要注意一个问题，我们一定要保持e和e的符号是一样的，那么就要保证dx大于0！所以说，在这种情况下，我们的dx一定要大于0，如果小于0，可以交换起点和终点坐标，总之起点一定要从x坐标小的点开始。而且我们要注意以前当e0时，我们要e=e-1，现在：e=e/2*dx所以e/2*dx

3、= e/2*dx-1展开e = e-2*dx。具体的代码如下：void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=y1;CString s;/这里一定要注意，由于使用的是改良算法，所以dx一定是要大于0才能保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0)/如果k大于0if(dx0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;if(dydx)/第一种情况

4、，k-(0,1)e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e+dy+dy;if(e=0)y+;e=e-dx-dx;B斜率在1-无穷之间如图二，在这种情况下，我们可以看到y的变化速度比x快，所以说，我们这里每次让y加1，而不是让x加1，所以我们每次让y加1时，x的增长是d，注意，此处的d不是斜率k，而是1/k，按照以往我们的目的，我们要消除除法和小数：1.消除除法e=e+d;e=e+dx/dy;dy*e=dy*e+dx;2消除2*dy*e=2*dy*e+2dx;由于算法中只用到误差项的符号，所以可以使用如下替换：e=2*e*dy注意：为了让代换后符号

5、不改变，必须保证dy0,如果不满足，如此可以按上述方法交换起点终点坐标。代码如下：void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=y1;CString s;/这里一定要注意，由于使用的是改良算法，所以dx一定是要大于0才能保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0)/如果k大于0if(dx=dx)/第一种情况，k-(0,1)e=-dy;for(int i=0;iSetP

6、ixel(x,y,color);y+;e=e+dx+dx;if(e=0)x+;e=e-dy-dy;C.斜率在0-1之间如图三，在这种情况下可以类比斜率在0-1之间的情况，不过呢，我们要注意一个问题，就是现在的斜率是负数，我们使用时，需要改变符号，下面直接看改良：1.消除除法e=e-dy/dx注意是减号，因为现在的斜率是负数e*dx=e*dx-dy2.消除小数2*e*dx= 2e*dx-2dy由于算法中只用到误差项的符号，所以可以使用如下替换：e=2*e*dx注意：为了让代换后符号不变，必须保证dx0dd代码如下：void CMyDrawLineView:DrawBresenham(int x1

7、,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=y1;CString s;/这里一定要注意，由于使用的是改良算法，所以dx一定是要大于0才能保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0)/如果k大于0。elseint tempx,tempy;/保存x和y的绝对值if(dx0)/dx小于0说明终点xtempx=-dx;tempy=dy;if(dytempy)/第三种情况，k-(-1,0)if(dx0)/dx小于0说明终点xdx=-dx;x=x2;dy=-

8、dy;y=y2;e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e-dy-dy;if(e=0)y-;e=e-dx-dx;D斜率在-1-负无穷之间如图四，在这种情况下可以类比斜率在1到正无穷之间的情况，不过呢，我们要注意一个问题，就是现在的斜率是负数，我们使用时，需要改变符号，下面直接看改良：1.消除除法e=e-dx/dy注意是减号，因为现在的斜率是负数e*dy=e*dy-dx2.消除小数2*e*dy= 2*e*dy-2dx由于算法中只用到误差项的符号，所以可以使用如下替换：e=2*e*dy注意：为了让代换后符号不变，必须保证dy0 代码如下：void C

9、MyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CDC* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=y1;CString s;/这里一定要注意，由于使用的是改良算法，所以dx一定是要大于0才能保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0)/如果k大于0。elseint tempx,tempy;/保存x和y的绝对值if(dx0)/dx小于0说明终点xtempx=-dx;tempy=dy;if(dy0)tempx=dx;tempy=-dy

10、;if(tempxtempy)/第四种情况，k-(-1,min)if(dy0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;e=-dy;for(int i=0;iSetPixel(x,y,color);y+;e=e-dx-dx;if(e=0)x-;e=e-dy-dy;/if(edy)/e=e-dy-dy;/完整的程序如下：/*x1:直线起点xx2:直线终点xy1:直线起点yy2:直线终点ycolor:直线颜色*/void CMyDrawLineView:DrawBresenham(int x1,int x2,int y1,int y2,COLORREF color,CD

11、C* pDC)int x,y,dx,dy,e;dx=x2-x1;dy=y2-y1;x=x1;y=y1;CString s;/这里一定要注意，由于使用的是改良算法，所以dx一定是要大于0才能保证其符号不变if(dx=0&dy=0)|(dx=0&dy=0)/如果k大于0if(dx0)|(dx=0&dy0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;if(dydx)/第一种情况，k-(0,1)e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e+dy+dy;if(e=0)y+;e=e-dx-dx;else/第二种情况，k-(1,max)

12、e=-dy;for(int i=0;iSetPixel(x,y,color);y+;e=e+dx+dx;if(e=0)x+;e=e-dy-dy;else/如果k小于0int tempx,tempy;/保存x和y的绝对值if(dx0)/dx小于0说明终点xtempx=-dx;tempy=dy;if(dytempy)/第三种情况，k-(-1,0)if(dx0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;e=-dx;for(int i=0;iSetPixel(x,y,color);x+;e=e-dy-dy;if(e=0)y-;e=e-dx-dx;else/第四种情况，k-(

13、-1,min)if(dy0)/dx小于0说明终点xdx=-dx;x=x2;dy=-dy;y=y2;e=-dy;for(int i=0;iSetPixel(x,y,color);y+;e=e-dx-dx;if(e=0)x-;e=e-dy-dy;/ 程序名称：基于 Bresenham 算法画任意斜率的直线/ 编译环境：Visual C+ 6.0 / 2010，EasyX 2011惊蛰版/ 作者：yangw80 / 最后修改：2011-4-26/#include #include / 使用 Bresenham 算法画任意斜率的直线包括起始点，不包括终止点void Line_Bresenham(int

14、 x1, int y1, int x2, int y2, int color)int x = x1;int y = y1;int dx = abs(x2 - x1);int dy = abs(y2 - y1);int s1 = x2 x1 ? 1 : -1;int s2 = y2 y1 ? 1 : -1;bool interchange = false;/ 默认不互换 dx、dyif (dy dx)/ 当斜率大于 1 时，dx、dy 互换int temp = dx;dx = dy;dy = temp;interchange = true;int p = 2 * dy - dx;for(int i = 0; i = 0)if (!interchange)/ 当斜率 1 时，选取左右象素点x += s1;p -= 2 * dx;if (!interchange)x += s1;/ 当斜率 1 时，选取 y 为步长p += 2 * dy;/ 主函数void main()initgraph(640, 480);/ 测试画线Line_Bresenham(100, 1, 1, 478, GREEN);Line_Bresenham(1, 478, 638, 1, GREEN);/ 按任意键退出getch();closegraph();15 / 15