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

摘要：

针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数.算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形.该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理.同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点.

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

所属期刊栏目：39

分类号：P208(一般性问题)

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

在线出版日期：2015-01-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：102-108