夏兰芳, 胡鹏, 黄梦龙. 空间数据的零初始化与障碍空间下的最小生成树实现方法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(1): 60-63.
引用本文: 夏兰芳, 胡鹏, 黄梦龙. 空间数据的零初始化与障碍空间下的最小生成树实现方法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(1): 60-63.
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): 60-63.
Citation: 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): 60-63.

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

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

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

     

    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.

     

/

返回文章
返回