空间数据的零初始化与障碍空间下的最小生成树实现方法  

Zero Initialization of Spatial Data and Minimum Spanning Tree Algorithm in Presence of Arbitrary Obstacles

作　　者：夏兰芳[1,2] 胡鹏[1,2] 黄梦龙[1,2,3] 

机构地区：[1]武汉大学资源与环境科学学院,武汉市珞喻路129号430079 [2]武汉大学地理信息系统教育部重点实验室,武汉市珞喻路129号430079 [3]福建省基础地理信息中心,福州市华林路205号350003

出　　处：《武汉大学学报（信息科学版）》2009年第1期60-63,共4页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金资助项目(40471107)

摘　　要：介绍了障碍空间下的最小生成树实现方法。首先采用零初始化的思想,初始化'位'数据;然后在构建障碍空间下实体点的Voronoi图的基础上,通过障碍空间下的回溯算法得到实体点间的最近连通图,也即障碍空间下实体点之间的Delaunay图;最后根据连通图,采用贪婪策略来得到最小生成树。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.

关 键 词：零初始化 障碍 VORONOI图 Delaunay图 最小生成树MST 

分 类 号：P208[天文地球—地图制图学与地理信息工程]