直线生成算法 DDA画线算法、中点画线算法、Bresenham画线算法

实验一、直线生成算法

DDA画线算法

一 .名称：DDA画线算法； 二 . 算法分析：

1.设直线两端点为:P1(x1,y1)及 P0(x0,y0),

k??yy1?y0??xx1?x02.则直线斜率 3.则直线方程为

yi?kxi?B4.当 k<1 , x每增加1，y 最多增加1(或增加小于1)。

yi?1?kxi?1?B?k?xi??x??B?kxi?B?k?x yi?1?yi?k?xlet?x?1yi?1?yi?k yi

5.当 k>1 ,y每增加1,x 最多增加1 (或增加小于1) 。

?k?1?

yi+1 xi xi+1 yByB?yxi?1?i?1??i??kkkkklet?y?1xi?1?xi?1k

?k?1?三．算法实现：

void CHuayahuaView::OnDda() //DDA画直线 {

ReleaseDC(pdc1);

// TODO: Add your command handler code here CDC* pdc1 = GetDC(); int color = RGB(255,0,0); int x1=10,y1=20,x2=200,y2=200; double k=(y2-y1)*1.0/(x2-x1);//k<1; double y=y1;

for(int i=x1;i<=x2;i++) { }

pdc1->SetPixel(i,(int)(y+0.5),color); y=y+k;

}四：程序截图：

中点画线算法

一． 实验名称：中点画线算法 二． 算法分析：

直线方程: F(x,y)=ax+by+c=0 y 直线将二维空间划分为三个区域: 如F(x,y)=0, 则(x,y) 在直线上 如F(x,y)<0, 则(x,y)在直线下方 如F(x,y)>0, 则(x,y)在直线上方 条件: a= -(y1-y0)

b=(x1-x0) c= -B(x1-x0) 三． 代码实现：

void CHuayahuaView::MidPointLine() {

// TODO: Add your command handler code here CDC* pdc1 = GetDC(); int color = RGB(255,0,0);

int x1=30,y1=50,x2=200,y2=100;//斜率； int x,y,a,b,d,d0,d1,d2; a=y2-y1; b=x2-x1; d=2*a+b; d1=2*a; d2=2*(a+b); x=x1,y=y1;

pdc1->SetPixel(x,(int)(y+0.5),color);

(x0,y0) F(x,y)>0 F(x,y)=0 F(x,y)<0 x (x1,y1) }

while(x < x2) { }

if(d>0) { } else { }

pdc1->SetPixel(x,(int)(y+0.5),color);

x++; d+=d1; x++; y++; d+=d2;

ReleaseDC(pdc1);

四． 程序截图：

Bresenham画线算法

一． 算法名称：Bresenham画线算法 二． 算法分析：

定义决策变量 d = d+k (0

则点，为: （x+1,y） (d<0.5) 或（x+1,y+1）(d>=0.5) 当d>1时, 让以证0<=d<1d0=0定义决策变量 d = d+k (0=0.5) 当d>1时, 让d=d-1,以保证0<=d<1 定义决策变量 e = d-0.5 (0=0) 当e >0时, 让

e=e-1, (重新初始化误差项)

由于算法只用到误差项的符号,为了改用整数以避免除法,可以作如下替换:

e = 2*e*dx 定义决策变量 e = 2*e*dx, e0 = - dx;

e=e +2*dy 则下一点为: （x+1,y） (e <0) ;或（x+1,y+1）(e >=0) 当e >0时, 让

e= e - dx, (重新初始化误差项)

三．算法实现：

void CHuayahuaView::Breshnham() { }

四：程序运行截图：

// TODO: Add your command handler code here CDC* pdc2 = GetDC(); int color = RGB(255,0,0); int x1=50,y1=50,x2=200,y2=150; int x,y,dx,dy,e;

dx=x2-x1;dy=y2-y1;e=-dx； x=x1; y=y1;

for(int i=0;i<=dx;i++) { }

ReleaseDC(pdc2);

pdc2->SetPixel(x,(int)(y+0.5),color); x++; e=e+2*dy; if(e>=0) { }

y++; e=e-2*dx;

本文来源：https://www.bwwdw.com/article/ftd2.html