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

Bisearch-Based Line Clipping Algorithm Against a Convex Polygonal Window

作　　者：李伟青[1] 

机构地区：[1]浙江大学CAD&CG国家重点实验室,杭州310027

出　　处：《计算机辅助设计与图形学学报》2005年第5期962-965,共4页Journal of Computer-Aided Design & Computer Graphics

摘　　要：在Skala算法基础上,提出了一个更加快速的线裁剪算法该算法将裁剪窗口分割成4条折线,依据折线的两个端点与被裁剪直线的位置关系,确定折线是否与直线相交;采用折半查找方法,快速确定与直线相交的窗口边界线,并求出交点位置与Cyrus Beck算法相比,该算法在乘除法次数和计算速度方面具有非常明显的优势。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.

关 键 词：计算机图形学 线裁剪 计算复杂度 折半查找 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]