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

Line Clipping Against a Polygon Based on Convex Decomposition

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在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.