《填充圆的算法设计.docx》由会员分享，可在线阅读，更多相关《填充圆的算法设计.docx（8页珍藏版）》请在三一办公上搜索。
1、敢入式Linux软件设计课程设计报告填充圆的算法设计、项目名称设计圆的两种以上填充算法，并比较其在ARM Lmux的执行速度二、项目需求分析在实验箱的LCD (Linux framebuffer设备)上完成圆或椭圆的两种以上填充 算法，比较他们的填充效果和填充速度。本实验计划完成圆的两种填充算法，分 别用点和线的方式填充半径相等的两个圆，并进行比较。三、概要设计在ARM机上执行填充圆算法，需要在软硬件方面协调工作方可。一、硬件a) 保证虚拟机和ARM机的通信，本次实验采用串口通信方式；b) 本实验要在LCD画圆，所以需要使用到帧缓冲设备(Framebuffer)。二、软件所编写的填充圆算法必须
2、可执行的，能够得出正确结果的。可利用交义 编译工具在宿主机上开发在目标板上运行的软件，即在Linux下先编写主函 数然后编译连接成ARM可运行的二进制文件，最后把该二进制文件下载到 超级终端上运行。软硬件流程图如图所示GUN交义编译工具链:a）ami-linux-gcc编译C程序（.c）或汇编程序（.s）使用交又编译工具编译一个程序的arm可执行程序：b）#arm-lmux-gcc -Wall -o * -hh-.c （-h-+.c 9己编译好的 c 程序，*为生成 的arm程序的名字）-c:只编译不链接，-o:编译且链接，-Wall:显示出借信息c）gcc 的使用格式如下：$ gcc opt
3、ionsfilenames其中filenames为所要编译的程序源文件。当使用gcc时，gcc会完成预处理、编译、汇编和连接。前三步分别生成目 标文件，连接时，把生成的目标文件链接成可执行文件。gcc可以针对支持不 同的源程序文件进行不同处理，文件格式以文件的后缀来识别。U!详细设计在本次实验中我采用了两种填充圆算法。（一）第一种算法：以为判断准则对LCD屏幕上的每一个点进行其相对圆心的距离是否小于圆的半径进行判断，若小于等于则进行填充，反之，则不进行动作。以一个16*16的网格为底板分别画一个半径为5和为6的圆，则填充效果如 下图所示，则其圆的边界会随着半径的增大而变得更加光滑。半径为5半径
4、为6（圆心未填充只是为了更清楚的标识）（二）第二种算法:以 为判断准则判断边界点，取该绝对值最小的点为直线一端 端点端点，并以此取得另一个端点，从而画以此两点为端点的直线。最终将整个 圆完成。以一个16*16的网格为底板分别画一个半径为5的圆，填充过程如下：（圆心未填充只是为了更清楚的标识）（三）流程图进行第二种填充圆算法 关闭 Framebuffer 设备退出程序(四) 关键代码第一种填充算法：i=100;x0=450;y0=240;foi (y=yO-i;yv=yO+i ;y十十)取与该圆相切的正方形为目标点范围，从而缩小计算范围(fbi(x=xO-r;x=xO+i;x-H-)if(x-x
5、O)* (x-xO)+(y-yO)* (y-yO)第二种算法void diawcircle(unsigned mt xO,unsigned mt yOjinsigned int radius,unsigned int c) unsigned mt x,yyl=0;int s0,sl,s2;/int 1=0;x=xO+radius+l;y=yO;dosO=abs(x-xO-1) * (x-xO-1)十(y-yO) * (y-yO)-radius*radius)；求(x-l,y)到(xO,yO)的距离与t的差的绝对值s 1 =abs(x-xO)*(x-xO)+(y-yO-1 )*(y-yO-1 )
6、-radius*radius);求(x,y-l)到(xO,yO)的距离与t的差的绝对值s2=abs(x-x0l)*(xx0-l)+(y-y0-l)*(y-y0l)-tadius*iadius);求(x-l,y-l)到(xO,yO)的距离与t的差的绝对值sO=s 1 ?(s0 v=s2?x=x-1: (x=x-1 ,y=y- l):(sl=s2?y=y-1: (x=x-1 ,y=y-1);选出距(xO,yO)距离最接近i的点iR(x!=2*xO-x)&(yl !=y)( diawpoint(2*x0-x,y,c);drawpoint(x,2*y0-y,c);drawline(x-1 ,y,2*x
7、0-x+l ,y,c);填充以(x-l,y),( 2*x0-x+l,y)为两端的直线)iR(y!=2*yO-y)&(yl !=y)diawpomt(x,y,c);drawpoint (2 *xO-x,2 *yO-y,c);diawlme(2*x0-x+l ,2 *yO-y,x- l,2*y0-y,c);填充以(2*xO-x+l,2*yO-y),( x-l,2*y0-y)为两端端点的直线)yi=y； while(x! =xO)&(y!=(yO-radius);计算代码执行时间(需包含头文件#include)clock_t start, finish;float t;start = clock()
8、; 计时开始倍计算时间的算法代码fimsli2 = clock(j; 计时结束t= (float)(fuiisli2 - start2)；五、调试结果与改进方案调试过程：(1) 最开始调试，是将两种填充圆算法分为两个程序来进行的，以此先确定 两种算法的可行性。其中，第一种非常顺利第一次就在LCD显示出了一个很完美的圆。而第二种则出现了一些问题，后来发现是程序中的数据类型在函数调用过程中出 现了一些不一致性，调整过后，则运行正常。同时，在对第二种算法程序进行调试过程中，我首先采用的传递填充色的方 法为传递指针，后调整为直接传值，发现二者执行速度，后者明显快于前者。两种算法均证明可执行后，此时，第
9、一种算法执行时间为0.021s,第二种为 0.043s。但是因为并未在同一个程序下执行，所以这组数据只能作为参考，并不 能很肯定的说第一种的执行速度优于第二种。(2) 在将两种算法整合进同一个程序时，在调试过程中也出现了一些问题。 首先，两种算法的填充点的算法是不一致的，所以先对其进行了统一。其次，两 个分程序中有很多重复的参数，将其进行区分后，再次调试，最终运行正常。此 时第一种算法执行时间为0.021s,第二种为0.032s。结论： 执行时间：由本次实验结果可见，第一种填充算法的填充时间是明显优于第 二种算法的。填充效果：如详细设计中两个半径为5的填充圆图所示，第二种算法的圆的 轮廓明显比
10、第一种更接近圆。因为第二种是以点到圆心的距离哪个更接近来判 断轮廓点的，而第一种则是单纯的选择点到圆心的距离小于等于I的点来进行判 断，这样较于第二种则明显太过片面。冗余点部分整个正方形区域均为第一种算法的目标点LCD不确定性:仔细分析可知，第一种算法是以一个与圆相切的正方形内的所有点为目标点进行 判断的。而第二种算法的目标点则与圆所包含的范围大致相等。所以当第一种算 法中目标点的冗余点越多，第一种算法的优势可能会越来越不明显。改进方案：基于本次实验的结果，可以计算出临界t,即两者运行时间相等时的圆的半 径“以此为界，在不同时选择不同的算法来进行运算。不过，此法是否行得 通，以及是否经济还需要
11、进一步验证。六、实验心得这次的嵌入式Linux课程，让我感触良多。在最开始的时候，我以为它很简 单，就仅仅只是将C语言换了一个执行的平台。但是随着后面深入的学习，我 感觉到Linux也有很多本身的特色，而且本课程真的与硬件结构关系十分密切。 因为种种原因，这次的实验我并没有像以前的模电、数电、C语言和数据结构等 课程那样投入非常大的精力，这固然与这门课的ARM机只能在教室使用有关， 但也与我自身其他课程的紧张、本次课程平时考查的宽松政策和课程的难度有一 定的关系。虽然这次最终的课程设计我有惊无险的验收了，但是我还是觉得这是 因为老师的选题给予了很大的仁慈。尽管如此,我还是很开心能够学习这门课程, 毕竟这为我们未来读研的方向乂打开了一扇窗户。谢谢！
