bresenham算法例题分析

Bresenham快速画直线算法一、算法原理简介：算法原理的详细描述及部分实现可参考：http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html假设以(x, y)为绘制起点，一般情况下的直观想法是先求m = dy /dx（即x每增加1，y的增量），然后逐步递增x, 设新的点为x1 = x + j, 则y1 = round(y + j * m)。

可以看到，这个过程涉及大量的浮点运算，效率上是比较低的（特别是在嵌入式应用中，DSP可以一周期内完成2次乘法，一次浮点却要上百个周期）。

下面，我们来看一下Bresenham算法，如Fig. 1,(x, y +ε)的下一个点为(x, y + ε + m)，这里ε为累加误差。

可以看出，当ε+m < 0.5时，绘制(x + 1, y)点，否则绘制(x + 1, y + 1)点。

每次绘制后，ε将更新为新值：ε = ε + m ,如果(ε + m) <０.５ (或表示为2*(ε + m) < 1)ε = ε + m – 1, 其他情况将上述公式都乘以dx, 并将ε*dx用新符号ξ表示，可得ξ = ξ + dy, 如果2*(ξ + dy) < dxξ = ξ + dy – dx, 其他情况可以看到，此时运算已经全变为整数了。

以下为算法的伪代码及实例：起点：（x1,y1）=(0,0)，终点：（x2,y2）=(5,3)ξ← 0, y ← y1For x ← x1 to x2 doPlot Point at (x, y)If (2(ξ + dy) < dx)ξ←ξ + dy； y←y;Elsey ← y + 1,ξ←ξ + dy – dxEnd Ifx ←x+1;End For二、画图步骤如下：起点：（x1,y1）=(0,0)，终点：（x2,y2）=(5,3); dx=5; dy=3；ξ=0；第一步：(1)ξ=0；x=x1=0; y=y1=0; 画点（x1,y1）=(0,0)；(2)2(ξ + dy)= 2(0 + 3)=6>dx=5; 因此：y2=y+1=1; ξ=ξ+dy–dx=0+3-5=-2;X2=x1+1=1;第二步：(1)ξ=-2；x=x2=1; y=y2=1; 画点（x2,y2）=(1,1)；(2)2(ξ + dy)= 2(-2 + 3)=2<dx=5; 因此：y3=y=1; ξ=ξ+dy=-2+3=1; X3=x+1=2;第三步：(1)ξ=1；x=x3=2; y=y3=1; 画点（x3,y3）=(2,1)；(2)2(ξ + dy)= 2(1 + 3)=8>dx=5; 因此：y4=y+1=2; ξ=ξ+dy-dx=1+3-5=-1; X4=x+1=3;第四步：(1)ξ=-1；x=x4=3 y=y4=2; 画点（x4,y4）=(3,2)；(2)2(ξ + dy)= 2(-1+ 3)=4<dx=5; 因此：y5=y=2; ξ=ξ+dy=-1+3=2; X5=x+1=4;第五步：(1)ξ=2；x=x5=4; y=y5=2; 画点（x5,y5）=(4,2)；(2)2(ξ + dy)= 2(2 + 3)=10>dx=5; 因此：y6=y+1=3; ξ=ξ+dy-dx=2+3-5=0; X6=x+1=5;第六步：(1)ξ=0；x=x6=5; y=y6=3; 画点（x6,y6）=(5,3)；x1x2x3x4x5x6三、算法的注意点：在实际应用中，我们会发现，当dy > dx或出现Fig.2 右图情况时时，便得不到想要的结果，这是由于我们只考虑dx > dy，且x, y的增量均为正的情况所致。

[整理]案例2-直线中点bresenham算法课程实验报告课程名称计算机图形学班级实验日期姓名学号实验成绩实验名称直线中点Bresenham算法实斜率0?k?1直线的中点Bresenham算法。

验任意斜率直线段绘制算法。

目颜色类的定义不调用方法。

的直线类的定义不调用方法。

及鼠标按键消息映射方法。

要求1、案例描述实在屏幕客户区内按下鼠标左键赞扬直线的起点,移动鼠标指针到直线验终点上,弹起鼠标左键绘制任意斜率的直线段。

内 2、功能说明容，1，设计CRGB类其成员变量为double型的红绿蓝分量red,green和blue,将red,green和blue分量分别规范到[0,1]区间。

，2，设计Cline直线类,其成员变量为直线段的起点坐标P0和终点坐标P1,成员函数为MoveTo()和LineTo()函数。

，3，Cline类的LineTo()函数使用中点Bresenham算法绘制任意斜率的直线段,包括k=??,k>1,错误!未找到引用源。

0???1, -1??<0和k<-1这5种情况。

，4，自定义屏幕二维坐标系,原点位于客户区中心,x轴水平向右为正,y轴垂直向上为正。

直线段的起点坐标和终点坐标相对于屏幕客户区中心定义。

1、案例分析算 MFC提供的CDC类的成员函数MoveTo()和LineTo()函数用于绘制傻法任意斜率的直线段,直线段的颜色由所选用的画笔指定。

MoveTo()函数移描动当前点到参数(x,y)所指定的点,不画线;LineTo()函数从当前点画一述直线段到参数(x,y)所指定的点,但不包括(x,y)。

本案例通过定义Cline类来模拟CDC类绘制任意斜的直线段,采用直线中点Bresenham算法。

2、算法设计对于0???1的直线段,中点Bresenham算法如下:，1，使用鼠标选择起点坐标p0(x0,y0)和终点坐标p1(x1,y1)。

要求起点的的坐标小于等于终点的x坐标。

Bresenham算法是计算机图形学中常用的一种画直线的算法。

它的原理是利用像素点在屏幕上的排列规律，从而高效地计算出直线上的像素点。

本文将以一个具体的例题来说明Bresenham算法的原理及应用。

1. 问题描述假设我们需要在一个分辨率为800x600的屏幕上，画一条直线，起点坐标为(100, 200)，终点坐标为(400, 300)。

请使用Bresenham算法计算直线上的像素点，并用符号“*”表示出来。

2. Bresenham算法原理Bresenham算法的核心思想是利用像素点的整数坐标值与直线的斜率之间的关系，从而逐个确定直线上的像素点。

具体步骤如下：- 计算直线的斜率k，即k = (y2 - y1) / (x2 - x1)，其中(x1, y1)为起点坐标，(x2, y2)为终点坐标。

- 以起点坐标作为初始值，从左至右依次求解直线上各点像素的坐标。

- 对于每一个x坐标，根据斜率k的大小确定y坐标的增长方向。

3. Bresenham算法应用根据上述原理，我们来解决具体的例题。

计算直线的斜率k：k = (300 - 200) / (400 - 100) = 1/3以起点坐标(100, 200)作为初始值，从左至右依次求解直线上各点像素的坐标。

当x坐标从100递增至400时，y坐标的增长方向由斜率k来确定。

具体计算如下：- 当x=100时，y=200- 当x=101时，y=200+1/3≈200- 当x=102时，y=200+2/3≈201- ...- 当x=400时，y=300现在，我们可以得到直线上的像素点坐标，并用符号“*”表示出来。

4. 结果展示根据上述计算，我们可以得到该直线上的像素点坐标，展示如下：(100, 200) *(101, 200) *(102, 201) *...(400, 300) *通过Bresenham算法，我们成功地计算出了直线上的像素点，并用符号“*”进行了展示。

随着计算机图形学的发展，Bresenham算法作为一种高效的直线扫描算法被广泛应用。

本文将结合中点Bresenham算法和斜率大于1的具体例题，深入探讨其原理及应用。

1. 中点Bresenham算法中点Bresenham算法是一种用于绘制直线的算法，其特点是高效、精确。

该算法通过在每个x处选择最接近直线的y坐标，从而实现了高效的直线绘制。

中点Bresenham算法的原理可用以下步骤描述：1）假设直线连接点A(x0, y0)和点B(x1, y1)。

2）计算直线斜率m = (y1-y0)/(x1-x0)。

3）设置初始值x=x0, y=y0。

4）计算决策参数P0 = 2*(y1-y0) - (x1-x0)。

5）循环执行以下步骤直至x达到x1:a) 如果P0<0，则选择点(x+1, y)，即决策参数P0 = P0 + 2*(y1-y0)。

b) 如果P0>=0，则选择点(x+1, y+1)，即决策参数P0 = P0 + 2*(y1-y0) - 2*(x1-x0)。

2. 斜率大于1的例题假设有一条直线连接点A(2, 5)和点B(7, 10)，斜率m = (10-5)/(7-2) = 1。

我们可以通过中点Bresenham算法来绘制这条直线，具体步骤如下：1）设定初始值 x=2, y=5；2）计算初始的决策参数P0 = 2*(10-5) - (7-2) = 10；3）根据决策参数P0的值来确定下一个点的位置：a) 当P0<0时，选择点(3, 5)，更新P0 = P0 + 10 = 20；b) 当P0>=0时，选择点(4, 6)，更新P0 = P0 + 10 - 10 = 20；c) 重复上述步骤直至x=7。

3. 结论通过上述例题的分析，我们可以看出中点Bresenham算法在斜率大于1的情况下同样适用，并且能够高效地绘制直线。

其原理简单易懂，应用广泛，是计算机图形学领域的重要算法之一。

《图形学》实验七：中点Bresenham算法画椭圆VC++6.0，OpenGL使⽤中点Bresenham算法画椭圆。

1 #include <gl/glut.h>23#define WIDTH 5004#define HEIGHT 5005#define OFFSET 15 //偏移量，偏移到原点6#define A 67#define B 589void Init() //其它初始化10 {11 glClearColor(1.0f,1.0f,1.0f,1.0f); //设置背景颜⾊，完全不透明12 glColor3f(1.0f,0.0f,0.0f); //设置画笔颜⾊1314 glMatrixMode(GL_PROJECTION);15 glLoadIdentity();16 gluOrtho2D(0.0, 30.0, 0.0, 30.0);17 glMatrixMode(GL_MODELVIEW);18 }1920void MidBresenhamEllipse(int a,int b) //中点Bresenham算法画椭圆21 {22int x,y;23float d1,d2;24 x = 0;y = b;25 d1=b*b+a*a*(-b+0.25);26 glPointSize(5); //设置画笔尺⼨2728 glBegin(GL_POINTS);29 glVertex2i(OFFSET+x,OFFSET+y);30 glVertex2i(OFFSET-x,OFFSET-y);31 glVertex2i(OFFSET-x,OFFSET+y);32 glVertex2i(OFFSET+x,OFFSET-y);33 glEnd();3435while(b*b*(x+1) < a*a*(y-0.5)){36if(d1<=0){37 d1+=b*b*(2*x+3);38 x++;39 }40else{41 d1+=b*b*(2*x+3)+a*a*(-2*y+2);42 x++;43 y--;44 }45 glBegin(GL_POINTS);46 glVertex2i(OFFSET+x,OFFSET+y);47 glVertex2i(OFFSET-x,OFFSET-y);48 glVertex2i(OFFSET-x,OFFSET+y);49 glVertex2i(OFFSET+x,OFFSET-y);50 glEnd();51 }//while上半部分52 d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;53while(y>0){54if(d2<=0){55 d2+=b*b*(2*x+2)+a*a*(-2*y+3);56 x++,y--;57 }58else{59 d2+=a*a*(-2*y+3);60 y--;61 }62 glBegin(GL_POINTS);63 glVertex2i(OFFSET+x,OFFSET+y);64 glVertex2i(OFFSET-x,OFFSET-y);65 glVertex2i(OFFSET-x,OFFSET+y);66 glVertex2i(OFFSET+x,OFFSET-y);67 glEnd();68 }69 }7071void Display()72 {73 glClear(GL_COLOR_BUFFER_BIT); //清空颜⾊堆栈7475 MidBresenhamEllipse(A,B); //画⼀个半径为8的椭圆7677 glFlush(); //清空缓冲区指令78 }7980int main(int argc,char** argv)81 {82 glutInit(&argc,argv);83 glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); //初始化显⽰模式84 glutInitWindowSize(WIDTH,HEIGHT); //初始化窗⼝⼤⼩85 glutInitWindowPosition(200,100); //初始化窗⼝出现位置86 glutCreateWindow("中点Bresenham画椭圆"); //初始化窗⼝标题8788 glutDisplayFunc(Display); //注册显⽰函数89 Init(); //其它初始化90 glutMainLoop(); //进⼊程序循环9192return0;93 }Freecode :。

Bresenham算法是计算机图形学典型的直线光栅化算法。

∙从另一个角度看直线光栅化显示算法的原理o由直线的斜率确定选择在x方向或y方向上每次递增（减）1个单位，另一变量的递增（减）量为0或1，它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。

∙1)Bresenham的基本原理o假定直线斜率k在0~1之间。

此时，只需考虑x方向每次递增1个单位，决定y方向每次递增0或1。

设直线当前点为(xi,y)直线当前光栅点为(xi,yi)则下一个直线的点应为(xi+1,y+k)下一个直线的光栅点或为右光栅点(xi+1,yi)（y方向递增量0）或为右上光栅点(xi+1,yi+1)（y方向递增量1）记直线与它垂直方向最近的下光栅点的误差为d，有：d=(y+k)–yi，且0≤d≤1当d<0.5：下一个象素应取右光栅点(xi+1,yi)当d≥0.5：下一个象素应取右上光栅点(xi+1,yi+1)如果直线的（起）端点在整数点上，误差项d的初值：d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即：d＝d + k。

一旦d≥1，就把它减去1，保证d的相对性，且在0-1之间。

令e=d-0.5，关于d的判别式和初值可简化成：e的初值e0= -0.5，增量亦为k;e<0时，取当前象素(xi,yi)的右方象素(xi+1,yi)；e>0时，取当前象素(xi,yi)的右上方象素(xi+1,yi+1)；e=0时，可任取上、下光栅点显示。

Bresenham算法的构思巧妙：它引入动态误差e，当x方向每次递增1个单位，可根据e 的符号决定y方向每次递增 0 或 1。

e<0，y方向不递增e>0，y方向递增1x方向每次递增1个单位，e = e + k因为e是相对量，所以当e>0时，表明e的计值将进入下一个参考点（上升一个光栅点），此时须：e = e - 1∙2)Bresenham算法的实施——Rogers 版o通过(0,0)的所求直线的斜率大于0.5，它与x=1直线的交点离y=1直线较近，离y=0直线较远，因此取光栅点(1,1)比(1,0)更逼近直线；o如果斜率小于0.5，则反之；o当斜率等于0.5，没有确定的选择标准，但本算法选择(1,1)（程序）▪//Bresenham's line resterization algorithm for the first octal.▪//The line end points are (xs,ys) and (xe,ye) assumed not equal.▪// Round is the integer function.▪// x,y, ∆x, ∆y are the integer, Error is the real.▪//initialize variables▪x=xs▪y=ys▪∆x = xe -xs▪∆y = ye -ys▪//initialize e to compensate for a nonzero intercept▪Error =∆y/∆x-0.5▪//begin the main loop▪for i=1 to ∆x▪ WritePixel (x, y, value)▪if (Error ≥0) then▪ y=y+1▪ Error = Error -1▪ end if▪ x=x+1▪ Error = Error +∆y/∆x▪next i▪finish∙3)整数Bresenham算法o上述Bresenham算法在计算直线斜率和误差项时要用到浮点运算和除法，采用整数算术运算和避免除法可以加快算法的速度。

Bresenham算法画圆bresenham画圆算法bresenham画圆算法中点画圆算法在⼀个⽅向上取单位间隔，在另⼀个⽅向的取值由两种可能取值的中点离圆的远近⽽定。

实际处理中，⽤决策变量的符号来确定象素点的选择，因此算法效率较⾼。

⼀、中点画圆算法描述设要显⽰圆的圆⼼在原点(0，0)，半径为R，起点在(0，R)处，终点在(，)处，顺时针⽣成⼋分之⼀圆，利⽤对称性扫描转换全部圆。

为了应⽤中点画圆法，我们定义⼀个圆函数F(x，y)=x2+y2-R2 (2－19)任何点(x，y)的相对位置可由圆函数的符号来检测：F(x，y) <0点(x，y)位于数学圆内=0点(x，y)位于数学圆上>0点(x，y)位于数学圆外(2－20)如下图所⽰，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针⽣成圆，那么下⼀点只能取正右⽅的点E(xi+1，yi)或右下⽅的点SE(xi+1，yi-1)两者之⼀。

中点画线算法假设M是E和SE的中点，即，则：1、当F(M)<0时，M在圆内(圆弧A)，这说明点E距离圆更近，应取点E作为下⼀象素点；2、当F(M)>0时，M在圆外(圆弧B)，表明SE点离圆更近，应取SE点；3、当F(M)=0时，在E点与SE点之中随便取⼀个即可，我们约定取SE点。

⼆、中点画圆算法思想因此，我们⽤中点M的圆函数作为决策变量d i，同时⽤增量法来迭代计算下⼀个中点M的决策变量d i+1。

(2－21)下⾯分两种情况来讨论在迭代计算中决策变量d i+1的推导。

1、见图（a），若d i <0，则选择E点，接着下⼀个中点就是，这时新的决策变量为：(2－22)（a）(di<0) 中点画线算法式(2－22)减去(2－21)得：d i+1=d i+2x i+3(2－23)2、见图（b），若di≥0，则选择SE点，接着下⼀个中点就是，这时新的决策变量为：(2－24)（b）(d i ≥0) 中点画线算法式(2－24)减去(2－21)得：d i+1=d i+2(x i-y i)+5(2－25)我们利⽤递推迭代计算这⼋分之⼀圆弧上的每个点，每次迭代需要两步处理：（1）⽤前⼀次迭代算出的决策变量的符号来决定本次选择的点。

Bresenham算法1.直线光栅化直线光栅化是指用像素点来模拟直线. 比如下图中用蓝色的像素点来模拟红色的直线. 图中坐标系是显示器上的坐标系: x轴向右, y轴向下.设deltaX = endX –startX, deltaY = endY –startY. 那么斜率为k = deltaY / deltaX. 我们先考虑简单的情况: 当0 < k < 1即直线更贴近x轴. 在这种情况下deltaY < deltaX, 所以在光栅化的过程中, 在y轴上描的点比在x轴上描点少. 那么就有一个很直观的光栅化算法:line_bresenham(startX, startY, endX, endY){deltaX = endX - startX;deltaY = endY - startY;k = deltaY / deltaX;for (x = startX, y = startY; x <= endX; ++x){if (满足一定条件){++y;}drawPixel(x, y);}}2.基于斜率/ 距离的两个简单直线光栅化算法好了，貌似很简单, 就剩一个问题: “满足一定条件”是什么? 可以用斜率判断, 也可以用上图中直线与光栅线交点 (红点) 与光栅点 (蓝点)的距离来判断. 继续用伪代码讲解:// 算法1: 用斜率判断void line_bresenham_k(startX, startY, endX, endY){deltaX = endX - startX;deltaY = endY - startY;k = deltaY / deltaX;for (x = startX, y = startY; x <= endX; ++x){if (x - startX != 0){currentK = (y - startY) / (x - startX); // 计算当前斜率if (currentK < k) // 如果当前斜率< k, 则增加y坐标{++y}}drawPixel(x, y);}}// 算法2: 用距离判断. 计算直线与光栅线交点y坐标我们需要用到// 直线方程y = k (x - startX) + startYline_bresenham_dist(startX, startY, endX, endY){deltaX = endX - startX;deltaY = endY - startY;k = deltaY / deltaX;for (x = startX, y = startY; x <= endX; ++x){// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离ptY = k * (x - startX) + startY;dist = ptY - y;// 如果距离> 0.5或者< -0.5,需要增加y以将距离的绝对值控制在0.5之类if (dist > 0.5 || dist < -0.5){++y;}drawPixel(x, y);}}3.消灭浮点数以上都是很直观的算法, 下面不直观的来了–上面的算法都需要在循环体内执行乘法, 准确的说, 是进行浮点数的乘法. 我们怎么能减少这些浮点数的乘法开销呢? 以基于距离的算法2为例: 首先, k是一个浮点数, 0.5也是浮点数. 我们可以通过将这些表达式都乘以2 * deltaX (整数) 来解决浮点数的问题. 伪代码:// 算法3: 在算法2的基础上消灭浮点数!line_bresenham_dist(startX, startY, endX, endY){deltaX = endX - startX;deltaY = endY - startY;for (x = startX, y = startY; x <= endX; ++x){// 计算直线与光栅线交点的y坐标, 以及与光栅点的距离ptY1 = deltaY * (x - startX) + startY * deltaX;dist1 = ptY1 - y * deltaX;dist1 = dist1 << 1; // dist1 = dist1 * 2// 如果距离> 0.5或者< -0.5, 说明我们需要增加y以// 将距离的绝对值控制在0.5之类if (dist1 > deltaX || dist < -deltaX){++y;}drawPixel(x, y);}}4.消灭乘法圆满解决浮点数运算问题! 不过…乘法运算还在. 消灭乘法问题的办法比较不直观, 让我们想一想: 还有什么办法能简化运算. 直线方程已经不能再简化, 所以唯一的突破口就是能不能利用递推，用上一次循环的计算结果推导下一次循环的计算结果.首先我们来看看在算法2的基础上 (因为算法2计算红点蓝点之间的距离, 比较直观), 怎么通过第n – 1次循环计算出的dist值 (设为d1) 来推导出第n次循环的dist值 (设为d2). 先回顾一下: dist = 直线与光栅线交点的y坐标–相应光栅点的y坐标. 我们从几何上直观地考虑: 在第n次循环中, 我们先根据上一次循环所计算出来的d1, 暂时令d2 = d1 + k（x每次递增1，所以直线方程，相当于每次增加一个K）, 因为我们要保证-0.5 < d2 < 0.5, 而d1 + k满足d1 + k > –0.5, 所以我们只需要考虑当d1 + k > 0.5时, 我们需要将光栅点y坐标增加1, 并且将d2减去1. 显然, 设y1是第n – 1次循环中光栅点的y坐标, y2是第n次循环中光栅点的y坐标. 我们有1) d2 = d1 + k – (y2 – y1)2) 当d1 + k > 0.5时y2 = y1 + 1, 否则y2 = y1我们已经能根据上面的两个关系式写出算法, 不过为了消除乘法和浮点数, 我们将这两个关系式两端同时乘以2 * deltaX, 并且设e = 2 * deltaX * d, 则我们有：3) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)4) 当e1 + 2 * deltaY > deltaX时y2 = y1 + 1, 否则y2 = y1终于, 没有了乘法 (2 * deltaY在循环体外计算且被简化为左移一位的运算), 没有了浮点数, 根据关系式3) 和 4), 写出算法:// 算法4: 在算法2, 3的基础上利用递推消灭乘法和浮点数!line_bresenham(startX, startY, endX, endY){deltaX = endX - startX;deltaY = endY - startY;e = 0;deltaX2 = deltaX << 1;deltaY2 = deltaY << 1;drawPixel(startX, startY);for (x = startX + 1, y = startY; x <= endX; ++x){// 关系式3) e2 = e1 + 2 * deltaY –2 * deltaX * (y2 –y1)// 关系式4) 当e2 + 2 * deltaY > deltaX时y2 = y1 + 1, 否则y2 = y1e += deltaY2;if (e > deltaX){e -= deltaX2;++y;}drawPixel(x, y);}}上面递推关系的推导过程是从图形上“直观”地分析得来的, 但是不严密. 我们能不能形式化地证明关系式1), 2), 3), 4)呢? 因为关系式3), 4)和1), 2)能互相推导, 我们只证明3), 4)如下:在算法3的基础上设第n –1次循环计算出的dist1值为e1, 对应的y值为y1, 第n次循环计算出的dist1值为e2, 对应的y值为y2. 根据算法3,dist1 = 2 * deltaY * (x –startX) + 2 * startY * deltaX –2 * y * deltaX, 则e2 – e1= 2 * deltaY * (x – startX) + 2 * startY * deltaX – 2 * y2 * deltaX – [2 * deltaY * (x – 1 – startX) + 2 * startY * deltaX – 2 * y1 * deltaX ]= – 2 * y2 * deltaX + 2 * deltaY + 2 * y1 * deltaX= 2 * deltaY – 2 * deltaX * (y2 – y1)所以e2 = e1 + deltaY –deltaX * (y2 –y1). 所以我们有关系式1) e2 = e1 + 2 * deltaY – 2 * deltaX * (y2 – y1)2) –deltaX < e1 < deltaX3) –deltaX < e2 < deltaX4) y2 –y1 = 0 或者1我们根据e1 + 2 * deltaY的取值范围进行讨论. 首先, 因为不等式6), 我们有2 * deltaY – deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX情况1: 如果2 * deltaY –deltaX < e1 + 2 * deltaY < deltaX, 则2 * deltaY – deltaX – 2 * deltaX * (y2 – y1) < e2 < deltaX– 2 * deltaX * (y2 – y1)反证: 若y2 –y1 = 1, 则2 * deltaY –deltaX –2 * deltaX < e2 < deltaX –2 * deltaX = -deltaX, 所以y2 –y1 = 1不成立. 即情况1中y2 = y1.情况2: 如果deltaX < e1 + 2 * deltaY < 2 * deltaY + deltaX, 则deltaX – 2 * deltaX * (y2 – y1) < e2 < 2 * deltaY + deltaX – 2 * deltaX * (y2 – y1)反证: 若y2 –y1 = 0, 则deltaX < e2 < 2 * deltaY + deltaX 所以y2 –y1 = 0不成立. 即情况2中y2 = y1 + 1.打了这么多字, 累…以上就是当0 < k < 1的情况, 剩余几种情况(k > 1, –1 < k < 0, k <–1. 不要挑剔我不用“>=”这种符号…) 都可以通过简单的x, y交换以及正负交换来搞定.。

中点bresenham算法中点bresenham算法原理由Bresenham提出的直线生成算法的基本原理是，每次在最大位移方向上走一步，而另一个方向是走步还是不走步取决于误差项的判别。

这时直线将平面分成三个区域:对于直线上的点，F(x,y)=0;对于直线上方的点，F(x,y)>0;对于直线下方的点,F(x,y)<0。

首先假设0≤k≤1，由于x是最大位移方向，因此每次在x方向上加1，y方向上或加1 或加0。

假定当前点是P(xi,yi),则下一个点在pu(xi+1,yi+1)与pd(xi+1,yi)中选一。

以M表示pu和pd的终点即M(xi+1,yi+0.5)。

又设Q是理想直线与垂直线x=xi+1的交点。

显然,若M在Q 的下方，则pu(xi+1,yi+1)离直线近，应取为下一个像素，否则应取Pd（xi+1,yi）。

所以如前所述，欲判断Q在M的上方还是下方，只要把M代入F(x,y),并判断它的符号即可。

如上构造判别式，当di<0时，M在直线下方，故应取Pu。

当di>0时，应取正右方的Pd。

当di=0时，两者一样合适，可以随便取一个。

所以现在根据上面的判别式对误差项进行递推。

当di<0时，取右上方像素Pu,欲判断再下一个像素应该取那个应计算此时di的增量为1-k。

当di≥0时，取右上方像素Pd,欲判断再下一个像素应该取那个应计算下面进行di的初值计算。

显然直线的第一个像素P(x0,y0)在直线上,因此响应的di的初始值计算如下但是这其中仍然有小数,由于我们使用的只是di的符号，因此可以用2di△x摆脱小数Bresenham算法对任意斜率的直线段具有通用性，对于斜率为整且大于1的直线段，只需要交换x和y之间的规则。

对于负斜率，除了一个坐标递减而另一个坐标地政外，其余程序是类似的。

附页:一实验分析要求和算法如上表格所示二核心算法1．CTestView.h文件// TestView.h : interface of the CTestView class/////////////////////////////////////////////////////////////////////////////#if !defined(AFX_TESTVIEW_H__A75FDCFB_621C_4E38_A154_C344803E6372__INCLUDED_) #define AFX_TESTVIEW_H__A75FDCFB_621C_4E38_A154_C344803E6372__INCLUDED_#if _MSC_VER > 1000#pragma once#endif // _MSC_VER > 1000#include "InputDlg.h"//对话框头文件class CTestView : public CView{protected: // create from serialization onlyCTestView();DECLARE_DYNCREA TE(CTestView)// Attributespublic:CTestDoc* GetDocument();// Operationspublic:void Mbline();//直线中点Bresenham函数// Overrides// ClassWizard generated virtual function overrides//{{AFX_VIRTUAL(CTestView)public:virtual void OnDraw(CDC* pDC); // overridden to draw this viewvirtual BOOL PreCreateWindow(CREATESTRUCT& cs);protected:virtual BOOL OnPreparePrinting(CPrintInfo* pInfo);virtual void OnBeginPrinting(CDC* pDC, CPrintInfo* pInfo);virtual void OnEndPrinting(CDC* pDC, CPrintInfo* pInfo);//}}AFX_VIRTUAL// Implementationpublic:virtual ~CTestView();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected:double x0, y0, x1, y1;//直线的起点和终点坐标// Generated message map functionsprotected://{{AFX_MSG(CTestView)afx_msg void OnMENUMbline();//}}AFX_MSGDECLARE_MESSAGE_MAP()};#ifndef _DEBUG // debug version in TestView.cppinline CTestDoc* CTestView::GetDocument(){ return (CTestDoc*)m_pDocument; }#endif///////////////////////////////////////////////////////////////////////////////{{AFX_INSERT_LOCA TION}}// Microsoft Visual C++ will insert additional declarations immediately before the previous line.#endif // !defined(AFX_TESTVIEW_H__A75FDCFB_621C_4E38_A154_C344803E6372__INCLUDED_) 2．CTestView. cpp文件// TestView.cpp : implementation of the CTestView class#include "stdafx.h"#include "Test.h"#include "TestDoc.h"#include "TestView.h"#define ROUND(a) int(a+0.5) //四舍五入#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif/////////////////////////////////////////////////////////////////////////////// CTestViewIMPLEMENT_DYNCREATE(CTestView, CView)BEGIN_MESSAGE_MAP(CTestView, CView)//{{AFX_MSG_MAP(CTestView)ON_COMMAND(ID_MENUMbline, OnMENUMbline)//}}AFX_MSG_MAP// Standard printing commandsON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)END_MESSAGE_MAP()/////////////////////////////////////////////////////////////////////////////// CTestView construction/destructionCTestView::CTestView(){// TODO: add construction code here}CTestView::~CTestView(){}BOOL CTestView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// the CREA TESTRUCT csreturn CView::PreCreateWindow(cs);}/////////////////////////////////////////////////////////////////////////////// CTestView drawingvoid CTestView::OnDraw(CDC* pDC){CTestDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);// TODO: add draw code for native data here}/////////////////////////////////////////////////////////////////////////////// CTestView printingBOOL CTestView::OnPreparePrinting(CPrintInfo* pInfo){// default preparationreturn DoPreparePrinting(pInfo);}void CTestView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: add extra initialization before printing}void CTestView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) {// TODO: add cleanup after printing}/////////////////////////////////////////////////////////////////////////////// CTestView diagnostics#ifdef _DEBUGvoid CTestView::AssertValid() const{CView::AssertValid();}void CTestView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CTestDoc* CTestView::GetDocument() // non-debug version is inline{ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CTestDoc)));return (CTestDoc*)m_pDocument;}#endif //_DEBUG/////////////////////////////////////////////////////////////////////////////// CTestView message handlersvoid CTestView::Mbline() //直线中点Bresenham函数{CClientDC dc(this);COLORREF rgb=RGB(0,0,255); //定义直线颜色为蓝色double x,y,d,k;x=x0;y=y0;k=(y1-y0)/(x1-x0);d=0.5-k;for(x=x0;x<=x1;x++){dc.SetPixel(ROUND(x),ROUND(y),rgb);if(d<0){y++;d+=1-k;}elsed-=k;}}void CTestView::OnMENUMbline()//菜单函数{// TODO: Add your command handler code hereInputDlg dlg;if(dlg.DoModal()==IDOK){x0=dlg.m_x0;y0=dlg.m_y0;x1=dlg.m_x1;y1=dlg.m_y1;}AfxGetMainWnd()->SetWindowText("基本图形扫描转换:Mbline");RedrawWindow();Mbline();}四结果截图五小结通过本次实验的设计,让我对计算机图形图像处理有了更加深刻的理解,学会了这种绘制直线的算法Bresenham。

bresenham算法画直线例题摘要：1.介绍Bresenham算法2.Bresenham算法的原理3.使用Bresenham算法画直线的步骤4.Bresenham算法的应用示例5.总结Bresenham算法在计算机图形学中的重要性正文：Bresenham算法是一种计算几何中用于画直线的算法，由英国计算机科学家Jack Bresenham于1965年提出。

该算法广泛应用于计算机图形学、视频游戏和各种嵌入式系统。

Bresenham算法的核心思想是使用简单的加法和减法运算，以及位运算来计算直线上的每个点的坐标，从而实现画直线的目标。

Bresenham算法的原理基于对直线方程y = mx + b的观察。

当m为正数时，直线是从左下到右上的；当m为负数时，直线是从左上到右下的。

根据这个特点，Bresenham算法将画直线的过程分为两个阶段：第一阶段是向上扫描，第二阶段是向下扫描。

在每一阶段，算法仅使用简单的加法和减法运算来更新当前点的坐标。

使用Bresenham算法画直线的步骤如下：1.初始化x和y坐标，以及直线的斜率m和截距b。

2.判断m的正负性。

如果m为正，进入第一阶段；如果m为负，进入第二阶段。

3.在第一阶段，每次将y坐标加b，然后将x坐标加m，直到x坐标达到最大值或y坐标达到最小值。

4.在第二阶段，每次将y坐标加b，然后将x坐标减m，直到x坐标达到最小值或y坐标达到最大值。

5.如果需要，可以将画直线的过程进行迭代，以获得更高的精度。

Bresenham算法在计算机图形学中具有重要应用价值。

它不仅计算简单、速度快，而且可以在各种不同的硬件平台上实现。

下面给出一个使用Bresenham算法画直线的示例：```pythondef bresenham_line(x0, y0, x1, y1):m = (y1 - y0) / (x1 - x0)b = y0 - m * x0x = x0y = y0e = 0if m < 0:y = y0while x < x1:put_pixel(x, y)e = e + abs(m)if e > abs(b):x = x + 1e = e - abs(m)y = y + 1else:x = x0while y < y1:put_pixel(x, y)e = e + abs(m)if e > abs(b):y = y + 1e = e - abs(m)x = x + 1bresenham_line(0, 0, 10, 5)```总之，Bresenham算法是一种简单而有效的计算几何画直线方法。

一、概述在计算机视觉和图像处理领域，检测两点所确定直线上的像素是一个常见的问题。

这个问题在很多应用中都有实际的意义，比如在车道线检测、边缘检测、图像配准等领域都有广泛的应用。

如何高效准确地检测两点所确定的直线上的像素，是一个具有挑战性的问题。

二、问题描述假设给定一幅图像和图像中的两个点A和B，现在要求检测出直线AB 上的像素。

这个问题可以被抽象为一个线段上的离散点检测问题。

在实际应用中，图像是由像素组成的离散点集合，直线上的像素也是被离散的。

我们需要通过一定的算法来检测直线上的像素。

三、常见方法在计算机视觉领域，有一些常见的方法来检测直线上的像素。

下面介绍几种常见的方法：1. Bresenham算法Bresenham算法是一种经典的离散直线绘制算法，它可以高效地计算出直线上的像素。

该算法通过计算直线的斜率来确定水平和竖直方向上的像素点，从而绘制出直线。

Bresenham算法在计算效率和准确性上都有较好的表现，因此在实际应用中被广泛采用。

2. 数值方法除了Bresenham算法之外，还有一些基于数值计算的方法可以用来检测直线上的像素。

这些方法通常是通过拟合直线方程，然后计算其上的离散点。

虽然这些方法在理论上可以计算出直线上的像素，但在实际应用中往往会受到噪声和采样等因素的干扰，导致结果不够稳定和准确。

3. 图像处理方法另外，还有一些基于图像处理的方法可以用来检测直线上的像素。

比如基于边缘检测的方法，可以通过检测图像中的边缘来得到直线上的像素。

这类方法通常需要预先对图像进行边缘检测，然后根据图像中的边缘来确定直线上的像素点。

四、改进方法虽然上述方法在一定程度上可以用来检测直线上的像素，但仍然存在一些问题。

比如Bresenham算法只能用于整数像素点的计算，对于浮点型像素的计算就比较困难。

而数值方法对采样点的选择非常敏感，容易受到噪声的干扰。

图像处理方法则需要进行边缘检测等预处理步骤，增加了计算的复杂度。

Bresenham画圆算法与中点画圆法Bresenham画圆算法不失⼀般性，假设圆的圆⼼位于坐标原点（如果圆⼼不在原点，可以通过坐标平移使其与原点重合），半径为R。

以原点为圆⼼的圆C有四条对称轴：x = 0, y = 0, x = y和x = -y。

若已知圆弧上⼀点P1＝C（x, y），利⽤其对称性便可以得到关于四条对称轴的其它7个点，即： P2＝C（x,－y）， P3＝C（－x, y）， P4＝C（－x,－y）， P5＝C（y，x）， P6＝C（－y，x）， P7＝C（y，－x）， P8＝C（－y，－x）。

这种性质称为⼋对称性。

因此，只要扫描转换⼋分之⼀圆弧，就可以通过圆弧的⼋对称性得到整个圆。

【Bresenham算法】简单图形的扫描转换常⽤算法是Bresenham算法。

它的思想在于⽤误差量来衡量点选取的逼近程度。

其过程如下：以平⾯⼆维图形的扫描转换为例，设要画的图形⽅程为F(x, y)=0，要画的区域为[x0, x]（不妨设x⽅向是最⼤位移⽅向，即△x > △y），则Ｆ(x,y) 也是⼀个误差度量函数，我们拿离散的点值代⼊如果⼤于0则正向偏离，否则负向偏离，等于0的情况⽐较少，它表⽰的是不偏离即恰好与真实点重合。

既然x是最⼤位移⽅向，那每次对x⾃增1，相应的y可以选择不增或增1(或-1，具体问题具体分析)，选择的⽅法就是d = F(x + 1, y ± 0.5)的正负情况进⾏判断从⽽选择y的值。

实际情况中还要考虑到浮点数的计算问题，因为基本的图形扫描转换算法最好能够硬件实现，所以摆脱浮点数是最好的，常⽤的⽅法是对d 进⾏递推，⽽不是直接由Ｆ(x,y)给出(直接给出速度会慢)。

【圆的扫描转换算法】以画圆为例，给出圆⼼的坐标(0, 0)和半径Ｒ，求圆图像的最佳逼近点。

圆是中⼼对称的特殊图形，所以可以将圆⼋等分，则只须对⼋分之⼀圆孤求解，其它圆孤可以由对称变换得到，我们求的⼋分之⼀圆孤为(0, R) -(R√2,R√2)，可知最⼤位移⽅向是x⽅向，x0 = 0, y0 = R，每次对x⾃增，然后判断y是否减1，直到x >= y为⽌(从点(0, R)到圆的⼋分之⼀处就有这种情况)。

写这篇文章的原因是因为发觉网络上太少关于计算机图形学算法的资料了，所以我希望从我这次完成计算机图形学大作业的例子给一些也正在学的人一些小小的帮助，即使不是些很高深的问题，但我更觉得我需要做的是扫盲。

当然我写的也不是教程，只是针对一道题目而讨论。

题目：图元扫描转换算法改进：实现改进的画线算法(DDA或Bresenham)，使得线段无论从哪个端点开始画，算法求出的象素点都是相同的(即与方向无关)。

(要求：交算法说明；源程序及详细注释；程序输出每一个象素点坐标)另外一个题目可能没有明确说到但是我们做的时候要按照的规定是：如果开始是起点A，终点B，你的改进算法是应该以B为起点，A为终点，但不能在程序中又把A变为起点，B为终点。

我手头上得到的一个Bresenham算法如下：Bresenham_line（int x1 ,int y1,int x2 ,int y）{ int dx,dy,s1,s2,temp,interchange=0,p,i;float x,y;dx = abs(x2 – x1); dy = abs(y2 – y1);s1 = sign(x2 – x1); s2 = sign(y2 – y1); /*决定方向*/x = x1 + 0.5*s1; y = y1 + 0.5*s2;if（dy > dx）{ /*决定m值*/temp = dx; dx = dy; dy = temp; /*dx为增长快的边*/interchange = 1;} /*在2,3,6,7区间*/p = 2 * dy – dx;for( i = 1; i <= dx; i++) {setPixel(int(x), int(y));if( p>0 ){if(interchange)x = x + s1; /*把xi当成yI */elsey = y +s2;p = p – 2 * dx;}if(interchange) /*当pi<=0，yi不变*/y = y + s2; /*把yi当成xi*/elsex = x + s1;p = p + 2 * dy;}/*for*/}/* Bresenham_line */(因为以上是从PPT上直接copy下来的代码，在编译的时候会因为很多符号问题而产生错误，如果有意想用者请将错误的符号先改正，因为此算法只作原理参考，所以我就不再改正了，呵呵，我还是很懒的) 从上面的算法看，可自己验证出，从(0,0)点画直线到(3,5)点和从(3,5)点画直线到(0,0)中间的像素点坐标值是有区别的，所以上面的Bresenham算法是跟方向有关的。