A Linear Time Algorithm for the Line Clipping against Concave Polygon

There are not enough algorithms for line clipping against concave polygon, linear time algorithm against concave polygon even does not exist. This paper presents a linear time algorithm for the line clipping against concave polygon (including concave polygon with a hole inside). Line segment was represented by parametric representation; firstly, calculate the intersection point (represented by parameter values) between the line segment and concave polygon; then analyze the characteristics of parameter values, use a sort algorithm which can be completed in linear time; then introduces the concept of intersection eigenvalue, process the overlap intersection point and edge, ultimately obtain the visible segment.