Generation of constrained network Voronoi diagram using linear tessellation and expansion method: Fid-Bau Portal

Generation of constrained network Voronoi diagram using linear tessellation and expansion method

Ai, Tinghua / Yu, Wenhao / He, Yakun

Highlights • Constructing the network Voronoi diagram by linear segmentation and expansion under network space. • Considering multiple urban movement factors impacting on VD and generating the constrained VD. • The algorithm is more efficient compared with the traditional Dijkstra’s based algorithm.

Abstract As a well-known geometric construction, Voronoi diagrams play an important role in applications of location-based services, such as accessibility analysis and nearest route detection. Because the movement in urban areas is constrained by the street network under certain transformation conditions, it is necessary to construct a new type of Voronoi diagram based on the network path distance rather than the conventional Euclidean distance. This study presents a constrained network Voronoi diagram using stream flowing ideas. A new distance, the “lixel distance”, is defined to measure the travel cost by subdividing the edge into small linear segments constrained by travel speed and other traffic conditions. Based on the stream of flowing ideas, the algorithm lets all studied source streams spread over the network paths until meeting other streams or arriving at the end of an edge. This process is similar to the expansion operation in the raster geo-processing of Euclidean space. By comparison with the previous approaches in a static environment, this algorithm can be applied to accurately estimate service areas for facilities in real time and to easily add constraints of movement and traffic, such as one-way traffic and restricted street access. The experiment on real POI data to find the service areas in Guangzhou city, China shows that the proposed algorithm is efficient and effective.