摘要
介绍了障碍空间下的最小生成树实现方法。首先采用零初始化的思想,初始化'位'数据;然后在构建障碍空间下实体点的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.
出处
《武汉大学学报（信息科学版）》
EI
CSCD
北大核心
2009年第1期60-63,共4页
Geomatics and Information Science of Wuhan University
基金
国家自然科学基金资助项目(40471107)
