A New Network Voronoi Diagram Considering the OD Point Density of Taxi and Visual Analysis of OD Flow
Xin Ru · Geo-information Science · 2015
It is very difficult to analyze every vehicle trajectory carefully due to the huge number of data.Therefore, it is necessary to divide the space of one city into a collection of smaller areas, among which we can analyze and exploit the vehicle trajectories. Unfortunately, the existing partitioning methods have many disadvantages which may hinder the progress of our study. For example, some traditional partitioning methods based on the Euclidean distance don't take into account the spatial characteristics of the roads in the city, which may cause a variety of man-made rigid division. Meanwhile, some other partitioning methods ignore the density distribution of taxi's track points. With further research on trajectory data, the use of traditional space partitioning methods has difficulty meeting the demands of spatio-temporal trajectory data analysis. As a result,we propose a new Voronoi subdivision algorithm on road network which considers the density of taxi's OD points and the behavior characteristics of taxis. The main body of the algorithm consists following steps. First,the road network should be divided into a series of edges by their intersections. After that, the edges of the road network are subdivided into small linear units. Next, we produce n×n sized regular grids as the space constraints and choose the generating elements in every grid to make them distributing uniformly in space. Then, we can set different speed values for different generating elements and let them spread to the surrounding roads at different speed. Finally, we can get the road network partitioning results consistent with the density distribution of OD points. A series of city sub- regions can be obtained based on the result of network partitioning. Then, we can analyze the track data in these sub-regions with the help of spatio-temporal data visualization methods, such as color sorting, flow graphs, constructing graph structure, etc. At last, we developed an experimental system to generate the network Voronoi diagram, on which we verify the algorithm and analysis methods presented in this paper by testing with the real Beijing taxi trajectory data of one day. Results of these experiments showed that the information about the trajectory data can be obtained intuitively with the help of network Voronoi diagram and the use of various visualization methods for spatio-temporal data.