基于地图代数的最小生成树实现方法  

The algorithm of minimum spanning tree based on map algebra

作　　者：夏兰芳[1] 胡鹏[1] 白轶多[1] 黄梦龙[1] 

机构地区：[1]武汉大学资源与环境科学学院,武汉430079

出　　处：《测绘科学》2008年第1期141-143,共3页Science of Surveying and Mapping

摘　　要：本文介绍了最小生成树及其常见的算法,对比栅格算法分析了基于矢量的最小生成树算法的缺点,介绍了地图代数的距离变换和基于地图代数的距离变换图生成Voronoi图、Delaunay三角网,然后根据最小生成树MST是Delaunay三角剖分的一个子集,逐次删掉Delaunay三角网中每个三角形的最长边,从而得到最小生成树,该方法不仅适用于欧氏非障碍空间,同样也适用于障碍空间的情况,解决了以往最小生成树在障碍空间下(尤其是当障碍空间中的障碍是全形态的条件下)难以求解的问题,具有一定的理论意义。In this paper, the algorithm of minimum spanning tree is introduced firstly.And the disadvantages of vector MST algorithm compared with raster algorithm are analyzed too.At the same time, based on map algebra, map algebra distance transformation and the generation algorithm of Voronoi diagram and Delaunay TIN are provided.With the fact that MST is a subset of Delaunay TIN, the authors conclude that it can be obtained by removing the longest edge of each triangle in the Delaunay TIN.This method can be used in Euclidean space with obstacle or without obstacle, which resolves the MST building problem in space with obstacles, especially with arbitrary obstacles, and has some theoretical significance.

关 键 词：最小生成树 距离变换 VORONOI图 DELAUNAY三角网 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] P282[自动化与计算机技术—计算机科学与技术]