基本图形生成算法

news/2024/7/8 5:26:12 标签: 算法, 图形, DDA, Bresenham

                       基本图形生成算法

一.目的：

  1.学习使用MFC的图形编程。

    2.了解光栅显示的原理及基本图元线段和圆弧的生成算法。

二.内容：

    1．实现DDA直线段生成算法。

    2．实现Bresenham直线段生成算法。

    3．实现Bresenham圆弧生成算法。

三．要求：

    1．构建MFC工程：

    工程名：CgLineDraw和CgCircleDraw。

    选择单文档MFC框架结构：

     .app为应用程序；.doc为文档，用来存放数据；.view用来绘制文档数据图形；

     .MainFrame为主窗体。

    2．添加图形实验程序，修改View类，显示绘制OnDraw（）。

    3．建立坐标系：

     （1）以屏幕中心为原点（0，0），X轴为横轴，Y轴为竖轴；

     （2）生成实例占据八个8分圆；

     （3）分别用DDA算法和Bresenham算法绘制直线段，重复绘制100次，比较两种算法绘制直线段的效率和光滑程度，并在屏幕上显示出来。

     （4）用Bresenham算法绘制完整的圆和任意角度的圆弧。

四．步骤：

   (1)算法介绍：

    i.数值微分法（DDA算法）：直线扫描转换的最简单方法是先算出直线的斜率k=Δy/Δx，其中，Δx=x1-x0， Δy=y1-y0，（x0,y0）和（x1,y1）分别是直线的端点坐标。然后，从直线的起点开始，确定最佳逼近于直线的y坐标。假定端点坐标均为整数，让x从起点到终点变化，每步递增1，计算对应的y坐标，y=kx+B,并取象素（x,round(y)）。

DDAline(int x1,int y1, int x2, int y2, CDC *pDC)
{
             int i,step;
             float x,y,dx,dy;
step = abs(x2-x1) > abs(y2-y1) ?
                           abs(x2-x1) :abs(y2-y1);
             dx = (float) (x2-x1) / step;
             dy = (float) (y2-y1) / step;
             x = x1 + 0.5;
             y = y1 + 0.5;
             for (i = 0; i <= step; i++) {
                          pDC->SetPixel(m_wndWidth/2+(int)x,
                                                m_wndHeight/2-(int)y,RGB(255,0,0));
               x += dx;
               y += dy;
         }
}

    ii.Bresenham画线算法：通过在每列象素中确定与理想直线最近的象素来进行直线的扫描转换的。原理是过各行，各列象素中心构造一组虚拟网格线，按直线起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。

Bline(int x1, int y1, int x2, int y2, CDC *pDC)
{
	    int i,x,y,e,dx,dy,xSign,ySign,interChange = 0;
	    dx=abs(x2-x1);
        dy=abs(y2-y1);
	    if(dy>dx){
		     interChange=1;
		     e=dx;dx=dy;dy=e;
	     }
	     xSign=(x2-x1) ? 1 : -1;
         ySign=(y2-y1) ? 1 : -1;
	     x=x1;
	     y=y1;
	     e=2*dy-dx;
	     for(i=0;i<=dx;i++)
	    {
		    pDC->SetPixel(m_wndWidth/2+x,m_wndHeight/2+y,RGB(0,0,255));
            pDC->SetPixel(m_wndWidth/2+x,m_wndHeight/2-y,RGB(0,0,255));
	        pDC->SetPixel(m_wndWidth/2-x,m_wndHeight/2+y,RGB(0,0,255));
            pDC->SetPixel(m_wndWidth/2-x,m_wndHeight/2-y,RGB(0,0,255));
    	    if(e>=0)
		    {
			  e=e-2*dx;
			  if(interChange)
				x=x+xSign;
			  else
				y=y+ySign;
		    }
		   if(!interChange)
			 x=x+xSign;
		   else
		   {
			y=y+ySign;
		   }
		 e=e+2*dy;
       }
}

   iii.Bresenham画圆算法：圆心在原点，半径为R的第一个四分圆。取（0，R）为起点，按顺时针方向生成圆。从这段圆弧的任意一点出发，按顺时针方向生成圆时，为了最佳逼近该圆，下一象素的取法只有三种可能的选择：正右方象素，右下方象素和正下方象素。分别记为H，D和V。这三个象素中，与理想圆弧最近者为所求象素。理想圆弧与这三个候选点之间的关系只有下列五种情况：

      1. H，D，V全在圆内；

      2. H在圆外，D，V在圆内；

      3. D在圆上，H在圆外，V在圆内；

      4. H，D在圆外，V在圆内；

      5. H，D，V全在圆外。

   上述三点到圆心的距离平方与圆弧上一点到圆心的距离平方之差分别为：

   ΔH=（x+1）^2+(y)^2-R^2

   ΔD=（x+1）^2+(y-1)^2-R^2

   ΔV=（x）^2+(y-1)^2-R^2

     令δHD=|ΔH|-|ΔD|，

        δDV=|ΔD|-|ΔV|，计算下一象限的算法：

         当ΔD>0时，若δDV<=0，则取D，否则取V；

         当ΔD<0时，若δHD<=0，则取H，否则取D；

         当ΔD=0时，取D。

Bcircle(int r, CDC *pDC)
{
                int x,y,delta,delta1,delta2,direction;
                x=0;
                y=r;
                delta=2*(1-r);
                while(y>=0)
               {
	              pDC->SetPixel(x+m_wndWidth/2,y+m_wndHeight/2,RGB(255,0,255));
                  pDC->SetPixel(-x+m_wndWidth/2,y+m_wndHeight/2,RGB(255,0,255));
                  pDC->SetPixel(-x+m_wndWidth/2,-y+m_wndHeight/2,RGB(255,0,255));
                  pDC->SetPixel(x+m_wndWidth/2,-y+m_wndHeight/2,RGB(255,0,255));
	              if(delta<0)
	              {
		             delta1=2*(delta+y)-1;
		             if(delta1<=0) direction=1;
		             else
			            direction=2;
	              }
	              else if(delta>0)
	              {
		             delta2=2*(delta-x)-1;
		             if(delta2<=0) direction=2;
		           else
			          direction=3;
	             }
	             else
		            direction=2;
	             switch(direction)
	             {
	                 case 1:x++;
		                  delta+=2*x+1;
		                  break;
	                 case 2:x++;
		                  y--;
		                  delta+=2*(x-y+1);
		                  break;
	                 case 3:y--;
		                  delta+=(-2*y+1);
		                  break;
	      }
     }
}

 （2）部分代码：

    a.生成坐标系及两种画线算法比较：

void CCgQBlineDemoView::OnDraw(CDC* pDC)
{
	CCgQBlineDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	pDC->MoveTo(m_wndWidth/2,  0);
	pDC->LineTo(m_wndWidth/2,  m_wndHeight);

	pDC->MoveTo(         0,  m_wndHeight/2);
	pDC->LineTo(m_wndWidth,  m_wndHeight/2);

	clock_t start,finish;//typedef long clock_t; 
    double totaltime ;
    char str[10];
    
     if (pDoc->DDAlineMode) 
	{
		 
       	 start=clock();//clock():确定处理器当前时间
         //for(int n=0;n<1000;n++)
		 //{
	      DDAline(0, 0, 280, 70, pDC);
	      DDAline(0, 0, 70, 280, pDC);
	      DDAline(0, 0, -280, 70, pDC);
	      DDAline(0, 0, -70, 280, pDC);
	      DDAline(0, 0, 280, -70, pDC);
	      DDAline(0, 0, 70, -280, pDC);
	      DDAline(0, 0, -280, -70, pDC);
	      DDAline(0, 0, -70, -280, pDC);
		 //} 
         finish=clock();
         totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
	 }
      else 
	 {
         
		 
       	 start=clock();//clock():确定处理器当前时间
         //for(int n=0;n<1000;n++)
		 //{

	       Bline(0, 0, 280,70, pDC);
	       Bline(0, 0, 70, 280, pDC);
	       Bline(0, 0, -280, 70, pDC);
	       Bline(0, 0, -70, 280, pDC);
           Bline(0, 0, 280, -70, pDC);
	       Bline(0, 0, 70, -280, pDC);
	       Bline(0, 0, -280, -70, pDC);
	       Bline(0, 0, -70, -280, pDC);
		 //}
        finish=clock();
        totaltime=((double)(finish-start)/CLOCKS_PER_SEC)/1000;
        
	 }
    sprintf(str,"%lf",totaltime );//转换整型a至str 
    pDC->TextOut(100, 100,str);
}

  b.画圆算法及任意角度圆弧：

void CCgQBlineDemoView::OnDraw(CDC* pDC)
{
	CCgQBlineDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	pDC->MoveTo(m_wndWidth/2,  0);
	pDC->LineTo(m_wndWidth/2,  m_wndHeight);

	pDC->MoveTo(         0,  m_wndHeight/2);
	pDC->LineTo(m_wndWidth,  m_wndHeight/2);


       if (pDoc->DDAlineMode) 
	{
		 Bcircle(200, pDC);
	 
	 }
        else 
	{

      Bave(250.0,-3.14/4,3.14/3,pDC);
       
	}
   
}

void CCgQBlineDemoView::Bave(float r, double k1, double k2,CDC *pDC)
{
	 double x,y,delta,delta1,delta2,x1,x2,y1,y2,y3,y4;
	 int direction;
     x=0;
     y=r;
	 x1=r*cos(k1);
	 x2=r*cos(k2);
	 y1=r*sin(k1);
	 y2=r*sin(k2);

	 if(y2>=y1)
	 {
		 y3=y2;
	     y4=y1;
	 }
	 else
	 {
		 y3=y1;
	     y4=y2;
	 }
     delta=2*(1-r);
   while(y>=y3||y<=y4)
   {
	   pDC->SetPixel(x+m_wndWidth/2,y+m_wndHeight/2,RGB(255,0,0));
       pDC->SetPixel(-x+m_wndWidth/2,y+m_wndHeight/2,RGB(255,0,0));
       //pDC->SetPixel(x+m_wndWidth/2,-y+m_wndHeight/2,RGB(255,0,0));
       //pDC->SetPixel(-x+m_wndWidth/2,-y+m_wndHeight/2,RGB(255,0,0));
	  if(delta<0)
	   {
		   delta1=2*(delta+y)-1;
		   if(delta1<=0) direction=1;
		   else
			   direction=2;
	   }
	   else if(delta>0)
	   {
		   delta2=2*(delta-x)-1;
		   if(delta2<=0) direction=2;
		   else
			   direction=3;
	   }
	   else
		   direction=2;
	   switch(direction)
	   {
	   case 1:x++;
		      delta+=2*x+1;
		      break;
	   case 2:x++;
		   y--;
		   delta+=2*(x-y+1);
		   break;
	   case 3:y--;
		   delta+=(-2*y+1);
		   break;
	   }
     
   }

五．结果及分析：

  i.两种画线算法比较：

  

  

  由上述结果可知，Bresenham直线段生成算法画线效率较DDA直线段生成算法要高，两者画线的平滑度基本持平。DDA直线段生成算法虽然较易理解，但效率偏低，所以两者相比Bresenham直线段生成算法相对较优。

  ii.B算法完整的圆和任意角度的圆：

  

  

  









http://www.niftyadmin.cn/n/835320.html

相关文章

HTTP强制浏览器下载文件

HTTP强制浏览器下载文件

2019独角兽企业重金招聘Python工程师标准>>> https://blog.csdn.net/github_38885296/article/details/81205684 转载于:https://my.oschina.net/u/3697586/blog/1934238
阅读更多...
深圳APP开发共享汽车APP

深圳APP开发共享汽车APP

共享汽车APP&#xff0c;共享经济时代下的又一产物&#xff0c;是一款为用户提供汽车共享租赁的APP平台。共享汽车APP开发是为了让用户租车更加方便&#xff0c;根据人们用车的需求为用户制定租车方案&#xff0c;在各种需要用车的场景下无需再担心用车的问题。     共享汽车…
阅读更多...
区域填充算法

区域填充算法

区域填充算法 一&#xff0e;目的&#xff1a; 掌握有序编表法的基本原理与实现&#xff0c;了解简单的交互技术。 二&#xff0e;要求&#xff1a; 1. 边界种子交互输入&#xff1b; 2. 实例包含有凹凸多边形类型&#xff1b; 3. 支持颜色选择&#xff0c;图案编辑。 三&…
阅读更多...
atomic 和 nonatomic 有什么区别？

atomic 和 nonatomic 有什么区别？

2019独角兽企业重金招聘Python工程师标准>>> 在定义 property 的时候&#xff0c;atomic和 nonatomic有何区别&#xff1f; property(nonatomic, retain) UITextField *userName; property(atomic, retain) UITextField *userName; property(retain) UITextField *u…
阅读更多...
React-Redux应用

React-Redux应用

1、拆分文件 redux整个流程&#xff08;简版&#xff09;&#xff1a; 1、先在action-types.js里定功能 2、组件 3、reducer 4、合并reducer 5、产生store 6、渲染组件并运行文件 安装redux yarn add redux 复制代码目录&#xff1a; src/components/Counter.js import React,{…
阅读更多...
android Arcface人脸识别框/人脸抓拍框/人脸追踪框

android Arcface人脸识别框/人脸抓拍框/人脸追踪框

2019独角兽企业重金招聘Python工程师标准>>> 为什么要改&#xff1f; 先来看看sdk demo中提供的人脸框样式&#xff0c;这个框看上去并不是非常美观&#xff08;个人觉得&#xff09; 再看看下面这个框是不是就要顺眼一点 怎么换&#xff1f; 先来看看原始的画法&…
阅读更多...
使用多线程查询百万条用户数据将汉字转化成拼音

使用多线程查询百万条用户数据将汉字转化成拼音

现在有一个需求&#xff1a;用户表里面有将近200万条数据&#xff0c;查询时需要按用户名字的汉语拼音按从a-z排序。有两种解决方案&#xff1a;1.查询时使用数据库自带的CONVERT()函数进行转化&#xff0c;按拼音首字母排序;2.新加一个拼音字段&#xff08;spell_name&#xf…
阅读更多...
UML 教程

UML 教程

关键词&#xff1a;部署图, 组件图, 包图, 类图, 复合结构图, 对象图, 活动图, 状态机图, 用例图, 通信图, 交互概述图, 时序图, 时间图 简介 UML 图类型 UML 图类型如下图所示&#xff1a; 结构式建模图 结构式建模图&#xff08;Structure diagrams&#xff09;强调的是系统式…
阅读更多...
最新文章

Copyright @ 2022~2023