首页 | 本学科首页   官方微博 | 高级检索  
     

三角网格模型上任意两点间的近似最短路径算法研究
引用本文:张丽艳,吴熹.三角网格模型上任意两点间的近似最短路径算法研究[J].计算机辅助设计与图形学学报,2003,15(5):592-597.
作者姓名:张丽艳  吴熹
作者单位:南京航空航天大学CAD/CAM工程研究中心,南京,210016
基金项目:国家自然科学基金 (60 2 730 97),江苏省自然科学基金 (BK2 0 0 14 0 8),南京航空航天大学创新科研基金 (S0 2 72 0 5 4)
摘    要:提出一种任意三角网格模型上两点间的近似最短路径算法.该算法首先将三角网格模型表示为带权图结构,然后用Dijkstra算法计算带权图中两顶点间的最短路径,并将其作为网格模型上该两点间最短路径的初始近似.通过不断地迭代对相关三角形边进行自适应细分,并构造每次细分后新的带权图,从而对网格模型上的两点间最短路径进行迭代逼近.该算法效率高,可以很好地控制精度,适用于大型三角网格模型两点间最短路径寻找.文中还讨论了该算法在任意三角网格模型区域划分中的应用.

关 键 词:计算机图形学  三角网格模型  近似最短路径算法  Dijkstra算法  图形显示
修稿时间:2002年10月23

Approximate Shortest Path on Triangular Mesh Surface
Zhang Liyan,Wu Xi.Approximate Shortest Path on Triangular Mesh Surface[J].Journal of Computer-Aided Design & Computer Graphics,2003,15(5):592-597.
Authors:Zhang Liyan  Wu Xi
Abstract:The triangle mesh model is represented by a weighted graph structure and Dijkstra's algorithm is used to calculate the shortest path between two points on the graph By iteratively subdividing the related triangle edges and constructing new weighted graph, the shortest path between points on the graph finally approaches the shortest path on the mesh surface The algorithm is highly efficient, and quite suitable for the shortest path finding of large scale models Application of the algorithm in model segmentation is also demonstrated
Keywords:computer graphics  mesh surface  approximate shortest path
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号