湖北大学数计学院 1
计算机图形学余 敦 辉湖北大学 数计学院湖北大学数计学院 2
第六章 二维图形的运算
6.1 交点计算
6.2 几何图形的关系判别
6.2 直线段裁剪直接求交算法；
Cohen-Sutherland算法；
Nicholl-Lee-Nicholl算法中点算法
6.3 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
6.4 字符裁剪湖北大学数计学院 3
6.1 交点计算
1,两直线段的交点设有两线段 S1,S2。 S1的端点分别为 P1(x1,y1),
P2(x2,y2),S2的端点分别为 P3(x3,y3),P4(x4,y4).
则两直线段的参数方程为：
13)43()12(
13)43()12(
:;3)34(1)12(;3)34(1)12(
:
)10(
3)34(
3)34(
:2
)10(;1)12(;1)12(
:1
yyvyyuyy
xxvxxuxx
yvyyyuyy
xvxxxuxx
，，
v
yvyyy
xvxxx
S
u
yuyyy
xuxxx
S
上式可进一步整理成则应满足如果两直线段能相交显然湖北大学数计学院 4
6.1 交点计算
1,两直线段的交点讨论：
无解，此时意味两线段平行或重合；
有唯一解，但不一定是有效解，有效解应该是交点必须位于两直线段上。此时应满足如下条件：
0≤u≤1.0
0≤v≤1.0
根据 u,v的值，即可获得交点的坐标。
13)43()12(
13)43()12(
:;3)34(1)12(;3)34(1)12(
:
)10(
3)34(
3)34(
:2
)10(;1)12(;1)12(
:1
yyvyyuyy
xxvxxuxx
yvyyyuyy
xvxxxuxx
，，
v
yvyyy
xvxxx
S
u
yuyyy
xuxxx
S
上式可进一步整理成则应满足如果两直线段能相交显然湖北大学数计学院 5
6.1 交点计算
2,直线段与圆弧的交点
。t
ryytyy
rxxtxx
：
ryy
rxx
r、yxc
t
ytyyy
xtxxx
c
c
es
c
c
cc
值和联立求解即可获得则有如果直线段和圆弧相交的圆弧方程为半径为圆心为假定直线段的方程如下
s i n*1)12(
co s*1)12(
)(
s i n*
co s*
:),(
)0.10(
1)12(
1)12(
:
湖北大学数计学院 6
6.1 交点计算
2,直线段与圆弧的交点讨论：
无解，第一种情况；
一解，第三种情况；
两解，第二种情况。
当有解时，还须进一步判断：
0≤t≤1.0,αs≤α≤αe
湖北大学数计学院 7
6.1 交点计算
3,两圆弧的交点设有两段圆弧 A,B。 A圆弧的圆心坐标 (xa,ya),半径为 ra,
B圆弧的圆心坐标 (xb,yb),半径为 rb 。
则有如下方程：
)(
s i n*
c o s*
)(
s i n*
c o s*
es
bb
bb
es
aa
aa
ryy
rxx
ryy
rxx
如果两圆相交，则应有：
si n*si n*
cos*cos*
bbaa
bbaa
ryry
rxrx
湖北大学数计学院 8
6.1 交点计算
3,两圆弧的交点讨论：
两圆之间的关系存在以上三种。
而对圆弧来说，有效解应在圆弧的定义域内：
即：
2 1
2 1
eses
eses
湖北大学数计学院 9
6.2 关系判别
1,点的包含性检验点的包含性检验是指,判断一个点是否被包含在某一个区域内。为讨论方便，我们定义该区域为一多边形。但所采用的方法可推广到曲线边界。
夹角和法设有一个点 P和多边形 ABCDE，如下图所示,
A
B C
D
E
湖北大学数计学院 10
6.2 关系判别
1,点的包含性检验若依次将 P点与多边形各顶点相连，且令 αi为多边形各相邻顶点与点 P相连所形成的夹角。
则有如下结论：
若 ∑ αi = 0,则点 P在多边形之外；
若 ∑ αi = ± 2π,则点 P在多边形之内；
夹角 αi的计算可采用余弦定理获得。而其方向则可按右手法则确定，用公式表示如下：
连线为两矢量 Vi,V i+1,,则 Vi × V i+1=
])(y*) x-x()y-(y*) x-(x 0j 0[
z-z y-y x-x
z-z y x-x
k j
ip1ip1ipi
p1ip1ip1i
piipi kyiy
i
pp
湖北大学数计学院 11
6.2 关系判别
1,点的包含性检验因此，可用如下判别式判断夹角的方向,
当 T>0时，为逆时针方向；
当 T<0时，为顺时针方向。
交点数判别法
)(y*) x-x()y-(y*) x-(x ip1ip1ipi pyT
A
B C
D
E
A
B C
D
E
湖北大学数计学院 12
6.2 关系判别
1,点的包含性检验交点数法所利用的原理：
由 P点向任一方向作一条射线，然后求出该射线与多边形边的交点数。则有：
1）当交点数为偶数（ 0）时，则说明点 P在多边形外；
2）当交点数为奇数时，则说明点 P在多边形内。
为处理简单，通常射线的与坐标轴平行。
湖北大学数计学院 13
6.2 关系判别
1,点的包含性检验奇异情况处理：
即当射线穿过多边形顶点时的特殊处理 。
当射线穿过的顶点两边在射线两侧，此时认为相交一次。而在同侧时，则认为相交两次。
湖北大学数计学院 14
6.2 关系判别
2,多边形重叠性检验通常采用“最小最大试验法”，也称为“排斥试验法”。这种方法可迅速排除掉不可能相互重叠的情况，从而减少计算工作量，加快图形处理速度。
1）多边形的最小包含矩形是指平面上能包含多边形的最小的矩形。如下图所示。
最小包含矩形湖北大学数计学院 15
6.2 关系判别
2,多边形重叠性检验
2）重叠性检验利用最小包含矩形，可排除两个多边形不重叠情况。
如果两个多边形的最小包含矩形，不发生重叠，
则这两个多边形必不重叠。
湖北大学数计学院 16
6.2 关系判别
2,多边形重叠性检验假定两个多变形的最小矩形为 a和 b,左下角和右上角的坐标分别为：
湖北大学数计学院 17
6.2 关系判别
2,多边形重叠性检验则当 a,b两矩形满足下列条件之一时,a和 b不重叠
Xamax<=Xbmin
Yamax<=Ybmin
Xamin>=Xbmax
Yamin>=Ybmax
当 a,b两矩形不满足上述条件，即意味两多边形可能重叠。此时需通过两多边形的边边求交来判断是否重叠。当存在交点时，既表明两多边形重叠，否则不重叠。
湖北大学数计学院 18
6.3 直线段裁剪
裁剪的目的
– 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分
裁剪的处理的基础
– 图元关于窗口内外关系的判别
– 图元与窗口的求交
假定条件
– 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
– 待裁剪线段,P x y P x y0 0 0 1 1 1(,) (,)
湖北大学数计学院 19
6.3 直线段裁剪
在二维坐标系中,需要在观察坐标系下对窗口进行裁剪,即只保留窗口内的那部分图形,去掉窗口外的图形 。
假设窗口是标准矩形,即边与坐标轴平行的矩形,由上 （ y=wyt）,下 （ y=wyb）,左 （ x=wxl）,右
（ x=wxr） 四条边描述 。
x
y
o
wyt
wyb
wxl wxr
窗口湖北大学数计学院 20
6.3 直线段裁剪
待裁剪线段和窗口的关系
– 线段完全可见
– 显然不可见
– 线段至少有一端点在窗口之外，但非显然不可见为提高效率，算法设计时应考虑：
(一）快速判断情形 (1)(2)；
(二 ) 设法减少情形 (3)求交次数和每次求交时所需的计算量 。
湖北大学数计学院 21
6.3 直线段裁剪
实交点 是直线段与窗口矩形边界的交点 。
虚交点 则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点 。
窗口图6- 2 5 实交点与虚交点
A
B
C
D
E
F
H
G
I
J
虚交点实交点实交点实交点虚交点虚交点湖北大学数计学院 22
6.3 直线段裁剪点裁剪
点裁剪
– 点 (x,y)在窗口内的充分必要条件是：
x x xm i n m a x
y y ym i n m a x
x
y
o
wyt
wyb
wxl wxr
窗口问题：对于任何多边形窗口，如何判别？
湖北大学数计学院 23
6.3 直线段裁剪直接求交算法直线与窗口边都写成参数形式，求参数值。
湖北大学数计学院 24
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
基本思想：对每条直线段 p1(x1,y1)p2(x2,y2)分三种情况处理：
(1) 直线段完全可见,,简取,之 。
(2) 直线段完全不可见,,简弃,之 。
(3) 直线段既不满足,简取,的条件,也不满足,简弃,
的条件,需要对直线段按交点进行分段,分段后重复上述处理 。
裁剪过程是递归的。
湖北大学数计学院 25
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
– 特点,对显然不可见线段的快速判别
– 编码方法,由窗口四条边所在直线把二维平面分成 9个区域，每个区域赋予一个四位编码,CtCbCrCl，上下右左；
e l s e
yyC
t 0
m a x1 当
e l s e
xxC
r 0
m a x1 当
e l s e
xxC
l 0
m in1 当
e l s e
yyC
b 0
m in1 当湖北大学数计学院 26
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
(1)若 code1|code2=0,对直线段应简取之 。
(2)若 code1&code2≠ 0,对直线段可简弃之 。
(3)若上述两条件均不成立 。 则需求出直线段与窗口边界的交点 。 在交点处把线段一分为二,其中必有一段完全在窗口外,可以弃之 。 再对另一段重复进行上述处理,直到该线段完全被舍弃或者找到位于窗口内的一段线段为止 。
裁剪一条线段时，先求出端点
p1和 p2的编码 code1和 code2，
然后：
湖北大学数计学院 27
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
求交,假定直线的端点坐标为 (x1,y1)和 (x2,y2)
左,右边界交点的计算：
上,下边界交点的计算：
窗口
A
B
C
D
E
F
H
G
I
J
虚交点实交点实交点实交点虚交点虚交点湖北大学数计学院 28
– 求交点，并判断
I,若 x1＜ xl,则：
线段的起点坐标可能位于 3区,4区,5区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上直线 x= xl和线段的交点上第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
bs
b
yy
yyxxyyxx )/())(( 121211s
ts
t
yy
yyxxyyxx )/())(( 121211s
第三种情况：
此时，若 yb≤ys≤ yt 则 (xs ys)为有效新起点。
三种情况都不满足，则此线段不在窗口区内。
x x
y y y y x x x x
l
l l
( )( ) / ( )1 0 0 1 0
湖北大学数计学院 30
II,若 x1>xr
线段的起点坐标可能位于 6区,7区,8区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上直线 x= xr和线段的交点上
0
1
2
3
4
5
6
7
8
(x1,y1)
yb
yt
xl xr
第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第三种情况：
此时，若 yb≤ys≤ yt 则 (xs ys)为有效新起点。
若此三种情况都不满足，则此线段不在窗口区内 。
bs
b
yy
yyxxyyxx )/())(( 121211s
ts
t
yy
yyxxyyxx )/())(( 121211s
)/())((y 121211s xxyyxxy
xx
r
rs
湖北大学数计学院 32
若 Xl<=X<=Xr
线段的起点坐标可能位于 1区和 2区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
若此二种情况都不满足，则此线段不在窗口区内。
使用同样的方法，可得到直线在窗口的另一个可见端点。
x x x x y y y y
y y
s t
s t
0 1 0 0 1 0( )( ) / ( )
x x x x y y y y
y y
s b
s b
0 1 0 0 1 0( )( ) / ( )
算法的步骤：
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3) 若 code1|code2=0,对 直 线 段 应 简 取 之,转 (6) ；否则,若
code1&code2≠ 0,对直线段可简弃之,转 (7)；当上述两条均不满足时,
进行步骤 (4)。
(4)确保 p1在窗口外部：若 p1在窗口内,则交换 p1和 p2的坐标值和编码 。
(5)按 左,右,上,下 的顺序求出直线段与窗口边界的交点,并用该交点的坐标值替换 p1的坐标值 。 也即在交点 s处把线段一分为二,并去掉 p1s这一段 。 考虑到 p1是窗口外的一点,因此可以去掉 p1s。 转 (2)。
(6)用直线扫描转换算法画出当前的直线段 p1p2。
(7)算法结束 。
P1,(－ 3/2,1/6)；编码 (0001)
P2,(1/2,3/2)； 编码 (1000)
(2) 求右边交点，得 P’’1(1,11/6)
P2(-1,1/2)；并编码，判别之
(1) 求左边交点，得 P’1P2; P’1:(-
1,1/2); 编码 (0000)
判别知非完全可见，且 P’1在窗口内，因此交换 P’1P2得新线段 P1P2；
P1,(1/2,3/2)；编码 (1000)
P2,(-1,1/2)； 编码 (0000)
(3) 求上边交点，得 P’’’1(-1/4,1)
P2(-1,1/2)；并编码，两端点编码全部为 0，线段完全可见，程序结束例题：
P1
P2
P1’
P1’’
P1’’’
湖北大学数计学院 36
求交测试顺序固定 (左上右下）
最坏情形，线段求交四次。
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
1）特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合；
窗口特别小的场合 (如,光标拾取图形时,
光标看作小的裁剪窗口。 ）
湖北大学数计学院 37
6.3 直线段裁剪中点分割法
想法,从 P0点出发找出距 P0最近的可见点，从
P1点出发找出距 P1最近的可见点。
取中点 Pm=(P1+P2)/2。
（算法见框图）
湖北大学数计学院 38
6.3 直线段裁剪中点分割法基本思想：
当对直线段不能简取也不能简弃时,简单地把线段等分为二段,对两段重复上述测试处理,直至每条线段完全在窗口内或完全在窗口外 。
湖北大学数计学院 39
6.3 直线段裁剪中点分割法算法步骤：
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3)若 code1|code2=0,对直线段应简取之,保留当前直线段的端点坐标,转 (5)；否则,若 code1&code2≠ 0,对直线段可简弃之,
转 (5)；当上述两条均不满足时,进行步骤 (4)。
(4)求出直线段的中点 M,将 p1M,p2M入栈 。
(5)当栈不空时,从栈中弹出一条直线段,取为 p1p2,转 (2)进行处理 。 否则,继续 (6)。
(6)当栈为空时,合并保留的直线段端点,得到窗口内的直线段 p1p2。
用直线扫描转换算法画出当前的直线段 p1p2,算法结束 。
湖北大学数计学院 40
核心思想,通过二分逼近来确定直线段与窗口的交点 。
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2.中点分割算法重新构造算法步骤：
(1)若 code1|code2=0,对直线段应简取之,结束；否则,若
code1&code2≠ 0,对直线段可简弃之,结束；当这两条均不满足时,进行步骤 (2)。
(2)找出该直线段离窗口边界最远的点和该直线段的中点 。 判中点是否在窗口内：若中点不在窗口内,则把中点和离窗口边界最远点构成的线段丢掉,以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内,则又以中点和最远点构成线段,
并求其中点,直到中点与窗口边界的坐标值在规定的误差范围内相等,则该中点就是该线段落在窗口内的一个端点坐标 。
(3)如另一点在窗口内,则经 (2)即确定了该线段在窗口内的部分 。
如另一点不在窗口内,则该点和所求出的在窗口上的那一点构成一条线段,重复步骤 (2),即可求出落在窗口内的另一点 。
湖北大学数计学院 42
例如：
特点：
1,只需使用加法和移位即可完成,无需乘除,效率高
2,易于用算法实现
p
1
p
2
p
3
p
4
p
5
p
6
p
7
湖北大学数计学院 43
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
特点：可对任意凸多边形窗口实现二维和三维裁剪
考虑一个凸多边形 R 和一个线段 P1P2，
P1 P2 与 R 最多只有两个交点
设 A 是 R 边界上一点,N 是该区域边界在 A 点的内法向量
将 P1 P2用参数方程表示,P(t) ＝ (P2－ P1) t ＋ P1
则线段上任一点 P(t),与 N 的点积有三种可能
(1) P(t) 在多边形外侧,N 。 (P(t)－ A) < 0
(2) P(t) 在多边形的边及其延长线上,N 。 (P(t)－ A) = 0
(3) P(t) 在多边形内侧,N 。 (P(t)－ A) > 0
P(t)
N
A
P1
P2
R
湖北大学数计学院 44
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
因此,P(t)在凸多边形内的 充要条件 是：对凸多边形边界上任意一点 A和该处内法向量 N，都有,N? (P(t)－ A) > 0
上述问题是一个线性规划问题，可求得满足条件的一系列 t 值，
在实际操作中我们只关心其最大和最小值，它们对应可见线段区间的端点
设多边形有 M 条边,可以在每条边上取一个点 Ai 和该点的法向量 Ni，则可见线段的参数区间为下列不等式的解
10
0))((
t
AtPN ii
（ i＝ 1,2,… … M)
湖北大学数计学院 45
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
为具体求解 t，将线段方程代入上述判别式得：
10
0))(( 121
t
AtPPPN ii
化简得：
10
0)()( 121
t
tPPNAPN iii
讨论：
(1) 当 Ni? (P2－ P1)＝ 0 时,Ni 垂直于 (P2－ P1),第 i 条边与
P1P2 平行，无交点
(2) 当 Ni? (P2－ P1) > 0 时,P1 在该边外侧,可求出交点 t i,并将其归入下限组
(3) 当 Ni? (P2－ P1) < 0 时,P2 在该边外侧,可求出交点 t i,并将其归入上限组
(P2－ P1)
N
Ni (P2－ P1) > 0 情况
(P2－ P1)N
Ni (P2－ P1) < 0 情况
讨论 (续 )：
(6) 当 t l < t h,则 t l 和 t h 是可见线段的端点参数，否则线段在区域之外
(4) 前述判别式 ＝ 0 对应线段与边的交点，因此当 Ni (P2－ P1) ≠ 0
时可求出 t 为,
)(
)(
12
1
PPN
APNt
i
ii
i
(5) 可见线段 为下限组中的最大值至上限组中的最小值之间的线段即：
}}0)(:m i n {,1m i n {
}}0)(:m a x {,0m a x {
12
12
PPNtt
PPNtt
iih
iil
通过上述方法可以求出任意凸多边形对线段的裁剪
10
0)()( 121
t
tPPNAPN iii
湖北大学数计学院 48
6.3 直线段裁剪
Liang-Barsky算法分析推导湖北大学数计学院 49
特殊处理：
(a) 直线段与窗口边界
wxl 和wxr 平行的情况
(b) 直线段与窗口边界
wyb 和wyt 平行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
算法步骤,
(1)输入直线段的两端点坐标,(x1,y1)和 (x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)若 Δx= 0,则 p1=p2=0。 此时进一步判断是否满足 q1<0或 q2<0，
若满足,则该直线段不在窗口内,算法转 (7)。 否则,满足
q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转 (5)。
(3)若 Δy= 0,则 p3=p4=0。 此时进一步判断是否满足 q3<0或 q4<0，
若满足,则该直线段不在窗口内,算法转 (7)。 否则,满足
q1>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)利用直线的扫描转换算法绘制在窗口内的直线段 。 算法结束 。
湖北大学数计学院 51
6.4 多边形裁剪
错觉,直线段裁剪的组合？
新的问题,1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？
湖北大学数计学院 52
6.4 多边形裁剪
2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？
湖北大学数计学院 53
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪基本思想输入：A B C D E F G H
A
B
C
D
E
F
G
H
输出：A 1 2 D E F G H
1
2
( a ) 用左边界裁剪输出：A 1 3 4 D 5 6 F G H
A
D
E
F
G
H
输入：A 1 2 D E F G H
1
2
( b ) 用下边界裁剪
3 4 5 6
湖北大学数计学院 54
输入：A 1 3 4 D 5 6 F G H
A
D F
G
H
1
( c ) 用右边界裁剪
3 4 5 6
输出：A 1 3 4 D 5 6 7 8 G H
7
8
A
D
G
H
1
( d ) 用上边界裁剪
3 4 5 6
7
8
输入：A 1 3 4 D 5 6 7 8 G H
输出：K 3 4 D 5 6 7 8 9 I H J
9IJK
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪湖北大学数计学院 55
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪算法实施策略：
为窗口各边界裁剪的多边形存储输入与输出顶点表 。
在窗口的一条裁剪边界处理完所有顶点后,其输出顶点表将用窗口的下一条边界继续裁剪 。
窗口的一条边以及延长线构成的裁剪线把平面分为两个区域,包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧 。
湖北大学数计学院 56
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪
沿着多边形依次处理顶点会遇到四种情况：
S
P S
P SP S
P
I
I
(a)输出I、P (b)输出P (c)输出I
可见侧
(d)不输出可见侧 可见侧可见侧多边形边与裁剪线相对位置的四种情况与处理方法：
(1) 位于可见一侧：输出终点，作为新多边形顶点
(2) 位于不可见一侧：不输出
(3) 由可见到不可见：输出与裁剪线的交点
(4) 由不可见到可见：输出与裁剪线的交点及终点湖北大学数计学院 57
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪
特点,A
( a ) 裁剪前
(b)Sutherland-Hodgeman
算法的裁剪结果
B C
D
E
F
A
B C
D
E
F
V 1 V 2 V 3 V 4
湖北大学数计学院 58
6.4 多边形裁剪
Weiler-Athenton算法裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
湖北大学数计学院 59
主多边形和裁剪多边形把二维平面分成两部分。
内裁剪,A∩B
外裁剪,A-B
6.4 多边形裁剪
Weiler-Athenton算法裁剪结果区域的边界由 A的部分边界和 B的部分边界两部分构成，并且在交点处边界发生交替，即由 A的边界转至 B的边界，或由 B的边界转至 A的边界湖北大学数计学院 60
6.4 多边形裁剪
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出现,它们被分为如下两类：
进点,主多边形边界由此进入裁剪多边形内如,I1,I3,I5,I7,I9,I11
出点,主多边形边界由此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
湖北大学数计学院 61
6.4 多边形裁剪
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
Weiler_Athenton裁剪算法（内裁剪）步骤：
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪如果存在没有被跟踪过的交点，执行以下步骤：
(1)建立裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点湖北大学数计学院 62
6.4 多边形裁剪
Weiler-Athenton算法湖北大学数计学院 63
6.4 多边形裁剪
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点湖北大学数计学院 64
5.3 字符裁剪
1)串精度裁剪
2)字符精度裁剪湖北大学数计学院 65
5.3 字符裁剪
3)笔划、象素精度裁剪
– 点阵字符：点裁剪
– 矢量字符：线裁剪湖北大学数计学院 66
习题
1,试用作图法实现对多边形的逐次裁剪 (Sutherland-Hodgman算法 )，
显示每步产生的中间多边形，多边形顶点取 (-4,2),(8,14),(8,2),
(12,6),(12,-2),(4,-2),(4,6),(0,2)，裁剪窗口为 (0,0,10,10)
2,已知点 P (xp,yp)，及直线 L 的方程 ax+by+c＝ 0，试推导一个相对 L作对称变换的矩阵 M，使点 P 对 L 的对称点为 P’＝ P*M
3,给定空间一点 P (x,y,z) 及任一平面 Q,ax+by+cz+d = 0,求 P 对
Q 的对称点 P’(x’,y’,z’) 的变换矩阵湖北大学数计学院 67
上机作业
实现一个裁剪算法。
计算机图形学余 敦 辉湖北大学 数计学院湖北大学数计学院 2
第六章 二维图形的运算
6.1 交点计算
6.2 几何图形的关系判别
6.2 直线段裁剪直接求交算法；
Cohen-Sutherland算法；
Nicholl-Lee-Nicholl算法中点算法
6.3 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
6.4 字符裁剪湖北大学数计学院 3
6.1 交点计算
1,两直线段的交点设有两线段 S1,S2。 S1的端点分别为 P1(x1,y1),
P2(x2,y2),S2的端点分别为 P3(x3,y3),P4(x4,y4).
则两直线段的参数方程为：
13)43()12(
13)43()12(
:;3)34(1)12(;3)34(1)12(
:
)10(
3)34(
3)34(
:2
)10(;1)12(;1)12(
:1
yyvyyuyy
xxvxxuxx
yvyyyuyy
xvxxxuxx
，，
v
yvyyy
xvxxx
S
u
yuyyy
xuxxx
S
上式可进一步整理成则应满足如果两直线段能相交显然湖北大学数计学院 4
6.1 交点计算
1,两直线段的交点讨论：
无解，此时意味两线段平行或重合；
有唯一解，但不一定是有效解，有效解应该是交点必须位于两直线段上。此时应满足如下条件：
0≤u≤1.0
0≤v≤1.0
根据 u,v的值，即可获得交点的坐标。
13)43()12(
13)43()12(
:;3)34(1)12(;3)34(1)12(
:
)10(
3)34(
3)34(
:2
)10(;1)12(;1)12(
:1
yyvyyuyy
xxvxxuxx
yvyyyuyy
xvxxxuxx
，，
v
yvyyy
xvxxx
S
u
yuyyy
xuxxx
S
上式可进一步整理成则应满足如果两直线段能相交显然湖北大学数计学院 5
6.1 交点计算
2,直线段与圆弧的交点
。t
ryytyy
rxxtxx
：
ryy
rxx
r、yxc
t
ytyyy
xtxxx
c
c
es
c
c
cc
值和联立求解即可获得则有如果直线段和圆弧相交的圆弧方程为半径为圆心为假定直线段的方程如下
s i n*1)12(
co s*1)12(
)(
s i n*
co s*
:),(
)0.10(
1)12(
1)12(
:
湖北大学数计学院 6
6.1 交点计算
2,直线段与圆弧的交点讨论：
无解，第一种情况；
一解，第三种情况；
两解，第二种情况。
当有解时，还须进一步判断：
0≤t≤1.0,αs≤α≤αe
湖北大学数计学院 7
6.1 交点计算
3,两圆弧的交点设有两段圆弧 A,B。 A圆弧的圆心坐标 (xa,ya),半径为 ra,
B圆弧的圆心坐标 (xb,yb),半径为 rb 。
则有如下方程：
)(
s i n*
c o s*
)(
s i n*
c o s*
es
bb
bb
es
aa
aa
ryy
rxx
ryy
rxx
如果两圆相交，则应有：
si n*si n*
cos*cos*
bbaa
bbaa
ryry
rxrx
湖北大学数计学院 8
6.1 交点计算
3,两圆弧的交点讨论：
两圆之间的关系存在以上三种。
而对圆弧来说，有效解应在圆弧的定义域内：
即：
2 1
2 1
eses
eses
湖北大学数计学院 9
6.2 关系判别
1,点的包含性检验点的包含性检验是指,判断一个点是否被包含在某一个区域内。为讨论方便，我们定义该区域为一多边形。但所采用的方法可推广到曲线边界。
夹角和法设有一个点 P和多边形 ABCDE，如下图所示,
A
B C
D
E
湖北大学数计学院 10
6.2 关系判别
1,点的包含性检验若依次将 P点与多边形各顶点相连，且令 αi为多边形各相邻顶点与点 P相连所形成的夹角。
则有如下结论：
若 ∑ αi = 0,则点 P在多边形之外；
若 ∑ αi = ± 2π,则点 P在多边形之内；
夹角 αi的计算可采用余弦定理获得。而其方向则可按右手法则确定，用公式表示如下：
连线为两矢量 Vi,V i+1,,则 Vi × V i+1=
])(y*) x-x()y-(y*) x-(x 0j 0[
z-z y-y x-x
z-z y x-x
k j
ip1ip1ipi
p1ip1ip1i
piipi kyiy
i
pp
湖北大学数计学院 11
6.2 关系判别
1,点的包含性检验因此，可用如下判别式判断夹角的方向,
当 T>0时，为逆时针方向；
当 T<0时，为顺时针方向。
交点数判别法
)(y*) x-x()y-(y*) x-(x ip1ip1ipi pyT
A
B C
D
E
A
B C
D
E
湖北大学数计学院 12
6.2 关系判别
1,点的包含性检验交点数法所利用的原理：
由 P点向任一方向作一条射线，然后求出该射线与多边形边的交点数。则有：
1）当交点数为偶数（ 0）时，则说明点 P在多边形外；
2）当交点数为奇数时，则说明点 P在多边形内。
为处理简单，通常射线的与坐标轴平行。
湖北大学数计学院 13
6.2 关系判别
1,点的包含性检验奇异情况处理：
即当射线穿过多边形顶点时的特殊处理 。
当射线穿过的顶点两边在射线两侧，此时认为相交一次。而在同侧时，则认为相交两次。
湖北大学数计学院 14
6.2 关系判别
2,多边形重叠性检验通常采用“最小最大试验法”，也称为“排斥试验法”。这种方法可迅速排除掉不可能相互重叠的情况，从而减少计算工作量，加快图形处理速度。
1）多边形的最小包含矩形是指平面上能包含多边形的最小的矩形。如下图所示。
最小包含矩形湖北大学数计学院 15
6.2 关系判别
2,多边形重叠性检验
2）重叠性检验利用最小包含矩形，可排除两个多边形不重叠情况。
如果两个多边形的最小包含矩形，不发生重叠，
则这两个多边形必不重叠。
湖北大学数计学院 16
6.2 关系判别
2,多边形重叠性检验假定两个多变形的最小矩形为 a和 b,左下角和右上角的坐标分别为：
湖北大学数计学院 17
6.2 关系判别
2,多边形重叠性检验则当 a,b两矩形满足下列条件之一时,a和 b不重叠
Xamax<=Xbmin
Yamax<=Ybmin
Xamin>=Xbmax
Yamin>=Ybmax
当 a,b两矩形不满足上述条件，即意味两多边形可能重叠。此时需通过两多边形的边边求交来判断是否重叠。当存在交点时，既表明两多边形重叠，否则不重叠。
湖北大学数计学院 18
6.3 直线段裁剪
裁剪的目的
– 判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分
裁剪的处理的基础
– 图元关于窗口内外关系的判别
– 图元与窗口的求交
假定条件
– 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
– 待裁剪线段,P x y P x y0 0 0 1 1 1(,) (,)
湖北大学数计学院 19
6.3 直线段裁剪
在二维坐标系中,需要在观察坐标系下对窗口进行裁剪,即只保留窗口内的那部分图形,去掉窗口外的图形 。
假设窗口是标准矩形,即边与坐标轴平行的矩形,由上 （ y=wyt）,下 （ y=wyb）,左 （ x=wxl）,右
（ x=wxr） 四条边描述 。
x
y
o
wyt
wyb
wxl wxr
窗口湖北大学数计学院 20
6.3 直线段裁剪
待裁剪线段和窗口的关系
– 线段完全可见
– 显然不可见
– 线段至少有一端点在窗口之外，但非显然不可见为提高效率，算法设计时应考虑：
(一）快速判断情形 (1)(2)；
(二 ) 设法减少情形 (3)求交次数和每次求交时所需的计算量 。
湖北大学数计学院 21
6.3 直线段裁剪
实交点 是直线段与窗口矩形边界的交点 。
虚交点 则是直线段与窗口矩形边界延长线或直线段的延长线与窗口矩形边界的交点 。
窗口图6- 2 5 实交点与虚交点
A
B
C
D
E
F
H
G
I
J
虚交点实交点实交点实交点虚交点虚交点湖北大学数计学院 22
6.3 直线段裁剪点裁剪
点裁剪
– 点 (x,y)在窗口内的充分必要条件是：
x x xm i n m a x
y y ym i n m a x
x
y
o
wyt
wyb
wxl wxr
窗口问题：对于任何多边形窗口，如何判别？
湖北大学数计学院 23
6.3 直线段裁剪直接求交算法直线与窗口边都写成参数形式，求参数值。
湖北大学数计学院 24
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
基本思想：对每条直线段 p1(x1,y1)p2(x2,y2)分三种情况处理：
(1) 直线段完全可见,,简取,之 。
(2) 直线段完全不可见,,简弃,之 。
(3) 直线段既不满足,简取,的条件,也不满足,简弃,
的条件,需要对直线段按交点进行分段,分段后重复上述处理 。
裁剪过程是递归的。
湖北大学数计学院 25
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
– 特点,对显然不可见线段的快速判别
– 编码方法,由窗口四条边所在直线把二维平面分成 9个区域，每个区域赋予一个四位编码,CtCbCrCl，上下右左；
e l s e
yyC
t 0
m a x1 当
e l s e
xxC
r 0
m a x1 当
e l s e
xxC
l 0
m in1 当
e l s e
yyC
b 0
m in1 当湖北大学数计学院 26
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
(1)若 code1|code2=0,对直线段应简取之 。
(2)若 code1&code2≠ 0,对直线段可简弃之 。
(3)若上述两条件均不成立 。 则需求出直线段与窗口边界的交点 。 在交点处把线段一分为二,其中必有一段完全在窗口外,可以弃之 。 再对另一段重复进行上述处理,直到该线段完全被舍弃或者找到位于窗口内的一段线段为止 。
裁剪一条线段时，先求出端点
p1和 p2的编码 code1和 code2，
然后：
湖北大学数计学院 27
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
求交,假定直线的端点坐标为 (x1,y1)和 (x2,y2)
左,右边界交点的计算：
上,下边界交点的计算：
窗口
A
B
C
D
E
F
H
G
I
J
虚交点实交点实交点实交点虚交点虚交点湖北大学数计学院 28
– 求交点，并判断
I,若 x1＜ xl,则：
线段的起点坐标可能位于 3区,4区,5区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上直线 x= xl和线段的交点上第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
bs
b
yy
yyxxyyxx )/())(( 121211s
ts
t
yy
yyxxyyxx )/())(( 121211s
第三种情况：
此时，若 yb≤ys≤ yt 则 (xs ys)为有效新起点。
三种情况都不满足，则此线段不在窗口区内。
x x
y y y y x x x x
l
l l
( )( ) / ( )1 0 0 1 0
湖北大学数计学院 30
II,若 x1>xr
线段的起点坐标可能位于 6区,7区,8区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上直线 x= xr和线段的交点上
0
1
2
3
4
5
6
7
8
(x1,y1)
yb
yt
xl xr
第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第三种情况：
此时，若 yb≤ys≤ yt 则 (xs ys)为有效新起点。
若此三种情况都不满足，则此线段不在窗口区内 。
bs
b
yy
yyxxyyxx )/())(( 121211s
ts
t
yy
yyxxyyxx )/())(( 121211s
)/())((y 121211s xxyyxxy
xx
r
rs
湖北大学数计学院 32
若 Xl<=X<=Xr
线段的起点坐标可能位于 1区和 2区。
而新起点的坐标可能在直线 y= yb和线段的交点上直线 y= yt和线段的交点上第一种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
第二种情况：
此时，若 xl≤xs≤ xr 则 (xs ys)为有效新起点。
若此二种情况都不满足，则此线段不在窗口区内。
使用同样的方法，可得到直线在窗口的另一个可见端点。
x x x x y y y y
y y
s t
s t
0 1 0 0 1 0( )( ) / ( )
x x x x y y y y
y y
s b
s b
0 1 0 0 1 0( )( ) / ( )
算法的步骤：
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3) 若 code1|code2=0,对 直 线 段 应 简 取 之,转 (6) ；否则,若
code1&code2≠ 0,对直线段可简弃之,转 (7)；当上述两条均不满足时,
进行步骤 (4)。
(4)确保 p1在窗口外部：若 p1在窗口内,则交换 p1和 p2的坐标值和编码 。
(5)按 左,右,上,下 的顺序求出直线段与窗口边界的交点,并用该交点的坐标值替换 p1的坐标值 。 也即在交点 s处把线段一分为二,并去掉 p1s这一段 。 考虑到 p1是窗口外的一点,因此可以去掉 p1s。 转 (2)。
(6)用直线扫描转换算法画出当前的直线段 p1p2。
(7)算法结束 。
P1,(－ 3/2,1/6)；编码 (0001)
P2,(1/2,3/2)； 编码 (1000)
(2) 求右边交点，得 P’’1(1,11/6)
P2(-1,1/2)；并编码，判别之
(1) 求左边交点，得 P’1P2; P’1:(-
1,1/2); 编码 (0000)
判别知非完全可见，且 P’1在窗口内，因此交换 P’1P2得新线段 P1P2；
P1,(1/2,3/2)；编码 (1000)
P2,(-1,1/2)； 编码 (0000)
(3) 求上边交点，得 P’’’1(-1/4,1)
P2(-1,1/2)；并编码，两端点编码全部为 0，线段完全可见，程序结束例题：
P1
P2
P1’
P1’’
P1’’’
湖北大学数计学院 36
求交测试顺序固定 (左上右下）
最坏情形，线段求交四次。
6.3 直线段裁剪
Cohen-SutherLand算法 (编码算法 )
1）特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合；
窗口特别小的场合 (如,光标拾取图形时,
光标看作小的裁剪窗口。 ）
湖北大学数计学院 37
6.3 直线段裁剪中点分割法
想法,从 P0点出发找出距 P0最近的可见点，从
P1点出发找出距 P1最近的可见点。
取中点 Pm=(P1+P2)/2。
（算法见框图）
湖北大学数计学院 38
6.3 直线段裁剪中点分割法基本思想：
当对直线段不能简取也不能简弃时,简单地把线段等分为二段,对两段重复上述测试处理,直至每条线段完全在窗口内或完全在窗口外 。
湖北大学数计学院 39
6.3 直线段裁剪中点分割法算法步骤：
(1)输入直线段的两端点坐标,p1(x1,y1),p2(x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)对 p1,p2进行编码：点 p1的编码为 code1,点 p2的编码为 code2。
(3)若 code1|code2=0,对直线段应简取之,保留当前直线段的端点坐标,转 (5)；否则,若 code1&code2≠ 0,对直线段可简弃之,
转 (5)；当上述两条均不满足时,进行步骤 (4)。
(4)求出直线段的中点 M,将 p1M,p2M入栈 。
(5)当栈不空时,从栈中弹出一条直线段,取为 p1p2,转 (2)进行处理 。 否则,继续 (6)。
(6)当栈为空时,合并保留的直线段端点,得到窗口内的直线段 p1p2。
用直线扫描转换算法画出当前的直线段 p1p2,算法结束 。
湖北大学数计学院 40
核心思想,通过二分逼近来确定直线段与窗口的交点 。
p
1
p
2
p
3
p
4
p
5
p
6
p
7
2.中点分割算法重新构造算法步骤：
(1)若 code1|code2=0,对直线段应简取之,结束；否则,若
code1&code2≠ 0,对直线段可简弃之,结束；当这两条均不满足时,进行步骤 (2)。
(2)找出该直线段离窗口边界最远的点和该直线段的中点 。 判中点是否在窗口内：若中点不在窗口内,则把中点和离窗口边界最远点构成的线段丢掉,以线段上的另一点和该中点再构成线段求其中点；如中点在窗口内,则又以中点和最远点构成线段,
并求其中点,直到中点与窗口边界的坐标值在规定的误差范围内相等,则该中点就是该线段落在窗口内的一个端点坐标 。
(3)如另一点在窗口内,则经 (2)即确定了该线段在窗口内的部分 。
如另一点不在窗口内,则该点和所求出的在窗口上的那一点构成一条线段,重复步骤 (2),即可求出落在窗口内的另一点 。
湖北大学数计学院 42
例如：
特点：
1,只需使用加法和移位即可完成,无需乘除,效率高
2,易于用算法实现
p
1
p
2
p
3
p
4
p
5
p
6
p
7
湖北大学数计学院 43
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
特点：可对任意凸多边形窗口实现二维和三维裁剪
考虑一个凸多边形 R 和一个线段 P1P2，
P1 P2 与 R 最多只有两个交点
设 A 是 R 边界上一点,N 是该区域边界在 A 点的内法向量
将 P1 P2用参数方程表示,P(t) ＝ (P2－ P1) t ＋ P1
则线段上任一点 P(t),与 N 的点积有三种可能
(1) P(t) 在多边形外侧,N 。 (P(t)－ A) < 0
(2) P(t) 在多边形的边及其延长线上,N 。 (P(t)－ A) = 0
(3) P(t) 在多边形内侧,N 。 (P(t)－ A) > 0
P(t)
N
A
P1
P2
R
湖北大学数计学院 44
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
因此,P(t)在凸多边形内的 充要条件 是：对凸多边形边界上任意一点 A和该处内法向量 N，都有,N? (P(t)－ A) > 0
上述问题是一个线性规划问题，可求得满足条件的一系列 t 值，
在实际操作中我们只关心其最大和最小值，它们对应可见线段区间的端点
设多边形有 M 条边,可以在每条边上取一个点 Ai 和该点的法向量 Ni，则可见线段的参数区间为下列不等式的解
10
0))((
t
AtPN ii
（ i＝ 1,2,… … M)
湖北大学数计学院 45
6.3 直线段裁剪参数化裁剪方法（ Cyrus-Beck 算法）
为具体求解 t，将线段方程代入上述判别式得：
10
0))(( 121
t
AtPPPN ii
化简得：
10
0)()( 121
t
tPPNAPN iii
讨论：
(1) 当 Ni? (P2－ P1)＝ 0 时,Ni 垂直于 (P2－ P1),第 i 条边与
P1P2 平行，无交点
(2) 当 Ni? (P2－ P1) > 0 时,P1 在该边外侧,可求出交点 t i,并将其归入下限组
(3) 当 Ni? (P2－ P1) < 0 时,P2 在该边外侧,可求出交点 t i,并将其归入上限组
(P2－ P1)
N
Ni (P2－ P1) > 0 情况
(P2－ P1)N
Ni (P2－ P1) < 0 情况
讨论 (续 )：
(6) 当 t l < t h,则 t l 和 t h 是可见线段的端点参数，否则线段在区域之外
(4) 前述判别式 ＝ 0 对应线段与边的交点，因此当 Ni (P2－ P1) ≠ 0
时可求出 t 为,
)(
)(
12
1
PPN
APNt
i
ii
i
(5) 可见线段 为下限组中的最大值至上限组中的最小值之间的线段即：
}}0)(:m i n {,1m i n {
}}0)(:m a x {,0m a x {
12
12
PPNtt
PPNtt
iih
iil
通过上述方法可以求出任意凸多边形对线段的裁剪
10
0)()( 121
t
tPPNAPN iii
湖北大学数计学院 48
6.3 直线段裁剪
Liang-Barsky算法分析推导湖北大学数计学院 49
特殊处理：
(a) 直线段与窗口边界
wxl 和wxr 平行的情况
(b) 直线段与窗口边界
wyb 和wyt 平行的情况
wyt
wyb
wxl wxr wxrwxl
wyb
wyt
A
B
C
D
E
F
G
H I
J
K
L
算法步骤,
(1)输入直线段的两端点坐标,(x1,y1)和 (x2,y2),以及窗口的四条边界坐标,wyt,wyb,wxl和 wxr。
(2)若 Δx= 0,则 p1=p2=0。 此时进一步判断是否满足 q1<0或 q2<0，
若满足,则该直线段不在窗口内,算法转 (7)。 否则,满足
q1>0且 q2>0,则进一步 计算 u1和 u2。 算法转 (5)。
(3)若 Δy= 0,则 p3=p4=0。 此时进一步判断是否满足 q3<0或 q4<0，
若满足,则该直线段不在窗口内,算法转 (7)。 否则,满足
q1>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)利用直线的扫描转换算法绘制在窗口内的直线段 。 算法结束 。
湖北大学数计学院 51
6.4 多边形裁剪
错觉,直线段裁剪的组合？
新的问题,1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？
湖北大学数计学院 52
6.4 多边形裁剪
2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？
湖北大学数计学院 53
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪基本思想输入：A B C D E F G H
A
B
C
D
E
F
G
H
输出：A 1 2 D E F G H
1
2
( a ) 用左边界裁剪输出：A 1 3 4 D 5 6 F G H
A
D
E
F
G
H
输入：A 1 2 D E F G H
1
2
( b ) 用下边界裁剪
3 4 5 6
湖北大学数计学院 54
输入：A 1 3 4 D 5 6 F G H
A
D F
G
H
1
( c ) 用右边界裁剪
3 4 5 6
输出：A 1 3 4 D 5 6 7 8 G H
7
8
A
D
G
H
1
( d ) 用上边界裁剪
3 4 5 6
7
8
输入：A 1 3 4 D 5 6 7 8 G H
输出：K 3 4 D 5 6 7 8 9 I H J
9IJK
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪湖北大学数计学院 55
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪算法实施策略：
为窗口各边界裁剪的多边形存储输入与输出顶点表 。
在窗口的一条裁剪边界处理完所有顶点后,其输出顶点表将用窗口的下一条边界继续裁剪 。
窗口的一条边以及延长线构成的裁剪线把平面分为两个区域,包含有窗口区域的一个域称为可见侧；不包含窗口区域的域为不可见侧 。
湖北大学数计学院 56
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪
沿着多边形依次处理顶点会遇到四种情况：
S
P S
P SP S
P
I
I
(a)输出I、P (b)输出P (c)输出I
可见侧
(d)不输出可见侧 可见侧可见侧多边形边与裁剪线相对位置的四种情况与处理方法：
(1) 位于可见一侧：输出终点，作为新多边形顶点
(2) 位于不可见一侧：不输出
(3) 由可见到不可见：输出与裁剪线的交点
(4) 由不可见到可见：输出与裁剪线的交点及终点湖北大学数计学院 57
6.4 多边形裁剪
Sutherland-Hodgeman多边形裁剪
特点,A
( a ) 裁剪前
(b)Sutherland-Hodgeman
算法的裁剪结果
B C
D
E
F
A
B C
D
E
F
V 1 V 2 V 3 V 4
湖北大学数计学院 58
6.4 多边形裁剪
Weiler-Athenton算法裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
湖北大学数计学院 59
主多边形和裁剪多边形把二维平面分成两部分。
内裁剪,A∩B
外裁剪,A-B
6.4 多边形裁剪
Weiler-Athenton算法裁剪结果区域的边界由 A的部分边界和 B的部分边界两部分构成，并且在交点处边界发生交替，即由 A的边界转至 B的边界，或由 B的边界转至 A的边界湖北大学数计学院 60
6.4 多边形裁剪
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出现,它们被分为如下两类：
进点,主多边形边界由此进入裁剪多边形内如,I1,I3,I5,I7,I9,I11
出点,主多边形边界由此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
湖北大学数计学院 61
6.4 多边形裁剪
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
Weiler_Athenton裁剪算法（内裁剪）步骤：
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪如果存在没有被跟踪过的交点，执行以下步骤：
(1)建立裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点湖北大学数计学院 62
6.4 多边形裁剪
Weiler-Athenton算法湖北大学数计学院 63
6.4 多边形裁剪
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点湖北大学数计学院 64
5.3 字符裁剪
1)串精度裁剪
2)字符精度裁剪湖北大学数计学院 65
5.3 字符裁剪
3)笔划、象素精度裁剪
– 点阵字符：点裁剪
– 矢量字符：线裁剪湖北大学数计学院 66
习题
1,试用作图法实现对多边形的逐次裁剪 (Sutherland-Hodgman算法 )，
显示每步产生的中间多边形，多边形顶点取 (-4,2),(8,14),(8,2),
(12,6),(12,-2),(4,-2),(4,6),(0,2)，裁剪窗口为 (0,0,10,10)
2,已知点 P (xp,yp)，及直线 L 的方程 ax+by+c＝ 0，试推导一个相对 L作对称变换的矩阵 M，使点 P 对 L 的对称点为 P’＝ P*M
3,给定空间一点 P (x,y,z) 及任一平面 Q,ax+by+cz+d = 0,求 P 对
Q 的对称点 P’(x’,y’,z’) 的变换矩阵湖北大学数计学院 67
上机作业
实现一个裁剪算法。
