Line clipping algorithm with respect to elliptical window based on region encoding
采用区域编码的椭圆对直线裁剪算法

The key in clipping algorithm is the efficiency which is mainly influenced by computing the intersection points between the clipping window and the clipped object. Particularly, for line clipping with respect to elliptical window, to compute the intersection points between the ellipse and the line the quadratic equation has to be solved which involves the extraction of square root that is considered inefficient. To address this, we develop a technique of 5-bit region encoding by which the relationship between an ellipse and a line segment can be determined quickly and accurately. The line segments that are completely visible or completely invisible are discarded; the line segments that surely intersect with the ellipse are dealt with by middle-point segmentation algorithm to obtain the approximate intersection points; and the remaining line segments are clipped by solving the quadratic equations. The proposed algorithm is much more efficient than traditional algorithms, and is straightforward.