Auto-generation of a centerline graph from the geometrically complex roadmap of real-world traffic systems using a hierarchical quadtree for cellular automata simulations

Abstract

This paper proposes a method of auto-generation of a centerline graph from the geometrically complex roadmap of real-world traffic systems by using a hierarchical quadtree for cellular automata simulations. Our method is summarized as follows. At first, we store the binary values of the monochrome image of targeting roadmap (one and zero represent the road and the other areas respectively) in the two-dimensional square map. Second, we recursively divide the square map into sub-leafs by a quadtree until each leaf has equal or less than one. Third, we keep removing the distal leaves which adjacent to the leaves whose depth are shallower than the distal leaf, until one step before the distal leaf does not connect to any stable leaves. After that, we trace the remaining distal leaves of the tree using Morton's space-filling curve, while selecting the leaves which keep a certain distance among the previously selected leaves as the nodes of the graph. Finally, each selected node searches the neighboring nodes and stores them as the edges of the graph. We demonstrated our method by generating a centerline graph from a complex roadmap of a real-world airport and by carrying out a typical network analysis using Dijkstra's method.