2D arrangement-based hierarchical spatial partitioning: An application to pedestrian network generation

This paper addresses the creation and maintenance of partitions of city surfaces for mapping and transportation applications. It proposes a hierarchical spatial surface partitioning, encoding the spatial partition with a 2D arrangement and structuring a generic hierarchy of semantic objects with a directed acyclic graph (DAG), in which the leaves point to the partition elements (polygonal regions, line strings, points). Semantic objects such as buildings, sidewalks and roads are described by grouping other objects and partition elements with their semantic relationships. In the proposed generic data model, geometry and spatial relationships of the semantic objects are respectively described by the geometry and topology of the planar partition. The proposed geometric data structure for creating and maintaining this partition is a 2D arrangement. In addition, the hierarchical object model encodes the thematic and semantic relationships between the objects. Besides the data model, methods and algorithms are discussed for leveraging existing vector datasets to create and maintain such partitions. These partitions are then fit to further processing and analysis using computational geometry and graph theory algorithms. For this purpose, three application-wise generic algorithms were integrated into our system called Streetmaker: two skeleton operators for centerline generation (straight skeleton and medial axis) and connectivity graphs for itinerary calculations. Moreover, specific algorithms can be integrated into Streetmaker for specific applications. We demonstrated an example usage of this framework for generating static obstacle avoiding pedestrian network graphs. The representation of the network graph and the process used to generate it, can be considered as the second contribution of our work besides the proposed data model.