文献类型：期刊文章

作　　者：赵俊莉[1,2] 辛士庆[3] 刘永进[4] 王醒策[1] 武仲科[1] 周明全[1] 贺英[5]

机构地区：[1]北京师范大学信息科学与技术学院,北京100875 [2]青岛大学软件技术学院,山东266071 [3]宁波大学信息科学与工程学院,浙江315211 [4]清华大学计算机科学与技术系,北京100084 [5]School of Computer Engineering, Nanyang Technological University

出　　处：《中国科学：信息科学》

基　　金：国家自然科学基金(批准号:61170170;61170203;61271366;61322206)资助项目

年　　份：2015

卷　　号：45

期　　号：3

起止页码：313-335

语　　种：中文

收录情况：BDHX、BDHX2014、CSCD、CSCD2015_2016、JST、RCCSE、ZGKJHX、核心刊

摘　　要：测地线是微分几何中的重要概念,用于描述曲面上两点之间的最短曲线,相当于平面上两点之间的直线段,它在计算机图形学、图像处理、计算几何、计算机视觉等学科中有着广泛的应用.自20世纪80年代以来,关于离散测地线已有广泛研究,众多学者提出了许多切实可行的算法.本文将在介绍光滑曲面上的测地线和离散网格上测地线概念的基础上,对网格模型上的离散最短测地线和最直测地线的定义、性质及相关算法进行归纳总结,重点讨论网格模型上离散最短测地线的相关算法,包括完整网格和有缺陷网格上最短测地线的精确算法和逼近算法,对各类算法进行深入研究,详细论述每个算法的基本思想与实现方法,从多个角度分析每个算法的优缺点,并对他们各自的时间复杂度、空间复杂度及适用范围等进行对比,最后对离散测地线的相关研究进行展望,有利于后续对测地线算法的深入研究.

关 键 词：测地线 测地距离 最短测地线  最直测地线  网格 算法  

分 类 号：O186.1[数学类]