填充圆的算法设计

《嵌入式Linux软件设计》 课程设计报告 填充圆的算法设计  一、 项目名称 设计圆的两种以上填充算法，并比较其在ARM Linux的执行速度 二、 项目需求 在实验箱的LCD(Linux framebuffer设备)上完成圆或椭圆的两种以上填充算法，比较他们的填充效果和填充速度。本实验完成圆的两种填充算法，分别用点和线的方式填充半径相等的两个圆，并进行比较。 三、 概要设计 在ARM机上执行填充圆算法，需要在软硬件方面协调工作方可。 一、硬件 a) 保证虚拟机和ARM机的通信，本次实验采用串口通信方式； b) 本实验要在LCD上画圆，所以需要使用到帧缓冲设备（Framebuffer）。 二、软件 所编写的填充圆算法必须可执行的，能够得出正确结果的。可利用交叉编译工具在宿主机上开发在目标板上运行的软件，即在Linux下先编写主函数然后编译连接成ARM可运行的二进制文件，最后把该二进制文件下载到超级终端上运行。 Ubuntu虚拟机 GUN交叉编译 ARM9超级终端 预处理 汇编 编译 链接 .C源程序 运行 预处理器      编译器        汇编器      连接器          可执行文件 软硬件流程图如图所示 GUN交叉编译工具链： a) arm-linux-gcc 编译C程序（.c）或汇编程序（.s） 使用交叉编译工具编译一个程序的arm可执行程序: b) #arm-linux-gcc -Wall -o *** +++.c（+++.c为已编译好的c程序，***为生成的arm程序的名字） -c:只编译不链接，-o:编译且链接，-Wall:显示出错信息 c) gcc的使用格式如下：$ gcc [options][filenames] 其中filenames为所要编译的程序源文件。 当使用gcc时，gcc会完成预处理、编译、汇编和连接。前三步分别生成目标文件，连接时，把生成的目标文件链接成可执行文件。 gcc可以针对支持不同的源程序文件进行不同处理，文件格式以文件的后缀来识别。 四、 详细设计 在本次实验中我采用了两种填充圆算法。 （一） 第一种算法： 以 为判断准则对LCD屏幕上的每一个点进行其相对圆心的距离是否小于圆的半径进行判断，若小于等于则进行填充，反之，则不进行动作。 以一个16*16的网格为底板分别画一个半径为5和为6的圆，则填充效果如下图所示，则其圆的边界会随着半径的增大而变得更加光滑。 半径为5                              半径为6 （圆心未填充只是为了更清楚的标识） （二） 第二种算法： 以 为判断准则判断边界点，取该绝对值最小的点为直线一端端点端点，并以此取得另一个端点，从而画以此两点为端点的直线。最终将整个圆完成。 以一个16*16的网格为底板分别画一个半径为5的圆，填充过程如下： （圆心未填充只是为了更清楚的标识） （三） 流程图 （四） 关键代码 ? 第一种填充算法： r=100;x0=450;y0=240; for(y=y0-r;y<=y0+r;y++)  //取与该圆相切的正方形为目标点范围，从而缩小计算范围 { for(x=x0-r;x<=x0+r;x++) { if(((x-x0)*(x-x0)+(y-y0)*(y-y0))<=r*r) { *(fbp + y * 640*2 + x*2) = 0x00; *(fbp + y * 640*2 + x*2 +1) = 0xF8; } else{} } } ? 第二种算法 void drawcircle(unsigned int x0,unsigned int y0,unsigned int radius,unsigned int c) {    unsigned int x,y,y1=0; int s0,s1,s2; //int i=0; x=x0+radius+1;        y=y0; do {      s0=abs((x-x0-1)*(x-x0-1)+(y-y0)*(y-y0)-radius*radius)； //求(x-1,y)到(x0,y0)的距离与r的差的绝对值 s1=abs((x-x0)*(x-x0)+(y-y0-1)*(y-y0-1)-radius*radius); //求(x,y-1)到(x0,y0)的距离与r的差的绝对值 s2=abs((x-x0-1)*(x-x0-1)+(y-y0-1)*(y-y0-1)-radius*radius); //求(x-1,y-1)到(x0,y0)的距离与r的差的绝对值 s0<=s1?(s0<=s2?x=x-1:(x=x-1,y=y-1)):(s1<=s2?y=y-1:(x=x-1,y=y-1)); //选出距(x0,y0)距离最接近r的点 if((x!=2*x0-x)&&(y1!=y)) {    drawpoint(2*x0-x,y,c); drawpoint(x,2*y0-y,c); drawline(x-1,y,2*x0-x+1,y,c); //填充以(x-1,y),( 2*x0-x+1,y)为两端的直线 } if((y!=2*y0-y)&&(y1!=y)) {    drawpoint(x,y,c);    drawpoint(2*x0-x,2*y0-y,c); drawline(2*x0-x+1,2*y0-y,x-1,2*y0-y,c); //填充以(2*x0-x+1,2*y0-y),( x-1,2*y0-y)为两端端点的直线 }            y1=y; }while((x!=x0)&&(y!=(y0-radius))); } ? 计算代码执行时间（需包含头文件#include） clock_t start, finish; float  t; start = clock(); //计时开始 -------------------------------------------------------- 倍计算时间的算法代码 -------------------------------------------------------- finish2 = clock(); //计时结束 t= (float)(finish2 - start2)； 五、 调试结果与改进

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

调试过程： （1） 最开始调试，是将两种填充圆算法分为两个程序来进行的，以此先确定两种算法的可行性。 其 中，第一种非常顺利第一次就在LCD上显示出了一个很完美的圆。 而第二种则出现了一些问

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

，后来发现是程序中的数据类型在函数调用过程中出现了一些不一致性，调整过后，则运行正常。 同时，在对第二种算法程序进行调试过程中，我首先采用的传递填充色的

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

为传递指针，后调整为直接传值，发现二者执行速度，后者明显快于前者。 两种算法均证明可执行后，此时，第一种算法执行时间为0.021s，第二种为0.043s。但是因为并未在同一个程序下执行，所以这组数据只能作为参考，并不能很肯定的说第一种的执行速度优于第二种。 （2） 在将两种算法整合进同一个程序时，在调试过程中也出现了一些问题。首先，两种算法的填充点的算法是不一致的，所以先对其进行了统一。其次，两个分程序中有很多重复的参数，将其进行区分后，再次调试，最终运行正常。此时第一种算法执行时间为0.021s，第二种为0.032s。 结论： ? 执行时间：由本次实验结果可见，第一种填充算法的填充时间是明显优于第二种算法的。 ? 填充效果：如详细设计中两个半径为5的填充圆图所示，第二种算法的圆的轮廓明显比第一种更接近圆。因为第二种是以点到圆心的距离哪个更接近r来判断轮廓点的，而第一种则是单纯的选择点到圆心的距离小于等于r的点来进行判断，这样较于第二种则明显太过片面。 ? 不确定性：                                      LCD 冗余点部分 整个正方形区域均为第一种算法的目标点 仔细分析可知，第一种算法是以一个与圆相切的正方形内的所有点为目标点进行判断的。而第二种算法的目标点则与圆所包含的范围大致相等。所以当第一种算法中目标点的冗余点越多，第一种算法的优势可能会越来越不明显。 改进方案： 基于本次实验的结果，可以计算出临界r，即两者运行时间相等时的圆的半径r。以此为界，在r不同时选择不同的算法来进行运算。不过，此法是否行得通，以及是否经济还需要进一步验证。 六、实验心得 这次的嵌入式Linux课程，让我感触良多。在最开始的时候，我以为它很简单，就仅仅只是将C语言换了一个执行的平台。但是随着后面深入的学习，我感觉到Linux也有很多本身的特色，而且本课程真的与硬件结构关系十分密切。因为种种原因，这次的实验我并没有像以前的模电、数电、C语言和数据结构等课程那样投入非常大的精力，这固然与这门课的ARM机只能在教室使用有关，但也与我自身其他课程的紧张、本次课程平时考查的宽松政策和课程的难度有一定的关系。虽然这次最终的课程设计我有惊无险的验收了，但是我还是觉得这是因为老师的选题给予了很大的仁慈。尽管如此，我还是很开心能够学习这门课程，毕竟这为我们未来读研的方向又打开了一扇窗户。谢谢！