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

Algorithm for Massive Contours Clipping Against General Polygon Window

作　　者：李楠[1,2] 吴信才[1] 肖克炎[2] 

机构地区：[1]中国地质大学(北京)地球科学与资源学院,北京100083 [2]中国地质科学院矿产资源研究所区划室,北京100037

出　　处：《小型微型计算机系统》2011年第10期2068-2073,共6页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2006AA06Z114)资助;国家科技支撑计划项目(2006BAB01A01)资助;中央国家机关基本业务费基金项目资助

摘　　要：针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.Presented a new algorithm for massive Contour Clipping against General Polygon Window.The algorithm builds relationship of local topology between massive disorder line segments and edges of clipping polygon windows by using uniform grid segmentation,which reduces intersecting calculation among line segments.Secondly,based on these topological relations,using local ray method decreases time complexity generated by calculation of verifying point in general polygon windows.Thus,it could rapidly distinguish the reserve parts of contours that users needed.Furthermore,the algorithm makes itself more universal as a result of modifying shortage of pre-algorithms that polygon window cannot be a general polygon.

关 键 词：局部拓扑 裁剪 线段求交 

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