凸多边形窗口线裁剪的折半查找算法

在Skala算法基础上，提出了一个更加快速的线裁剪算法．该算法将裁剪窗口分割成4条折线，依据折线的两个端点与被裁剪直线的位置关系，确定折线是否与直线相交；采用折半查找方法，快速确定与直线相交的窗口边界线，并求出交点位置．与Cyrus-Beck算法相比，该算法在乘除法次数和计算速度方面具有非常明显的优势，也比、Skala算法的效率更高。

Bisearch-Based Line Clipping Algorithm Against a Convex Polygonal Window

A fast line clipping algorithm against a convex polygonal window based on Skala algorithm is presented in this paper. By the algorithm, the clipping window is first divided into four polylines, then the clip of a line against the window is performed by determination of the intersection of the line with each of the four polylines according to the positional relationships between the two end points of each polyline and the line to be clipped. A bisearch method is used to quickly find out the window's edges that intersect the line to be clipped. The algorithm uses less multiplication and division operations and has higher execution speed, in comparison with the others like Cyrus-Beck algorithm and Skala algorithm.