采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题，而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪，由于椭圆的方程是二次的，求椭圆与线段的交点需要求解一元二次方程，涉及开方运算，非常浪费机器时间。为提高裁剪速度，设计出5位的区域编码，利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见或显然完全不可见的线段立即做出保留或弃掉的决定，避免求交运算；对于能够明确断定与椭圆相交的线段，采用中点分割算法求椭圆和线段的近似交点，避免求解一元二次方程和开方运算；对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比，算法实现简单，裁剪速度具有较大提高。

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.