计算机形学 余敦辉 湖北大学数计学院 湖北大学数计学院
湖北大学数计学院 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 :
6.1交点计算 2.直线段与圆弧的交点 讨论: 无解,第一种情况; 一解,第三种情况; 两解,第二种情况。 当有解时,还须进一步判断: ●0≤t1.0,、≤≤ 湖北大学数计学院
湖北大学数计学院 6 6.1 交点计算 2. 直线段与圆弧的交点 讨论： 无解，第一种情况； 一解，第三种情况； 两解，第二种情况。 当有解时，还须进一步判断： 0≤t≤1.0 , αs≤α≤αe
6.1交点计算 3.两圆弧的交点 设有两段圆弧A,B。A圆弧的圆心坐标(xa2),半径为ra2 B圆弧的圆心坐标(xbyb),半径为rb 则有如下方程: 水 x=x +r COS Ol y=y+r*sin a x=xb+r cos B (B≤B≤B2) y=yb+r *sin B 如果两圆相交,则应有: x,+r*cos c=xh +r *cos Va +rasin a=yh +r sin B 湖北大学数计学院 7
湖北大学数计学院 7 6.1 交点计算 3. 两圆弧的交点 设有两段圆弧A，B。A圆弧的圆心坐标(xa ,ya ),半径为ra , B圆弧的圆心坐标(xb ,yb ),半径为rb 。 则有如下方程： ( ) *sin *cos ( ) *sin *cos s e b b b b s e a a a a y y r x x r y y r x x r = + = + = + = + 如果两圆相交，则应有： + = + + = + *sin *sin *cos *cos a a b b a a b b y r y r x r x r
6.1交点计算 3.两圆弧的交点 讨论: 两圆之间的关系存在以上三种 而对圆弧来说,有效解应在圆弧的定义域内: 即:a,≤l≤a。a,≤以2≤a。 B。≤B1≤BB,≤B2≤B 湖北大学数计学院 8
湖北大学数计学院 8 6.1 交点计算 3. 两圆弧的交点 讨论： 两圆之间的关系存在以上三种。 而对圆弧来说，有效解应在圆弧的定义域内： 即： 1 2 1 2 s e s e s e s e
62关系判别 1.点的包含性检验 点的包含性检验是指:判断一个点是否被包含 在某一个区域内。为讨论方便,我们定义该 区域为一多边形。但所采用的方法可推广到 曲线边界 夹角和法 设有一个点P和多边形 ABCDE,如下图所示: B C A D E 湖北大学数计学院 9
湖北大学数计学院 9 6.2 关系判别 1. 点的包含性检验 点的包含性检验是指：判断一个点是否被包含 在某一个区域内。为讨论方便，我们定义该 区域为一多边形。但所采用的方法可推广到 曲线边界。 • 夹角和法 设有一个点P和多边形ABCDE，如下图所示： A B C D E
62关系判别 1.点的包含性检验 若依次将P点与多边形各顶点相连,且令0为多 边形各相邻顶点与点P相连所形成的夹角 则有如下结论: 若∑a1=0,则点P在多边形之外; 若∑a1=±2兀,则点P在多边形之内 夹角α的计算可采用余弦定理获得。而其方向 则可按右手法则确定,用公式表示如下: 连线为两矢量V1Vn则V1×V计1 yi-y Z (x-xp)y:-y2)-(x-xp)*(y1-y 湖北大学数计学院 10
湖北大学数计学院 10 6.2 关系判别 1. 点的包含性检验 若依次将P点与多边形各顶点相连，且令αi为多 边形各相邻顶点与点P相连所形成的夹角。 则有如下结论： 若∑ αi = 0, 则点P在多边形之外； 若∑ αi = ±2π, 则点P在多边形之内； 夹角αi的计算可采用余弦定理获得。而其方向 则可按右手法则确定，用公式表示如下： 连线为两矢量Vi , V i+1 ,,则Vi ×V i+1= [0 0 j (x - x )*(y - y ) (x - x )*(y ) ] x - x y - y z - z x - x y z - z j k i p i 1 p i 1 p i i 1 p i 1 p i 1 p i p i i p y i y k i p p − = − − + + + + +