简单多边形裁剪算法  

Algorithm for simple polygon clipping

作　　者：宋树华[1,2] 濮国梁[1] 罗旭 陈东[1] 陈润强 

机构地区：[1]北京大学遥感与地理信息系统研究所,北京100871 [2]中国资源卫星应用中心,北京100094 [3]中煤科技集团公司,北京100013 [4]北京应用气象研究所,北京100029

出　　处：《计算机工程与设计》2014年第1期192-197,共6页Computer Engineering and Design

摘　　要：为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法。该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形。其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数。该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点。To decrease the difficulty for polygon clipping, an algorithm for simple polygon clipping based on traversing polygon＇s vertices is proposed. The algorithm inserts intersection points into the vertexes＇ vector of clipping land clips polygon. By recor ding intersection points and its predecessor and successor, it may generate results polygon quickly. The algorithm optimizes the data structure of intersection point, saves storage space, and reduces the time complexity that is O（（m＋k） ）〈 k） where m is the larger vertex number of two polygons, and k is the number of intersection points. The algorithm is simple, easy to implement and high efficiency.

关 键 词：多边形裁剪 交点 前驱 后继 矢量数组 

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