A Linear Time Algorithm for the Line Clipping against Concave Polygon
Liang-liang Tang, Yuanjun He · 2009
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.