The Solution On Euclidean Space Shortest Path With Obstacles-Map Algebra ESPO

ESPO(Euclidean space Shortest Path with Obstacles) is the generalized issue of Shortest Path issue, which is also the basic key issue in network analysis. It is the basic academic issue in graph theory, S-computational geometry, network design and optimization. Especially, the three-Dimension ESPO is a NP-hard problem, and there are no efficiency solutions of this question up to the present. This dissertation mainly aims at ESPO.In this dissertation, the author analyses the basic features and expression model of spatial data, puts forward the location, neighborhood, nearness and influence conceptions of spatial data, so that consummates the description of spatial relation. According to the difficulties meeting with performing the initialization of spatial data based on vector data: the complexity in spatial data expressing and the huge cost of storage and operation, not fit for the need of continuous dynamic geographical analysis, spatial complexity theory is given as a whole in GIS spatial analysis.It also discusses a new type of spatial data model tightly binding vector with raster. The model uses vector as framework while raster for calculation, and easily interchanges raster and vector whenever needed. All of above build a new GIS construction method. The feasibility, dynamic feature, criterion of it later is discussed to entirely resolve spatial issues. A new method changing raster data to vector of Map Algebra together with the traditional method changing vector data to raster construct the support techniques of vector-raster interchange. Basing on the techniques of 3D shape set operation, 3D point set critically plotting and the complex 3D ESPO spatial analysis, the author gives the experiments to demonstrate his results on some key issues.The method of MA-ESPO is given in this dissertation. Both in theory and in experiments, MA-ESPO can completely resolve 2D and 3D ESPO. Further more, obstacles, source shapes and destination shapes in MA-ESPO can be shapes in all form. It's the generalized solution of the famous method Dijkstra. MA-ESPO method bases on the theory of Map Algebra Raster Route Distance Transformation. It's theoretically demonstrated that MA-ESPO can effectively realize the shortest path in specified precision in any limited obstacle space. The arithmetic realizes a template (2k+l)3 and a automatism together with k(plus integer) dynamic increase, so that ensures subsection and division in huge area on either theory or technique. Time complexity of MA-ESPO is O(kn) (k is a small invariable decided by the template size of area) while storage complexity is O(n).The integrative software of MA-ESPO has been developed to validate generalized ESPO : 30002 pixels in 2D area and 2003 in 3D area.Performance of MA-ESPO on universality of graph, initialization, time and storage complexity is obviously better than performance of other kindred methods of 2D ESPO while there are no other methods dealing with 3D ESPO up to the present.Correspond to MA-ESPO, MA-DTO (Map Algebra-Distance Transformation with Obstacles) that actually generates all distance toward fountain of all points in the whole obstacle space is given at last. It prepares the key work of finding shortest path for all points in the space, thereby comes to be the key technique for Voronoi generation of all-kind shapes in E2 or E3 obstacle space. Ditto there are no other kindred methods up to the present.