一种存储复杂多边形包含关系的四叉树索引  

A Quadtree Spatial Index Method with Inclusion Relations for Complex Polygons

作　　者：汪红松[1] 周晓光[1] WANG Hongsong;ZHOU Xiaoguang(School of Geosciences and Info-Physics,Central South University,Changsha 410083,China)

机构地区：[1]中南大学地球科学与信息物理学院,湖南长沙410083

出　　处：《湖南大学学报（自然科学版）》2020年第4期99-109,共11页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金资助项目(41371366)。

摘　　要：地表覆盖/土地利用矢量数据中存在大量包含成千上万个空洞(甚至嵌套空洞)的复杂多边形,现有空间数据索引没有表达复杂多边形及其空洞之间的包含关系,导致空间数据冲突检测与更新等处理存在计算量大、效率低等问题.针对此问题,提出了一种存储多边形包含关系的四叉树索引方法.该方法根据结点中的多边形与四叉树相应象限中轴线相交的方式将多边形对象分为5种类型,即仅与X正轴相交、仅与X负轴相交、仅与Y正轴相交、仅与Y负轴相交以及与XY轴都相交,并将这些多边形对象分别存储在相应层次索引结点中的5个子列表(桶)中,然后在结点多边形对象中存储多边形之间的父子包含关系.最后设计并实现了该索引及相应的查询、插入、删除等算法,并用实际地表覆盖数据验证了本文方法的有效性.实验结果表明,采用本文索引方法的复杂地表覆盖矢量数据增量更新效率数倍于现有四叉树索引方法,且随着数据量的增加效率提高更明显.There are a large number of complex polygons containing thousands of holes(or even nested holes)in the land cover/land use vector data,and the existing spatial data indexing method has failed to indicate the inclusion relationship between complex polygons and their holes,resulting in computationally heavy and inefficient processing such as spatial data conflict detection and updating.In order to solve this problem,an improved quadtree spatial index method with inclusion relations of the complex polygons is presented in this paper.The method classifies the polygons in the nodes into five types according to the way they intersect the axes in the corresponding quadrant of the quadtree,i.e.,intersect only the X positive axis,intersect only the X negative axis,intersect only the Y positive axis,intersect only the Y negative axis,and intersect both X and Y axes,and stores each of these polygons in five sublists(buckets)in the corresponding hierarchical index nodes,and then stores the parent-child inclusion relationship between the polygons in the node polygon objects.The authors developed the spatial index structure with inclusion relations and the algorithms of the corresponding operations(e.g.,insert,delete and query)for the complex polygons.The effectiveness of the approach in this paper is verified by an experiment of land cover data incremental updating,experimental results show that the time efficiency of the incremental updating is increased about several times using the proposed index method than that of the traditional quadtree index,and the improvement in efficiency is more significant with increasing data volume.

关 键 词：空间索引 复杂多边形 包含关系 四叉树 空间数据管理 

分 类 号：P208[天文地球—地图制图学与地理信息工程]