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

该算法使用单调链减少了多边形求交过程的比较次数，与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。充分利用简单要素类叠置分析的特点，利用STR(Sort-Tile-Recursive)树将尽量多的多边形节点存储在STR树的叶子节点，减少了在空间数据库中检索多边形时的磁盘读取次数。算法先对多边形边界进行关于坐标轴的单调链分割，并在多边形求交过程中引入平面图的概念，并利用平面图元素与各个多边形的相对拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间，在线段求交中加入了对连续出入点，重交点等特殊数据的处理。基于本算法开发的功能用于实际问题中，可较好的解决大规模复杂数据层的叠置运算，并以叠置交运算为例进行的试验表明该算法性能优于其他同类算法。