A Quadtree Spatial Index Method with Inclusion Relations and Its Application in Landcover Database Update

Received: 20 February 2019 Accepted: 18 May 2019 Landcover database often has numerous nonuniform polygons that contain thousands of holes, and even nesting holes. During incremental update, the new changed polygon is used to clip the base state complex polygons, and may intersect a few holes in the latter ones. The traditional update tools, mainly clipping algorithms, must traverse all the holes of complex polygons, which seriously affects the update efficiency. To solve the problem, this paper improves the quadtree spatial index considering the inclusion relations between polygons. In this method, the polygons are divided into two categories: intersecting polygons (intersecting the quadrant axes) and disjointed polygons (disjoint to the quadrant axes). The intersecting polygons are stored on the root nodes on different levels, while the disjointed polygons are stored in the leaf nodes on the index tree. Then, the author introduced the construction of the spatial index and the table of inclusion relations, and explained the operations of the improved quadtree spatial index, namely, insertion, deletion and query. After that, the proposed method was applied to the incremental update of landcover database, and compared with the MX-CIF quadtree index through experiments. The results show that the update efficiency of our method was several times better than that of the contrastive method, and that the efficiency of our method increased with the data volume and complexity.