直线生成算法的实现.doc

实验二：直线的生成算法的实现
班级 08信计2班 学号 20080502055 姓名 陈静 分数

一、实验目的和要求：
1、理解直线生成的原理；
2、掌握几种常用的直线生成算法；
3、利用C实现直线生成的DDA算法。
二、实验内容：
1、了解直线的生成原理
2、掌握几种基本的直线生成算法：DDA画线法、中点画线法、Bresenham画线法。
3、仿照教材关于直线生成的DDA算法，编译程序。
4、调试、编译、运行程序。
三、实验过程及结果分析
1、直线DDA算法：
算法原理：已知过端点P0（x0,y0），P1（x1,y1）的直线段L(P0,P1)，斜率为k=(y1-y0)/(x1-x0)，画线过程从x的左端点x0开始，向x右端点步进，步长为1个像素，计算相应的y坐标为y=kx+B。
计算yi+1 = kx i+B
=kx i +B+kx
=yi +kx
当x=1,yi+1=yi+k，即当x每递增1，y递增k。由计算过程可知，y与k可能为浮点数，需要取y整数，源程序中round(y）=(int)(y+0.5)表示y四舍五入所得的整数值。

（1）程序代码：
#include"stdio.h"
#include"graphics.h"
void linedda(int x0,int y0,int x1,int y1,int color)
{
int x,dy,dx,y;
float m;
dx=x1-x0;
dy=y1-y0;
m=dy/dx;
y=y0;
for(x=x0;x<=x1;x++)
{
putpixel(x,(int)(y+0.5),color);
y+=m;
setbkcolor(7);
}
}
main()
{
int a,b,c,d,e;
int graphdriver=DETECT;
int graphmode=0;
initgraph(&graphdriver,&graphmode,"");
a=100;
b=100;
c=200;
d=300;
e=5;
linedda(a,b,c,d,e);
getch();
closegraph();
}
运行结果：

2、中点画线算法：
假定所画直线的斜率为k∈[0,1]，如果在x方向上增量为1，则y方向上的增量只能在0~1之间。
中点画线法的原理是：假设x坐标为xp的各像素点中，与直线最近着已经确定，为P（xp，yp），用小实心圆表示。那么，下一个与直线最近的像素只能是正右方的P1（xp+1，yp），或右上方的P2（xp+1，yp+1），用小空心圆表示。
程序代码：
#include"stdio.h"
#include"graphics.h"
void midpointline(int x0,int y0,int x1,int y1, int color)
{
int a,b,delta1,delta2,d,x,y;
a=y0-y1;
b=x1-x0;
d=2*a+b;
delta1=2*a;
delta2=2*(a+b);
x=x0;
y=y0;
putpixel(x,y,color);
while(x<x1)
{
if(d<0)
{
x++;y++;
d+=delta2;
}
else
{
x++;
d+=delta1;
}
putpixel(x,y,color);
setbkcolor(7);
}
}
main()
{
int a,b,c,d,e;
int graphdriver=DETECT;
int graphmode=0;
initgraph(&graphdriver,&graphmode,"");
a=50;
b=100;
c=200;
d=300;
e=5;
midpointline(a,b,c,d,e);
getch();
closegraph();
}
运行结果：

3、Bresenham画线算法：
Bresenham算法的基本原理是：过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。
程序代码：
#include <stdio.h>
#include <graphics.h>
void bresenhamline(x1,y1,x2,y2,color)
int x1,y1,x2,y2,color;
{
int dx;
int dy;
int x;
int y;
int d;
int d1;
int d2;
int inc;
int tmp;
dx=x2-x1;
dy=y2-y1;
if(dx*dy>=0)
inc=1;
else
inc=-1;
if(abs(dx)>abs(dy))
{
if(dx<0)
{
tmp=x1;
x1=x2;
x2=tmp;
tmp=y1;
y1=y2;
dx=-dy;
dy=-dy;
}
d=2*dy-dx;
d1=2*dy;
d2=2*(dy-dy);
x=x1;
y=y1;
putpixel(x,y,color);
while(x<x2)
{
x++;
if(d<0)
d+=d1;
else
{
y+=inc;
d+=d2;
}
setpixel(x,y,color);
}
}
else
{
if(dy<0)
{
tmp=x1;
x1=x2;
x2=tmp;
tmp=y1;
y1=y2;
dx=-dy;
dy=-dy;
}
d=2*dx-dy;
d1=2*dx;
d2=2*(dx-dy);
x=x1;
y=y1;
putpixel(x,y,color);
while(y<y2)
{
y++;
if(d<0)
d+=d1;
else
{
x+=inc;
d+=d2;
putpixel(x,y,color);
setbkcolor(7);
}
}
}
}
main()
{
int a,b,c,d,e;
int graphdriver=DETECT;
int graphmode=0;
initgraph(&graphdriver,&graphmode,"");
a=100;
b=200;
c=200;
d=300;
e=5;
bresenhamline(a,b,c,d,e);
getch();
closegraph();
}
运行结果：

结果分析：
三种算法的区别：
(1)DDA算法画线算法也称数值微分法，是一种增量算法。它的算法实质上是用数值方法解微分方程，同时对x和y各增加一个小增量来计算下一步的x、y值。
DDA算法画线比较直观可行，逻辑简单，但是每一步都需要一个浮点乘法与一个round函数进行舍入运算，效率不高。
(2)中点画线算法如果进替补把上述程序中的（2*a）改为（a+a）等，那么这个算法不仅包含中枢变量，而且不包含乘除法，更适于软件实现。
(3) Bresenham画线算法是计算机图形学领域使用最广泛的直线生成方法，该方法类似于中点画线算法，由误差项符号决定下一个像素正右方还是右上方点。