基于外切正方形与角区的圆形窗口线裁剪算法

摘要

Based on the analysis of the posilion relations among circular window and the eircumseribed-square, the corner region is introduced. The intersection can be identified quickly according to positions of a line segment in relation to the circumscribed-square and the corner regions. The regions that the line crosses the circumscribed-square are distinguished by drawing the semi-infinite line segments from one endpoint to the involved key points and comparing the slope of the line segment to the slopes of the semi-infinite line segments. If the line segment crosses the boundaries of a corner region, the intersection can be determined according to the two intersection points in the corner region. If the line segment crosses the boundaries of the two different corner regions, the intersection can be determined immediately, and the intersection calculation is unnecessary. The new algorithm further improves the clipping efficiency due to the avoidance of the complicated auxiliary operation and the simplification of the intersection calculation.%通过分析圆形窗口与其外切正方形的位置关系,引入角区概念.根据被裁剪线段相对于外切正方形及角区的位置快速判断线段是否与圆形窗口相交.通过端点向所涉及的关键点引射线并比较被裁剪线段斜率与射线斜率来区分被裁剪线段与外切正方形的相交区域.如果被裁剪线段相交于同一角区外界,根据该角区上的两交点确定线段是否与圆形窗口相交；如果被裁剪线段相交于不同角区外界,可直接确定线段是否与圆形窗口相交,不必求与外切正方形的交点.该方法避免了复杂的辅助操作,简化求交过程,显著提高裁剪效率.