摘要：针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题，减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍，本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引，应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上，基于均匀网格索引，提出局部射线法，简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进：首先提出基于两种空间索引模型进行线段求交计算，保证算法在理论上具有较低的时间复杂度；其次，在射线法和网格索引基础上提出局部射线法，使得判断每个交点出入属性的时间复杂度为O（1）～O（√n），与参考文献中的算法相比，此方法的优点是避免判断多边形上顶点的方向；最后，算法中裁剪多边形可以是包含任意多个洞的任意简单多边形，克服传统算法中对裁剪多边形的特定约束条件。

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

单位：中国地质科学院矿产资源研究所 北京100037 中国地质大学(北京)地球科学与资源学院 北京100083 中南大学信息科学与工程学院 湖南长沙410083 合肥工业大学资源与环境工程学院 安徽合肥230009