Auto-generation of centerline graphs from geometrically complex roadmaps of real-world traffic systems using hierarchical quadtrees for cellular automata simulations

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. (C) 2019 Elsevier Inc. All rights reserved.