- 1 - 实验二 直线的生成算法的实现

班级 08信计2班 学号 59 姓名 分数

一、实验目的和要求

1.理解直线生成的基本原理。

2.掌握几种常用的直线生成算法。

3.利用Visual C++实现直线生成的DDA 算法。

二、实验内容

1.了解直线的生成原理，尤其是Bresenham 画线法原理。

2.掌握几种基本的直线生成算法：DDA 画线法、Bresenham 画线法、中点画线法。

3.利用Visual C++实现直线生成的DDA 算法，在屏幕上任意生成一条直线。

三、实验步骤

1.直线的生成原理：

（1）DDA 画线法也称数值微分法，是一种增量算法。是一种基于直线的微分方程来生成直线的方法。

（2）中点画线法原理

以下均假定所画直线的斜率[0,1]k ∈，如果在x 方向上的增量为1，则y 方向上的增量只能在01 之间。中点画线法的基本原理是：假设在x 坐标为p x 的各像素点中，与直线最

近者已经确定为(,)p p P x y ，用小实心圆表示。那么，下一个与直线最近的像素只能是正右

方的1(1,)p p P x y +，或右上方的2(1,1)p p P x y ++，用小空心圆表示。以M 为1P 和2P 的中点，则M 的坐标为(1,0.5)p p x y ++。又假设Q 是理想直线与垂直线1p x x =+的交点。显然，若M 在Q 的下方，则2P 离直线近，应取2P 为下一像素点；若M 在Q 的上方，则1P 离直线近，应取1P 为下一像素点。

（3）B resenham 画线法原理

直线的中点Bresenham 算法的原理：每次在主位移方向上走一步，另一个方向上走不走步取决于中点偏差判别式的值。

给定理想直线的起点坐标为P0（x0，y0），终点坐标为P1（x1，y1），则直线的隐函数方程为：

0b kx y y)F(x,=--= （3-1）

构造中点偏差判别式d 。

b x k y y x F y x F d i i i i M M -+-+=++==)1(5.0)5.0,1(),(

- 2 - ⎩⎨⎧≥<+=+)0( )0( 11d y d y y i i i

(1) 当d<0时

b

x k y y x F d i i i i i -+-+=++=+)2(5.1)5.1,2(1 k d k b x k y i i i -+=-+-+-+=11)1(5.0

⑵ 当d ≥0时

b

x k y y x F d i i i i i -+-+=++=+)2(5.0)5.0,2(1 k d k b x k y i i i -=--+-+=)1(5.0

2.实现前面所述的各种直线生成算法，包括DDA 算法、中点生成算法、Bresenham 生成算法等。程序运行后的菜单界面如图2-1所示。

图2-1 直线生成图形的程序运行界面

首先创建工程名为“基本图形的生成与填充”的单文档应用程序框架，操作步骤如下：

（1）创建单文档应用程序框架。

启动Visual C++，选择“文件/新建”菜单命令，在弹出的新建对话框中单击“工程”标签；选择.MFC AppWizard(exe)，在“工程名称”编辑框中输入“基本图形的生成与填充”（也可以使用英文名称），选择所要存放的位置后，单击“确定”按钮，出现Stept1对话框；选择“单个文档”选项，单击“下一步”按钮，在接着的Stept2～Stept5中，均可以直接单击“下一步”按钮完成应用程序框架的构建。也可以在Stept1步选择“单文档”（Single document ）后，直接单击“完成”按钮完成。

（2）编辑菜单资源。

在工作区中的Resource V iew 标签中，单击Menu 项左边的“+”，然后双击其子项IDR ＿MAINFRAME ，弹出编辑主菜单项，根据表1中定义的菜单项资源来编辑菜单，如图2-2

所示。

图2-2 编辑主菜单项

（3）添加消息处理函数。

利用类向导（Class Wizard）为应用程序添加与菜单项相关的消息处理函数。右击菜单项标题，选择“建立类向导…”，在弹出的MFC ClassWizard窗口中，选择Message Maps 标签，在Class Name栏中选择CMyView，根据表2建立消息映射函数，如图2-3所示。MFC ClassWizard会自动完成有关的函数声明。

- 3 -

- 4 -

图2-3 添加消息处理函数

（4）添加程序代码。

在CMyView.cpp 文件中相应的位置添加各算法的程序代码，在Visual C++的MFC 中绘制图形，一般可以调用一个“CDC ”类，从CDC 开始，添加代码。

添加代码如下：

//DDA算法生成直线，起点（x0,y0），终点（x1,y1）。

void CMyView::OnDdaline()

{

CDC *pDC=GetDC();

int x0=100,y0=100,x1=300,y1=200,c=RGB(255,0,0);

int x,y,i;

float dx,dy,k;

dx=(float)(x1-x0);

dy=(float)(y1-y0);

k=dy/dx;

x=x0;

y=y0;

if(abs(k)<1)

{

for(;y<=y1;y++)

{

pDC->SetPixel(x,int(y+0.5),c);

y=y+k;

}

}

if(abs(k)>=1)

{

for(;y<=y1;y++)

{

pDC->SetPixel(int(x+0.5),y,c);

x=x+1/k;

}

}

ReleaseDC(pDC);

}

//中点算法生成直线

void CMyView::OnMidpointline()

{

CDC *pDC=GetDC();

int x0=100,y0=100,x1=400,y1=300,c=RGB(0,0,0);

float 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;

- 5 -

y=y0;

pDC->SetPixel(x,y,c);

while(x<x1)

{

if(d<0) {x++;y++;d+=d2;}

else {x++;d+=d1;}

pDC->SetPixel(x,y,c);

}

ReleaseDC(pDC);

}

//Bresenham算法生成直线

void CMyView::OnBresenhamline()

{

CDC *pDC=GetDC();

int x0=100,y0=100,x1=500,y1=600,color=RGB(0,0,255);

int i,x,y,dx,dy;

float k,e;

dx=x1-x0;

dy=y1-y0;

e=-dx;

x=x0;

y=y0;

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

{

pDC->SetPixel(x,y,color);

x++;

e+=2*dy;

if(e>=0) {y++;e=e-2*dx;}

}

ReleaseDC(pDC);

}

（5）编译连接生成可执行程序，运行该程序。

仔细检查上述各个操作步骤，核对以上信息，点击调试按钮，调试程序准确无误后即可完整运行该程序。

四、实验结果分析

运行该程序后，运行程序后，我们可以得到如图2-1的界面，分别单击菜单中的“直线生成”项的“DDA算法生成直线”、“中点算法生成直线”、“Bresenham算法生成直线”，可以得到相应的直线：DDA算法得到的是红色线段，中点生成算法得到的是黑色线段，Bresenham 生成算法得到的是蓝色线段，如图2-4所示。

- 6 -

图2-4 直线的生成效果图

备注：DDA法就是根据直线的斜率来计算出下一个y值，经取整后以确定下一个像素点，

因为在进行取整运算，这就难以避免出现所取像素点片在实际直线某一侧的情况。

- 7 -