bresenham直线算法

⑴ 直线的生成算法有哪些

第一种算法：DDA直线生成算法是一种使用微分方程生成直线的算法，又称作数值微分法。该算法的基本思想是：根据斜率确定增量最大的方向，每次迭代时均在该方向上走一步，然后根据直线方程计算出另一方向上的值，对其四舍五入后得到像素坐标。第二种算法：Bresenham直线生成算法与DDA算法类似，每次迭代时均在增量最大方向上走一步，并计算决策参数，根据决策参数确定像素坐标。算法的巧妙之处在于采用了增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素坐标。

⑵ 直线扫描算法（个人总结，仅供参考）

直线扫描算法主要包含三种算法，DDA算法、中点画线算法、Bresenham直线算法。

这三种算法都要事先要确定两个端点（起点和终点），从起点开始每次走一步，每走一步画一个点，直至到达终点。

这个前提也比较好理解，因为如果朝斜率大的方向走，可能没走几步就走完了，那画出来的直线就是离散的。

以下我们只讨论朝x方向移动的情况。（y方向的情况是一样的）

DDA算法实际上是根据 斜截式直线方程 来画的。

但这么做实际上是比较消耗性能的，因为斜截式方程， 它涉及到了乘法运算 。因此我们需要通过 增量思想 对它进行优化。

这样转换后，我们就可以根据当前的位置来找到下一步的位置，且每次计算只需要进行一次 浮点的加法运算 ，一次四舍五入取整即可。

中点画线算法实际上是根据 一般式直线方程 来画的。它是通过判断中点在直线的下方还是上方，来决定下一步的坐标位置。

但这样也是非常消耗性能的，把中点带入F(x, y)中，会涉及到2个乘法，4个加法。我们依然可以通过增量的方式来对它进行优化。

这样我们就优化到每次只需要一次 整数加法 即可，且还不需要四舍五入。因此它要更优于DDA算法。

Breseham算法是通过比较d(交点与交点下方最近的点的距离)来进行选择的。d每次按照k的大小增加。

但这么做依旧和DDA算法一样，会涉及到浮点数k的加法。我们可以通过 换元的方式 对它进行下优化。

这样就能使得每次进行一次或两次的 整数加法运算 ，不需要四舍五入。效率高于DDA，低于中点画线算法。

但Bresenham算法不依赖直线方程，使得它能有更宽泛的适用范围。

⑶ Bresenham画线算法

基本上Bresenham画线算法的思路如下:
//
假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2).
//
根据对称性,可推导至全象限内的线段.
1.画起点(x1,y1).
2.准备画下个点。x坐标增1，判断如果达到终点，则完成。否则，由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点.
2.1.如果线段ax+by+c=0与x=x1+1的交点的y坐标大于M点的y坐标的话,下个点为U(x1+1,y1+1)
2.2.否则,下个点为B(x1+1,y1+1)
3.画点(U或者B).
4.跳回第2步.
5.结束.
这里需要细化的是怎么判断下个要画的点为当前点的右邻接点还是当前点的右上邻接点.
设线段方程：ax+by+c=0(x1<x<x2,y1<y<y2)
令dx=x2-x1,dy=y2-y1
则：斜率-a/b
=
dy/dx.
从第一个点开始，我们有F(x,1,y1)
=
a*x1+b*y1+c=0
下面求线段ax+by+c=0与x=x1+1的交点:
由a*(x1+1)+b*y+c
=
0,
求出交点坐标y=(-c-a(x1+1))/b
所以交点与M的y坐标差值Sub1
=
(-c-a(x1+1))/b
-
(y1+0.5)
=
-a/b-0.5，即Sub1的处始值为-a/b-0.5。
则可得条件当
Sub1
=
-a/b-0.5>0时候,即下个点为U.
反之,下个点为B.
代入a/b,则Sub1
=
dy/dx-0.5.
因为是个循环中都要判断Sub,所以得求出循环下的Sub表达式,我们可以求出Sub的差值的表达式.下面求x=x1+2时的Sub，即Sub2
1.如果下下个点是下个点的右上邻接点，则
Sub2
=
(-c-a(x1+2))/b
-
(y1+1.5)
=
-2a/b
-
1.5
故Sub差值Dsub
=
Sub2
-
Sub1
=
-2a/b
-
1.5
-
(-a/b-0.5)
=
-a/b
-
1.代入a/b得Dsub
=
dy/dx
-1;
2.如果下下个点是下个点的右邻接点，
Sub2
=
(-c-a(x1+2))/b
-
(y1+0.5)
=
-2a/b
-
0.5
故Sub差值Dsub
=
Sub2
-
Sub1
=
-2a/b
-
0.5
-
(-a/b-0.5)
=
-a/b.
代入a/b得Dsub
=
dy/dx;
于是，我们有了Sub的处始值Sub1
=
-a/b-0.5
=
dy/dx-0.5,又有了Sub的差值的表达式Dsub
=
dy/dx
-1
（当Sub1
>
0）或
dy/dx（当Sub1
<
0）.细化工作完成。
于是pcode可以细化如下：
//
Pcode
for
Bresenham
Line
//
By
SoRoMan
x=x1;
y=y1;
dx
=
x2-x1;
dy
=
y2-y1;
Sub
=
dy/dx-0.5;
//
赋初值，下个要画的点与中点的差值
DrawPixel(x,
y);
//
画起点
while(x<x2)
{
x++;
if(Sub
>
0)
//
下个要画的点为当前点的右上邻接点
{
Sub
+=
dy/dx
-
1;
//下下个要画的点与中点的差值
y++;
//
右上邻接点y需增1
}
else//
下个要画的点为当前点的右邻接点
{
Sub
+=
dy/dx;
}
//
画下个点
DrawPixel(x,y);
}
PS:一般优化：
为避免小数转整数以及除法运算，由于Sub只是用来进行正负判断，所以可以令Sub
=
2*dx*Sub
=
2dy-dx,则
相应的DSub
=
2dy
-
2dx或2dy.
思考1:如果Sub
=
0时，会产生取两个点都可以的问题。这个问题还没深入。

⑷ 关于Bresenham算法的求助

今天一下子遇到三个类似的问题，所以我这篇东西就连续复制粘贴了三遍：

（下面的坐标本来是有下标的，但复制过来就变没了，你可能看的有点晕）

Bresenham算法是Bresenham提出的一种光栅线生成算法！

DDA算法表面上看起来很有效，并且代码也比较容易实现，但是显示每个像素都需要进行一次浮点数加法运算，而Bresenham算法的最大优点是不需要进行浮点数运算！这是一种精确而有效的光栅线生成算法，该算法仅使用增量整数计算，计算速度比DDA要快，另外，Bresenham算法还可用于显示圆和其他曲线，这里暂时只显示直线！

与DDA一样，我们假设线段的两个端点坐标是整数值（x0,y0）（xEnd,yEnd）,且斜率m满足0<=m>=1!坐标轴的垂直轴表示扫描线位置，水平轴标识像素列，假设以单位x间隔取样，需要确定下一个每次取样时两个可能的像素位置中的哪一个更接近于线路径！

从给定线段的左端点（x0,y0）开始,逐步处理每个后继列（x位置），并在其扫描线y值最接近线段的像素处描出一点，假如已经确定要显示的像素在（xk,yk），那么下一步就要确定在列xk+1=xk+1上绘制哪个像素，是在位置(xk+1,yk)还是在(xk+1,yk+1)

在取样位置xk+1，我们使用dlower和pper来标识两个像素与数学上线路径的垂直偏移（就是通过这两个值来比较哪个点离线上的点最近，以下推导过程你可能看得有点晕，但都是为了推出后续的点而已，你可以结合下面例子程序中的Bresenham函数来看），在像素列xk+1处的直线上的y坐标根据直线方程可计算得：

y=m(xk+1)+b

那么可求得：

dlower=y-yk=m(xk+1)+b-yk

pper=(yk+1)-y=yk+1-m(xk+1)-b

令斜率m=dy/dx,引入决策参数Pk，定义为：

Pk=dx(dlower-pper)

=2dx*xk-2dy*yk+c

C是一个常数，值为2dx+dx(2b-1)

由此可以计算得到

pk+1=Pk+2dy-2dx(yk+1-yk)

其中yk+1-yk取0还是取1取决于参数Pk的符号，Pk为负时取0，Pk非负时取1！

而Pk为负时，下一个要绘制的点就是（xk+1,yk）且pk+1=Pk+2dy

Pk为非负时则下一个要绘制的点就是（xk+1,yk+1）且pk+1=Pk+2dy-2dx

至此，Bresenham算法介绍完毕，以下为某个示例：

#include<gl/glut.h>

#include<math.h>

#include<stdio.h>

voiddraw_pixel(intix,intiy)

{

glBegin(GL_POINTS);

glVertex2i(ix,iy);

glEnd();

}

voidBresenham(intx1,inty1,intxEnd,intyEnd)

{

intdx=abs(xEnd-x1),dy=abs(yEnd-y1);

intp=2*dy-dx;

inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;

intx,y;

if(x1>xEnd)

{

x=xEnd;y=yEnd;

xEnd=x1;

}

else

{

x=x1;

y=y1;

}

draw_pixel(x,y);

while(x<xEnd)

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyMinusDx;

draw_pixel(x,y);

}

}

}

voiddisplay()

{

glClear(GL_COLOR_BUFFER_BIT);

Bresenham(0,0,400,400);

glFlush();

}

voidmyinit()

{

glClearColor(0.8,1.0,1.0,1.0);

glColor3f(0.0,0.0,1.0);

glPointSize(1.0);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(0.0,500.0,0.0,500.0);

}

voidmain(intargc,char**argv)

{

glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);

glutInitWindowSize(500,500);

glutInitWindowPosition(200.0,200.0);

glutCreateWindow("CG_test_Bresenham_Lineexample");

glutDisplayFunc(display);

myinit();

glutMainLoop();

}

运行效果：

⑸ Bresenham直线算法的演算方法

Bresenham直线算法描绘的直线。假设我们需要由 (x0, y0) 这一点，绘画一直线至右下角的另一点(x1, y1)，x,y分别代表其水平及垂直坐标，并且 x1 - x0 > y1 - y0。在此我们使用电脑系统常用的坐标系，即x坐标值沿x轴向右增长，y坐标值沿y轴向下增长。
因此x及y之值分别向右及向下增加，而两点之水平距离为x1 − x0且垂直距离为y1-y0。由此得之，该线的斜率必定介乎于1至0之间。而此算法之目的，就是找出在x0与x1之间，第x行相对应的第y列，从而得出一像素点，使得该像素点的位置最接近原本的线。
对于由(x0, y0)及(x1, y1)两点所组成之直线，公式如下：
因此，对于每一点的x，其y的值是
因为x及y皆为整数，但并非每一点x所对应的y皆为整数，故此没有必要去计算每一点x所对应之y值。反之由于此线之斜率介乎于1至0之间，故此我们只需要找出当x到达那一个数值时，会使y上升1，若x尚未到此值，则y不变。至于如何找出相关的x值，则需依靠斜率。斜率之计算方法为m = (y1 − y0) / (x1 − x0)。由于此值不变，故可于运算前预先计算，减少运算次数。
要实行此算法，我们需计算每一像素点与该线之间的误差。于上述例子中，误差应为每一点x中，其相对的像素点之y值与该线实际之y值的差距。每当x的值增加1，误差的值就会增加m。每当误差的值超出0.5，线就会比较靠近下一个映像点，因此y的值便会加1，且误差减1。
下列伪代码是这算法的简单表达（其中的plot(x,y)绘画该点，abs返回的是绝对值）。虽然用了代价较高的浮点运算，但很容易就可以改用整数运算（详见最佳化一节）：
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax // 假设 deltax != 0 （非垂直线），
// 注意：需保留除法运算结果的小数部分
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs(error) ≥ 0.5 then
y := y + 1
error := error - 1.0

⑹ 分别解释直线生成算法DDA法、中点画线法和Bresenham法的基本原理

DDA称为数值微分画线算法，是直线生成算法中最简单的一种。原理相当简单，就是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例，m为斜率）
假定直线斜率k在0~1之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理

Bresenham：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。

大概就是这样，预知详细，可以参考图形学的书籍

⑺ 用C实现Bresenham算法生成直线和圆的程序(要求具体步骤有必要解述)

Bresenham算法生成直线
假定直线从(x1,y1)到(x2,y2)，
令dx=x2-x1，dy=y2-y1
不妨设(dx,dy)在第一象限,并且直线的斜率不大于1

画线过程中有三个循环变量
x,y,d
初值
x=x1,y=y1,d=2*dy-dx

循环，直到x==x2为止
{
如果d>=0,y++,d+=2*(dy-dx)
如果d<0 ,x++,d+=2*dy
}

如果(dx,dy)不在第一象限，要做变换，即先把第一象限的画出来
如果斜率大于1，x,y交换

非常简单的，很容易实现
圆的算法：

int Bres(int x0,int y0,double r,int color)

{
int x,y,d;
x=0;
y=(int)r;
d=(int)(3-2*r);
while(x<y)
{
cirpot(x0,y0,x,y,color);
if(d<0)
d+=4*x+6;
else
{
d+=4*(x-y)+10;
y--;
}
x++;
}
if(x==y)
cirpot(x0,y0,x,y,color);
return(0);
}
int cirpot(int x0,int y0,int x,int y,int color)
{
setcolor(color);
putxicl((x0+x),(y0+y));
putxicl((x0+y),(y0+x));
putxicl((x0+y),(y0-x));
putxicl((x0+x),(y0-y));
putxicl((x0-x),(y0-y));
putxicl((x0-y),(y0-x));
putxicl((x0-y),(y0+x));
putxicl((x0-x),(y0+y));
setcolor(color);
return(0);
}

这是圆的算法，你若要整个程序，把你的电邮给我，我给你发过去、
运行环境是Turboc 2.0
int Bresline(int x1,inty1,int x2,int y2,int color)
{
int color,itag;
int dx,dy,tx,ty,inc1,inc2,d,curx,cury;
setcolor(color);
putxicl(x1,y1);
if(x1==x2&&y1==y2)
{
setcolor(color);
return(1);
}
itag=0;
dx=abs(x2-x1);
dy=abs(y2-y1);
if(dx<dy)
{
itag=1;]
iswap(&x1,&y1);
iswap(&x2,&y2);
iswap(&dx,&dy);
}
tx=(x2-x1)>0? 1:-1;
ty=(y2-y1)>0? 1:-1;
curx=x1;
cury=y1;
inc1=2*dy;
inc2=2*(dy-dx);
d=inc1-dx;
while(curx!x2)
{
if(d<0)
{
d+=inc1;
}
else
{
cury+=ty;
d+=inc2;
}
if(itag)
setpixel(cury,curx);
else
setpixel(curx,cury);
curxd+=tx;
}
setcolor(color);
return(0);
}
iswap(int*a,int*b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}

这是直线的算法：和圆的差不多，你可以参考一下：）

⑻ bresenham算法的原理

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。
其原理是：
过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的
顺序计算直线各垂直网格线的交点，然后确定该列像素中与此交点最近
的像素。
该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项
的符号，就可以确定该列所求的像素。