顾及出租车OD点分布密度的空间Voronoi剖分算法及OD流可视化分析

为对城市各区域出租车OD轨迹流进行可视化分析,需对城市作空间剖分处理,以产生研究所需的子区域。传统的欧氏距离空间剖分方法,在空间上进行硬性切割不能有效地顾及城市人、物的时空流动模式,因此,本文提出了一种空间约束条件下,顾及出租车OD点分布密度的网络Voronoi剖分方法。首先,将道路网的边细分成线性单元,然后,设定空间约束以产生合适的发生元,让各发生元在路网上以线性单元为单位扩散步长,以不同的速度向周围联通道路进行扩散,最终将城市空间划分成一系列与出租车OD点分布密度相适应的空间子区域。利用OD流可视化理论与技术,基于划分的城市子区域分析出租车在这些区域的时空流动,并结合图论知识探究城市空间OD流拓扑图结构的变化,分析不同划分区域出租车流动模式。最后,通过北京地区一天的出租车轨迹数据,对本文提出的算法及分析方法进行了实验。

A New Network Voronoi Diagram Considering the OD Point Density of Taxi and Visual Analysis of OD Flow

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.