一种基于Dijkstra算法的三角网格地表模型算法.pdfVIP

第29卷 第3期 江 西 科 学 V01．29No．3 2011年6月 JIANGXI SCIENCE Jna ．201l 文章编号：1001—3679(2011)03—0387—04 一 种基于Dijkstra算法的三角网格地表模型算法 谢 璞，黎敬涛 (昆明理工大学信息工程与自动化学院，云南 昆明650000) 摘要：对二维地表模型运用Dijkstra算法求解最短路径时，为了减少计算量，需要对模型进行简化后，才开始 进行Dijkstra算法的求解，所以结果并不符合实际地表情况。不在模型上进行任何简化，而是直接在模型上 划分三角网格来处理最原始的模型。然后用基于Dijkstra算法和矢量夹角的三角网格地表模型算法求解最 短路径。通过此算法完成了一个实例的最短路径求解。结果表明，采用文中算法所得到的结果符合Dijkstra 算法求得的路径和实际情况，而复杂度并没有因为未简化模型而大幅上升，并且算法具有效率高、复杂度低、 稳定性好等优点。 关键词：三角网格地表模型算法；Dijkstra；三维网格 ；矢量夹角 中图分类号：TP301．6 文献标识码 ：A ATriangularMeshSurfaceModelAlgorithm BasedonDijkstraAlgoritmh XIEPu．U Jing—tao (InstituteofInformationEngineeringandAutomation， KunmingUniversityofScienceandTechnology，YtmnanKunming650000PRC) Abstract：TheUSeoftwo—dimensionalsurfacemodeloftheDijkstrashortestpathalgorihtm，inorder toreducethecomputationalload，hteneedforsimplifiedmodelsbeforestartinghteDijkstraalgorihtm tosolve．SOhteresultsarenotconsistentwiht theactualgroundsituation．rhepaperdoesnotmake anysimplifiedmodel，butdirecdydividetriangularmeshonmodeltodealwihtthemostprimitiveof htemode1．Then，usetriangularmeshsurfacemodelalgorithmwhichbasedonDijkstraalgorihtmand vectornagleot solvehteshortestpaht．Inhtepaper，allinstanceof theshortestpaht solutioniscom— pletedbyhtealgorihtm． eresultsshowhtathtisalgorihtm isconsistentwiht hteresultsobtainedhte pahtobtainedbyDijkstraalgorithmandtheactualsiutation，nadhtecomplexityofhtealgorithmis notsignificantlyincreasedbecauseofnosimplificatieation，andhtealgorihtmhavehtebenefitofhi出 effieieney，complexlow，stableand80no． Keywords：Trianuglarmeshsurfacemodelalgorihtm，Dijkstra，3dmesh，Vectorangle o艏 萎 譬