下载文档原格式
中点Bresenham算法是一种用于计算在直线上的格点的算法。
它是由Bresenham在1965年提出的，是一种高效的计算机图形学算法，通常用于直线、圆、椭圆等形状的绘制。
通过这篇文章，我们将详细介绍中点Bresenham算法的过程。
1. 背景知识在计算机图形学中，我们经常需要在屏幕上绘制直线、圆、椭圆等形状。
而计算机屏幕上的图像是由像素组成的，因此我们需要一种算法来计算出这些形状上的像素坐标，从而进行绘制。
中点Bresenham算法就是用来解决这个问题的。
2. 中点Bresenham算法的原理中点Bresenham算法的原理是通过巧妙的数学推导，找到离直线最近的像素点，从而确定需要绘制的像素坐标。
该算法通过利用误差项来判断下一个像素点的位置，具有高效、简洁的特点。
3. 中点Bresenham算法的过程中点Bresenham算法的过程可以分为以下几个步骤：3.1 初始化变量：首先需要确定直线的起点和终点，并初始化相关变量，如起点坐标(x0, y0)、终点坐标(x1, y1)、误差项d和增量变化量dx、dy等。
3.2 计算斜率k和误差项初始值：通过计算直线的斜率k，并根据斜率确定误差项的初始值。
3.3 循环计算像素点的坐标：根据误差项的大小，确定下一个像素点的位置，并更新误差项的值，直到绘制完整条直线。
4. 中点Bresenham算法的优势* 算法简洁高效：中点Bresenham算法通过简单的数学计算，即可确定直线上的像素坐标，避免了直接计算斜率导致的浮点数运算，因此在计算速度上具有较大优势。
* 适用范围广泛：中点Bresenham算法不仅适用于直线，还可以用于绘制圆、椭圆等图形，具有良好的通用性。
5. 中点Bresenham算法的应用中点Bresenham算法广泛应用于计算机图形学中的直线、圆、椭圆等图形的绘制。
其高效、简洁的特点使得它成为了计算机图形学中不可或缺的算法之一。
中点Bresenham算法是计算机图形学中的重要算法之一，通过巧妙的数学计算，实现了高效、简洁的直线绘制。
改进的Bresenham算法这里不仔细讲原理，只是把我写的算法发出来，跟大家分享下，如果有错误的话，还请大家告诉我，如果写的不好，也请指出来，一起讨论进步。
算法步骤：(1)输入直线的两端点P0(x0,y0)和P1(x1,y1)。
(2)计算初始值dx,dy,e=-dx,x=x0,y=y0。
(3)绘制点(x,y)。
(4)e更新为e+2*dy。
判断e的符号，若e 0,则(x,y)更新为(x+1,y+1)，同时将e更新为e-2*dx；否则(x,y)更新为(x+1,y)。
(5)当直线没有画完时，重复步骤(3)和(4)否则结束。
水平、垂直和|k|=1的直线可以直接装入帧缓冲存储器面无须进行画线算法处理。
下面是我的算法，如有错误请指出。
#include GL/freeglut.h voidinit(void){glClearColor(0.0f,0.0f,0.0f,1.0f)；}void drawLine(intx1,int y1,int x2,int y2){int x,y,dx,dy,e；//k does not existif(x1==x2){if(y1 y2){y=y1；glBegin(GL_POINTS)；while(y=y2){glVertex2i(x1,y)；++y；}glEnd()；}//if(y1 y2)else{y=y2；glBegin(GL_POINTS)；while(y=y1){glVertex2i(x1,y)；++y；}glEnd()；}}//if(x1==x2)else if(y1==y2)//k=0{if(x1 x2){x=x1；glBegin(GL_POINTS)；while(x=x2){glVertex2i(x,y1)；++x；}glEnd()；}//if(x1 x2)else{x=x2；glBegin(GL_POINTS)；while(x=x1){glVertex2i(x,y1)；++x；}glEnd()；}}else{if(x1 x2){int temp=x1；x1=x2；x2=temp；temp=y1；y1=y2；y2=temp；}x=x1；y=y1；dx=x2-x1；dy=y2-y1；//k=1 if(dx==dy){glBegin(GL_POINTS)；while(x=x2){glVertex2i(x,y)；++x；++y；}glEnd()；}else if(dx==-dy)//k=-1{glBegin(GL_POINTS)；while(x=x2){glVertex2i(x,y)；++x；--y；}glEnd()；}else if(dy dx)//k 1{glBegin(GL_POINTS)；dx=1；e=-dy；dy=1；y=y1 y2?y2：y1；int maxY=y1 y2?y1：y2；while(y=maxY){glVertex2i(x,y)；++y；e+=dx；if(e 0){++x；e-=dy；}}glEnd()；}else if(dy 0)//0 k1{e=-dx；dx=1；dy=1；glBegin(GL_POINTS)；while(x=x2){glVertex2i(x,y)；++x；e+=dy；if(e0){e-=dx；++y；}}glEnd()；}else if(-dy dx)//0 k-1{e=-dx；dx=1；dy=1；glBegin(GL_POINTS)；while(x=x2){glVertex2i(x,y)；++x；e+=dy；if(e0){--y；e+=dx；}}glEnd()；}else if(-dy dx)//k-1{e=dy；dx=1；dy=1；glBegin(GL_POINTS)；y=y1 y2?y1：y2；int minY=y1 y2?y2：y1；while(y=minY){glVertex2i(x,y)；--y；e+=dx；if(e 0){++x；e+=dy；}}glEnd()；}}}void display(void){glClear(GL_COLOR_BUFFER_BIT)；glColor3f(1.0f,0.0f,0.0f)；//Vertical line drawLine(0,-200,0,200)；//Horizontal line drawLine(-200,0,200,0)；//k=1 line drawLine(-200,-200,200,200)；//k=-1 line drawLine(-200,200,200,-200)；//k=1/2 line drawLine(200,100,-200,-100)；//k=2 line drawLine(-100,-200,100,200)；//k=-1/2 line drawLine(-200,100,200,-100)；//k=-2 line drawLine(-100,200,100,-200)；drawLine(30,120,10,70)；drawLine(10,70,30,10)；drawLine(30,10,60,50)；drawLine(60,50,80,10)；drawLine(80,10,120,80)；drawLine(120,80,70,80)；drawLine(70,80,30,120)；glutSwapBuffers()；}void reshape(int w,inth){glViewport(0,0,(GLsizei)w,(GLsizei)h)；glMatrixMode(GL_PROJECTION)；glLoadIdentity()；if(w=h){gluOrtho2D(-600.0,600.0,-600.0*(GLfloat)h/(GLfloat)w,600.0*(GLfloat)h/(GLfloat)w)；}else{gluOr tho2D(-600.0*(GLfloat)w/(GLfloat)h,600.0*(GLfloat)w/(GLfloat)h,-600.0,600.0)；}glMatrixMode(GL_MODELVIEW)；glLoadIdentity()；}void keyboard(unsigned char key,int x,int y){switch(key){case 27：//'VK_ESCAPE'exit(0)；break；default：break；}}int main(intargc,char*argv){glutInit(&argc,argv)；glutInitDisplayMode(GLUT_DOUBLE|GLUT_RGB)；glutInitWindowSize(600,600)；glutCreateWindow("optimized Bresenhamline")；init()；glutReshapeFunc(reshape)；glutDisplayFunc(display)；glutKeyboardFunc(keyboard)；glutMainLoop()；return 0；}作者：断桥&残雪发表于2010-12-04 20：29原文链接评论：0查看评论发表评论最新新闻：·马云：B2C创业者别埋怨淘宝不会停下来等你(2010-12-04 20：17)·Chrome to WP7手机端应用程序已经通过审核，可以下载了(2010-12-04 20：00)·盘点网络犯罪与信息战风云30年(2010-12-04 18：06)·网易邮箱：推出简历中心(2010-12-04 18：03)·马云：互联网三座大山将败给创新型小网站(2010-12-04 17：33)编辑推荐："博客无双"活动：写博客、攒园豆、赢大奖网站导航：博客园首页我的园子新闻闪存小组博问知识库。
bresenham圆生成算法Bresenham圆生成算法是一种经典的计算机图形学算法，用于在计算机屏幕上绘制圆形。
该算法是由美国计算机科学家Jack E. Bresenham于1965年发明的。
这个算法非常简单，但是它却非常有效，因为它只需要使用整数运算。
Bresenham圆生成算法的基本思想是使用一个叫做“决策参数”的变量来决定下一个像素点的位置。
该变量根据当前像素点到圆心的距离和半径之间的差异进行调整。
如果该差异小于0，则移动到右上方的像素点；否则，移动到右上方和正上方之间的像素点。
具体来说，Bresenham圆生成算法可以通过以下步骤来实现：1. 输入圆心坐标和半径。
2. 初始化x和y坐标为0，并计算出初始决策参数d=3-2r。
3. 在每个步骤中，检查当前像素点是否在圆内。
如果是，则将该像素点绘制出来；否则，不绘制。
4. 计算下一个像素点的位置。
如果d小于0，则移动到右上方；否则，移动到右上方和正上方之间。
5. 更新决策参数d。
Bresenham圆生成算法的优点是它非常快速和有效。
它只需要使用整数运算，因此可以在计算机上非常快速地执行。
此外，该算法还可以轻松地扩展到三维空间中的球体和其他形状。
尽管Bresenham圆生成算法已经有几十年的历史了，但它仍然是计算机图形学中最常用的算法之一。
它被广泛应用于游戏开发、计算机辅助设计、虚拟现实等领域。
此外，该算法还被用于许多其他领域，如数字信号处理和图像处理。
总之，Bresenham圆生成算法是一种简单而有效的计算机图形学算法。
它可以快速地绘制出圆形，并且可以轻松地扩展到其他形状。
尽管这个算法已经有几十年的历史了，但它仍然是计算机图形学中最常用的算法之一，并且在许多其他领域也得到了广泛应用。
计算机图形学——圆的扫描转换（基本光栅图形算法）与直线的⽣成类似，圆弧⽣成算法的好坏直接影响到绘图的效率。
本篇博客将讨论圆弧⽣成的3个主要算法，正负法、Bresenham 法和圆的多边形迫近法，在介绍算法时，只考虑圆⼼在原点，半径为R的情况。
⼀、正负法1、基本原理假设已选取Pi-1为第i-1个像素，则如果Pi-1在圆内，就要向圆外⽅向⾛⼀步；若已在圆外就要向圆内⾛⼀步。
总之，尽量贴近圆的轮廓线。
2、正负法的具体实现1）圆的表⽰：设圆的圆⼼为(0,0),半径为R，则圆的⽅程为：F(x,y)=x2+y2–R2=0当点(x,y)在圆内时，F(x,y)<0。
当点(x,y)在圆外时，F(x,y)>0。
2）实现步骤第1步：x0=0，y0=R第2步：求得Pi(x i,y i)后找点P i+1的原则为：当P i在圆内时(F(xi,yi)≤0)，要向右⾛⼀步得P i+1，这是向圆外⽅向⾛去。
取x i+1= x i+1, y i+1= y i当P i在圆外时(F(xi,yi)>0)，要向下⾛⼀步得P i+1，这是向圆内⽅向⾛去，取x i+1= x i, y i+1= y i-1⽤来表⽰圆弧的点均在圆弧附近且 F(xi, yi)时正时负假设已经得到点（x i, y i），则容易算出F(x i, y i)，即确定了下⼀个点（x i＋1, y i＋1），则如何计算F(x i+1, y i+1)，以确定下下个点（x i＋2, y i＋2）？分为两种情况：右⾛⼀步后：x i+1=x i+1，y i+1=y i，此时：F(x i+1, y i+1)=x i+12+y i2-R2=x i2+y i2-R2+2x i+1 = F(x i, y i)+2x i+1下⾛⼀步后：x i+1=x i，y i+1=y i-1， 此时：F(x i+1, y i+1)=x i2+（y i-1)2-R2= F(x i, y i)-2y i+1由此可得：确定了F(xi+1, yi+1)之后，即可决定下⼀个点(xi+2, yi+2)，选择道理同上。
§3.2圆的生成——Bresenham算法条件：给定圆心(x c,y c)和半径R约定：只考虑圆心在原点，半径为整数R的圆x2+y2.=R2。
对于圆心不在原点的圆，可先通过平移转换，化为圆心在原点的圆，再进行扫描转换，把所得到的像素集合加上一个位移量，就可以把目标圆光栅化。
在众多圆的生成算法，如逐点比较法、角度DDA法、Bresenham算法中，Bresenham画圆法是一种最简单有效的的方法。
首先注意到只要生成一个八分圆，那么，圆的其它部分就可以通过一系列的对成变换得到。
12345678由算法生成y=x第一八分圆关于y=x对称变换第一四分圆关于x=0对称变换上半圆关于y=0对称变换如果以点x=0，y=R为起点按顺时针方向生成圆，则在第一象限内y是x 的单调递减函数。
要在这三个像素中选择一个使其与理想圆的距离的平方达到最小，即下列数值中的最小者。
R(0,R)(R,0)xy这样，从圆上任一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，对于下一像素的取法只有三种可能的选择，即正右方像素、正下方像素和右下角像素，分别记作：m H、m V、m D。
(x i，y i)(x i，y i-1)(x i+1，y i)(x i+1，y i-1)m Hm Dm Vm H=|(x i+1)2+(y i)2-R2|m V=|(x i)2+(y i+1)2-R2|m D=|(x i+1)2+(y I-1)2-R2|m H(x i,y i)(x i+1,y i)(x i+1,y i+1)(x i+1,y i-1)(x i-1,y i-1)(x i,y i-1)m Vm D12354圆与点(x i，y i)附近光栅格网的相交关系只有五种可能。
从圆心到右下角像素(x i+1,y i-1)的距离平方m D与圆心到圆上点的距离平方R2之差等于：Δi=(x i+1)2+(y i-1)2-R2如果Δi<0,那么右下角像素(x i+1,y i-1)在该圆内(图中①、②)，显然这时只能取像素(x i+1,y i)，即m H；或像素(x i+1,y i-1)，即m D。
Bresenham直线算法与画圆算法（转）在我们内部开发使用的一个工具中，我们需要几乎从0 开始实现一个高效的二维图像渲染引擎。
比较幸运的是，我们只需要画直线、圆以及矩形，其中比较复杂的是画直线和圆。
画直线和圆已经有非常多的成熟的算法了，我们用的是Bresenham的算法。
计算机是如何画直线的？简单来说，如下图所示，真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。
（上图来自于互联网络，《计算机图形学的概念与方法》柳朝阳，郑州大学数学系）接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。
Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。
这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。
是计算机图形学中最先发展出来的算法。
(引自wiki 百科布雷森漢姆直線演算法)这个算法的流程图如下：可以看到，算法其实只考虑了斜率在 0 ~ 1 之间的直线，也就是与 x 轴夹角在 0 度到 45 度的直线。
只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。
下面是一个C 语言实现版本。
1 2 3 4 5 // 交换整数 a 、b 的值inline void swap_int(int *a, int *b) {*a ^= *b;*b ^= *a;*a ^= *b;6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 }// Bresenham's line algorithmvoid draw_line(IMAGE *img, int x1, int y1, int x2, int y2, unsigned long c) {// 参数 c 为颜色值int dx = abs(x2 - x1),dy = abs(y2 - y1),yy = 0;if (dx < dy) {yy = 1;swap_int(&x1, &y1);swap_int(&x2, &y2);swap_int(&dx, &dy);}int ix = (x2 - x1) > 0 ? 1 : -1,iy = (y2 - y1) > 0 ? 1 : -1,cx = x1,cy = y1,n2dy = dy * 2,n2dydx = (dy - dx) * 2,d = dy * 2 - dx;if (yy) { // 如果直线与 x 轴的夹角大于 45 度while (cx != x2) {if (d < 0) {d += n2dy;} else {cy += iy;d += n2dydx;}putpixel(img, cy, cx, c);cx += ix;}} else { // 如果直线与 x 轴的夹角小于 45 度while (cx != x2) {if (d < 0) {d += n2dy;} else {cy += iy;d += n2dydx;}50515253putpixel(img, cx, cy, c);cx += ix;}}}可以看到，在画线的循环中，这个算法只用到了整数的加法，所以可以非常的高效。
Bresenham画圆算法的改进
王志喜;王润云
【期刊名称】《计算机工程》
【年(卷),期】2004(30)12
【摘要】由于没有充分考虑圆弧的特点,使得传统的Bresenham画圆算法效率还不够高,算法过于复杂,容易造成失真.该文总结了传统的Bresenham画圆算法,指出了传统Bresenham画圆算法的缺陷,提出改进的Bresenham画圆算法,并用实例进行验证,对Bresenham画圆算法的优越性进行了分析.
【总页数】3页(P178-180)
【作者】王志喜;王润云
【作者单位】湘潭工学院计算机系,湘潭,411201;湘潭工学院计算机系,湘
潭,411201
【正文语种】中文
【中图分类】TP312
【相关文献】
1.一种改进的等分迭代Bresenham直线生成算法 [J], 李竹林;邓石冬
2.嵌入式自像系统的改进Bresenham反走样算法的应用 [J], 张鹏;王良
3.一种快速的Bresenham直线生成改进算法 [J], 孙云
4.改进的Bresenham直线生成算法 [J], 陈定钰
5.串联型机械臂直线轨迹规划Bresenham算法应用与改进 [J], 张岩;过仕安;李争;安国庆;薛智宏;盖祥虎
因版权原因，仅展示原文概要，查看原文内容请购买。
易懂的Bresenham布雷森汉姆算法画圆的原理与Python编程实现教程Bresenham 布雷森汉姆算法画圆的原理与编程实现教程注意：Bresenham的圆算法只是中点画圆算法的优化版本。
区别在于Bresenham的算法只使⽤整数算术，⽽中点画圆法仍需要浮点数。
注意：不要因为我提到了中点画圆法你就去先看完再看Bresenham算法，这样是浪费时间。
中点画圆法和Bresenham画圆法只是思想⼀样，但是思路并没有很⼤关联。
所以直接看Bresenham算法就可以。
看下⾯这个图，这就是⼀个像素⼀个像素的画出来的。
我们平常的圆也是⼀个像素⼀个像素的画出来的，你可以试试在“画图”这个软件⾥⾯画⼀个圆然后放⼤很多倍，你会发现就是⼀些像素堆积起来的。
我们看出来圆它是⼀个上下左右都对称，⽽且也是中⼼对称的。
所以我们只⽤画好⼋分之⼀圆弧就可以，其他地⽅通过对称复制过去就好。
看下⾯这幅图，绿线夹住的那部分就是⼋分之⼀圆弧。
注意我们是逆时针画圆的（即从⽔平那个地⽅即(r,0)开始画因为⼀开始我们只知道⽔平位置的像素点该放哪其他地⽅我们都不知道）。
Bresenham 算法画完⼀个点(x,y)后注意x,y都是整数。
他们代表的是x,y⽅向上的第⼏个像素。
，它下⼀步有两个选择(x,y+1),(x-1,y+1)。
也就是说y⼀定增加,但是x要么保持不变要么减⼀（你也可以让x⼀定增加y要么不变要么加⼀，其实差不多的）。
当程序画到粉红⾊那个像素点的时候，程序选择下⼀步要绘制的点为(x-1，y+1)。
当程序画到黄⾊的那个像素点时候，程序选择下⼀步要绘制的点为(x,y+1)。
我们看看粉⾊的那个点的下⼀步是如何抉择的。
Bresenham是根据待选的两个点哪个离圆弧近就下⼀步选哪个。
那它是怎么判断的呢？这两个点⼀定有⼀个在圆弧内⼀个在圆弧外。
到底选哪个？Bresenham的⽅法就是直接计算两个点离圆弧之间的距离，然后判断哪个更近就选哪个。
生成圆的bresenham算法原理描述详细Bresenham算法是计算机图形学中非常重要的算法之一，可以生成各种形状的图像。
其中，生成圆形图像的Bresenham算法也是应用比较广泛的算法之一。
本文将详细描述生成圆的Bresenham算法原理。
1. 圆的数学表示圆是一个几何图形，其数学表示为：x² + y² = r²，其中，x、y是圆上点的坐标，r是圆的半径。
因此，生成圆的Bresenham算法需要计算出符合该数学表示的所有点的坐标。
2. Bresenham算法的核心思想Bresenham算法的核心思想是利用对称性和递推式来快速计算出每个点的坐标。
对于圆而言，其有四分之一的区域可以通过对称性计算出来，而另外四分之三的区域可以通过递推式来得出。
3. 圆的对称性对于圆而言，其具有对称性，即当坐标为（x,y）在圆上时，也必然存在（y,x）、（y,-x）、（x,-y）、(-x,-y)、(-y,-x)、(-y,x)、(-x,y)在圆上的点，也就是说，直接通过圆的对称性可以得到大约四分之一的在圆上的点。
4. 圆的递推式对于圆的另外四分之三的部分，我们可以使用递推式来获得。
根据圆的坐标表示式x² + y² = r²，我们可以得到下届式：x² + y² - r² = 0根据这个方程，可以计算出下一个点的坐标为：x + 1, y 或 x + 1, y - 1如果采用当前点（x,y）的对称点来计算，比如（y,x），那么坐标可以改成：y + 1, x 或 y + 1, x - 1通过这种方式，就可以逐个计算出每个点的坐标了。
5. 算法步骤生成圆的Bresenham算法的步骤如下：1）确定圆的中心点的坐标和半径；2）以圆心为原点建立坐标系，以x轴为基准线向右，y轴向上；3）通过圆的对称性计算出直径上的点的坐标；4）使用递推式计算出剩余的坐标；5）根据得到的坐标渲染圆的边缘。
