bresenham算法算法思想

Ⅰ 画圆为什么要用Bresenham算法

算法引入的本意是解决像素填充的问题的
点和线这种东西在理论上都是没有宽度的，但是要在屏幕上绘制的时候就要去填充像素以形成痕迹
一行上经常有2个以上的像素都被线所贯穿， 如何填充是个问题

而且像素填充本身是使用非常频繁的需求，故而画线的算法效率是非常重要的，对整个系统影响巨大

Bresenham算法是通过增量计算的方式快速判别下一个行或者列上的要填充的像素的位置，从计算上来说非常的节省，几乎都是整数的算法，速度非常的快

Ⅱ 以圆的Bresenham生成算法为例,图解矢量图形和光栅图形的区别

有电子艺术图像被分为两种核心类型：光栅图像（也称为“位图”）和矢量图像。简而言之，光栅图像由连接的点组成，矢量是由连接的线组成的图像。这两种格式彼此完全不同，但当适当地用于所需的最终输出方法时，它们彼此形成对比和互补。光栅图像通过扫描源图稿或使用照片编辑或绘图程序（如Corel、PhotoPAINT或Adobe PhotoShop）“绘画”来创建，而矢量图像是通过使用CorelDRAW或Adobe Illustrator等矢量插图程序绘制的过程来创建的。

一、Bresenham算法原理

由Bresenham提出的一种精确而有效的光栅线生成算法，可用于显示线、圆和其他曲线的整数增量运算。它是目前最有效的线段生成算法。

推导：

设线段端点：(,),(,),∆x和∆y为水平和垂直偏移量,m为斜率

当|m| <= 1时,对于给定的x增量∆x

当|m| >= 1时,对于给定的y增量∆y，

（当 0<m < 1）

假设已经确定了要显示的像素，那么，需要确定下一点是绘制在，

还是。

根据直线的方程，直线上处的y坐标为：

将m带入d1 – d2中，并变换得：

其中，为算法中第k步的决策参数，c为一常量，其值为。

那么：

若，即,有

若, 即,有

同理，可求得第k+1步的决策参数

因此，有如下递推关系：

因为0<m<1 因此，带入上式得：

其中，的值取决于的值：

当时，，

当时， ，

Bresenham算法描述 (0 < m < 1)

算法从线段的起始端点开始，反复计算每个点的决策参数并绘制像素。

起始端点处的决策参数为：

算法：

1、输入线段的两个端点，并将左端点存储在中；

2、将装入帧缓冲器，画出第一个点；

3、计算常量∆x，∆y，2∆y 和2∆y – 2∆x，并得到决策参数的第一个值：

4、从k = 0开始，在沿线的每个处，进行下列检测：

若，下一个待画点是，且

若 ，下一个待画点是，且

5、重复步骤4，共∆x次。

————————————————

版权声明：本文为CSDN博主“地泽万物”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_41883085/article/details/102706471

Ⅲ 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

Ⅳ 直线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();

}

运行效果：

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

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

Ⅷ bresenham算法的算法

void IntegerBresenhamlin(int x0,int y0,int x1,int y1,int color)
{
int x,y,dx,dy,unitx,unity,fabs_dx,fabs_dy,e;
unsigned char i;
dx=x1-x0;
dy=y1-y0;
fabs_dx = (int)fabs(dx);
fabs_dy = (int)fabs(dy);
unitx = dx / fabs_dx ;
unity = dy / fabs_dy ;
x=x0;
y=y0;
if( fabs_dx> fabs_dy )
{
e=-fabs_dx;
for(i=0;i<=fabs_dx;i++)
{
drawpixel(x,y,color);
x+=unitx,e=e+2*fabs_dy;
if(e>=0)
{
y+=unity;e=e-2*fabs_dx;
}
} // for end
}
else
{
e-=fabs_dy;
for(i=0;i<=fabs_dy;i++)
{
drawpixel(x,y,color);
y+=unity,e=e+2*fabs_dx;
if(e>=0)
{
x+=unitx;e=e-2*fabs_dy;
}
} // for end
}// if end
} //:~

Ⅸ bresenham算法的介绍

bresenham算法是计算机图形学中为了“显示器（屏幕或打印机）系由像素构成”的这个特性而设计出来的算法，使得在求直线各点的过程中全部以整数来运算，因而大幅度提升计算速度。

Ⅹ dda法生成直线的基本原理是什么为什么说Bersenham画圆的算法效率较高

DDA算法主要是根据直线公式y = kx + b来推导出来的，其关键之处在于如何设定单位步进，即一个方向的步进为单位步进，另一个方向的步进必然是小于1。算法的具体思路如下：
1. 输入直线的起点、终点；
2. 计算x方向的间距：△X和y方向的间距：△Y。
3. 确定单位步进，取MaxSteps = max（△X，△Y）; 若△X>=△Y，则X方向的步进为单位步进，X方向步进一个单位，Y方向步进△Y/MaxSteps;否则相反。
4. 设置第一个点的像素值
5. 令循环初始值为1，循环次数为MaxSteps，定义变量x,y，执行以下计算：
a. x增加一个单位步进，y增加一个单位步进
b. 设置位置为（x,y）的像素值

Bresenham算法是DDA算法画线算法的一种改进算法。本质上它也是采取了步进的思想。不过它比DDA算法作了优化，避免了步进时浮点数运算，同时为选取符合直线方程的点提供了一个好思路。首先通过直线的斜率确定了在x方向进行单位步进还是y方向进行单位步进：当斜率k的绝对值|k|<1时，在x方向进行单位步进；当斜率k的绝对值|k|>1时，在y方向进行单位步进。
1. 输入线段的起点和终点。
2. 判断线段的斜率是否存在（即起点和终点的x坐标是否相同），若相同，即斜率不存在，
只需计算y方向的单位步进（△Y+1次），x方向的坐标保持不变即可绘制直线。
3. 计算线段的斜率k，分为下面几种情况处理
a. k等于0，即线段平行于x轴，即程序只需计算x方向的单位步进，y方向的值不变
b. |k|等于1，即线段的x方向的单位步进和y方向的单位步进一样，皆为1。直接循环△X次计算x和y坐标。
4. 根据输入的起点和终点的x、y坐标值的大小决定x方向和y方向的单位步进是1还是-1
6. 画出第一个点。
7. 若|k| <1，设m =0,计算P0，如果Pm>0，下一个要绘制的点为（Xm+单位步进，Ym），
Pm+1 = Pm -2*△Y;
否则要绘制的点为（Xm+单位步进，Ym+单位步进）
Pm+1 = Pm+2*△X-2*△Y；
8. 重复执行第七步△X-1次；
9. 若|k| <1，设m =0,计算Q0，如果Qm>0，下一个要绘制的点为（Xm，Ym+单位步进），
Pm+1 = Pm -2*△X;
否则要绘制的点为（Xm+单位步进，Ym+单位步进）
Pm+1 = Pm+2*△Y-2*△X；
10. 重复执行第9步△Y-1次；