| 空间数据的零初始化与障碍空间下的最小生成树实现方法 |
| |
| 引用本文： | 夏兰芳,胡鹏,黄梦龙.空间数据的零初始化与障碍空间下的最小生成树实现方法[J].武汉大学学报(信息科学版),2009,34(1). |
| |
| 作者姓名： | 夏兰芳 胡鹏 黄梦龙 |
| |
| 作者单位： | 武汉大学资源与环境科学学院，武汉大学地理信息系统教育部重点实验室，福建省基础地理信息中心 |
| |
| 摘 要： | 介绍了障碍空间下的最小生成树实现方法。首先采用零初始化的思想,初始化"位"数据;然后在构建障碍空间下实体点的Voronoi图的基础上,通过障碍空间下的回溯算法得到实体点间的最近连通图,也即障碍空间下实体点之间的Delaunay图;最后根据连通图,采用贪婪策略来得到最小生成树。
|
| 关 键 词： | 零初始化 障碍 Voronoi图 Delaunay图 最小生成树MST |
Zero Initialization of Spatial Data and Minimum Spanning Tree Algorithm in Presence of Arbitrary Obstacles |
| |
| XIA Lanfang,HU Peng,HUANG Menglong.Zero Initialization of Spatial Data and Minimum Spanning Tree Algorithm in Presence of Arbitrary Obstacles[J].Geomatics and Information Science of Wuhan University,2009,34(1). |
| |
| Authors: | XIA Lanfang HU Peng HUANG Menglong |
| |
| Abstract: | A raster algorithm of minimum spanning tree in space with obstacles is described.Firstly,with the idea of zero initialization,location data,including entity point,obstacle point and ordinary spatial point,are initialized.Secondly,the nearest connected graph in space with obstacles,also known as the Delaunay graph,is gained by trace back algorithm on the basis of Voronoi graph.Lastly,minimum spanning tree is gained by greedy strategy according to the nearest connected graph. |
| |
| Keywords: | zero initialization obstacle Voronoi graph Delaunay graph minimum spanning tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
