习题解 余敦辉 湖北大学数计学院
习 题 解 答 余敦辉 湖北大学 数计学院
习题解答 1、试用 liang- bar sky算法裁剪图中的线段AB。 A(33) 窗口 X B(-2,-1)
习题解答 窗口 B(-2,-1) A(3,3) x y 1、试用liang-barsky算法裁剪图中的线段AB
3. Li ang-Bar sky算法 分析:P1(x1,y1)和P2(x2,y2) 左 右 上 p p 将线段看成由方向性:外到内内到外
3. Liang-Barsky算法 分析：P1(x1,y1)和P2(x2,y2) 将线段看成由方向性：外到内 内到外 p1 p2 p1 p1 左 右 下 上
3. Liang- Barsky算法 任意直线段(X1,Y1)J(ⅨX2,Y2)的参数方程: x=x1+u(x2-X1) y=y1+uy2y1)0≤u≤1 给定裁剪窗口: wyt 窗 wy WXP X
3. Liang-Barsky算法 x=x1+u·(x2-x1) y=y1+u·(y2-y1) 0 ≤ u ≤ 1 任意直线段I（X1,Y1）J(X2,Y2)的参数方程： x y o wyt wyb wxl wxr 窗口 给定裁剪窗口：
wy 窗 3. Liang- Barsky算法 wyb- 如果任一点()在窗口内则 u(X1-×2)≤X1-Wx左边界 Wxx2+u(x2x1)≤Wxru(x2x)≤WXr-x1右边界 Wyb≤y1+u(y2y1)≤Wytu(y1y2)≤y1-Wyb下边界 u(y2-y1)≤Wyt-y1上边界 p1=×1×2q1=X1-WX 2 2×1q2=WXr-X1 pk≤qk=1,2,3, p3= y1-y2 q3= y1-wyb P4= y2-y1 g4=wyt-y1 ◇取“=”时求得的u对应的是直线与窗口边界的交点 ☆1、2、3、4分别对应左、右、下、上边界裁剪后的两端点是哪些点? 今U0和时分别对应直线的起点和中点
3. Liang-Barsky算法 wxl≤ x1+u·(x2-x1) ≤ wxr wyb≤y1+u·(y2-y1) ≤ wyt u·(x1-x2) ≤ x1 – wxl 左边界 u·(x2-x1) ≤ wxr – x1 右边界 u·(y1-y2) ≤ y1 – wyb 下边界 u·(y2-y1) ≤ wyt – y1 上边界 p1 = x1-x2 p2 = x2-x1 p3 = y1-y2 p4 = y2-y1 令： q1 = x1 – wxl q2 = wxr – x1 q3 = y1 – wyb q4 = wyt – y1 u·pk≤qk k=1,2,3,4 如果任一点（）在窗口内则： ❖ 取“=”时求得的u对应的是直线与窗口边界的交点 ❖ 1、2、3、4分别对应左、右、下、上边界 ❖ U=0和1时分别对应直线的起点和中点 x y o wyt wyb wxl wxr 窗口 裁剪后的两端点是哪些点？
左p1=×1-×2q1=X1-WX 右p2=×2-×1q2=WXr 下p3=y1y2q3=y1-Wyb 分析:裁剪的本质 上p4=y2-y1q4=Wyt-y1 假定Pk不为0 1 对于|1J U=max(0, ukIpk<o,uk|pk<0)PP小于0U在0、U1、U取大者 U+wo=min(1, uklpk0,up 4p0)P2、P大于0U在1、U2、U取小者 如果Uone≤Utw取可求得两端点
分析：裁剪的本质 Uone=max(0,uk|pk0,uk|pk>0) I1 J1 对于I1J1 P1、P4小于0 U在0、U1、U4取大者 P2、P3大于0 U在1、U2、U3取小者 如果Uone≤ Utwo取可求得两端点 左p1 = x1-x2 右p2 = x2-x1 下p3 = y1-y2 上p4 = y2-y1 q1 = x1 – wxl q2 = wxr – x1 q3 = y1 – wyb q4 = wyt – y1 假定PK不为0
左p1=×1-×2q1=X1-WX 右p2=×2-×1q2=WXr 下p3=y1y2q3=y1-Wyb 如果UneU+w表明什么? 上p4=y2-y1q4=Wyt-y1 1 1 one max(0,uklk0, unIpue0)P1、P小于0U在0、U、U3取大者 Utw。=min(1 kpk>0, lpl P2、P大于0U在1、U2、U取小者
左p1 = x1-x2 右p2 = x2-x1 下p3 = y1-y2 上p4 = y2-y1 q1 = x1 – wxl q2 = wxr – x1 q3 = y1 – wyb 如果 q4 = wyt – y1 Uone> Utwo表明什么？ P1、P3小于0 U在0、U1、U3取大者 P2、P4大于0 U在1、U2、U4取小者 Uone=max(0,uk|pk0,uk|pk>0) I1 J1
左p1=×1-×2q1=X1-WX 右p2=×2-×1q2=WXr 下p3=y1y2q3=y1-Wyb 特殊处理为0 上p4=y2-y1q4=Wyt-y1 C yt yt F H B A K D W wXl E WXr wX I WXI (a)直线段与窗口边界 (b)直线段与窗口边界 wx1和wxr平行的情况 Wyb和wyt平行的情况 p1=p2=0 Uone=max(o, uklpko U+wo-min(1, ukl pk>o) 3-4
特殊处理： (a)直线段与窗口边界 wxl和wxr平行的情况 (b)直线段与窗口边界 wyb和wyt平行的情况 wyt wyb wxl wxr wxl wxr wyb wyt A B C D E F G H I J K L PK为0 p1=p2=0 p3=p4=0 Uone=max(0,uk|pk0) 左p1 = x1-x2 右p2 = x2-x1 下p3 = y1-y2 上p4 = y2-y1 q1 = x1 – wxl q2 = wxr – x1 q3 = y1 – wyb q4 = wyt – y1
算法步骤: (1)输入直线段的两端点坐标:(x1,y1)和(x2,y2),以及窗 口的四条边界坐标:wyt、wyb、Wx|和wxr (2)若△x=0,则p1=p2=0。此时进一步判断是否满足q10且q2>0,则进一步计算u1和u2。算法转 (5)。 (3)若△y=0,则p3p4=0。此时进一步判断是否满足q30且q2>0,则进一步计算u1和U2。算法转 (5)。 (4)若上述两条均不满足,则有p≠0(k=1,2,3,4)。此 时计算u和u2 (5)求得u和u2后,进行判断:若u1>u2,,则直线段在窗口 外,算法转(7)。若u1<u2,利用直线的参数方程求得直 线段在窗口内的两端点坐标
算法步骤： (1)输入直线段的两端点坐标：(x1 ,y1 )和(x2 ,y2 )，以及窗 口的四条边界坐标：wyt、wyb、wxl和wxr。 (2)若Δx=0，则p1 =p2 =0。此时进一步判断是否满足q1 0且q2 >0，则进一步计算u1和u2。算法转 (5)。 (3)若Δy=0，则p3 =p4 =0。此时进一步判断是否满足q3 0且q2 >0，则进一步计算u1和u2。算法转 (5)。 (4)若上述两条均不满足，则有pk≠0（k=1,2,3,4）。此 时计算u1和u2。 (5)求得u1和u2后，进行判断：若u1 >u2，则直线段在窗口 外，算法转(7)。若u1 <u2，利用直线的参数方程求得直 线段在窗口内的两端点坐标。 (6)利用直线的扫描转换算法绘制在窗口内的直线段。算
、试用|iang- bar sky算法裁剪图中的线段AB 解: 直线段AB的参数方程为: A(3,3) x=3+u(-2-3) y=3+u(-1-3)0≤u≤ 窗口 即 x=3-5u(0≤u≤1) 3-4u X 这里 wx=0, wXr=2 B(-2,-1) wyb=o, wyt=2 p1=×1-×2=5>0 q1= 1-wX p2=X2-×1=-50 b=3 p4=y2y1=-4<0可见P均不为0q4=Wyt-y1=-1
窗口 B(-2,-1) A(3,3) x y x=3+u·(-2-3) y=3+u·(-1-3) 0 ≤ u ≤ 1 即： x=3-5u y=3-4u 这里： wxl=0,wxr=2 wyb=0,wyt=2 （0 ≤ u ≤ 1） 解： 直线段AB的参数方程为： p1 = x1-x2=5>0 p2 = x2-x1 =-50 p4 = y2-y1 =-4<0 可见P均不为0 因此： q1 = x1 – wxl=3 q2 = wxr – x1=-1 q3 = y1 – wyb=3 q4 = wyt – y1=-1 1、试用liang-barsky算法裁剪图中的线段AB