A modified binary space partitioning tree for geographic information systems

We present a reactive data structure, that is, a spatial data structure with detail levels. The two properties, spatial organization and detail levels, are the basis for a geographic information system (GIS) with a multi-scale database. A reactive data structure is a novel type of data structure catering to multiple detail levels with rapid responses to spatial queries. It is presented here as a modification of the binary space partitioning tree that includes the levels of detail. This tree is one of the few spatial data structures that does not organize space in a rectangular manner. A prototype system has been implemented. An important result of this implementation is that it shows that binary space partitioning trees of real maps have O(n) storage space complexity in contrast to the theoretical worst case O(n² ), with n the number of line segments in the map.     

A multiple representation data structure for dynamic visualisation of generalised 3D city models

In this paper, a novel multiple representation data structure for dynamic visualisation of 3D city models, called CityTree, is proposed. To create a CityTree, the ground plans of the buildings are generated and simplified. Then, the buildings are divided into clusters by the road network and one CityTree is created for each cluster. The leaf nodes of the CityTree represent the original 3D objects of each building, and the intermediate nodes represent groups of close buildings. By utilising CityTree, it is possible to have dynamic zoom functionality in real time. The CityTree methodology is implemented in a framework where the original city model is stored in CityGML and the CityTree is stored as X3D scenes. A case study confirms the applicability of the CityTree for dynamic visualisation of 3D city models.