简化真实感地形中爬行路径设计的算法研究  

Design of Moving Path Based on Simplified Terran

作　　者：杜安红[1] 戴光明[2] 

机构地区：[1]安徽师范大学数学与计算机学院,芜湖241000 [2]中国地质大学计算机科学与技术系,武汉430074

出　　处：《计算机工程与应用》2005年第18期45-47,206,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(编号:60273075);国家高性能计算基金(编号:00301);部委预研基金的联合资助

摘　　要：该文在概括三维路径设计的基础上给出了爬行路径的定义,并且指出了真实感地形中爬行路径规划与点状图中路径规划的区别。文章首先对问题进行了简化,重点是把地形中地物的形状简化成包围其边界的凸多边形包围盒,提出使用改进的Dijkstra算法解决问题思想,并且提出了构造包围盒顶点间关联矩阵的方法。实验结果表明,该方案总能得到简化问题的解,并从理论上证明了解的最优性,具有较大应用价值。This paper gives a definition of moving path based on summing up design of 3D path,and points out design method of moving path in real terran is different from path designing in point graph.This paper simplifies the problem firstly,emphasis is to simplify the shape of object,and seeing encasing box of planar convex polygon as simplified object,and puts forward using Dijkstra Algorithm to solve the problem,but this paper modifies Dijkstra Algorithm,and we present an algorithm of creating linked matrix of vertexes of encasing box.Experiments prove the method can get shortest path,and has preferable applied importance.

关 键 词：路径 非点状图 凸多边形 包围盒 关联矩阵 DIJKSTRA算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]