Line Clipping Against a Polygon through Convex Segments

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.