基于单调链和STR树的简单要素模型多边形叠置分析算法  

Polygon Overlay Analysis Algorithm Based on Monotone Chain and STR Tree in the Simple Feature Mode

作　　者：陈占龙[1,2] 吴信才[1] 吴亮[1] 

机构地区：[1]中国地质大学信息工程学院,湖北武汉430075 [2]教育部地理信息系统软件开发及应用工程中心,湖北武汉430074

出　　处：《测绘学报》2010年第1期102-108,共7页Acta Geodaetica et Cartographica Sinica

基　　金：国家863计划(2006AA12Z218);国家自然科学基金(40771165);中央高校基本科研业务费专项资金(CUGL090251)

摘　　要：针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。An improved overlay analysis algorithm based on monotone chain and STR （sort-tile-recursive） tree index is introduced. The algorithm can save the time for vertex listing and intersection point computation, also the memory space. Making full use of the function of overlay analysis for simple features, as many as possible nodes of the polygon can be filled in the STR tree index structure. The algorithm reduces the access times when querying the pol- ygons in the spatial database. The algorithm splits the edges in the polygon by the monotone chain algorithm to compute the intersect point firstly. Secondly, the concept of plane graph is used in this algorithm. The algorithm organizes the result polygons by computing the topology location between the plane graph components of the two polygons. It has been reduced the computing intersect point time and emphasizes on the solution of the problem of the entry point or exit-point successive and the alternative searching of the intersected polygon.

关 键 词：简单要素模型 单调链 STR树 平面图 空间叠置 

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