| 基于CSR存储的三维网格最短路径算法 |
| |
| 引用本文： | 孙晓鹏,李华. 基于CSR存储的三维网格最短路径算法[J]. 计算机工程与应用, 2005, 41(10): 5-7 |
| |
| 作者姓名： | 孙晓鹏 李华 |
| |
| 作者单位： | 中国科学院计算技术研究所智能信息处理重点实验室,北京,100080;中国科学院研究生院,北京,100039;中国科学院计算技术研究所智能信息处理重点实验室,北京,100080 |
| |
| 基金项目： | 国家973重点基础研究发展规划(编号:G2004CB318000)，国家863高技术研究发展计划项目(编号:2001AA231031,2002AA231021)，国家科技攻关计划课题奥运科技专项(编号:2001BA904B08)，中国科学院知识创新工程项目(编号:20006160,20016190(C)) |
| |
| 摘 要： | 论文针对数据组织结构导致Dijkstra算法的存储空间、邻接关系检索效率等关键问题,介绍了相关研究工作。并针对三维网格模型的邻接关系为稀疏图这一要点,基于三维网格模型的CSR存储结构,给出了记录Dijkstra最短路径的算法。该文算法返回了最短路径长度,记录最短路径上点集,充分利用了中间计算结果。
|
| 关 键 词： | CSR存储结构 最短路径 Dijkstra算法 三维网格模型 |
| 文章编号： | 1002-8331-(2005)10-0005-03 |
| 修稿时间： | 2005-01-01 |
A Shortest Path Algorithm Based-on Compressed Storage Format of 3D Mesh |
| |
| Sun Xiaopeng,Li Hua. A Shortest Path Algorithm Based-on Compressed Storage Format of 3D Mesh[J]. Computer Engineering and Applications, 2005, 41(10): 5-7 |
| |
| Authors: | Sun Xiaopeng Li Hua |
| |
| Affiliation: | Sun Xiaopeng1,2 Li Hua11 |
| |
| Abstract: | In this paper,we focus on the key problems of Dijkstra algorithm,memory and index of adjacency.After a brief introduction of related researches,we present a novel implementation of Dijkstra algorithm based on CSR data structure of 3D mesh model's sparse matrix adjacency.The length of the shortest path and the data set in the path is recoded,and the middle result is reused to save the computing source. |
| |
| Keywords: | CSR data structure shortest path Dijkstra algorithm 3D mesh model |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
