基于Dijkstra距离剪枝的测地线求解算法  

Dijkstra-based Pruning Geodesic Algorithm

作　　者：周竞文[1] 程志全[1] 金士尧[1] 

机构地区：[1]国防科技大学计算机学院PDL重点实验室,长沙410073

出　　处：《系统仿真学报》2009年第S1期141-144,共4页Journal of System Simulation

基　　金：国家自然科学基金(60707030)

摘　　要：在计算机图形学领域,测地线有着广泛的应用,但其计算过程是低效的,常常需要用近似值来代替。2005年,Surazhsky等人提出了一种基于三角网格模型的精确算法,用来计算任意点到源点的测地线,该算法较为实用,但对于很多情况,其所做的大部分运算是没有意义的。为此,结合Dijkstra距离,给出一种基于精确算法的剪枝算法,用来计算任意两点间的测地线,这能在一定程度上提高精确算法的效率。In the field of computer graphics, the geodesic is widely used. But its computation is inefficient so that many researchers have to use approximate value to instead the exact one. An exact algorithm was proposed by Surazhsky and his coworkers in 2005. This algorithm bases on triangle mesh. It could calculate the geodesic from sources to arbitrary vertices. This algorithm is practical. However, in many case, a large number of results during computation in this algorithm are useless. With the Dijkstra algorithm, it may give a pruning algorithm bases on the exact algorithm used to calculate the shortest path between two arbitrary vertices. It improves the exact algorithm in a certain extent.

关 键 词：测地距离 最短路径 DIJKSTRA算法 剪枝 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]