二维裁剪 1直线段裁剪 直接求交算法 Cohen-Sutherland-算法 中点分割裁剪算法 梁友栋-Basky算法 2多边形裁剪 Sutlerland_ Hodgman算法 Weiler-Atherton-算法
直线段裁剪(3/15) ●点裁剪 点(x,y)在窗口内的充分必要条件是: x min < x sx max ymin≤y≤ymax 问题:对于任何多边形窗口,如何判别? 5
x min x x max y min y y max
直线段裁剪(415) 假定条件 矩形裁剪窗口:[xmin, xmax]Xlymin, ymax 待裁剪线段:P(xy)P(x1, 任何平面线段相对于凸多边形窗口进行裁剪后?
P x y P x y 0 0 0 1 1 1 ( , ) ( , )
直线段裁剪(615) 为提高效率,算法设计时应考虑: 1.快速判断情形(1)(2); 2.设法减少情形(3)求交次数和每次求交时所需的计算量
为提高效率,算法设计时应考虑: 1. 快速判断情形(1)(2); 2. 设法减少情形(3)求交次数和每次求交时所需的计算量
直线段裁剪(7/15) Cohen-Sutherland算法(编码算法) 算法步骤: 第一步判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步; 第三步求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃 对余下的另一段重新进行第一步,第二步判断 直至结束 裁剪过程是递归的
算法步骤: 第一步 判别线段两端点是否都落在窗口内,如果是, 则线段完全可见;否则进入第二步; 第二步 判别线段是否为显然不可见,如果是,则裁 剪结束;否则进行第三步 ; 第三步 求线段与窗口边延长线的交点,这个交点将 线段分为两段,其中一段显然不可见,丢弃。 对余下的另一段重新进行第一步,第二步判断, 直至结束 裁剪过程是递归的