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

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

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立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.