一种基于几何关系编码的高效凸多边形线裁剪算法  

AN EFFICIENT ALGORITHM OF LINE CLIPPING AGAINST CONVEX POLYGON WINDOW BASED ON GEOMETRICAL RELATIONSHIP ENCODING

作　　者：范延军[1] 孙燮华[1] 

机构地区：[1]中国计量学院计算机科学与技术系,浙江杭州310034

出　　处：《计算机应用与软件》2007年第2期148-150,共3页Computer Applications and Software

摘　　要：提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪。实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右。如果m的数值也较大时,该算法的速度还将大大提高。所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性。Based on the geometrical relationship between a line and a convex polygon, a new algorithm of line clipping against convex polygon window is established. Using a convex polygon with n edges to clip m lines, if n is sufficiently large, the experimental results have proved that the time used by the new algorithm is one third of that of the famous Cyrus-Beck algorithm. The algorithmic speed of the new algorithm would be enhanced much if m is large enough. In practical applications, the new algorithm further improves the clipping effciency and it has good stability at the same time.

关 键 词：凸多边形 线裁剪 几何位置关系 

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