Quadtree construction method for storing polygon inclusion relation and indexing method

Abstract

The invention discloses a quadtree construction method for storing polygon inclusion relations and an indexing method. The construction method comprises the following steps: constructing a quadtree for storing the inclusion relation of polygons, establishing a rule for judging the inclusion relation between polygon objects, and identifying the parent-child inclusion relation between complex polygons and polygons surrounded by inner rings of the complex polygons; meanwhile, the polygons corresponding to the nodes in the quadtree are stored in barrels; indexing is carried out based on the constructed quadtree; the invention provides an implementation process of polygonal object query, deletion and insertion processes. Based on the constructed inclusion relation and the bucket storage characteristics, the query, deletion and insertion efficiency of the polygon object is greatly improved. Meanwhile, a technical support is provided for quickly determining an inner ring where the incrementalpolygon and the ground state polygon intersect in the incremental updating application process.

Description

technical field [0001] The invention belongs to the technical field of spatial data management and application, and in particular relates to a quadtree construction method and an indexing method for storing polygon inclusion relations. Background technique [0002] The discovery and effective update of land cover change is one of the hot research issues in recent years. Land cover data is divided into raster data and vector data. Since the raster data format does not directly store information such as the shape, size, and attributes of the target individual, it cannot meet the application needs of the majority of users. Therefore, global land cover vector data is ready to come out. However, there are a large number of complex polygons containing thousands of holes in the land cover vector data, and the nesting relationship between these polygons is complex. In the process of quality control and update of land cover vector data, the change pattern must overlap with one or mo...

AI Technical Summary

Problems solved by technology

However, the current spatial data index method is based on the index built for the outer ring of the polygon, and there is no nested relationship index between complex polygons that contain holes.

[0004]However, in the existing index mode, the application of land cover change conflict detection and update processing needs to calculate the topology of the change map, the ground state polygon and each hollow polygon In relational cases, the computational work is extremely complex for complex polygons containing tens of thousands of holes

Images