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

作者：孙春娟; 王文成; 李静; 吴恩华计算机图形学线裁剪凸片段二叉树多边形

摘要：将多边形窗口的边顺序地分割成一些片段，使得每个片段都能局部地形成一个凸多边形，称为凸片段，并建立一个二叉树来管理这些凸片段．在裁剪计算时，先根据二叉树快速地找到与被裁剪线段相交的凸片段，再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度，使其在O（logN）～O（N）之间自适应地变化，且大部分情况下时间复杂度小于O（N）．

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社