计算机形学 余敦辉 湖北大学数计学院 湖北大学数计学院
湖北大学数计学院 1 计算机图形学 余 敦 辉 湖北大学 数计学院
第六章二维图形的运算 61交点计算 62几何图形的关系判别 62直线段裁剪 直接求交算法; Cohen- Sutherland算法; Nicholl-Lee- Nichol算法 中点算法 6.3多边形裁剪 Sutherland Hodgman算法 Weiler- Atherton算法 64字符裁剪 湖北大学数计学院
湖北大学数计学院 2 第六章 二维图形的运算 6.1 交点计算 6.2 几何图形的关系判别 6.2 直线段裁剪 直接求交算法； Cohen-Sutherland算法； Nicholl-Lee-Nicholl算法 中点算法 6.3 多边形裁剪 Sutlerland_Hodgman算法 Weiler-Athenton算法 6.4 字符裁剪
6.1交点计算 1.两直线段的交点 设有两线段S1,S2。S1的端点分别为P1(x1,y1) P2(x2y2),S2的端点分别为P3(x3,3),P4(x4,y4) 则两直线段的参数方程为 S/:x=(x2-x1)+xl Ly=(y2-y1)u+yl (0≤≤1) S2.x=(x4-x3)v+x3 (0≤v≤1) y=(y4-y3)v+y3 湖北大学数计学院
湖北大学数计学院 3 6.1 交点计算 1. 两直线段的交点 设有两线段S1，S2。S1的端点分别为P1(x1,y1), P2(x2,y2), S2的端点分别为P3(x3,y3), P4(x4,y4). 则两直线段的参数方程为： − + − = − − + − = − − + = − + − + = − + = − + = − + = − + = − + ( 2 1) ( 3 4) 3 1 ( 2 1) ( 3 4) 3 1 : ( 2 1) 1 ( 4 3) 3; ( 2 1) 1 ( 4 3) 3; : (0 1) ( 4 3) 3 ( 4 3) 3 2 : (0 1) ( 2 1) 1; ( 2 1) 1; 1: y y u y y v y y x x u x x v x x y y u y y y v y x x u x x x v x ， ， v y y y v y x x x v x S u y y y u y x x x u x S 上式可进一步整理成 显然 如果两直线段能相交 则应满足
6.1交点计算 1.两直线段的交点 显然,如果两直线段能相交,则应满足 (x2-x1)+x1=(x4-x3)v+x3 l()u+yl=(4-33)v+33 上式可进一步整理成 (x2-x1)+(x3-x4)v=x3-x1 (y2-y1)+(y3-y4)=y3-y 讨论: 无解,此时意味两线段平行或重合; 有唯一解,但不一定是有效解,有效解应该是交点 必须位于两直线段上。此时应满足如下条件: 0<u<1.0 0<v<1.0 根据u,v的值,即可获得交点的坐标
湖北大学数计学院 4 6.1 交点计算 1. 两直线段的交点 讨论： 无解，此时意味两线段平行或重合； 有唯一解，但不一定是有效解，有效解应该是交点 必须位于两直线段上。此时应满足如下条件： 0≤u≤1.0 0≤v≤1.0 根据u,v的值，即可获得交点的坐标。 − + − = − − + − = − − + = − + − + = − + = − + = − + = − + = − + ( 2 1) ( 3 4) 3 1 ( 2 1) ( 3 4) 3 1 : ( 2 1) 1 ( 4 3) 3; ( 2 1) 1 ( 4 3) 3; : (0 1) ( 4 3) 3 ( 4 3) 3 2 : (0 1) ( 2 1) 1; ( 2 1) 1; 1: y y u y y v y y x x u x x v x x y y u y y y v y x x u x x x v x ， ， v y y y v y x x x v x S u y y y u y x x x u x S 上式可进一步整理成 显然 如果两直线段能相交 则应满足
6.1交点计算 2.直线段与圆弧的交点 假定直线段的方程如下 X=(x2-x1)t+x1 (0≤t≤1.0) y=(2-yDt+ yl 圆心为c(x2y2)半径为r的圆弧方程为 x=x +r cos a (a≤a≤a2) y=y+F米Sina 如果直线段和圆弧相交则有 (x2-xI)t+xl=x +r*cos a (2-yI)t+yl=y+rssin a 联立求解即可获得t和值 湖北大学数计学院
湖北大学数计学院 5 6.1 交点计算 2. 直线段与圆弧的交点 t 。 y y t y y r x x t x x r ： y y r x x r c x y 、 r t y y y t y x x x t x c c s e c c c c 联立求解即可获得 和 值 如果直线段和圆弧相交则有 圆心为 半径为 的圆弧方程为 假定直线段的方程如下 − + = + − + = + = + = + = − + = − + ( 2 1) 1 *sin ( 2 1) 1 *cos ( ) *sin *cos ( , ) : (0 1.0) ( 2 1) 1 ( 2 1) 1 :