A Study on Selecting the Shortest Routes by Voronoi Diagram in Route Networks of GIS

摘要

The problems of fast determining shortest paths through a polygonal subdivisionplanar with n vertices are considered in GIS. Distances are measured according to an Euclideanmetric. A geographical information system (GIS)has a collection of nearest neighborhoodoperations and this collection serves as a useful toolbox for spatial analysis. These operationsare undertaken through the Voronoi diagrams. This paper presents a novel algorithm thatconstructs a “shortest route set” with respect to a given source point and a target point byVoronoi diagrams. It will help to improve the efficiency of traditional algorithms, e. g. , Djkstraalgorithm, on selecting the shortest routes. Moreover, the novel algorithm can check theconnectivity in a complex network between the source point and target one.