地表模型上的最短路径算法研究

An Algorithm for the Shortest Path on DTM

本文提出了一种基于空间三角网格表示的地表模型上的最短路径算法,该算法利用离散点的空间信息计算得到起点到周围邻接点的最短距离,然后利用逐步向外层边界扩展的方法扩大起点的邻接点范围,直到起点的邻接点中包含终点,此过程可求得s0到t0的最短路径上的关键点,然后求取无原始边连接的两个关键点之间的精确路径点。

This article is designated to an algorithm to get the shortest path on the triangle grid in 3D space. Based on the information of vertexes in 3d space, the shortest distance between s0 and its adjacency vertexes can be first computed. With the gradual expansion of the scope of adjacency vertexes till t0 is in adjacency vertexes set, both the key vertexes on the shortest path from s0 to t0 and the exact vertexes on the shortest path between the two key vertexes can be computed.