一种路径规划算法的改进与设计

1、毕业设计说明书0906054116电子与计算机科学技术学院师少兵学生姓名： 学号： 软件工程学 院： 潘广贞专 业： 指导教师： 2013年 6 月楼宇煤气智能监测系统设计摘要本文主要介绍了楼宇煤气监测系统的工作原理及系统硬件设计、系统软件设计的实现方法。整个系统按逻辑分为主机控制模块、传感器输入模块、报警输出模块三部分，旨在完成室内煤气监控以减少因煤气泄漏造成的中毒或者火灾等意外事故的发生，从而更好的保护人民的人身财产安全。本系统基于单片机来设计，单片机根据传感器获取的煤气浓度来做出报警等一系列动作。当煤气浓度超过阀值时驱动声光报警并启动排气扇以降低室内煤气浓度。主机控制模块包括键盘子模块、

2、数码管及lcd显示子模块、时间及定时子模块等三个模块；传感器输入模块包括气敏传感器、温度传感器、光敏传感器、湿敏传感器四路输入以及a/d转换子模块；报警输出模块包括闪光报警、声音报警、排气装置、等三个子模块。整个系统由以上各模块协同工作最终完成煤气监测的任务，并能保证系统的稳定性及安全性。关键词：煤气检测，监测系统，智能，报警the design ofintelligent monitoring system of the building of gasabstractthis paper describes the principle of the gas detection system

3、of building and the design of the system hardware and its implementation method. the whole system is divided into three parts in logical, include the host control module, the sensor input module, the alarm output module, which in order to complete the indoor gas monitoring that to reduce the toxic g

4、as leaks or fires caused by accidents, and in order to protect peoples personal and property safety better.the system is designed based on single chip, the single chip make a series of actions when it obtained the gas concentration from the sensor. when gas concentrations exceed the threshold it sta

5、rting to drive the sound and light alarm then drive the exhaust fan to reduce the indoor gas concentrations. host control module include three modules: keyboard sub-modules, digital tube and lcd display sub-module, time and timing sub-module; sensor input module including four sensor: gas sensors, t

6、emperature sensors, light sensors，humid sensor and a a/d converter; the alarm module included three modules: flash alarm, sound alarm, exhaust. those modules above work together to finish the task of gas detection, and ensured the system stability and security.keywords: gas detection, monitoring sys

7、tem, intelligent, alarm目 录1 引言111 课题研究背景112 国内外研究现状113 研究的依据和意义214 研究的思路和方法315 主要研究内容32 系统规划和系统分析421 系统目标设计422 可行性研究423 拟采用的研究途径4231 拟合曲线的选择与实现4232 过凸极值点做水平切线5233 区域的划分与存储5234 构造连通无向图5235 设定权值，确定最优路径524 系统规划6241 基本的障碍物拟合及水平切线的求取6242 区域存储并构造无向图6243 设定权值及寻找最优路径625 系统流程分析63 系统设计831 系统配置832 系统结构模型设计833

8、系统数据结构设计9331 逻辑结构设计要点9332 基本物理结构设计要点9333 数据结构94 功能模块划分1141 障碍物拟合模块1142 凸极值点计算模块1143 水平切线划分区域模块1244 区域存储模块1345 无向图构造模块1346 路径寻找模块145 系统实现1551 障碍物的拟合1552 凸极值点的计算1653 水平切线划分区域1854 区域存储19541 区域寻找的方式19542 新区域的判定标准19543 区域存储需要的准备数据20544 区域寻找完之后应得到的数据2055 构造无向图2056 设定权值，确定最优路径216 系统测试2361 测试说明2362 测试内容2462

9、1 凸极值点的计算24622 水平切线划分区域24623 无向图的构造25624 最优路径的寻找267 结论与评价28参 考 文 献29致 谢311 引言11 课题研究背景随着城市的发展和人民生活水平的提高，人们出行的次数和出行的路程都在增加，作为城市枢纽的公共交通承担着越来越重的运输任务。同时，公交线路的条数和公交车数量也在迅速增多，公交的服务时间在延长，到站路程在扩大，服务质量在提高，给人民的日常生活带来了很多便利。然而，随着人们所到目的地范围扩大，出行往往需要转乘多亮公交车才能到达目的地，如何在短时间、路程最短、成本最低的情况到达目的地，是人们所关注的问题。因此，我们的课题是运用计算机及

10、网络技术，结合国内外先进的数学计算方法，运用路径规划的思想，设计一套方便人们出行时所需的最佳公交换乘方法，给人们出行节约更多的时间和金钱。12 国内外研究现状路径规划是运动规划的主要研究内容之一。运动规划由路径规划和轨迹规划组成，链接起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。路径规划在机器人学与虚拟装配中研究较多，主要研究内容可概括为：1） 静态结构化环境下的路径规划；2） 动态已知环境下的路径规划；3） 动态不确定环境下的路径规划；根据规划体对环境信息知道的程度不同，路径规划可分为两种类型：环境信息完全已知的全局路径规划，又称静态或离线路径规划；环境信息完全未

11、知或部分未知，通过传感器在线地对机器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局部路径规划，又称动态或在线路径规划。局部路径规划和全局路径规划并没有本质区别。很多适用于全局路径规划的方法经过改进都可以用于局部路径规划；而适用于局部路径规划的方法都可以适用于全局路径规划1。全局路径规划的方法主要有：栅格法2、构形空间法3-7、可视图法1,8、拓扑法和概率路径图法9,10；局部路径规划的主要方法有：人工势场法11,12、模糊逻辑算法1、遗传算法1,10和基于神经网络方法2。随着计算机传感器及控制技术的发展特别是各种新算法不断涌现，路径规划技术已经取得了丰硕研究成果，特别是周围环境

12、已知的全局路径规划其理论研究已比较完善，目前比较活跃的领域是研究在环境未知情况下的局部规划。从研究成果看，有以下趋势：1) 智能化的算法将会不断涌现。模糊控制、神经网络、遗传算法以及它们的相互结合也是研究热点之一。智能化方法能模拟人的经验，逼近非线性，具有自组织、自学习功能，并且具有一定的容错能力。2) 路径规划的性能指标将不断提高。这些性能指标包括实时性、安全性和可达性等。比如路径规划技术应用于移动机器人，一个性能指标不好的方法即使它能使移动机器人走出完美的轨迹也将被淘汰，而有些方法没有高深的理论，但计算简单，实时性、安全性好，就有存在的空间。如何使性能指标更好是路径规划各种算法研究的一个重

13、要方向。3) 多规划体系系统的路径规划。协调路径规划已成为新的研究热点，随着应用不断扩大，规划体工作环境复杂度和任务的加重，对其要求不再局限于单规划体，而是要求在动态环境中实现多规划体的合作与单规划体路径规划的统一。4) 多传感器信息融合用于路径规划。规划体在动态环境中进行路径规划所需信息是从传感器得来的，单传感器难以保证输入信息准确与可靠，多传感器所获得信息具有冗余性、互补性、实时性和低代价性，且可以快速并行分析现场环境。移动机器人的多传感器信息融合是当今一个比较活跃的研究领域。13 研究的依据和意义路径规划一直是国内外学者研究的重点课题，哪条路径是最优的，怎样选择最优的路径，如何在最短的时

14、间内选出最优的路径，各国学者对其进行了大量的研究工作。在20世纪50年代就已经出现了关于路径规划的算法，可是那时的算法不是很好，需要消耗很多的时间和空间；现在我们追求的是，如何在比较少的时间和空间消耗内，计算出最优的路径。该课题的目的就是为了解决这样的问题。针对路径规划的实用性，在本文中提出了一种新的路径规划处理算法，这种算法有助于提高寻找最优路径的时间效率和空间效率。14 研究的思路和方法本文研究的基本思路是: 根据现有的资料，从算法实现的角度出发，首先对改算法的应用背景及应用情况进行了解认识，在此基础上对模拟实现工具进行选取和学习，借鉴现有的理论研究和实践成果，结合现有国内研究情况进行深入

15、探讨。全面系统地学习实现和改进算法的相关理论知识和技术手段，然后设计整体结构，从整体的角度进行分析，从设计思想，设计目的进行详尽的规划，从而在此基础上逐步完成算法的实现与改进工作。15 主要研究内容本课题研究的主要内容是一种路径规划算法的改进与设计。具体的实现如下：在一个布满障碍物的地图上，过凸极值点划分区域；在相应的区域中抽象出一个点来对应各区域，画出连通无向图；根据对应的权值找出最优路径。2 系统规划和系统分析21 系统目标设计通过学习课题相关的理论知识，进行必要的调研和查阅相关的资料，了解曲线拟合和路径规划的特征与本质。在布满障碍物的地图上，采用拟合曲线对障碍物进行模拟，然后过拟合曲线的

16、凸极值点做水平切线划分区域，在相应的区域中抽象出一个点来对应各区域，画出连通无向图；根据对应的权值，找出最优的路径。我们的最终目标是将以上提出的方案变为实际的算法。22 可行性研究可行性研究随着科学技术发展和相关管理学科的研究深入而逐步完善，并日渐发展成为一门综合性研究学科。所谓可行研究，简单点说就是以最小的代价，在尽可能短的时间内分析研究，以确定问题是否能够解决，是否值得去研究。现在就对本算法的技术可行性进行简单的分析。该系统开发采用的技术是html5，因此需要支持html5的浏览器，目前大部分主流的浏览器都已经开始支持html5了，如chrome、firefox、ie9及其以上版本等等。采

17、用的javascript脚本语言作为编程语言，使用jcanvascript作为画图工具包，jcanvascript是一个面向html5画布（canvas）的javascript类库，它提供了许多方法用于简化处理html5画布（canvas）元素的内容。障碍物的拟合与最短路径的查找已经有了很多成功的案例。所以此系统在技术上是可行的。23 拟采用的研究途径231 拟合曲线的选择与实现地图中的障碍物，我们采用三次贝塞尔曲线进行模拟。贝塞尔曲线是依据四个位置任意的点坐标绘制出的一条光滑曲线，随着点有规律地移动，曲线将产生皮筋伸引一样的变换，带来视觉上的冲击。1963年，法国数学家pierre bzie

18、r第一个研究了这种矢量绘制曲线的方法，并给出了详细的计算公式，因此按照这样的公式绘制出来的曲线就用它的姓氏来命名是为贝塞尔曲线。贝塞尔曲线的操作特点是通过鼠标在面板上放置各个锚点，根据锚点的路径和描绘的先后顺序，产生直线或者曲线的效果。我们都知道路径由一个或多个直线段或曲线段组成。锚点标记路径段的端点。在曲线段上，每个选中的锚点显示一条或两条方向线，方向线以方向点结束。方向线和方向点的位置确定曲线段的大小和形状。232 过凸极值点做水平切线凸极值点是函数图象的某段子区间内极大值的横坐标，极值点出现在函数的驻点或不可导处；极值点上函数的导数为零或不存在，且函数的单调性必然变化。若一个函数的某一点

19、存在某一邻域，在该邻域内函数处处都有定义，而该点的函数值为最大（小），则该函数在该点处的值就是一个极大（小）值。如果它比邻域内其他各点处的函数值都大（小），它就是一个严格极大（小）值。该点就相应地称为一个极值点或严格极值点。在极值点的左右，函数的增减性不一样，比如说在极值点的左方邻域内函数单调增加，则在极值点的右方邻域内函数单调减小。极值是对函数某一区间的取值；极值不一定是整个函数定义域内的最值。几何上，切线指的是一条刚好触碰到曲线上某一点的直线。更准确的说，当切线经过曲线上的某点（即切点）时，切线的方向与曲线上该点的方向是相同的，此时，“切线在切点附近的部分”最接近“曲线在切点附近的部分”（

20、无限逼近思想）。233 区域的划分与存储根据拟合的曲线和过凸极值点做的水平切线，将整个地图划分为小块的区域，存储每个区域的边界值。通过计算每个区域的边界值，将每个区域抽象为一个点。234 构造连通无向图在图论中，连通图基于连通的概念。在一个无向图 g 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果 g 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。将区域抽象为一个点后，根据原来区域的关联性，将相应的点连接起来，构造连通无向图，使用邻接表或其他数据结构存储无向图

21、。235 设定权值，确定最优路径最优路径就是路径中最符合某种需求的一条路径，比如最短路径，就是从起点到终点的权值和最小的边。对图求最优路径的方法即称为最优路径算法，通常用计算机编程实现。在公路运输中，为了使运输的时间和花费最少（花费可以是油耗和费用），需要找到起点和终点的最优路径。这条最优路径可以是路程最短的路径，也可以是油耗最省的路径，依据实际需求而定。在实际应用中，知道起点和终点，便可用最优路径算法计算出路径，这对车辆的行驶有很好的指导作用。使用计算机编程实现，更能提高效率。24 系统规划该系统主要分为三部分，分别是基本的障碍物拟合及水平切线的求取、区域存储并构造无向图、设定权值然后寻找最

22、优路径。241 基本的障碍物拟合及水平切线的求取本部分主要包括多个障碍物的曲线拟合、求取每个障碍物的凸极值点和过凸极值点做水平切线。242 区域存储并构造无向图本部分主要包括对整个地图的区域进行遍历与编号和无向图的构造243 设定权值及寻找最优路径本部分主要包括起点与终点的设定，计算出一个或多个通路，然后根据权值寻找出最优的路径25 系统流程分析通过调查和分析，本系统的业务流程主要是：用户通过在画板上点击相应的点来构造障碍物，当障碍物完成之后，点击画切线按钮开始对地图中所有的障碍物进行凸极值点的计算，然后在凸极值点处画水平切线，将整个地图划分为多个区域；之后用户选择出起点和终点，然后输入起点和

23、终点所在的区域；最后点击完成按钮，程序开始计算所有可行的路径，并标记出最优的路径。在用户的操作过程中和系统运行的过程中，程序都要时刻地记下重要的数据，方便之后的计算。程序存储的数据主要有：用户点击的点的坐标、每个障碍物的边界经过的点的坐标、每个障碍物的凸极值点的坐标、过凸极值点做的水平切线的两个端点的坐标和用来存储无向图的邻接表等等。图2-1 系统流程图3 系统设计31 系统配置硬件平台：cpu：t2.10ghz内存：1gb以上软件平台：操作系统：windows、linux等开发工具：支持html5的浏览器、notepad+32 系统结构模型设计基于jquery的javascript框架的图形

24、化实现，数据由用户进行输入，数据处理分布在格子的类中，通过与界面类进行交互。根据系统的总体目标，本系统开发采用了面向消息机制的实时消息处理机制。不断的监听用户的动作，以做出相应的处理。在点击面板后，程序会做出相应的处理。同时采用了面向对象的思路和方法，对比较相似的操作写进一个类中，方便操作，提高了系统的安全性能，便于以后的扩展和维护。jquery是一个非常优秀的javascript框架。它是轻量级的js库 ，它兼容css3，还兼容各种浏览器（ie 6.0+, ff 1.5+, safari 2.0+, opera 9.0+）。jquery使用户能更方便地处理html documents、eve

25、nts、实现动画效果，并且方便地为网站提供ajax交互。jquery还有一个比较大的优势是，它的文档说明很全，而且各种应用也说得很详细，同时还有许多成熟的插件可供选择。jquery能够使用户的html页面保持代码和html内容分离，也就是说，不用再在html里面插入一堆js来调用命令了，只需定义id即可。jcanvascript是一个面向html5画布（canvas）的javascript类库，它提供了许多方法用于简化处理html5画布（canvas）元素的内容，只要支持canvas和javascript的浏览器都可以使用它，包括iphone、ipad和android等平台。图3-1 功能结构

26、图33 系统数据结构设计331 逻辑结构设计要点本系统内所使用的每个数据结构的名称、标识符以及它们之中每个数据项、记录、问卷和系的标识、定义、长度及它们之间的层次的或表格的相互关系。332 基本物理结构设计要点本系统内所使用的每个数据结构中的每个数据项的存储要求，访问方法、存取单位、存取的物理关系（索引、设备、存储区域）、设计考虑和保密条件。333 数据结构定义如下数据结构：表3-1 圆的数据结构字段类型长度描述xfloat11横坐标yfloat11纵坐标bint11半径ccolor8颜色boolboolean1是否填充circleidstring15编号表3-2 线段的数据结构字段类型长度描

27、述pointsarray端点的坐标集合colorcolor8颜色lwfloat11线段的宽度lineidstring8编号表3-3 三次贝赛尔曲线的数据结构字段类型长度描述pointsarray11端点的坐标集合extrapointsarray11额外点的坐标集合colorcolor8颜色lwfloat11宽度fillboolean1是否填充表3-4 文本的数据结构字段类型长度描述stringarray11文本内容xarray11文本左下方的横坐标ycolor8文本左下方的纵坐标maxwidthfloat11文本的最大宽度colorcolor8字体颜色fillboolean1是否填充4 功能模

28、块划分根据要实现的目标和思路，主要划分了以下的模块：障碍物拟合模块、凸极值点计算模块、水平切线划分区域模块、区域存储模块、无向图构造模块和路径寻找模块。每个模块都有着承上启下的作用，缺少了任何一个模块，都将无法进行。41 障碍物拟合模块该模块需要实现的功能主要有：获取用户点击的点的坐标，计算出所需要画三次贝赛尔曲线所需要的数据，调用画图函数拟合出障碍物，计算边界经过的点的坐标。图4-1 障碍物拟合模块当用户的鼠标处于画图区域中时，时刻检测鼠标的位置，当用户点击下左键时马上获取当前的坐标值并存储。用户点击一个障碍物完成之后，就开始计算三次贝赛尔曲线需要的其他的点的坐标；计算完成之后调用画图函数完

29、成一个障碍物的拟合。同时在这个模块中还要计算该障碍物经过的所有点的坐标，方便之后的区域存储模块的执行。障碍物的绘制与障碍物经过的点坐标使用的是不同的方法：障碍物的绘制调用的是jcanvascript类库中的方法，画出来的三次贝赛尔曲线是平滑的；而障碍物经过的点的坐标是使用三次贝赛尔曲线方程计算出来的，因此这些点是不连续的，相邻两点之间的距离也是不确定的。42 凸极值点计算模块在本系统中，凸极值点的含义是：边界上的点相对于障碍物的内部来说更偏向于外界。而且本系统仅仅使用水平方向上的凸极值点。对于某个障碍物的边界点，我们可以根据该点与相邻两点的y值进行比较，能够确认该点是不是极值点，但是目前还不能

30、确认该点是否是凸极值点，因为某些极值点是向障碍物内部凹陷的 。在计算极值点时要确认该极值点是向上凸的还是向下凸的，若该极值点是向上凸的则向下做射线，否则向上做射线；然后计算该射线与障碍物边界交点的个数，若交点个数是奇数则该极值点是凸极值点，否则不是。图4-2 凸极值点计算模块43 水平切线划分区域模块该模块的主要功能是将整个地图划分出几个区域，对每个区域和区域之间进行权值的计算，然后可以寻找出最优的路径。在凸极值点计算模块已经计算出所有障碍物的凸极值点，便可以过凸极值点做水平切线划分区域了。这个模块的难点是如何计算水平切线的两个端点的坐标。因为水平切线不可能穿过障碍物，因此必须得所有障碍物都完

31、成之后才能开始水平切线的计算。对于水平切线的计算，我们采用的是最好优先原则，遍历障碍物的边界点，若该点距离凸极值点较近且在同一水平线上，则认为该点更适合作为水平切线的端点。所有的边界点遍历完成之后，则能够寻找出水平切线的端点。图4-3 水平切线划分区域模块44 区域存储模块该模块的主要功能是将地图中的可用区域存储，便于之后无向图的构造和路径的寻找。区域存储，顾名思义就是将一个比较大的区域用某种方式存储下来，抽象为一个点。在本系统中，程序是无法得知这个区域有多大的，只是知道这是一个新的区域应该存储起来，同时为了能够构造无向图，还要存储该区域所有的边界。因为在程序没有计算完成之前，是无法得知下一个

32、区域是不是一个新的区域，因此不能在这里就开始无向图的构造。区域存储模块最大的难点是遍历程序的执行，整个地图是不规则的、无法预知的；还有新区域的判定也是一个难点，程序如何知道什么时候正好寻找到了一个新的区域，然后开始进行存储。目前程序暂时解决上面的几个难点，但是设定的比较简单，还不能搜索比较复杂的地形。图4-4 区域存储模块45 无向图构造模块无向图的构造是将之前散落的区域根据其两者的相邻关系拼接起来，同时还保留着原来区域的编号，使用邻接表存储两两之间的相邻关系。每个区域都存储了自己所有的边界，然后判断哪两个区域有公共边，则表示这两个区域是相邻的，同时还要以相邻区域编号为下标存储其公共边，方便接

33、下来的路径寻找。在这个模块中并不关心起点和终点所在的区域，只是对整个地图中的区域进行无向图构造46 路径寻找模块这是整个系统最后的一个模块，起点与终点所在的区域、起点到终点所有的可行路径和最优路径的选择等功能都是在这个模块进行的。在目前的系统中程序还不能实现自动获取起点与终点所在的区域，用户只能在点击完起点和终点后，输入起点与终点所在的区域，然后程序就可以根据之前构造的无向图寻找从起点到终点所有的路径了。从一个区域到其相邻的区域有多条路径可以行走，经过综合的考虑与测试，我们使用了公共边界的中点连线作为可行走路径。所有的路径寻找完成之后，在地图上进行标记，同时在这所有的路径中计算出最优的路径，用

34、特别的颜色进行标识。图4-5 路径寻找模块5 系统实现51 障碍物的拟合在本项目中，障碍物是使用三次贝塞尔曲线进行的拟合。具体实现如下：先算出相邻原始点的中点，再把相邻中点连成的线段平移到对应的原始点，以平移后的中点作为控制点，相邻原始点作为起始点画贝塞尔曲线。由于贝赛尔曲线的特性，使用上面的思路就能保证了连接处的平滑，而贝赛尔曲线本身也是平滑的，那么整体的曲线就是平滑的。程序的主要实现过程是： 获取构成当前障碍物的所有的点的坐标（称为集合a），计算出相邻的两个点的中间点（称为集合b），并将其存储；连接起相邻的中间点，求出相邻的中间点的中间点（称为集合c），集合c中的点与集合a中的点是一一对应

35、的；计算出从集合c中的点与到集合a对应的点的偏移量，然后将集合b中的点移动相同的偏移量，则得到了要求的额外点的坐标。一个障碍物拟合完成的标志是用户点击第一个点的一个范围内，程序则认为该障碍物构造完成。然后用户获取点击的该障碍物的所有的点的坐标，计算额外点的坐标，之后调用画图模块画三次贝赛尔曲线，拟合障碍物；同时为了能够直观地、明确地表示障碍物，我们使用填充的方式画三次贝赛尔曲线，去掉了之前点击的点和画出的线段。程序最终实现的效果如下：图5-1 程序实现的障碍物曲线拟合52 凸极值点的计算求凸极值点的方法很多，但是不一定能够适合本项目。因为本项目中凸极值点的定义与普通的凸极值点的定义不同。普遍意

36、义上我们认为向上凸的极值点称为凸极值点，向下凸的极值点称为凹极值点；但是在本项目中，凸极值点的含义是相对于障碍物来说，这个点是凸出来的还是凹进去的，若是凸出来的则认为是凸极值点，否则认为是凹极值点，跟向上凸或者向下凸没有任何的关系。图5-2 计算出的极值点比如上图（图2），向上凸的点1和点4，只有点1是凸极值点，而点4却不是；向下凸的点2和点3，点2却是凸极值点。因此需要寻找一种新的方式来判断哪些点是凸极值点。经过了多次的验证与测试，我们发现了一个原理：若该点是向上凸的则垂直向下做射线，若该点是向下凸的则垂直向上做射线，如果射线与该障碍物边界的交点是奇数个，则说明该点是凸极值点，否则不是凸极值

37、点。这个原理还没有很好地从数学的角度进行证明，但是通过多次的实践验证，该原理基本上是正确的。局部向上凸的点只有在该点是障碍物的上边界时才是凸极值点，如果该点是在障碍物的下边界，那么就成了凹极值点，同理局部向下凸的点，因此判断这一个点是在障碍物的上边界还是在下边界成为了关键。我们参考了如何判断一个点是否在不规则图形内部问题的解法，在这个问题中，采用的是射线法来判断的，射线法的主要思想是向由该点向x正方向发射一个射线，穿过多边形线段上的个数为奇数则在多边形内，偶数则在多边形外。在本项目中，所有的极值点都在障碍物上，因此交点的个数初始值都是1，为了简化计算，我们设定初始值为0；在局部求出极值点后，我

38、们反方向做的射线，因此如果该点在障碍物的上边界（下边界），必然会至少有一次穿过障碍物的边界，而穿过的次数必然是奇数；假如该点在障碍物的下边界（上边界），那么可能不会穿过障碍物的边界或者穿过偶数次。还有一种特殊的情况，假如射线正好穿过了障碍物的切线点，那么在计算交点个数的时候可能就会出错。我们考虑的解决方案是，在把图形放到极大的情况下时，切线就是由多个小的线段组成的，我们可以计算射线与这些小的选段的交点个数。某一个点是向上凸或者向下凸比较容易判定，只需要对该点与两点的点进行比较即可，然后决定是向下还是向上做射线。不过在实际的程序中，并没有做出射线，而是遍历障碍物边界上所有的点的坐标，比较哪个点的

39、坐标与该点的坐标相等或相近，同时还要判断这个点是在该点的下方或是上方。当然，这里还有一个重要的问题，点的坐标是精确到小数点后4位的，基本上很少有两个点的横坐标或纵坐标是是相等的，因此我们不能直接判断某一点是在该点正上方或者正下方，程序中是用相邻的两点来与该点进行比较。图5-3 凸极值点计算流程图53 水平切线划分区域画水平切线关键是计算出水平切线的两个端点的坐标，而且是要画完所有的障碍物之后才能开始水平切线的计算。程序实现的主要思路是：对某一个凸极值点做水平切线，假设切线的两个端点是地图的边界，也就是离凸极值点最远的点；然后开始遍历所有的障碍物的边界点，判断某一点的位置（该点是否与凸极值点在同

40、一水平线上，是在凸极值点的左边或是右边），若该点符合要求则记录该点，但该点不一定是最后符合要求的，若后面有更符合要求的点则替换该点；遍历完所有的边界点之后就能够寻找到水平切线的左右端点。水平切线的端点有可能在障碍物上，也有可能在在地图的边界上。图5-4 水平切线划分区域程序中实际实现的效果如下：图5-5 程序中实现的水平切线54 区域存储在进行区域存储之前，还需要明确的问题有：区域寻找的方式是什么；如何判定已经找到了一个新的区域，即寻找到新区域的标准是什么；为了能够顺利地执行区域存储，需要哪些准备数据；区域寻找完之后应该得到什么数据。541 区域寻找的方式一个地图中存在的区域的个数与位置完全是

41、任意的，程序在之前是无法得知的。因此我们考虑到使用递归的方式，从边界开始寻找，我们假设有两只爬虫从两边的边界开始爬行，将爬虫经过的点进行标记，直到爬虫没有路径可爬，则递归结束，所有的区域遍历完成。542 新区域的判定标准1） 两只爬虫都爬到了地图的边界，那么刚才经过的区域和地图的边界就构成了一个新的区域；2） 还有就是一个封闭的图形，这种图形只有一个出口的，如果某一边的爬虫重新爬回到了它原来的水平切线上，那么也能证明这是一个新的区域；3） 两只爬虫都爬到了同一条新的水平切线上，那么刚才经过的区域也是一个新的区域，这种情况与第一种很类似，只不过第一种情况是不同接着向下寻找新的区域了，因为它已经到

42、了地图的边界，而这一种还需要判断这条新的切线的性质，接着向下递归。图5-6 新区域的判定标准543 区域存储需要的准备数据在已经明确了区域寻找的方式和判定标准之后，就需要准备使用这种方式的数据了：1） 障碍物边界经过的点的坐标2） 水平切线的凸极值点和两个端点的坐标3） 凸极值点的性质（向上凸还是向下凸）544 区域寻找完之后应得到的数据我们接下来是要构造无向图，那么从这个步骤中应该的到的数据是，每个区域都包含有哪些水平边界。所有的准备工作都准备好后，就可以开始进行遍历了。每次当两只爬虫寻找到某些特殊点（比如水平切线的端点或凸极值点、地图的边界点）的时候，就说明找到了一个新的区域，同时存储该区

43、域所有的水平边界。此时还不能明确区域之间的相邻关系。之后就要判断这个新的水平切线的性质，经过一系列的计算之后开始下一步的遍历工作。这个程序的入口是最上端的两个角的坐标，每一次的递归都会传入下一个区域的两端的坐标值。递归结束后，就能得到每个区域的所有的水平边界。55 构造无向图已经获取了每个区域所有的水平边界的数据，那么就可以根据哪两个区域有相同的水平边界来决定其相邻的关系，我们使用邻接表存储区域的相邻关系，同时还要存储相邻区域的公共边界，为以后路径的寻找做好准备。56 设定权值，确定最优路径设定权值的关键是确定从起点到终点选择怎样的走法作为判定最优路径的标准。经过多次的实验与测试之后，我们决定

44、使用水平切线的中点作为路径中的关键点，将相邻的水平切线的中点连接起来则能够确认一条从起点到终点的路径。用户确定起点和终点所有的数据之后，程序就可以进行路径的寻找了，寻找完所有的路径后，还要在这所有的通路中寻找出一条最优的路径来。图5-7 最优路径寻找流程图程序中首先会默认一个最大值，然后遍历所有的通路，寻找出权值和最小的一条通路。遍历完成之后，则寻找到了最优的路径。程序中实际实现的效果如下（红色路径为最优路径）：图5-8 程序最终的实现结果6 系统测试61 测试说明在完成了所有的编码任务后，系统进入了测试阶段。系统测试是将已经确认的软件、计算机硬件和外设等元素结合在一起，进行信息系统的各种组装

45、测试和确认测试，其目的是通过与系统的需求相比较，发现所开发的系统与用户需求不符或矛盾的地方，从而提出更完善的方案。它的任务是尽可能彻底地检查出程序中的错误，提高软件系统的可靠性，其目的是检测系统做得完美程度。这阶段又分为三个步骤、模块测试，测试每个模块的程序是否有错误；组装测试，测试模块之间的接口是否正确；确认测试，测试整个软件系统是否满足用户功能和性能的要求。测试是产品交付前的最后一关，所有异常重要。该阶段结束应交付测试报告，说明测试数据的选择，测试用例以及测试结果是否符合预期结果。测试发现问题之后要经过调试找出错误原因和位置，然后进行改正。基于系统整体需求说明书的黑河类测试，应覆盖系统所有

46、联合的不建。系统测试是针对整个产品系统进行的测试，目的是验证系统是否满足了需求规格的定义，找出与需求规格不相符或与之矛盾的地方。系统测试的对象不仅仅包括需要测试的产品系统的软件，还要包含软件所依赖的硬件、外设甚至包括某些数据、某些支持软件及其接口等.因此，必须将系统中的软件与各种依赖的资源结合起来，在系统实际运行环境下来进行测试。功能测试：对于系统的功能测试而言，每一个独立的功能模块需要单独的测试的设计，主要依据为需求分析中的功能需求，进行功能的完整性测试，功能性测试。性能测试：系统的性能测试对于系统的运行而言非常重要，但是目前对于算法的性能测试体系还不够完善，我们在进行系统设计时也没有一个很

47、好的基准可以参考，因而建立系统的性能测试是至关重要的。代码合法性测试：主要包括2个部分，程序代码合法性检查与显示代码合法性检查。62 测试内容621 凸极值点的计算输入数据如下，我们点击了一些点拟合出障碍物的边界，预计的输出结果是点1、点3、点5、点6和点8为凸极值点。：图6-1 凸极值点测试数据测试结果为：图6-2 凸极值点测试结果程序的输出结果与预计的一样，说明程序计算准确，没有错误。622 水平切线划分区域输入数据如下，预计的输出结果：程序会在点1、点3、点5、点6和点8处画水平切线：图6-3 已计算出凸极值点的障碍物测试结果为：图6-4 在凸极值点处画完水平切线之后的地图程序的输出结果

48、与预计的一样，说明程序计算准确，没有错误。623 无向图的构造输入数据如下：图6-5 划分完区域之后的地图预计输出结果为：区域0:1、4；区域1:0、2、5；区域2:1、3；区域3:2、4；区域4:0、3；区域5:1程序最终的输出结果：图6-6 无向图的邻接表构造程序的输出结果与预计的一样，说明程序计算准确，没有错误。624 最优路径的寻找输入数据如下，确定起点和终点的坐标与其所在的区域：图6-7 确定起点和终点后的地图预计的输出结果为：从起点到终点应该有0-1-2-和0-4-3两条通路，并且前一条路径相对来说是最优路径。程序的输出结果为：图6-8 寻找所有路径并且标识最优路径图6-9 寻找到的所有路径7 结论与评价通过分析现有的路径规划方案的基础上，从实际的需求出发，搜索相关的资料，进行该算法的设计与改进系统的设计。在进行需求分析、总体设计和模块设计的基础上，采用notepad+作为开发工具。本系统通过了多次的运行及调试，完全满足了设计上的需求。能够实现障碍物的绘制及通路的求取，同时能根据权值求取其中的最优路径，进行显示的控制。该系统具有以下的一些特点：系统的模拟性好。能够满足用户的不可预测性输入，用户的点击是任意的，是不可预测的，因此程序需要能够满足各种输入，防止系统崩溃。开发效率高可移植性好。本系