bresenham画圆算法
1. 画圆为什么要用Bresenham算法
算法引入的本意是解决像素填充的问题的
点和线这种东西在理论上都是没有宽度的，但是要在屏幕上绘制的时候就要去填充像素以形成痕迹
一行上经常有2个以上的像素都被线所贯穿， 如何填充是个问题
而且像素填充本身是使用非常频繁的需求，故而画线的算法效率是非常重要的，对整个系统影响巨大
Bresenham算法是通过增量计算的方式快速判别下一个行或者列上的要填充的像素的位置，从计算上来说非常的节省，几乎都是整数的算法，速度非常的快
2. 用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;
}
这是直线的算法：和圆的差不多，你可以参考一下：）
3. C语言用Bresenham算法画圆，哪位高手教教，主要是算法里的内容，谢谢！
的确哈，关键在于对delta的理解
可以看到，都是delta=2*(1-radius)这样的，起作用应该是判断要画的点x、y坐标的变化趋势，先把我注释了的代码贴下，加了getch();可以看到画的过程
-----------------------------------------------------------------
#include<graphics.h>
#include<stdio.h>
void BresenhemCircle(int centerx, int centery, int radius, int color, int type);
void main()
{
int drive=DETECT,mode;
int i,j;
initgraph(&drive,&mode,"");
BresenhemCircle(300,200,100,15,0);
getch();
}
void BresenhemCircle(int centerx, int centery, int radius, int color, int type)
{
int x =type = 0;/*初始横坐标为原点*/
int y = radius; /*初始纵坐标远离原点*/
int delta = 2*(1-radius);
int direction;
while (y >= 0)
{
getch();
if (!type)/*执行*/
{
/*在上半圆画两点*/
putpixel(centerx+x, centery+y, color);
putpixel(centerx-x, centery+y, color);
/*在下半圆画两点*/
putpixel(centerx-x, centery-y, color);
putpixel(centerx+x, centery-y, color);
getch();
}
else/*不执行*/
{
line(centerx+x, centery+y, centerx+x, centery-y);
line(centerx-x, centery+y, centerx-x, centery-y);
getch();
}
/*以下代码设置下次四点的位置，圆是对称的，且此方法相当于同时画四个圆弧
观察右上方圆弧可知，前一半是x增的要快些，后一半是y减的快些*/
if (delta < 0)
{
if ((2*(delta+y)-1) < 0)
direction = 1; /*选择横向加*/
else
direction = 2;
}
else if(delta > 0)
{
if ((2*(delta-x)-1) > 0)
direction = 3; /*选择纵向减*/
else
direction = 2;
}
else
direction=2;
switch(direction)
{
case 1:
x++;/*只横坐标远离原点*/
delta += (2*x+1); /*小执行到这，所以加*/
break;
case 2:
x++;
y--;/*横向远离，同时纵向靠近*/
delta += 2*(x-y+1); /*即(2*x+1)+(-2*y+1)*/
break;
case 3:
y--;/*只纵坐标靠近原点*/
delta += (-2*y+1); /*大执行到这，所以减*/
break;
}
}
}
4. C++画圆（计算机图形学）
#include<math.h>
#include<graphics.h>/*预定义库函数*/
voidcirclePoint(intx,inty)/*八分法画圆程序*/
{
circle(320x*20,240y*20,3);
circle(320y*20,240x*20,3);
circle(320-y*20,240x*20,3);
circle(320-x*20,240y*20,3);
circle(320-x*20,240y*20,3);
circle(320-x*20,240-y*20,3);
circle(320-y*20,240-x*20,3);
circle(320y*20,240-x*20,3);
circle(320x*20,240-y*20,3);
}
voidMidBresenhamcircle(intr)/*中点Bresenham算法画圆的程序*/
{
intx,y,d;
x=0;y=r;d=1-r;/*计算初始值*/
while(x<y)
{circlePoint(x,y);/*绘制点(x,y)及其在八分圆中的另外7个对称点*/
if(d<0)d=2*x3;/*根据误差项d的判断,决定非最大位移方向上是走还是不走*/
else
{d=2*(x-y)5;
y--;
}
x;
delay(900000);
}/*while*/
}
main()
{
inti,j,r,graphmode,graphdriver;
detectgraph(&graphdriver,&graphmode);
initgraph(&graphdriver,&graphmode,"");
printf("中点Bresenhamcircle算法画圆的程序 ");/*提示信息*/
printf("注意|r|<=11");
printf(" 输入半径值r:");
scanf("%d",&r);
printf("按任意键显示图形...");
getch();
cleardevice();
setbkcolor(BLACK);
for(i=20;i<=620;i=20)/*使用双循环画点函数画出表格中的纵坐标*/
for(j=20;j<=460;j)
putpixel(i,j,2);
for(j=20;j<=460;j=20)/*使用双循环画点函数画出表格中的横坐标*/
for(i=20;i<=620;i)
putpixel(i,j,2);
outtextxy(320,245,"0");/*原点坐标*/
outtextxy(320-5*20,245,"-5");circle(320-5*20,240,2);/*横坐标值*/
outtextxy(3205*20,245,"5");circle(3205*20,240,2);
outtextxy(320-10*20,245,"-10");circle(320-10*20,240,2);
outtextxy(32010*20,245,"10");circle(32010*20,240,2);
outtextxy(320-15*20,245,"-15");circle(320-15*20,240,2);
outtextxy(32015*20,245,"15");circle(32015*20,240,2);
outtextxy(320,240-5*20,"-5");circle(320,240-5*20,2);/*纵坐标值*/
outtextxy(320,2405*20,"5");circle(320,2405*20,2);
outtextxy(320,240-10*20,"-10");circle(320,240-10*20,2);
outtextxy(320,24010*20,"10");circle(320,24010*20,2);
outtextxy(20,10,"Thecenterofthecircleis(0,0)");/*坐标轴左上角显示提示信息*/
setcolor(RED);/*标记坐标轴*/
line(20,240,620,240);outtextxy(32015*20,230,"X");
line(320,20,320,460);outtextxy(330,20,"Y");
setcolor(YELLOW);
MidBresenhamcircle(r);
setcolor(BLUE);/*绘制圆*/
circle(320,240,r*20);
setcolor(2);
getch();
closegraph();
}
5. 关于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();
}
运行效果：
6. bresenham算法的Bresenham改进算法
原理:
上述bresenham 算法在计算直线斜率与误差项时用到了小数与除法，可以改用整数以避免除法。由于算法中用到谈旅好误差含铅项的符号，因此可以做如下替换：e'=2*e*dx.
以下是C++语言方式描述的，在MFC下的镇兄核心绘图代码（画圆的算法）
{
CDC* pDC=GetDC();
int p,r,x,y,c,i;
r=50;
p=3-2*r;
c=RGB(0,0,0);
x=0;
y=r;
i=100;
for(;x<=y;)
{
pDC->SetPixel(x+i,y+i,c);
pDC->SetPixel(-x+i,-y+i,c);
pDC->SetPixel(-x+i,y+i,c);
pDC->SetPixel(x+i,-y+i,c);
pDC->SetPixel(y+i,x+i,c);
pDC->SetPixel(-y+i,x+i,c);
pDC->SetPixel(-y+i,-x+i,c);
pDC->SetPixel(y+i,-x+i,c);
if(p<0)p=p+4*x+6;
else {y--;p=p+4*(x-y)+10;}
x++;
}
}
7. 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次；
8. 请问中点bresenham算法画圆与bresenham算法画圆有区别吗
Bresenham算法画圆：
Bresenham算法用来画直线非常方便，但上次也说了，Bresenham算法也可以用来显示圆和其他曲线，只需要把直线方程改成圆方程或者其他曲线的方程就行，具体的推理过程就不演示了，大体跟直线的差不多！但由推算的结果可以看出，用Bresenham算法来画圆的确是不大明智的做法，要计算的步骤太多，计算速度比专门的画圆方法慢很多！并且在斜率越大的地方像素的间距就越大，当然我们可以在画某个像素之前先判断一下这一点跟前面一点的连线的斜率，然后在适当的时候交换x、y的坐标，但这样计算量必将增加！
直接给出Bresenham画圆的代码：
#include<gl/glut.h>
#include<math.h>
#include<stdio.h>
voiddraw_pixel(intix,intiy)
{
glBegin(GL_POINTS);
glVertex2i(ix,iy);
glEnd();
}
//intinlineround(constfloata){returnint(a+0.5);}
voidBresenham(intx1,inty1,intr,doublea,doubleb,doublec)/*圆心在（x1，y1），半径为r的圆*/
{
glColor3f(a,b,c);
intdx=r;//intdy=abs(yEnd-y1);
//intp=2*dy-dx;
//inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;
intx,y,d1,d2;
/*if(x1>xEnd)
{
x=xEnd;y=yEnd;
xEnd=x1;
}
else
{
x=x1;
y=y1;
}
*/
x=x1;
y=y1+r;
draw_pixel(x1,y1);
draw_pixel(x,y);//起始点装入帧缓存,起始点是圆的最上面一点，然后按顺时针来画
while(x<=x1+dx)
{
d1=y1+sqrt(pow(r,2)-pow(x-x1,2));/*lower*/
x++;
d2=2*(y1+sqrt(pow(r,2)-pow(x-x1,2)))-2*d1-1;/*lower-upper*/
if(1)
{
y=d1;
draw_pixel(x,y);
draw_pixel(x,2*y1-y);
draw_pixel(2*x1-x,y);
draw_pixel(2*x1-x,2*y1-y);
}
else
{
y++;
//p+=twoDyMinusDx;
draw_pixel(x,y);
}
}
}
voiddisplay()
{
glClear(GL_COLOR_BUFFER_BIT);
Bresenham(250,250,200,0.0,0.0,1.0);
Bresenham(300,250,150,1.0,0.0,0.0);
Bresenham(200,250,150,0.0,1.0,0.0);
//Bresenham(250,300,150,0.8,0.4,0.3);
//Bresenham(250,200,150);
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_Circleexample");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
以下为程序运行效果：
中点画圆：
用光栅画圆的不足在上次已经用实例表示的很明白了，上次画的那个圆怎么都不能算满意，虽然可以通过修改算法来得到改善，但本来计算步骤就已经很多了，交换坐标重新计算将会大大增加计算机的就是负担，为此我们采用另一种更加常用的画圆算法——中点画圆算法，之所以叫做“中点”画圆算法是由于它不是像Bresenham算法那样所绘像素不是（xk+1,yk）就是（xk+1,yk+1）,而是根据这两个点的中点来判断是（xk+1,yk）还是（xk+1,yk-1）更接近于圆！
对于给定的半径r和圆心（x0,y0）,我们先计算圆心在原点（0,0）的点，然后将其平移到圆心（x0,y0）处即可，跟Bresenham算法一样，我们也可以借助圆的高度对称性来减少计算机的计算步骤，在这里我们可以先计算出八分之一圆的像素点，然后根据对称性绘出其他点。这样可以大大加快画圆的速度！
跟光栅化方法一样，我们还是采用步进的方法来逐点描绘，但这里的决策参数计算方式跟Bresenham不大一样，设决策参数为p，则：
P=x2+y2-r2
对于任一个点（x，y），可以根据p的符号来判断点是在圆内还是圆外还是在圆上，这里不多说，假设我们在（xk,yk）处绘制了一个像素，下一步需要确定的是（xk+1,yk）还是（xk+1,yk-1）更接近于圆，在此代入这两个点的中点来求出决策参数：
Pk=（xk+1）2+（yk-1/2）2-r2
如果Pk<0,则yk上的像素更接近于圆，否则就是yk-1更接近于圆
同理可以推出Pk+1=Pk+2（xk+1）+（yk+12-yk2）-（yk+1-yk）+1
给出一个示例，这个圆比用Bresenham画出来的好看多了：
#include<glglut.h>
classscreenPt
{
private:
intx,y;
public:
screenPt(){x=y=0;}
voidsetCoords(GLintxCoordValue,GLintyCoordValue)
{
x=xCoordValue;
y=yCoordValue;
}
GLintgetx()const
{
returnx;
}
GLintgety()const
{
returny;
}
voidincrementx(){x++;}
voiddecrementy(){y--;}
};
voiddraw_pixel(intxCoord,intyCoord)
{
glBegin(GL_POINTS);
glVertex2i(xCoord,yCoord);
glEnd();
}
voidcircleMidpoint(GLintxc,GLintyc,GLintradius)
{
screenPtcircPt;
GLintp=1-radius;
circPt.setCoords(0,radius);
voidcirclePlotPoints(GLint,GLint,screenPt);
circlePlotPoints(xc,yc,circPt);
while(circPt.getx()<circPt.gety())
{
circPt.incrementx();
if(p<0)
p+=2*circPt.getx()+1;
else
{
circPt.decrementy();
p+=2*(circPt.getx()-circPt.gety())+1;
}
circlePlotPoints(xc,yc,circPt);
}
}
voidcirclePlotPoints(GLintxc,GLintyc,screenPtcircPt)//描绘八分圆各点
{
draw_pixel(xc+circPt.getx(),yc+circPt.gety());
draw_pixel(xc-circPt.getx(),yc+circPt.gety());
draw_pixel(xc+circPt.getx(),yc-circPt.gety());
draw_pixel(xc-circPt.getx(),yc-circPt.gety());
draw_pixel(xc+circPt.gety(),yc+circPt.getx());
draw_pixel(xc-circPt.gety(),yc+circPt.getx());
draw_pixel(xc+circPt.gety(),yc-circPt.getx());
draw_pixel(xc-circPt.gety(),yc-circPt.getx());
}
voiddisplay()
{
//screenPtPt;
glClear(GL_COLOR_BUFFER_BIT);
circleMidpoint(250,250,200);
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_中点画圆example");
glutDisplayFunc(display);
myinit();
glutMainLoop();
}
运行效果：