DDA算法 中点画线法 矩形填充

北京联合大学应用文理学院

空间数据库实验报告（1）

图形的光栅扫描转换

系：城市科学系专业：地理信息科学日期：10.6.2016 学号：姓名：Email：gulangmoyu96@http://doc.guandang.net

实验的目的

学习和理解基本图形生成的原理和算法，并通过实验上机编程，掌握直线的扫描转换的算法原理，并使得能初步掌握C语言的图像编程方法。

实验内容

在斜率k无限定、起点和终点坐标大小为任意的条件下，只利用一个可直接使用的作图函数putpixel (x, y, color)。实现数值微分画线法、中点画线法和矩形填充。

1．数值微分画线法（DDA算法）

（1）DDA算法的原理: 每走一步x+1,纵坐标对y+K+0.5取整。

（2）C语言程序

代码如下：

#include <graphics.h>

#include <conio.h>

#include <math.h>

void DDALine(int x0, int y0, int x1, int y1, int color)

{

int dx, dy, epsl, k;

float x, y, xincre, yincre;

dx = x1 - x0;

dy = y1 - y0;

if(abs(dx)>abs(dy))

{

epsl = abs(dx);

}

else

{

epsl = abs(dy);

}

xincre = (float)dx/(float)epsl;

yincre = (float)dy/(float)epsl;

for(k=0;k<=epsl;k++)

{

putpixel((int)(x+1),(int)(y+0.5),color);

1

北京联合大学应用文理学院

x += xincre;

y += yincre;

}

}

main()

{

int gdriver = VGA, gmode = VGAHI;

initgraph(&gdriver, &gmode, "C:\\TURBOC3\\BGI");

setbkcolor(WHITE);

DDALine(5, 3, 300, 600,4);

getch();

closegraph();

return 0;

}

运行结果：

2．中点画线法

（1）中点画线法的原理:首先根据所给两点算出a,b，给d付初值2（a+0.5b）如果d>=0说明中点在直线之上，取下方的点，即：（x+1,y），d=d+2a；如果d<=0，说明中点在直线之下，取上方的点，即：（x+1,y+1）,d=d+2(a+b)。如此循环调用，直到x达到终点。（2）C语言程序

2

北京联合大学应用文理学院

代码如下：

#include<stdio.h>

#include<graphics.h>

#include<stdlib.h>

#include<conio.h>

#define MAX 20

void swap(int* a,int* b)

{

int t=*a;

*a=*b;

*b=t;

}

void midpointline(int x1,int y1,int x2,int y2)

{

int dx,dy,d,incry,incre,incrne,slopegt1=0;

dx=abs(x1-x2);dy=abs(y1-y2);

if(dy>dx)

{

swap(&x1,&y1);

swap(&x2,&y2);

swap(&dx,&dy);

slopegt1=1;

}

if(x1>x2)

{

swap(&x1,&x2);

swap(&y1,&y2);

}

if(y1>y2)

incry=-1;

else

incry=1;

d=2*dy-dx;

incre=2*dy;

3

北京联合大学应用文理学院

incrne=2*(dy-dx);

while(x1<x2)

{

if(d<=0)

d+=incre;

else

{

d+=incrne;

y1+=incry;

}

x1++;

if(slopegt1)

putpixel(y1,x1,WHITE);

else

putpixel(x1,y1,WHITE);

}

}

void main()

{

int n,i;

int pt[MAX][2];

int gd=DETECT,gm;

printf("Enter the number of points:");

scanf("%d",&n);

printf("Enter the x and y coordinates:");

for(i=0;i<n;i++)

{

scanf("%d %d",&pt[i][0],&pt[i][1]);

pt[i][1]=480 - pt[i][1];

}

initgraph(&gd,&gm,"C:\\TURBOC3\\BGI");

line(1,0,1,480); // X – Axis

line(0,479,639,479); // Y – Axis

outtextxy(pt[0][0]-2,pt[0][1]-3,"*");

4

北京联合大学应用文理学院

for(i=0;i<n-1;i++)

{

midpointline(pt[i][0],pt[i][1],pt[i+1][0],pt[i+1][1]);

outtextxy(pt[i+1][0]-2,pt[i+1][1]-3,"*");

}

getch();

closegraph();

}

运行结果：

3．矩形填充

代码如下：

#include <conio.h>

#include <graphics.h>

main()

5

北京联合大学应用文理学院

{

int gdriver = VGA, gmode = VGAHI;

initgraph(&gdriver,&gmode,"c:\\turboc3\\bgi");

for(int i = 0;i<20;i++)

for(int j =0;j<30;j++)

putpixel(i,j,RED);

getch();

closegraph();

}

实验结果

用户分别输入k<-1,-1<k<0,0<k<1,k>1四种斜率的直线。分别在屏幕显示各算法产生的图形

6

北京联合大学应用文理学院

实验存在的问题及结果分析

Bresenham算法的优点是：

1、不必计算直线之斜率，因此不做除法；

2、不用浮点数，只用整数；

3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。

综上所述，Bresenham算法更加精确。

心得体会

通过本次实验的练习，基本理解了三种算法的操作过程，并可利用3种算法画任意斜率的图形

7