The method for indexing global-scale 3D vector data with R-tree based on approximate prism

Indexing global-scale 3D vector data is a challenging task because more and more vector datum is used to analyze global problems. Various indices of 2D vector based on tree or grid structures have been approached. Although these indices may support 2D vector indices effectively, they do have some significant drawbacks for indexing global-scale 3D vector, such as critical spatial overlapping, unstable query performance etc. To overcome these deficiencies, a new spatial index for improving the speed of accessing spatial data based on R-tree and approximate prism is developed in this paper. Our approaches start with a method for constructing approximate prism based on 2D convex hull of vector. Then, the process of querying operation is described. Next, an application case by using this index for managing 3D vector data is presented. In the end, the experiment is done to test the discussed algorithms and methods above by using of 1:1,000, 000 china road data and GTOPO30 data. The result indicates: the query speed of vector is improved rapidly by suing approximate prism index; the consuming time is 60–80% of R-tree index based on minimal bounding box and the spatial overlapping of querying operation is also obviously reduced.