基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法  

A Line Clip Algorithm of Based on Cell and R-Tree Spatial Indexes against Arbitrary Polygon Window

作　　者：李楠[1] 吴信才[2] 马金金[3] 王中[4] 

机构地区：[1]中国地质科学院矿产资源研究所,北京100037 [2]中国地质大学(北京)地球科学与资源学院,北京100083 [3]中南大学信息科学与工程学院,湖南长沙410083 [4]合肥工业大学资源与环境工程学院,安徽合肥230009

出　　处：《计算机工程与科学》2012年第11期96-103,共8页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(41002119);国家863计划资助项目(2006AA06Z114);国家科技支撑计划(2006BAB01A01);中央国家机关基本业务费基金项目

摘　　要：针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n^(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。There are three main problems in line clip：reducing the number of segments intersection, reducing the time complexity for computation property of intersections and determining whether non-in- tersection lines is in clip polygons. This paper presents an improved line clip algorithm against general polygon window. The algorithm uses R-Tree and Cell structures to calculate segment intersections be- tween segments in lines and segments in polygon edges. Then, based on uniform subdivision, a method named local radial is introduced in order to reduce the time complexity for point-in-polygon. The algo- rithm has three improvements. Firstly, segment-intersections of two spatial index structures can be calcu- lated simultaneously. Secondly, a ＇local radial method＇ is presented to reduce the time complexity for computation property of intersections, whose time complexity is 0（1）40（ √n ）, judging the orientation of clip polygons. Finally,the algorithm can be used in the , and the method avoids clipping window that is general polygon.

关 键 词：R-树 网格索引 线裁剪 局部射线法 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]