1
第五章
图形变换与裁剪（三）
计算机学院
苏小红
2
二维裁剪
1 直线段裁剪
直接求交算法
Cohen-Sutherland算法
中点分割裁剪算法
梁友栋 -Basky算法
2 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Atherton算法
3
直线段裁剪 (1/15)
裁剪的目的
? 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分
裁剪处理的基础
? 图元关于窗口内外关系的判别
? 图元与窗口的求交
裁剪、覆盖
4
直线段裁剪 (2/15)
裁剪窗口
? 矩形、圆形、一般多边形
被裁剪对象
? 线段、多边形、曲线、字符
裁剪的策略
? 先裁剪，后变换
? 先变换，后裁剪
裁剪算法的核心问题
? 效率
5
直线段裁剪 (3/15)
点裁剪
? 点 (x,y)在窗口内的充分必要条件是：
问题：对于任何多边形窗口, 如何判别？
x x xm in m a x? ?
y y ym i n m a x? ?
6
直线段裁剪 (4/15)
假定条件
? 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
? 待裁剪线段：
任何平面线段相对于凸多边形窗口进行裁剪后？
P x y P x y0 0 0 1 1 1(,) (,)
7
直线段裁剪 (5/15)
待裁剪线段和窗口的关系
? 完全落在窗口内
? 完全落在窗口外
? 部分在内，部分在外
8
直线段裁剪 (6/15)
为提高效率，算法设计时应考虑：
1,快速判断情形 (1)(2)；
2,设法减少情形 (3)求交次数和每次求交时所需的计算量
9
Cohen-Sutherland 算法 (编码算法 )
算法步骤：
第一步 判别线段两端点是否都落在窗口内，如果是，
则线段完全可见；否则进入第二步；
第二步 判别线段是否为显然不可见，如果是，则裁
剪结束；否则进行第三步 ；
第三步 求线段与窗口边延长线的交点，这个交点将
线段分为两段，其中一段显然不可见，丢弃。
对余下的另一段重新进行第一步，第二步判断，
直至结束
裁剪过程是递归的。
直线段裁剪 (7/15)
10
特点：
? 对显然不可见线段的快速判别
编码方法：
? 由窗口四条边所在直线把二维平面分成 9个区域，每个区域赋予一个四
位编码,CtCbCrCl，上下右左；
??
? ??
e ls e
yyC
t 0
m a x1 当
??
? ??
e ls e
xxC
r 0
m a x1 当
??
? ??
e ls e
xxC
l 0
m in1 当
??
? ??
e ls e
yyC
b 0
m in1 当
Cohen-Sutherland 算法
直线段裁剪 (8/15)
11
端点编码：
? 定义为它所在区域的编码
结论：
? 当线段的两个端点的编码的 逻辑“与”非零 时,显然不可见
Cohen-Sutherland 算法
直线段裁剪 (9/15)
1000
0001 00100000
0100
1001
0101 0110
1010
窗口
b
c
a
12
求交测试顺序固定 (左上右下）
最坏情形，线段求交四次。
对于那些非完全可见、又非完全不可见的线段，需要
求交,求交前 先测试 与窗口哪条边所在直线有交？
(按序判断端点编码中各位的值 ClCtCrCb）
Cohen-Sutherland 算法
直线段裁剪 (10/15)
13
1） 特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合
窗口特别小的场合
Cohen-Sutherland 算法的特点直线段裁剪 (11/15)
14
中点分割法
基本思想：
? 从 P0点出发找出距 P0最近的可见点
? 从 P1点出发找出距 P1最近的可见点
? 不断地在中点处将线段一分为二，对每段线段重复 Cohen-
Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与
窗口边界线的交点或分割子段的长度充分小可视为一点为止
取中点 Pm=(P1+P2)/2。
P2
P1
P2是离 P1点最远的可见点
Pm
P1
用 P1Pm代替 P1P2
P2
P2
用 PmP2代替 P1P2
Pm
P1
直线段裁剪 (12/15)
15
Liang-Barsky裁剪算法
直线 L与区域的交：
? 当 Q为空集时，线段 AB不可能在窗口中有可见线段。
? 当 Q不为空集时,Q可看成是一个一维窗口
P4
P1
P3
P2
ymax
ymin
xmin xmaxR
T
S
U
L
A
B
AS是一维窗口 TS中的可见部分
直线段裁剪 (13/15)
基本思想：
? 把二维裁剪化为一维裁剪问题，并向 x
（或 y）方向投影以决定可见线段。
Q ],;,[],;,[ m a xm i nm a xm i n4321 yyxxLPPPPL ?????????? ??? 口
]),;,[(]),;,[( m a xm i nm a xm i n yyLxxL ????????? ??? TURS??
16
Liang-Barsky裁剪算法
P4
P1
P3
P2
ymax
ymin
xmin xmaxR
T
S
U
L
A
B
AS是一维窗口 TS中的可见部分
直线段裁剪 (14/15)
存在可见线段的充要条件
? 不为空集
向 x轴投影，就得到可见线段上点的坐标的变化范围为
TURSAB ??
)],m a x (),,m a x (,m i n [)],m i n (),,m i n (,m a x [ m a xm i n UTBAUTBA xxxxxxxxxxx ??
)],m a x (),,m a x (,m i n [
)],m i n (),,m i n (,m a x [
m a x
m i n
UTBA
UTBA
xxxxxx
xxxxxx
?
?
?
?
左端点
右端点
17
Liang-Barsky裁剪算法
AB有可见部分的充分必要条件也可表示为
)],m a x (),,m a x (,m i n [)],m i n (),,m i n (,m a x [ m a xm i n UTBAUTBA xxxxxxxxxx ?
)],m i n (,m ax [ m i n BA xxxL ?
)],m ax (,m i n [ m a x BA xxxR ?
??
?
?
?
?
?
?
Rxx
xxL
RL
UT
UT
),m i n (
),m a x (
直线段裁剪 (15/15)
18
多边形裁剪 -1/2
用直线段裁剪算法，可以吗？
新的问题,
图 1 因丢失顶点信息而去法确定裁剪区域
A
B
A
B
图 2 原来封闭的多边形变成了孤立的线段
边界不再封闭，需要用窗口边界的恰当部分来封闭它
19
1
2
1
2
3
(a) (b) (c)
A B
图 3 裁剪后的多边形顶点形成的几种情况
分裂为几个多边形
多边形裁剪 -2/2
关键：
? 不仅在于求出新的顶点，删去界外顶点
? 还在于形成正确的顶点序列
20
Sutherland-Hodgman算法 -1/4
分割处理策略,
? 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所
在直线的裁剪。
流水线过程 (左上右下 ),左边的结果是右边的开始 。
亦称 逐边裁剪算法
21
Sutherland-Hodgman算法 -2/4
? 内侧空间与外侧空间
? 多边形的边与半空间的关系
线段与当前裁剪边的位置关系
可见一侧
窗口
(a) 输出 Pi+1
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 无输出
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 输出 I
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 输出 I和 Pi+1
当前裁剪边
Pi+1 Pi
22
Sutherland-Hodgman算法 -3/4
裁剪结果的顶点构成,
? 裁剪边内侧的原顶点；
? 多边形的边与裁剪边的交点。
顺序连接。
优点：
?裁剪算法采用流水线方式，适合硬件实现。
?可推广到任意凸多边形裁剪窗口
23
Sutherland-Hodgman算法 -4/4
存在的问题
逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？
逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，
这几个多边形沿边框产生多余的线段？
图 6 逐边裁剪法对凹多边形裁剪时可能出现的问题
3 2
1 8 7
695
4
10
3 2
1 7 6
54
10
89
3 2
1 7
4
10
89 5
6
原图
对左
边裁
对顶
边裁
3 2
1 7
4
10
89 5
6
对右
边裁
对底
边裁
24
Weiler-Atherton算法 -1/6
裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况
? 主多边形：被裁剪多边形，记为 SP
? 裁剪多边形：裁剪窗口，记为 CP
25
约定：
? SP与 CP均用它们顶点的环形链表定义
? 外边界取顺时针方向
? 内边界取逆时针方向
Weiler-Atherton算法 -2/6
C2
C1
C3
C4
C8 C7
C5 C6
I1 I8
I2
I3 I4
I5I6
I7
26
SP和 CP把二维平面分成两部分。
内裁剪,SP∩CP
外裁剪,SP-CP
Weiler-Atherton算法 -3/6
裁剪结果区域的边界由 SP的部分边界和
CP的部分边界两部分构成，并且在交点
处边界发生交替，即由 SP的边界转至 CP
的边界，或由 CP的边界转至 SP的边界
27
Weiler-Atherton算法 -4/6
? 主多边形与裁剪多边形 交点成对出现
? 分为如下两类：
进点,主多边形边界由此进入裁剪多边形内
出点,主多边形边界由此
离开裁剪多边形区域,
28
Weiler-Atherton算法 -5/6
C2
C1
C3
C4
S1
S2
S3 S4
S5
S6
I1
I2 I3
I4
I5
I6I7
I8
裁剪多边形 CP
主多边形 SP
算法裁剪后所生成的多边形为 I1I2I3S3I4I5I6I7S6I8 I1
主多边形表 裁剪多边形表
S1
S2
I1
S3
S4
S5
S6
I2
I3
I4
I5
I6
I7
I8
C1
C2
I3
I4
C4
I8
I1
I2
I5
C3
I5
I6
S1
I7
C1
开始
结束
29
Weiler-Atherton算法 -6/6
C2
C1
C3
C4
C8 C7
C5 C6
S2
S1
S3
S4
S8 S7
S5 S6
I1 I8
I2
I3 I4
I5I6
I7
主多边形表 裁剪多边形表
S1
S2
I1
I4
S4
S6
I5
I2
I3
S3
S1
S5
S7
I6
S8
I7
I8
S5
C1
C2
C3
C4
I4I
5
I1
I8
C1
C5
C5
C6
I2
I3
I6
C7
C8
I7
算法裁剪后所生成的多边形为 I1I2I7I8I1和 I3I4I5I6I3
裁剪多边形
主多边形 开始
开始
结束
结束
第五章
图形变换与裁剪（三）
计算机学院
苏小红
2
二维裁剪
1 直线段裁剪
直接求交算法
Cohen-Sutherland算法
中点分割裁剪算法
梁友栋 -Basky算法
2 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Atherton算法
3
直线段裁剪 (1/15)
裁剪的目的
? 判断图形元素是否在裁剪窗口之内并找出其位于内部的部分
裁剪处理的基础
? 图元关于窗口内外关系的判别
? 图元与窗口的求交
裁剪、覆盖
4
直线段裁剪 (2/15)
裁剪窗口
? 矩形、圆形、一般多边形
被裁剪对象
? 线段、多边形、曲线、字符
裁剪的策略
? 先裁剪，后变换
? 先变换，后裁剪
裁剪算法的核心问题
? 效率
5
直线段裁剪 (3/15)
点裁剪
? 点 (x,y)在窗口内的充分必要条件是：
问题：对于任何多边形窗口, 如何判别？
x x xm in m a x? ?
y y ym i n m a x? ?
6
直线段裁剪 (4/15)
假定条件
? 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
? 待裁剪线段：
任何平面线段相对于凸多边形窗口进行裁剪后？
P x y P x y0 0 0 1 1 1(,) (,)
7
直线段裁剪 (5/15)
待裁剪线段和窗口的关系
? 完全落在窗口内
? 完全落在窗口外
? 部分在内，部分在外
8
直线段裁剪 (6/15)
为提高效率，算法设计时应考虑：
1,快速判断情形 (1)(2)；
2,设法减少情形 (3)求交次数和每次求交时所需的计算量
9
Cohen-Sutherland 算法 (编码算法 )
算法步骤：
第一步 判别线段两端点是否都落在窗口内，如果是，
则线段完全可见；否则进入第二步；
第二步 判别线段是否为显然不可见，如果是，则裁
剪结束；否则进行第三步 ；
第三步 求线段与窗口边延长线的交点，这个交点将
线段分为两段，其中一段显然不可见，丢弃。
对余下的另一段重新进行第一步，第二步判断，
直至结束
裁剪过程是递归的。
直线段裁剪 (7/15)
10
特点：
? 对显然不可见线段的快速判别
编码方法：
? 由窗口四条边所在直线把二维平面分成 9个区域，每个区域赋予一个四
位编码,CtCbCrCl，上下右左；
??
? ??
e ls e
yyC
t 0
m a x1 当
??
? ??
e ls e
xxC
r 0
m a x1 当
??
? ??
e ls e
xxC
l 0
m in1 当
??
? ??
e ls e
yyC
b 0
m in1 当
Cohen-Sutherland 算法
直线段裁剪 (8/15)
11
端点编码：
? 定义为它所在区域的编码
结论：
? 当线段的两个端点的编码的 逻辑“与”非零 时,显然不可见
Cohen-Sutherland 算法
直线段裁剪 (9/15)
1000
0001 00100000
0100
1001
0101 0110
1010
窗口
b
c
a
12
求交测试顺序固定 (左上右下）
最坏情形，线段求交四次。
对于那些非完全可见、又非完全不可见的线段，需要
求交,求交前 先测试 与窗口哪条边所在直线有交？
(按序判断端点编码中各位的值 ClCtCrCb）
Cohen-Sutherland 算法
直线段裁剪 (10/15)
13
1） 特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合
窗口特别小的场合
Cohen-Sutherland 算法的特点直线段裁剪 (11/15)
14
中点分割法
基本思想：
? 从 P0点出发找出距 P0最近的可见点
? 从 P1点出发找出距 P1最近的可见点
? 不断地在中点处将线段一分为二，对每段线段重复 Cohen-
Sutherland裁剪算法的线段可见性测试方法，直至找到每段线段与
窗口边界线的交点或分割子段的长度充分小可视为一点为止
取中点 Pm=(P1+P2)/2。
P2
P1
P2是离 P1点最远的可见点
Pm
P1
用 P1Pm代替 P1P2
P2
P2
用 PmP2代替 P1P2
Pm
P1
直线段裁剪 (12/15)
15
Liang-Barsky裁剪算法
直线 L与区域的交：
? 当 Q为空集时，线段 AB不可能在窗口中有可见线段。
? 当 Q不为空集时,Q可看成是一个一维窗口
P4
P1
P3
P2
ymax
ymin
xmin xmaxR
T
S
U
L
A
B
AS是一维窗口 TS中的可见部分
直线段裁剪 (13/15)
基本思想：
? 把二维裁剪化为一维裁剪问题，并向 x
（或 y）方向投影以决定可见线段。
Q ],;,[],;,[ m a xm i nm a xm i n4321 yyxxLPPPPL ?????????? ??? 口
]),;,[(]),;,[( m a xm i nm a xm i n yyLxxL ????????? ??? TURS??
16
Liang-Barsky裁剪算法
P4
P1
P3
P2
ymax
ymin
xmin xmaxR
T
S
U
L
A
B
AS是一维窗口 TS中的可见部分
直线段裁剪 (14/15)
存在可见线段的充要条件
? 不为空集
向 x轴投影，就得到可见线段上点的坐标的变化范围为
TURSAB ??
)],m a x (),,m a x (,m i n [)],m i n (),,m i n (,m a x [ m a xm i n UTBAUTBA xxxxxxxxxxx ??
)],m a x (),,m a x (,m i n [
)],m i n (),,m i n (,m a x [
m a x
m i n
UTBA
UTBA
xxxxxx
xxxxxx
?
?
?
?
左端点
右端点
17
Liang-Barsky裁剪算法
AB有可见部分的充分必要条件也可表示为
)],m a x (),,m a x (,m i n [)],m i n (),,m i n (,m a x [ m a xm i n UTBAUTBA xxxxxxxxxx ?
)],m i n (,m ax [ m i n BA xxxL ?
)],m ax (,m i n [ m a x BA xxxR ?
??
?
?
?
?
?
?
Rxx
xxL
RL
UT
UT
),m i n (
),m a x (
直线段裁剪 (15/15)
18
多边形裁剪 -1/2
用直线段裁剪算法，可以吗？
新的问题,
图 1 因丢失顶点信息而去法确定裁剪区域
A
B
A
B
图 2 原来封闭的多边形变成了孤立的线段
边界不再封闭，需要用窗口边界的恰当部分来封闭它
19
1
2
1
2
3
(a) (b) (c)
A B
图 3 裁剪后的多边形顶点形成的几种情况
分裂为几个多边形
多边形裁剪 -2/2
关键：
? 不仅在于求出新的顶点，删去界外顶点
? 还在于形成正确的顶点序列
20
Sutherland-Hodgman算法 -1/4
分割处理策略,
? 将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所
在直线的裁剪。
流水线过程 (左上右下 ),左边的结果是右边的开始 。
亦称 逐边裁剪算法
21
Sutherland-Hodgman算法 -2/4
? 内侧空间与外侧空间
? 多边形的边与半空间的关系
线段与当前裁剪边的位置关系
可见一侧
窗口
(a) 输出 Pi+1
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 无输出
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 输出 I
当前裁剪边
Pi+1
Pi
可见一侧
窗口
(a) 输出 I和 Pi+1
当前裁剪边
Pi+1 Pi
22
Sutherland-Hodgman算法 -3/4
裁剪结果的顶点构成,
? 裁剪边内侧的原顶点；
? 多边形的边与裁剪边的交点。
顺序连接。
优点：
?裁剪算法采用流水线方式，适合硬件实现。
?可推广到任意凸多边形裁剪窗口
23
Sutherland-Hodgman算法 -4/4
存在的问题
逐边裁剪要求裁剪窗口为凸多边形，那么凹多边形窗口怎么办？
逐边裁剪法对凹多边形裁剪时，裁剪后分裂为几个多边形，
这几个多边形沿边框产生多余的线段？
图 6 逐边裁剪法对凹多边形裁剪时可能出现的问题
3 2
1 8 7
695
4
10
3 2
1 7 6
54
10
89
3 2
1 7
4
10
89 5
6
原图
对左
边裁
对顶
边裁
3 2
1 7
4
10
89 5
6
对右
边裁
对底
边裁
24
Weiler-Atherton算法 -1/6
裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况
? 主多边形：被裁剪多边形，记为 SP
? 裁剪多边形：裁剪窗口，记为 CP
25
约定：
? SP与 CP均用它们顶点的环形链表定义
? 外边界取顺时针方向
? 内边界取逆时针方向
Weiler-Atherton算法 -2/6
C2
C1
C3
C4
C8 C7
C5 C6
I1 I8
I2
I3 I4
I5I6
I7
26
SP和 CP把二维平面分成两部分。
内裁剪,SP∩CP
外裁剪,SP-CP
Weiler-Atherton算法 -3/6
裁剪结果区域的边界由 SP的部分边界和
CP的部分边界两部分构成，并且在交点
处边界发生交替，即由 SP的边界转至 CP
的边界，或由 CP的边界转至 SP的边界
27
Weiler-Atherton算法 -4/6
? 主多边形与裁剪多边形 交点成对出现
? 分为如下两类：
进点,主多边形边界由此进入裁剪多边形内
出点,主多边形边界由此
离开裁剪多边形区域,
28
Weiler-Atherton算法 -5/6
C2
C1
C3
C4
S1
S2
S3 S4
S5
S6
I1
I2 I3
I4
I5
I6I7
I8
裁剪多边形 CP
主多边形 SP
算法裁剪后所生成的多边形为 I1I2I3S3I4I5I6I7S6I8 I1
主多边形表 裁剪多边形表
S1
S2
I1
S3
S4
S5
S6
I2
I3
I4
I5
I6
I7
I8
C1
C2
I3
I4
C4
I8
I1
I2
I5
C3
I5
I6
S1
I7
C1
开始
结束
29
Weiler-Atherton算法 -6/6
C2
C1
C3
C4
C8 C7
C5 C6
S2
S1
S3
S4
S8 S7
S5 S6
I1 I8
I2
I3 I4
I5I6
I7
主多边形表 裁剪多边形表
S1
S2
I1
I4
S4
S6
I5
I2
I3
S3
S1
S5
S7
I6
S8
I7
I8
S5
C1
C2
C3
C4
I4I
5
I1
I8
C1
C5
C5
C6
I2
I3
I6
C7
C8
I7
算法裁剪后所生成的多边形为 I1I2I7I8I1和 I3I4I5I6I3
裁剪多边形
主多边形 开始
开始
结束
结束
