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

本文介绍了最小生成树及其常见的算法,对比栅格算法分析了基于矢量的最小生成树算法的缺点,介绍了地图代数的距离变换和基于地图代数的距离变换图生成Voronoi图、Delaunay三角网,然后根据最小生成树MST是Delaunay三角剖分的一个子集,逐次删掉Delaunay三角网中每个三角形的最长边,从而得到最小生成树,该方法不仅适用于欧氏非障碍空间,同样也适用于障碍空间的情况,解决了以往最小生成树在障碍空间下(尤其是当障碍空间中的障碍是全形态的条件下)难以求解的问题,具有一定的理论意义。

The algorithm of minimum spanning tree based on map algebra

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.