New Clipping Algorithm of Line Against Circular Window with Multi-encoding Approach

Based on the thorough analysis of relative positions of a line segment with circle, a new clipping algorithm for circular window is established. By introducing the common circumscribed-square encoding first, two new encoding methods are designed, i.e., the secondary 45° rotated-square encoding and the tertiary generalized-distance encoding. The common encoding joining with the secondary encoding can rapidly identify most of the line segments that are completely outside the window. The tertiary encoding can quickly identify all the line segments that are completely inside the window as well as quickly determine the relative positions between them. The generalized distance can also be used to quickly discarding the remaining lines that are outside the window and quickly calculating the intersections between line segment and circle. Experiment results show that the new algorithm has a high efficiency and a good stability.