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

摘要

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