基于凸剖分的多边形窗口线裁剪算法  

Line Clipping Against a Polygon Based on Convex Decomposition

作　　者：李静[1] 王文成[1] 吴恩华[1] 

机构地区：[1]中国科学院软件研究所计算机科学国家重点实验室

出　　处：《计算机辅助设计与图形学学报》2007年第4期425-429,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60373051);国家"九七三"重点基础研究发展规划项目(2002CB312102);国家"八六三"高技术研究发展计划(2006AA01Z306);国家"八六三"高技术研究发展计划(2006AA01Z306);澳门大学科研基金

摘　　要：以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.A novel line clipping algorithm against a general polygon is proposed in the paper. By the approach, the polygon is first decomposed into a set of convex polygons without adding new points and then these convex polygons are organized in a binary space partition tree, as a search tree. In the clipping procedure, the search tree is used to find the candidate convex polygons that intersect the clipped line segment and then an efficient line clipping algorithm against a convex polygon is applied to each such candidate. The algorithm can adaptively decrease the time complexity for line clipping, ranging from O（logn ） to O（ n ）, but less than O（ n ） in most cases, where n is the number of the edges of the polygon. Although a preprocess is required, in many applications （e. g. clipping a polygon against another polygon）, the total time consumed by the new method, including the time for preprocess and clipping calculation, is much less than that by the existing algorithms without preprocess.

关 键 词：多边形窗口 线裁剪 凸剖分 二叉树 加速 

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