第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
bresenham改进算法，适用于任何斜率任何方向！.docx
先标明这转载自
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<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=-dx;
x=x2;
dy=-dy;
y=y2;
}
if(dySetPixel(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=-dx;
x=x2;
dy=-dy;
y=y2;
}
if(dy>=dx)
{
//dx 小于 0 说明终点 x
//第一种情况，k-(0,1)
e=-dy;
for(int i=0;iSetPixel(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;
if(dx<0)
{
//保存 x 和 y 的绝对值
//dx 小于 0 说明终点 x
tempx=-dx;
tempy=dy;
}
if(dy<0)
{
tempx=dx;
tempy=-dy;
}
if(tempx>tempy)
{
if(dx<0)
{
dx=-dx;
x=x2;
dy=-dy;
y=y2;
//第三种情况，k-(-1,0)
//dx 小于 0 说明终点 x
}
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-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;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
