A Hierarchical Proximity Search Algorithm Based on Voronoi Diagram

摘要

In the paper, space partition can filter out a lot of useless information in the search process, so it can increase the search efficiency. According to the problems that the large-scale road network partition more layers, prctreatment time consumption and storage space has more, current search methods are difficult to be directly applied to the large-scale road network. To solve this problem, a hierarchical proximity search algorithm based on Voronoi diagram is proposed. Using the Voronoi diagram immediately adjacent properties and the space division, first, the space of road network is divided in accordance with the density of road network, and then solving the adjacency relationship between the respective regions, the search is limited in scope with the target object with the adjacent relation. At last, using Dijkstra algorithm solves the optimal path between the starting point and the ending point in these connected regions. Examples to verify the efficiency of the proposed method.