Bresenham中点画线算法.doc

先标明这转载自 

直线扫描算法之---bresenham改进算法(任何斜率，任何方向)
by zxx
图形学神马的全都是数学，看来以后我不能搞这个，伤脑筋，所以先把我现在懂得先记录下来吧。不过呢，我的水平实在有限，对于算法这种东西实在难以说明白，请大家包涵。
书上讲的实在是太过简略，所以这里我把一些简单的推导过程都记录下来：

1.重温bresenham未改进算法（斜率在0-1之间的直线）
我想要记录的是bresenham改进算法，所以在讲解改进算法之前，我先用一个简单的例子说明一下未改进算法的思想：
这是一个斜率k在0-1之间的一条直线，我就用斜率为0-1之间的直线来重温：
首先，如图1所示，假设x列的像素已定，其坐标为（x，y），那么下一个坐标一定是：
（x+1，y+1）或者（x+1，y）。而是哪一个取决于d的值，如果d>0.5那么就是（x+1，y+1），
如果d<0.5,那么就是（x+1，y），而d是什么呢？当然是斜率了。
（原因如下：
y=kx+b
当x增加1时：y=kx+k+b
所以当x增加1是，y方向的增量是d。）
所以每次我们只需要让d=d+k（k是斜率）即可，当d>=1时，就让d减一，这样就保证了d在0-1之间。
当d>0.5,下一个点取（x+1，y+1）
当d<0.5,下一个点取（x+1，y）

然后呢，我们为了判断的方便，让e=d-0.5，这样就变成了：
当e>0，下一个点取（x+1，y+1）
当e<0，下一个点取（x+1，y）

2.过渡，重温之后，我们就想要改进，为什么要改进呢？因为我们这里面有0.5，还有k，k里面有dx/dy，这些除法和小数都不是我们想要的，我们想要的是，只有整数，且只有加法的算法，下面就全面讨论一下改进算法。

3.改进算法篇（不同斜率，不同方向）
这里，我们主要分为4个角度来说明：
A.      斜率在0-1只间
B.      斜率在1-无穷之间
C.      斜率在0-（-1）之间
D.     斜率在（-1）-负无穷之间
E．两种特殊情况，两条直线。

A． 斜率在0-1只间
以往我们会产生除法和小数的地方主要是：
e=0.5
e=e+k
接下来我们一步一步实现我们的目标：
1.消除除法
e=e+dy/dx
e*dx=e*dx+dy
2.消除小数
2*e*dx= 2e*dx+2dy
由于算法中只用到误差项的符号，所以可以使用如下替换：
e’=2*e*dx
注意：为了让代换后符号不变，必须保证dx>0
使用这个替换以后，我们就可以消除除法和小数了，这里要注意一个问题，我们一定要保持e和e’的符号是相同的，那么就要保证dx大于0！！！所以说，在这种情况下，我们的dx一定要大于0，如果小于0，可以交换起点和终点坐标，总之起点一定要从x坐标小的点开始。
而且我们要注意以前当e>0时，我们要e=e-1，现在：e=e’/（2*dx）
所以e’/（2*dx）= 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大于0
       {    
                     if(dx<0)                       //dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;                   
}

              if(dy<dx)                             //第一种情况，k-(0,1)
              {
                     e=-dx;
                     for(int i=0;i<dx;i++)
                     {
                            pDC->SetPixel(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．消除0.5
       2*dy*e=2*dy*e+2dx;
由于算法中只用到误差项的符号，所以可以使用如下替换：
e’=2*e*dy
注意：为了让代换后符号不改变，必须保证dy>0,如果不满足，则可以按上述方法交换起点终点坐标。

代码如下：
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大于0
       {    
                     if(dx<0)                       //dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;                   
}

              if(dy>=dx)                                  //第一种情况，k-(0,1)
              {
                     e=-dy;
                     for(int i=0;i<dy;i++)
                     {
                            pDC->SetPixel(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-dy
2.消除小数
2*e*dx= 2e*dx-2dy
由于算法中只用到误差项的符号，所以可以使用如下替换：
e’=2*e*dx
注意：为了让代换后符号不变，必须保证dx>0
d

d
代码如下：
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大于0
       {    
              。。。。。。。。。
}
else
{
int tempx,tempy;    //保存x和y的绝对值
              if(dx<0)                //dx小于0说明终点x
              {
                     tempx=-dx;
                     tempy=dy;
              }
              if(dy<0)
              {
                     tempx=dx;
                     tempy=-dy;
              }

              if(tempx>tempy)                                //第三种情况，k-(-1,0)
              {
                     if(dx<0)                       //dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;
                     }
                     e=-dx;
                     for(int i=0;i<dx;i++)
                     {
                            pDC->SetPixel(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-dx
2.消除小数
2*e*dy= 2*e*dy-2dx
由于算法中只用到误差项的符号，所以可以使用如下替换：
e’=2*e*dy
注意：为了让代换后符号不变，必须保证dy>0

代码如下：
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大于0
       {    
              。。。。。。。。。
}
else
{
int tempx,tempy;    //保存x和y的绝对值
              if(dx<0)                //dx小于0说明终点x
              {
                     tempx=-dx;
                     tempy=dy;
              }
              if(dy<0)
              {
                     tempx=dx;
                     tempy=-dy;
              }

              if(tempx<tempy)                                //第四种情况，k-(-1,min)
              {
                     if(dy<0)//dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;
                     }
                     e=-dy;
                     for(int i=0;i<dy;i++)
                     {
                            pDC->SetPixel(x,y,color);
                            y++;
                            e=e-dx-dx;
                            if(e>=0)
                            {
                                   x--;
                                   e=e-dy-dy;
                            }
                            //if(e>dy)
                            //{
                            //     e=e-dy-dy;
                            //}
                     }
              }
}
}

完整的程序如下：
/*
x1:直线起点x
x2:直线终点x
y1:直线起点y
y2:直线终点y
color:直线颜色
*/
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大于0
       {    
                     if((dx<0)||(dx==0&&dy<0))                       //dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;

                     }
              if(dy<dx)                             //第一种情况，k-(0,1)
              {
                     e=-dx;
                     for(int i=0;i<dx;i++)
                     {
                            pDC->SetPixel(x,y,color);
                            x++;
                            e=e+dy+dy;
                            if(e>=0)
                            {
                                   y++;
                                   e=e-dx-dx;
                            }
                     }
              }
              else                                     //第二种情况，k-(1,max)
              {
                     e=-dy;
                     for(int i=0;i<dy;i++)
                     {
                            pDC->SetPixel(x,y,color);
                            y++;
                            e=e+dx+dx;
                            if(e>=0)
                            {
                                   x++;
                                   e=e-dy-dy;
                            }
                     }
              }
       }
       else                                            //如果k小于0
       {
              int tempx,tempy;    //保存x和y的绝对值
              if(dx<0)                //dx小于0说明终点x
              {
                     tempx=-dx;
                     tempy=dy;
              }
              if(dy<0)
              {
                     tempx=dx;
                     tempy=-dy;
              }

              if(tempx>tempy)                                //第三种情况，k-(-1,0)
              {
                     if(dx<0)                       //dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;
                     }
                     e=-dx;
                     for(int i=0;i<dx;i++)
                     {
                            pDC->SetPixel(x,y,color);
                            x++;
                            e=e-dy-dy;
                            if(e>=0)
                            {
                                   y--;
                                   e=e-dx-dx;
                            }
                     }
              }
              else                                     //第四种情况，k-(-1,min)
              {
                     if(dy<0)//dx小于0说明终点x
                     {
                            dx=-dx;
                            x=x2;
                            dy=-dy;
                            y=y2;
                     }
                     e=-dy;
                     for(int i=0;i<dy;i++)
                     {
                            pDC->SetPixel(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 <yw80@>
// 最后修改：2011-4-26
//
#include <graphics.h>
#include <conio.h>

// 使用 Bresenham 算法画任意斜率的直线（包括起始点，不包括终止点）
void Line_Bresenham(int 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、dy
if (dy > dx) // 当斜率大于 1 时，dx、dy 互换
{
int temp = dx;
dx = dy;
dy = temp;
interchange = true;
}

int p = 2 * dy - dx;
for(int i = 0; i < dx; i++)
{
putpixel(x, y, color);
if (p >= 0)
{
if (!interchange) // 当斜率 < 1 时，选取上下象素点
y += s2;
else // 当斜率 > 1 时，选取左右象素点
x += s1;
p -= 2 * dx;
}
if (!interchange)
x += s1; // 当斜率 < 1 时，选取 x 为步长
else
y += s2; // 当斜率 > 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();
}