|
|||||
|
|
| 基于单调链和STR树的简单要素模型多边形叠置分析算法 | |
| 引用本文： | 陈占龙,吴信才,吴亮. 基于单调链和STR树的简单要素模型多边形叠置分析算法[J]. 测绘学报, 2010, 39(1): 102-108 |
| 作者姓名： | 陈占龙 吴信才 吴亮 |
| 作者单位： | 中国地质大学信息工程学院,湖北,武汉,430075;教育部地理信息系统软件开发及应用工程中心,湖北,武汉,430074;中国地质大学信息工程学院,湖北,武汉,430075 |
| 基金项目： | 国家863计划(2006AA12Z218);;国家自然科学基金(40771165);;中央高校基本科研业务费专项资金(CUGL090251) |
| 摘 要： | 针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。 |
| 关 键 词： | 简单要素模型 单调链 STR树 平面图 空间叠置 |
Polygon Overlay Analysis Algorithm Based on Monotone Chain and STR Tree in the Simple Feature Mode |
|
| CHEN Zhanlong,WU Xincai,WU Liang. Polygon Overlay Analysis Algorithm Based on Monotone Chain and STR Tree in the Simple Feature Mode[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(1): 102-108 | |
| Authors: | CHEN Zhanlong WU Xincai WU Liang |
| Affiliation: | CHEN Zhanlong1,2,WU Xincai1,WU Liang11. Faculty of Information Engineering,China University of Geosciences,Wuhan 430075,China,2. China GIS Software Research , Application Engineering Center of the Ministry of Education,Wuhan 430074 |
| Abstract: | 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 polygons in the spatial database. The algorithm splits the edges in... |
| Keywords: | simple feature model monotone chain STR tree plane graph polygon intersection |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |