Auto-generation of centerline graphs from geometrically complex roadmaps of real-world traffic systems using hierarchical quadtrees for cellular automata simulations
Auto-generation of centerline graphs from geometrically complex roadmaps of real-world traffic systems using hierarchical quadtrees for cellular automata simulations
复制标题
DOI：
10.1016/j.ins.2019.07.049
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Satori Tsuzuki;D. Yanagisawa;K. Nishinari
中科院分区：
文献类型：
--
作者：
Satori Tsuzuki;D. Yanagisawa;K. Nishinari
本文提出了一种使用分层四叉树从现实世界交通系统的几何复杂路线图自动生成中心线图的方法，用于元胞自动机模拟。我们的方法总结如下：首先，我们将目标路线图的单色图像的二进制值（其中1和0分别代表道路和其他区域）存储在二维方形地图中。其次，我们使用四叉树递归地将方形图划分为子叶，直到每个叶内包含的像素值之和小于或等于 1。第三，我们依次去除邻近叶子深度较浅的远端叶子。第四，我们使用莫顿空间填充曲线追踪树的剩余远端叶子，同时在之前选择的叶子中选择保持一定距离的叶子作为图的节点。最后，每个选定的节点搜索相邻节点，并将这些节点存储为图的边。我们通过从真实机场的复杂路线图生成中心线图并使用 Dijkstra 方法执行典型网络分析来演示我们的方法。
This paper proposes a method for auto-generating centerline graphs from geometrically complex roadmaps of real-world traffic systems for cellular automata simulations, using hierarchical quadtrees. Our method is summarized as follows: First, we store the binary values of the monochrome image of the target roadmap (where one and zero represent the road and other areas, respectively) in a two-dimensional square map. Second, we recursively divide the square map into sub-leaves using a quadtree, until the sum of the values of pixels included inside each leaf becomes less than or equal to one. Third, we successively remove the distal leaves for which adjacent leaves have shallower depths. Fourth, we trace the remaining distal leaves of the tree using Morton’s space-filling curve, while selecting the leaves among those selected previously that preserve a certain distance as the nodes of the graph. Finally, each selected node searches the neighboring nodes, and these are stored as the edges of the graph. We demonstrate our method by generating a centerline graph from a complex roadmap of a real-world airport, and by performing a typical network analysis using Dijkstra’s method.