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

【Abstract】 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.更多还原