Line Clipping Against a Polygon Based on Convex Decomposition

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(log _n) 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.