中文摘要：

针对简单要素类叠置分析的特点，利用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.