基于凸片段分解的多边形窗口线裁剪算法  

Line Clipping Against a Polygon through Convex Segments

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

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

出　　处：《计算机辅助设计与图形学学报》2006年第12期1799-1805,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60373051);国家重点基础研究发展规划项目(2002CB312102);澳门大学科研基金

摘　　要：将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段．在裁剪计算时，先根据二叉树快速地找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度，使其在O（logN）～O（N）之间自适应地变化，且大部分情况下时间复杂度小于O（N）．A novel algorithm is proposed in the paper for line clipping against a general polygon. By the algorithm, the polygon edges are decomposed sequentially into certain segments, under the constraint that each segment is able to form a local convex polygon. These segments are called convex segments, and a BSP tree is constructed for the segments. During the line clipping process, the BSP tree is employed to search for the convex segments in intersection with the line, and then calculate the clipped line against the convex segments. The algorithm shows nice performance by experiments that the time complexity of the algorithm is in between O（log N） and O（N） adaptively, and better than O（N） in most cases.

关 键 词：计算机图形学 线裁剪 凸片段 二叉树 多边形 

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