Bresenham中点画线算法

先标明这转载自http://blog.csdn.net/xxxxxx91116/article/details/6295714

直线扫描算法之---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

（原因如下：

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

然后呢，我们为了判断的方便，让e=d-0.5，这样就变成了：

当e>0，下一个点取（x+1，y+1）

当e

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

{

if(dx

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

if(dy

{

e=-dx;

for(int i=0;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

{

if(dx

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

if(dy>=dx) //第一种情况，k-(0,1)

{

e=-dy;

for(int i=0;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

{

。。。。。。。。。

}

else

{

int tempx,tempy; //保存x 和y 的绝对值

if(dx

{

tempx=-dx;

tempy=dy;

}

if(dy

{

tempx=dx;

tempy=-dy;

}

if(tempx>tempy) //第三种情况，k-(-1,0)

{

if(dx

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

e=-dx;

for(int i=0;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

{

。。。。。。。。。

}

else

{

int tempx,tempy; //保存x 和y 的绝对值

if(dx

{

tempx=-dx;

tempy=dy;

}

if(dy

{

tempx=dx;

tempy=-dy;

}

if(tempx

if(dy

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

e=-dy;

for(int i=0;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

{

if((dx

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

if(dy

{

e=-dx;

for(int i=0;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

{

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

{

tempx=-dx;

tempy=dy;

}

if(dy

{

tempx=dx;

tempy=-dy;

}

if(tempx>tempy) //第三种情况，k-(-1,0)

{

if(dx

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

e=-dx;

for(int i=0;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

{

dx=-dx;

x=x2;

dy=-dy;

y=y2;

}

e=-dy;

for(int i=0;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

// 最后修改：2011-4-26

//

#include

#include

// 使用 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

{

putpixel(x, y, color); if (p >= 0)

{

if (!interchange) 选取上下象素点

y += s2; else 率 > 1 时，选取左右象素点

x += s1; p -= 2 * dx;

}

if (!interchange)

x += s1; 率

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();

} // 当斜率