| 多面体面上任意两点间最短路径算法 |
| |
| 引用本文： | 周培德.多面体面上任意两点间最短路径算法[J].北京理工大学学报,2005,25(4):332-336. |
| |
| 作者姓名： | 周培德 |
| |
| 作者单位： | 北京理工大学,信息科学技术学院计算机科学工程系,北京,100081 |
| |
| 摘 要： | 提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).
|
| 关 键 词： | 多面体面 最短路径算法 嵌入平面 三角形串 时间复杂性 多面体面 任意两点 最短路径算法 Surface the Shortest Path 时间复杂性 平面 旋转 三角形串 法线 法则 方法 折线 思想 近似算法 计算 |
| 文章编号： | 1001-0645(2005)04-0332-05 |
| 收稿时间： | 2004/5/19 0:00:00 |
| 修稿时间： | 2004年5月19日 |
Algorithms for the Shortest Path Between Two Arbitrary Points on a Polyhedral Surface |
| |
| ZHOU Pei-de.Algorithms for the Shortest Path Between Two Arbitrary Points on a Polyhedral Surface[J].Journal of Beijing Institute of Technology(Natural Science Edition),2005,25(4):332-336. |
| |
| Authors: | ZHOU Pei-de |
| |
| Institution: | Department of Computer Science and Engineering,School of Information Science and Techndogy, Beijing Institute of Technology, Beijing100081, China |
| |
| Abstract: | Three algorithms are presented for computing the shortest path between two arbitrary points on a polyhedral surface: One is an approximate algorithm; the other two can obtain the shortest path or an approximately shortest path. The approximate algorithm is to adopt a method for which the broken lines are constantly embedded in a series of triangles, whereas the other two are to find a series of triangles by using a specific normal line, and these triangles are rotated onto the same plane so as to obtain the shortest path. The time complexity of the former is O(n), but the time complexities of the latter two are O(n~2) and lower than O(2~nn~2) respectively. |
| |
| Keywords: | polyhedral surface shortest path algorithm embedded plane a series of triangles time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
| 点击此处可从《北京理工大学学报》下载免费的PDF全文 |
