直线生成算法

1、计算机地图制图 Turbo C提供了非常丰富的图形函数, 所有图形函数的原型均在graphics. h中，将集成开发环境Options/Linker中的Graphics lib选 为on, 只有这样才能保证正确使用图形函数。 基本图形生成算法 光栅中点的表示 直线的生成算法 圆的生成算法 椭圆生成算法 其它曲线的生成算法 区域的生成算法 字符生成技术 反走样技术光栅图形中点的表示 光栅显示器上显示的图形称为光栅图形，光栅显示器可以看作是一个像素矩阵。 光栅图形中的点也叫做像素，某一个点就是指某一个像素。 写入一点：putPixel(x,y,Color)#include int main() i

2、nt gdriver, gmode; gdriver=VGA; gmode=VGAHI; initgraph(&gdriver, &gmode, ); bar3d(100, 100, 300, 250, 50, 1); /*画一长方体*/ getch(); closegraph(); return 0; 直线的生成算法 数值微分法Digital Differential Analyzer 中点画线法 Bresenham算法 改进的Bresenham算法数值微分法(DDA)。数值微分法(DDA) 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。(X i

3、, Yi)。数值微分法(DDA)void DDALine(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx = x1-x0; dy=y1-y0; k=dy/dx ; y=y0; for (x=x0; xx1; x+) putpixel (x, int(y+0.5), color); y=y+k; 数值微分法(DDA)例：画直线段P0(0,0)-P1(5,2)x int(y+0.5) y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.50 1 2 3

4、4 5321Line: P0(0, 0)- P1(5, 2)数值微分法(DDA) 缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。中点画线法 当M在Q的下方- P2离直线更近更近-取P2 。 M在Q的上方- P1离直线更近更近-取P1 M与Q重合， P1、P2任取一点。 问题：如何判断M与Q点的关系？p,P=(xpy)中点画线法假设直线方程为：ax+by+c=0其中a=y0-y1, b=x1-x0, c=x0y1-x1y0由常识知：欲判断M点是在Q点上方还是在Q点下方，只需把M代入F(x,y),并检查它的符号。点在直线下方点在直线上方点在直线上面0,

5、0,0,yxFyxFyxFP=(xp,yp)QP2P1中点画线法构造判别式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c当d0，M在直线(Q点)上方，取右方P1；当d=0，选P1或P2均可，约定取P1；能否采用增量算法呢？P=(xp,yp)QP2P1中点画线法若d0-M在直线上方-取P1;此时再下一个象素的判别式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c= a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为aP=(xp,yp)QP2P1中点画线法若dM在直线下方-取P2;此时再下一个象素的判别式为

6、d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为abP=(xp,yp)QP2P1中点画线法 画线从(x0, y0)开始，d的初值d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。中点画线法void Midpoint Line (int x0,int y0,int x1, int y1,int color)

7、int a, b, d1, d2, d, x, y; a=y0-y1; b=x1-x0; d=2*a+b; d1=2*a ; d2=2* (a+b); x=x0; y=y0; putpixel(x, y, color); while (xx1) if (d=1，就减去1，保证d在0-1之间，当d=0.5时，取右上角像素，d0,取右上角像素，e0,取正右方像素。0 1 2 3 4 5321Bresenham算法 程序如下： BresenhamLine(x0,y0,x1,y1,color) int x0,y0,x1,y1,color; int x,y,dx,dy; float k,e; dx = x1-x0; dy = y1-y0; k = dy/dx;