欧氏障碍空间的最短路径问题解法

Solution of Euclidean Shortest Path Problem Space with Obstacles

提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间下距离变换方法(MA-DTO),其简便地生成了整个障碍空间所有点的趋源距离,从而成为E2生成所定义障碍空间下各任意形态图形的Voronoi图的实际方法。

MA-ESPO method was put forward. Both in theory and in experiments, MA-ES- PO can completely resolve 2D ESPO in raster method. Further more, obstacles, source shapes and destination shapes in MA-ESPO can be shapes in all form. It＇s the generalized solution of the method Dijkstra. MA-DTO （map algebra-distance transformation with obsta- cles） that actually generates all distance toward fountain of all points in the whole obstacle space was given at last. This method prepares the key work of finding shortest path for all points in the space, thereby comes to be the keytechnique for Voronoi generation of arbitrar ily shaped figures in E2 obstacle space.