大规模等值线图的任意简单多边形窗口裁剪算法

作者：李楠; 吴信才; 肖克炎

来源：小型微型计算机系统, 2011, (10): 2068-2073.

• 局部拓扑
• 裁剪
• 线段求交 local topology
• clipping
• segments intersections

针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.

• 出版日期2011
• 单位中国地质科学院矿产资源研究所; 中国地质大学（北京）