避障路径规划是移动机器人、虚拟仿真、超大规模集成电路、地理信息系统等诸多领域的基本问题。人们对如何快速找到一条从起点到目标点的最优无碰路径进行了多方探索,提出了可视图法、人工势场法、遗传算法等多种避障路径规划算法。本文主要对可视图法及凸点法进行研究。可视图法首先将障碍物的顶点、起始点及目标点用直线组合连接以建立起可视图,要求直线不穿过障碍物内部,即直线“可视”,然后基于可视图采用某种搜索策略找到最优路径。凸点法是用几何方法直接求取最短路径的避障路径规划方法。首先根据起始点、目标点连线上的障碍物生成初始交点集,经排序和简化处理为交点对,交点对将每一障碍物分成了左右两侧路径,然后用绕行方向选取策略选择绕行路径,生成初始路径,最后用搜索记录凸点的方法对初始路径进行优化。文中首先分析了可视图法及凸点法的基本原理,对包围盒检测、线段相交判断、节点凹凸性判定等在凸点法实现过程中涉及到的基础算法进行研究,分析各种特殊情况并给出解决方案。然后在理论分析的基础上对凸点法进行了程序实现。以Shape格式的Polygon数据作为障碍物的环境表达,采用Visual Basic.NET编程实现避障路径规划算法,并结合ArcGIS Engine实现障碍物及生成路径的可视化。在对实现的程序进行测试分析后发现,凸点法对凹凸多边形均适用,能简化障碍物多边形回绕、嵌套等复杂问题,算法效率较高。但凸点法未将全部障碍物考虑在内,不一定能获得全局最优解。同时,其绕行方向选取策略偏重于最靠近起始点的障碍物的绕行方向,容易使最后生成的结果偏离最短路径。最后针对测试结果中反映出的算法缺陷提出改进方案。改进凸点法在初始路径生成时直接选取各障碍物长度较短的一侧路径。生成优化路径后进行二次优化,顺序取用首次优化生成的路径中的各节点为新的起点和终点生成子优化路径,以得到更优路径。改进后的凸点法能找到更短路径,但耗时更久,且同样不一定能找到最短路径。