下载文档原格式
任意斜率bresenham算法Bresenham算法是一种经典的计算机图形学算法，用于在计算机屏幕上绘制直线。
它的主要特点是高效快速，并且不需要浮点数运算。
本文将介绍任意斜率下的Bresenham算法原理及实现方法。
一、原理介绍Bresenham算法的核心思想是利用整数计算代替浮点数计算，从而提高计算速度。
算法的基本原理是通过在直线路径上的每个像素点处做决策，选择最接近直线路径的像素点来绘制线段。
二、实现步骤1. 输入起点坐标(x0, y0)和终点坐标(x1, y1)；2. 计算斜率的绝对值的倒数：dx = x1 - x0，dy = y1 - y0，abs(dx) > abs(dy)时，倒数为1/abs(dx)，否则为1/abs(dy)；3. 初始化误差项：e = -1/2；4. 初始化绘制点坐标：x = x0，y = y0；5. 进行循环，直到绘制到终点坐标：- 绘制当前点(x, y)；- 更新误差项：e = e + abs(dy/dx)；- 若误差项大于等于1，则纵坐标y加1，并更新误差项：e = e - 1；- 横坐标x加1；6. 绘制终点坐标。
三、代码实现下面是使用C语言实现任意斜率Bresenham算法的代码示例：```c#include <stdio.h>void drawLine(int x0, int y0, int x1, int y1) {int dx = x1 - x0;int dy = y1 - y0;int stepx = (dx > 0) ? 1 : -1;int stepy = (dy > 0) ? 1 : -1;dx = abs(dx);dy = abs(dy);int e = 0;int x = x0;int y = y0;if (dx > dy) {for (int i = 0; i <= dx; i++) {// 绘制当前点(x, y)if (e >= 0) {y += stepy;e -= dx;}x += stepx;e += dy;}} else {for (int i = 0; i <= dy; i++) { // 绘制当前点(x, y)if (e >= 0) {x += stepx;e -= dy;}y += stepy;e += dx;}}}int main() {int x0 = 0, y0 = 0;int x1 = 10, y1 = 5;drawLine(x0, y0, x1, y1);return 0;}```四、实例分析以起点坐标(0, 0)和终点坐标(10, 5)为例，通过Bresenham算法计算得到的直线路径如下图所示：```(0,0) (1,0) (2,1) (3,1) (4,2) (5,2) (6,3) (7,3) (8,4) (9,4) (10,5)```五、总结Bresenham算法是一种高效快速绘制直线的算法，通过利用整数计算代替浮点数计算，避免了浮点数运算的开销。
分别解释直线生成算法dda法,中点画线法和
bresenham法的基本原理
直线生成算法DDA法、中点画线法和Bresenham法的基本原理如下：
1. DDA直线生成算法：基于差分运算的直线生成算法。
通过将直线分割成
若干个相邻的像素点，并按照一定的步长进行逐点绘制，实现直线的绘制。
算法主要涉及到线性插值的思想，即根据已知的两点坐标，通过计算它们之间的差值，然后根据这个差值和步长来确定新的像素点的位置。
2. 中点画线法：一种线段绘制算法，从线段的起点和终点出发，按照一定的规则向终点逐步逼近，并在途中以控制变量的方式得出每个像素点的坐标，从而绘制出所需的线条。
具体实现中，通过计算线段斜率的变化情况，分为斜率小于1和大于等于1两种情况，并采用Bresenham的对称性原理，以中点的颜色来控制每个像素点的生长方向，从而获得较高的绘制效率和图像质量表现。
3. Bresenham算法：通过一系列的迭代来确定一个像素点是否应该被绘制。
对于一条从点(x1,y1)到点(x2,y2)的直线，首先计算出斜率k。
然后，通过比较每个像素点的y值到直线上的y值，来决定哪些像素点应该被绘制。
当斜率k大于等于1时，在x方向上迭代，而对于每个x值，计算出y值，并将像素点(x,y)绘制。
当斜率k小于1时，在y方向上迭代，而对于每个y值，计算出x值，并将像素点(x,y)绘制。
以上内容仅供参考，如需更多信息，建议查阅相关文献或咨询数学专业人士。
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圆生成算法是一种简单而有效的计算机图形学算法。
它可以快速地绘制出圆形，并且可以轻松地扩展到其他形状。
尽管这个算法已经有几十年的历史了，但它仍然是计算机图形学中最常用的算法之一，并且在许多其他领域也得到了广泛应用。
直线的Bresenham算法本算法由Bresenham在1965年提出。
设直线从起点（x1, y1）到终点（x2, y2）。
直线可表示为方程y=mx+b。
其中b = y1 - m * x1,我们的讨论先将直线方向限于1a象限（图2.1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即xi+1=xi+1而y的相应增加应当小于1。
为了光栅化，yi+1只可能选择如下两种位置之一（图2.1.2）。
图2.1.2 yi+1的位置选择yi-1=yi 或者yi+1=yi+1选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。
计算式为：y=m(xi+1)+b (2.1.1)d1=y-yi (2.1.2)d2=yi+1-y (2.1.3)如果d1-d2>0，则yi+1=yi+1，否则yi+1=yi。
因此算法的关键在于简便地求出d1-d2的符号。
将式（2.1.1）、（2.1.2）、（2.1.3）代入d1-d2，得用dx乘等式两边，并以Pi=dx(d1-d2)代入上述等式，得Pi=2xidy-2yidx+2dy+dx(2b-1) (2.1.4)d1-d2是我们用以判断符号的误差。
由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。
Pi+1为：Pi+1=Pi+2dy-2dx(yi+1-yi) (2.1.5)误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, yi而得到：P1=2dy-dx综述上面的推导，第1a象限内的直线Bresenham算法思想如下：1、画点(x1, y2); dx=x2-x1; dy=y2-y1；计算误差初值P1=2dy-dx; i=1；2、求直线的下一点位置：xi+1=xi+1；if Pi>0 则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1, yi-1）；4、求下一个误差Pi+1；if Pi>0 则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1; if i<dx+1则转2；否则end。
Bresenham算法1 算法原理基本原理从某处摘得：设直线⽅程为y i+1=y i+k(x i+1-x i)+k。
假设列坐标象素已经确定为x i，其⾏坐标为y i。
那么下⼀个象素的列坐标为x i＋1，⽽⾏坐标要么为y i，要么递增1为y i＋1。
是否增1取决于误差项d的值。
误差项d的初值d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。
⼀旦d≥1，就把它减去1，这样保证d在0、1之间。
当d≥0.5时，直线与垂线x=x i＋1交点最接近于当前象素(x i，y i)的右上⽅象素(x i＋1，y i＋1)；⽽当d<0.5时，更接近于右⽅象素(x i＋1，y i)。
为⽅便计算，令e＝d－0.5，e的初值为－0.5，增量为k。
当e≥0时，取当前象素(x i，y i)的右上⽅象素(x i＋1，y i＋1)；⽽当e<0时，取(x i，y i)右⽅象素(x i＋1，y i)。
由于显⽰直线的像素点只能取整数值坐标,可以假设直线上第i个像素点的坐标为(X i,Y i),它是直线上点(X i,Y i)最佳近似,并且X i=X i(假设m<1),如下图所⽰.那么直线上下⼀个像素点的可能位置是(X i+1,Y i)或者(X i+1,Y i+1).由图可知：在x=X i+1处，直线上的点y的值是：y=m(X i+1)+b，该点离像素点(X i+1,Y i)和像素点(X i+1,Y i+1)的距离分别为d1和d2。
d1 = Y - Y i = m(X i+1)+b - Y i; (1) d2 = (Y i+1) - Y = (Y i+1) - m(X i+1) - b; (2) 两个距离的差是： d1-d2 = 2m(X i+1) - 2Y i + 2b -1; (3) 对于公式(3)： a：当此值为正时，d1>d2,说明直线上理论点离(X i+1,Y i+1)像素较近，下⼀个像素点应取(X i+1,Y i+1)； b：当此值为负时，d1<d2,说明直线上理论点离(X i+1,Y i)像素较近，下⼀个像素点赢取(X i+1,Y i)； c：当此值为零时，d1=d2,说明直线上理论点离上、下两个像素点的距离相等，取那个点都⾏，假设算法规定这种情况下取(X i+1,Y i+1)作为下⼀个像素点。
生成圆的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）根据得到的坐标渲染圆的边缘。
画圆形（Bresenham算法）下⾯先简要介绍常⽤的画圆算法（Bresenham算法），然后再具体阐述笔者对该算法的改进。
⼀个圆，如果画出了圆上的某⼀点，那么可以利⽤对称性计算余下的七段圆弧：Plot(x，y)，Plot(y，x)，Plot(y，-x)，Plot(x，-y)，Plot(-x，-y)，Plot(-y，-x)，Plot(-y，x)，Plot(-x，y)。
1、Bresenham 画圆算法。
Bresenham算法的主要思想是：以坐标原点（0，0）为圆⼼的圆可以通过0度到45°的弧计算得到，即x从0增加到半径，然后利⽤对称性计算余下的七段圆弧。
当x从0增加到时，y从R递减到。
设圆的半径为R，则圆的⽅程为：f(x，y)＝(x+1)2+y2-R2＝0 (1)假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi，yi)，根据第⼆卦限1/8圆的⾛向，下⼀列（x=xi+1列）中最接近圆弧的像素只能在P的正右⽅点H(xi+1，yi)或右下⽅点L(xi+1，yi-1)中选择，如图1所⽰。
Bresenham画圆算法采⽤点T(x，y)到圆⼼的距离平⽅与半径平⽅之差D(T)作为选择标准，即D(T)=(x+1)2+y2-R2 (2)通过⽐较H、L两点各⾃对实圆弧上点的距离⼤⼩，即根据误差⼤⼩来选取，具有最⼩误差的点为绘制点。
根据公式(2)得：对H(xi+1，yi)点有：D(H)=(xi+1)2+yi2-R2；对L(xi+1，yi-1)点有：D(L)=(xi+1)2+(yi-1)2-R2；根据Bresenham画圆算法，则选择的标准是：如果|D(H)|<|D(L)|，那么下⼀点选取H(xi+1，yi)；如果|D(H)|>|D(L)|，那么下⼀点选取L(xi+1，yi-1)；如果|D(H)|=|D(L)|，那么下⼀点可以取L(xi+1，yi-1)，也可以选取H(xi+1，yi)，我们约定选取H(xi+1，yi)。
任意斜率bresenham算法Bresenham算法是一种用于计算线段上像素点的算法，它的特点是具有高效和简单的特点，特别适合在计算机图形学中使用。
它可以根据给定的斜率，通过递增的方式计算出线段上的所有像素点。
本文将详细介绍Bresenham算法的原理和具体实现步骤。
一、Bresenham算法的原理Bresenham算法的核心思想是通过递增的方式计算出线段上的所有像素点，以实现高效的绘制线段的目的。
它基于以下两个关键观察：1. 如果直线斜率大于1，则将直线沿y轴方向递增，否则沿x轴方向递增。
2. 对于每个递增的步骤，根据当前像素点的位置和理想的线段位置之间的距离，选择最接近理想位置的像素点。
二、Bresenham算法的实现步骤Bresenham算法的实现步骤如下：1. 根据起点和终点的坐标，计算出线段的斜率。
如果斜率大于1，则将直线沿y轴方向递增，否则沿x轴方向递增。
2. 根据起点的坐标，计算出第一个像素点的位置，并将其绘制出来。
3. 计算出理想位置和当前像素点位置之间的距离，并记录下来。
4. 根据距离的大小，判断下一个像素点的位置。
如果距离小于等于0.5，则选择当前像素点的下一个位置作为下一个像素点；否则选择当前像素点的下一个位置的上方或右方作为下一个像素点。
5. 重复步骤4，直到绘制到终点的像素点为止。
三、Bresenham算法的优势相比于其他绘制线段的算法，Bresenham算法具有以下优势：1. 算法简单：Bresenham算法只需要进行简单的递增和判断操作，而没有复杂的计算和判断过程。
2. 高效性：Bresenham算法通过选择最接近理想位置的像素点，减少了不必要的计算和绘制，从而提高了绘制线段的效率。
3. 精度高：Bresenham算法通过选择最接近理想位置的像素点，可以实现精确绘制线段，避免了像素点之间的缺失或重叠现象。
四、Bresenham算法的应用领域Bresenham算法在计算机图形学中有着广泛的应用，特别是在线段绘制和扫描转换等方面。
这里不仔细讲原理，只是把我写的算法发出来，跟大家分享下，如果有错误的话，还请大家告诉我，如果写的不好，也请指出来，一起讨论进步。
算法步骤:(1) 输入椭圆的长半轴a和短半轴b。
(2) 计算初始值d = b*b + a * a * (-b + 0.25）， x = 0, y = b。
(3) 绘制点(x, y)及其在四分象限上的另外3个对称点。
(4) 判断d的符号。
若d <= 0，则先将d更新为d + b * b * (2 * x + 3)，再将(x, y)更新为(x+1, y)；否则先将d更新为d + b * b * (2 * x + 3) + a * a (-2 * y + 2)，再将(x, y)更新为(x+1, y-1)。
(5) 当b*b * (x+1) < a * a * (y - 0.5)时，重复步骤(3)和(4)，否则转到步骤(6)。
(6) 用上半部分计算的最后点(x, y)来计算下半部分中d的初值: d = b * b * (x + 0.5) * (x + 0.5) + a * a * (y - 1) * (y - 1) - a * a * b * b。
(7) 绘制点(x, y)及其在四分象限上的另外3个对称点。
(8) 判断d的符号。
若d <= 0，则先将d更新为d + b * b * (2 * xi + 2) + a *a * (-2 * yi + 3), 再将(x, y)更新为(x+1, y-1)；否则先将d更新为d + a * a * (-2 * yi + 3)，再将(x, y)更新为(x, y-1)。
(9) 当y >= 0，重复步骤(7)和(8)，否则结束。
下面是算法:#include <GL/freeglut.h>void init (void){glClearColor (0.0f, 0.0f, 0.0f, 1.0f);}void drawEllipse (int a, int b, int xLoc, int yLoc){glPushMatrix ();int x, y;float d1, d2, aa, bb;aa = a * a;bb = b * b;d1 = bb + aa * (-b + 0.25);glTranslatef ((GLfloat) xLoc, (GLfloat) yLoc, 0.0f);x = 0;y = b;glBegin (GL_POINTS);glVertex2i ( x, y);glVertex2i (-x, y);glVertex2i (-x, -y);glVertex2i ( x, -y);while (bb * (x + 1) < aa * (y - 0.5)){if (d1 <= -0.000001){d1 += bb * ((x << 1) + 3);}else{d1 += bb * ((x << 1) + 3) + aa * (2 - (y << 1));-- y;}++ x;glVertex2i ( x, y);glVertex2i (-x, y);glVertex2i (-x, -y);glVertex2i ( x, -y);}d2 = bb * (0.25 * x) + aa * (1 - (y << 1));while (y > 0){if (d2 <= -0.000001){++ x;d2 += bb * ((x + 1) << 1) + aa * (3 - (y << 1));}else{d2 += aa * (3 - (y << 1));}-- y;glVertex2i ( x, y);glVertex2i (-x, -y);glVertex2i (-x, y);glVertex2i ( x, -y);}glEnd ();glPopMatrix ();}void display (void){glClear (GL_COLOR_BUFFER_BIT);glLoadIdentity ();glColor3f (1.0f, 0.0f, 0.0f);// draw a ellipsedrawEllipse (200, 300, 50, 50);glutSwapBuffers ();}void reshape (int w, int h){glViewport (0, 0, (GLsizei) w, (GLsizei) h);glMatrixMode (GL_PROJECTION);glLoadIdentity ();if (w <= h){gluOrtho2D (-600.0, 600.0, -600.0 * (GLfloat) h / (GL float) w, 600.0 * (GLfloat) h / (GLfloat) w);}else{gluOrtho2D (-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 (int argc, char ** argv){glutInit (&argc, argv);glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);glutInitWindowSize (600, 600);glutCreateWindow ("Bresenham ellipse");init ();glutReshapeFunc (reshape);glutDisplayFunc (display);glutKeyboardFunc (keyboard);glutMainLoop ();return 0;}努力不一定有结果，但不努力一定没结果。
bresenham算法计算步骤Bresenham算法是一种经典的线段生成算法，其原理是利用递增的整数计算来逼近直线的路径，从而快速高效地绘制线段。
本文将详细介绍Bresenham算法的计算步骤。
1. 确定起点和终点我们需要确定线段的起点和终点的坐标。
假设起点为(x0, y0)，终点为(x1, y1)。
2. 计算斜率接下来，我们需要计算线段的斜率。
斜率可以通过以下公式来计算：m = (y1 - y0) / (x1 - x0)其中m表示斜率。
3. 判断斜率绝对值是否小于1判断斜率的绝对值是否小于1，如果小于1，则说明直线在x方向上变化的幅度更大；反之，如果斜率的绝对值大于等于1，则说明直线在y方向上变化的幅度更大。
4. 计算增量根据斜率的值，我们可以计算出在每个步骤中需要增加的x和y的值。
如果斜率的绝对值小于1，则每次x增加1，y增加斜率m；反之，如果斜率的绝对值大于等于1，则每次y增加1，x增加1/斜率m。
5. 计算初始误差计算初始误差值，初始误差值为0。
初始误差用于判断应该向x方向还是y方向进行绘制。
6. 迭代绘制线段根据初始误差值和增量，使用迭代的方式来绘制线段。
具体步骤如下：- 根据初始误差值，判断当前点应该绘制在哪个像素上。
如果误差大于等于0，则绘制在下一个像素上，同时误差减去1；反之，如果误差小于0，则绘制在当前像素上。
- 根据斜率的绝对值大小，更新初始误差的值。
如果斜率的绝对值小于1，则初始误差加上y的增量；反之，如果斜率的绝对值大于等于1，则初始误差加上x的增量。
- 根据斜率的绝对值大小，更新x和y的值。
如果斜率的绝对值小于1，则x加上1；反之，如果斜率的绝对值大于等于1，则y加上1。
7. 绘制结果将线段绘制在屏幕上，直到终点被绘制到。
通过以上步骤，我们可以使用Bresenham算法快速高效地绘制直线。
这个算法的优点是计算简单、速度快，并且不需要浮点运算，因此非常适合在计算能力较弱的设备上使用。
Course PagePage 1 of 6课程首页 > 第二章 二维图形的生成 > 2.1 直线的生成 > 2.1.2 生成直线的Bresenham算法全部隐藏2.1.2 生成直线的Bresenham算法从上面介绍的DDA算法可以看到，由于在循环中涉及实型数据的加减运算，因此直线的生成速度较慢。
在生成直线的算法中，Bresenham算法是最有效的算法之一。
Bresenham算法是一种基于误差判别式来生成直线的方法。
一、直线Bresenham算法描述： 它也是采用递推步进的办法，令每次最大变化方向的坐标步进一个象素，同时另一个方向的坐标依据误差判别式的符号来决定是否也要步进一 个象素。
我们首先讨论m=△ y/△x，当0≤m≤1且x1<x2时的Bresenham算法。
从DDA直线算法可知这些条件成立时，公式(2-2)、(2-3)可写成： xi+1=x i+1 yi+1=y i+m (2－6) (2－7)有两种Bresenham算法思想，它们各自从不同角度介绍了Bresenham算法思想，得出的误差判别式都是一样的。
二、直线Bresenham算法思想之一： 由于显示直线的象素点只能取整数值坐标，可以假设直线上第i个象素点坐标为(xi，yi)，它是直线上点(xi，yi)的最佳近似，并且xi=xi(假设 m<1），如下图所示。
那么，直线上下一个象素点的可能位置是(xi+1，yi)或(xi+1，yi+1)。
由图中可以知道，在x=xi+1处，直线上点的y值是y=m(xi+1)+b，该点离象素点(xi+1，yi)和象素点(xi+1，yi+1)的距离分别是d1和d2：d1=y-yi=m(xi+1)+b-yi d2=(yi+1)-y=(yi+1)-m(xi+1)-b 这两个距离差是 d1-d2=2m(xi+1)-2yi＋2b-1(2－8) (2－9)(2－10)我们来分析公式(2-10)： (1)当此值为正时，d1>d2，说明直线上理论点离(xi+1，yi+1)象素较近，下一个象素点应取(xi+1，yi+1)。
(2)当此值为负时，d1<d2，说明直线上理论点离(xi+1，yi)象素较近，则下一个象素点应取(xi+1，yi)。
(3)当此值为零时，说明直线上理论点离上、下两个象素点的距离相等，取哪个点都行，假设算法规定这种情况下取(xi+1，yi+1)作为下一个象 素点。
mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12Course PagePage 2 of 6因此只要利用(d1-d2)的符号就可以决定下一个象素点的选择。
为此，我们进一步定义一个新的判别式： pi=△x×(d1-d2)=2△ y·xi-2△x·yi+c (2－11)式(2-11)中的△x=(x2-x1)>0，因此pi与(d1-d2)有相同的符号； 这里△ y=y2-y1，m=△y/△ x；c=2△ y+△x(2b-1)。
下面对式(2-11)作进一步处理，以便得出误差判别递推公式并消除常数c。
将式(2-11)中的下标i改写成i+1，得到： pi+1=2 △y·xi+1-2△ x·yi+1+c (2－12)将式(2-12)减去(2-11)，并利用xi+1=xi+1，可得： pi+1= pi+2△y-2△x· (yi+1-yi) 再假设直线的初始端点恰好是其象素点的坐标，即满足： y1=mx1+b 由式(2-11)和式(2-14)得到p1的初始值： p1=2△y-△ x 这样，我们可利用误差判别变量，得到如下算法表示： 初始 p1=2 △y-△ x 当pi≥0时： yi+1=yi+1, xi+1=x i+1， pi+1=p i+2(△y-△ x) 否则： yi+1=yi, xi+1=x i+1， pi+1=p i+2△ y (2－16) (2－15) (2－14) (2－13)从式(2-16)可以看出，第i+1步的判别变量pi+1仅与第i步的判别变量pi、直线的两个端点坐标分量差△ x和△ y有关，运算中只含有整数相加和 乘2运算，而乘2可利用算术左移一位来完成，因此这个算法速度快并易于硬件实现。
三、直线Bresenham算法思想之二： 由于象素坐标的整数性，数学点(xi，yi)与所取象素点(xi，yir)间会引起误差(εi)，当xi列上已用象素坐标(xi，yir)表示直线上的点(xi， yi)，下一直线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是D(xi＋1，y(i+1)r)呢？ 设A为CD边的中点，正确的选择： 若B点在A点上方，选择D点； 否则，选C点。
mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12Course PagePage 3 of 6用误差式描述为： ε(xi+1)=BC-AC=(yi+1-yir)-0.5 求递推公式： ε(xi+2)=(yi+2-y(i+1)r)-0.5 = yi+1+m-y(i+1)r-0.5 当ε(xi+1)≥0时，选D点，y(i+1)r = yir+1 ε(xi+2)= yi+1+m-yir-1-0.5=ε(xi+1)+m-1 当ε(xi+1)﹤0时，选C点，y(i+1)r = yir ε(xi+2)= yi+1+m－yir-0.5=ε(xi+1)+m 初始时： ε(xs+1)=BC-AC=m-0.5 (2－12') (2－11') (2－10') (2－9') (2－8')为了运算中不含实型数，同时不影响不等式的判断，将方程两边同乘一正整数。
令方程两边同乘2·Δx，即d=2·Δx· ε，则： 初始时： d = 2·Δy-Δx 递推式： (2－13')当d≥0时：{ d=d+2·(Δy－Δx)； y++； x++； } (2－14')mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12Course PagePage 4 of 6否则： { d=d+2·Δy； x++； } 四、直线Bresenham算法实现： 条件：0≤m≤1且x1<x2 1、输入线段的两个端点坐标和画线颜色：x1，y1，x2，y2，color； 2、设置象素坐标初值：x=x1，y=y1； 3、设置初始误差判别值：p=2·Δy-Δx； 4、分别计算：Δx=x2-x1、Δy=y2-y1； 5、循环实现直线的生成： for(x=x1；x<=x2；x++) { putpixel(x,y,color) ； if(p>=0) { y=y+1； p=p+2· (Δy-Δx)； } else { p=p+2·Δy； } } 五、直线Bresenham算法完善： 现在我们修正(2-16)公式，以适应对任何方向及任何斜率线段的绘制。
如下图所示，线段的方向可分为八种，从原点出发射向八个区。
由线段 按图中所示的区域位置可决定xi+1和yi+1的变换规律。
容易证明：当线段处于①、④、⑧、⑤区时，以|△x|和|△y|代替前面公式中的△ x和△ y，当线段处于②、③、⑥、⑦区时，将公式中的|△ x|和|△ y|对换，则上述两公式仍有效。
在线段起点区分线段方向 六、直线Bresenham算法演示：mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12Course PagePage 5 of 6斜率小于1 七、直线Bresenham算法特点： 由于程序中不含实型数运算，因此速度快、效率高，是一种有效的画线算法。
八、直线Bresenham算法程序：斜率大于1void Bresenhamline (int x1,int y1,int x2,int y2,int color) { int x, y, dx, dy, s1, s2, p, temp, interchange, i; x=x1; y=y1; dx=abs(x2-x1); dy=abs(y2-y1);if(x2>x1) s1=1; else s1=-1;if(y2>y1) s2=1; else s2=-1;if(dy>dx) { temp=dx; dx=dy; dy=temp; interchange=1; } else interchange=0;p=2*dy-dx; for(i=1;i<=dx;i++)mhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12Course PagePage 6 of 6{ putpixel(x,y,color); if(p>=0) { if(interchange= =0) y=y+s2; else x=x+s1; p=p-2*dx; } if(interchange= =0) x=x+s1; else y=y+s2; p=p+2*dy; } }联系我们 | 制作小组 | 友情连接© 2009 洛阳理工学院. All rights reservedmhtml:file://C:\Documents and Settings\Administrator\桌面\Course Page.mht2011-7-12。
