北大计算机系多媒体与人机交互 1
第五讲 二维裁剪
5.1 直线段裁剪
直接求交算法；
Cohen-Sutherland算法；
Nicholl-Lee-Nicholl算法
中点算法
5.2 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
5.3 字符裁剪
北大计算机系多媒体与人机交互 2
直线段裁剪 (1/18)
? 裁剪的目的
– 判断图形元素是否落在裁剪窗口之内并找出
其位于内部的部分
? 裁剪的处理的基础
– 图元关于窗口内外关系的判别
– 图元与窗口的求交
? 假定条件
– 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
– 待裁剪线段：
P x y P x y0 0 0 1 1 1(,) (,)
北大计算机系多媒体与人机交互 3
直线段裁剪 (2/18)
? 待裁剪线段和窗口的关系
– 线段完全可见
– 显然不可见
– 线段至少有一端点在窗口之外，但非显然不
可见
为提高效率，算法设计时应考虑：
(一）快速判断情形 (1)(2)；
(二 ) 设法减少情形 (3)求交次数和每次求交时所需的计算量 。
北大计算机系多媒体与人机交互 4
直线段裁剪 (3/18)
? 点裁剪
– 点 (x,y)在窗口内的充分必要条件是：
问题：对于任何多边形窗口, 如何判别？
x x xm in m a x? ?
y y ym i n m a x? ?
北大计算机系多媒体与人机交互 5
直接求交算法
直线与窗口边都
写成参数形式，
求参数值。
参见 P109
北大计算机系多媒体与人机交互 6
Cohen-Sutherland 算法 (编码算法 )
算法步骤：
第一步 判别线段两端点是否都落在窗口内，如果是，
则线段 完全可见 ；否则进入第二步；
第二步 判别线段是否为 显然不可见,如果是，则裁
剪结束；否则进行第三步 ；
第三步 求线段与 窗口边延长线 的交点，这个交点将
线段分为两段，其中一段显然不可见，丢弃。
对余下的另一段重新进行第一步，第二步判断，
直至结束
裁剪过程是递归的。
北大计算机系多媒体与人机交互 7
Cohen-SutherLand算法 (编码算法 )
– 特点,对显然不可见线段的快速判别
– 编码方法,由窗口四条边所在直线把二维平面分成 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 当
北大计算机系多媒体与人机交互 8
Cohen-SutherLand算法 (编码算法 )
? 端点编码：定义为它所在区域的编码
结论：当线段的两个端点的编码的 逻辑“与”非
零 时,线段为显然不可见的
北大计算机系多媒体与人机交互 9
? 求交测试顺序固定 (左上右下）
? 最坏情形，线段求交四次。
Cohen-SutherLand算法 (编码算法 )
对于那些非完全可见、又非显然不可见的线段，需要
求交 （如，线段 AD)，求交前 先测试 与窗口哪条边所在
直线有交？ (按序判断端点编码中各位的值 ClCtCrCb）
1）特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合；
窗口特别小的场合 (如,光标拾取图形时,
光标看作小的裁剪窗口。）
北大计算机系多媒体与人机交互 10
Nicholl-Lee-Nicholl算法
? 消除 C-S算法中多次求交的情况。
? 基本想法：对 2D平面的更细的划分。
北大计算机系多媒体与人机交互 11
Nicholl-Lee-Nicholl算法
假定待裁剪线段 P0P1为非完全可见且非显然不可见。
– 步骤：
第一步，窗口四边所在的直线将二维平面划分成 9
个区域，假定 落在区域 0,4,5 P0
北大计算机系多媒体与人机交互 12
Nicholl-Lee-Nicholl算法
第二步：从 P0点向窗
口的四个角点发出
射线，这四条射线
和窗口的四条边所
在的直线一起将二
维平面划分为更多
的小区域 。
此时 P1的位置决定了 P0P1
和窗口边的相交关系。
北大计算机系多媒体与人机交互 13
Nicholl-Lee-Nicholl算法
第三步，确定 P1所在的区域 （ 判断 P1所在区域位置，可判
定 P0,P1与窗口那条边求交 ) 。
根据窗口四边的坐标值及 P0P1和各射线的斜率可确定 P1
所在的区域。
第四步，求交点，确定 P0P1的可见部分 。
特点,效率较高，但仅适合二维矩形窗口。
北大计算机系多媒体与人机交互 14
中点分割法
? 想法,从 P0点出发找出
距 P0最近的可见点，从
P1点出发找出距 P1最近
的可见点。
? 取中点 Pm=(P1+P2)/2。
（算法见框图）
北大计算机系多媒体与人机交互 15
5.2 多边形裁剪
? 错觉,直线段裁剪的组合？
? 新的问题, 1）边界不再封闭，需要用窗口边界的恰
当部分来封闭它，如何确定其边界？
北大计算机系多媒体与人机交互 16
多边形裁剪（ 2/12）
2）一个凹多边形可能被裁剪成几个小的多边形，如何
确定这些小多边形的边界？
北大计算机系多媒体与人机交互 17
Sutherland-Hodgman算法
? 分割处理策略, 将多边形关于矩形窗口的裁剪分解
为多边形关于窗口四边所在直线的裁剪。
? 流水线过程 (左上右下 ),左边的结果是上边的开始 。
亦称 逐边裁
剪算法
北大计算机系多媒体与人机交互 18
Sutherland-Hodgman算法
– 内侧空间与外侧空间
– 多边形的边与半空间的关系
北大计算机系多媒体与人机交互 19
Sutherland-Hodgman算法
? 裁剪结果的顶点构成, 裁剪边内侧的原顶点；多
边形的边与裁剪边
的交点。
? 顺序连接。
几点说明：
?裁剪算法采用流水线方式，
适合硬件实现。
?可推广到任意凸多边形裁剪
窗口
北大计算机系多媒体与人机交互 20
Weiler-Athenton算法
裁剪窗口为任意多边形（ 凸、凹、带内环） 的
情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
北大计算机系多媒体与人机交互 21
? 主多边形和裁剪多边形把二维平面分成
两部分。
? 内裁剪, A∩B
? 外裁剪, A-B
Weiler-Athenton算法
裁剪结果区域的边界由 A的部
分边界和 B的部分边界两部分
构成，并且在交点处边界发生
交替，即由 A的边界转至 B的边
界，或由 B的边界转至 A的边界
北大计算机系多媒体与人机交互 22
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出
现,它们被分为如下两类：
? 进点,主多边形边界由此进入裁剪多边形内
如,I1,I3,I5,I7,I9,I11
? 出点,主多边形边界由
此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
北大计算机系多媒体与人机交互 23
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
Weiler_Athenton裁剪算法（内裁剪）步骤：
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。
在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪
如果存在没有被跟踪过的交点，执行以下步骤：
(1)建立裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至
遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪
方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上
一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点
北大计算机系多媒体与人机交互 24
Weiler-Athenton算法
北大计算机系多媒体与人机交互 25
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边的边，如果落
在该裁剪边的内侧，将该顶点算作交点；而如果这条边
落在该裁剪边的外侧，将该顶点不看作交点
北大计算机系多媒体与人机交互 26
5.3 字符裁剪
1)基于字符串
2)基于字符
北大计算机系多媒体与人机交互 27
5.3 字符裁剪
? 基于构成字符的最小元素
– 点阵字符：点裁剪
– 矢量字符：线裁剪
北大计算机系多媒体与人机交互 28
上机作业
? 实现一个裁剪算法。
第五讲 二维裁剪
5.1 直线段裁剪
直接求交算法；
Cohen-Sutherland算法；
Nicholl-Lee-Nicholl算法
中点算法
5.2 多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法
5.3 字符裁剪
北大计算机系多媒体与人机交互 2
直线段裁剪 (1/18)
? 裁剪的目的
– 判断图形元素是否落在裁剪窗口之内并找出
其位于内部的部分
? 裁剪的处理的基础
– 图元关于窗口内外关系的判别
– 图元与窗口的求交
? 假定条件
– 矩形裁剪窗口,[xmin,xmax]X[ymin,ymax]
– 待裁剪线段：
P x y P x y0 0 0 1 1 1(,) (,)
北大计算机系多媒体与人机交互 3
直线段裁剪 (2/18)
? 待裁剪线段和窗口的关系
– 线段完全可见
– 显然不可见
– 线段至少有一端点在窗口之外，但非显然不
可见
为提高效率，算法设计时应考虑：
(一）快速判断情形 (1)(2)；
(二 ) 设法减少情形 (3)求交次数和每次求交时所需的计算量 。
北大计算机系多媒体与人机交互 4
直线段裁剪 (3/18)
? 点裁剪
– 点 (x,y)在窗口内的充分必要条件是：
问题：对于任何多边形窗口, 如何判别？
x x xm in m a x? ?
y y ym i n m a x? ?
北大计算机系多媒体与人机交互 5
直接求交算法
直线与窗口边都
写成参数形式，
求参数值。
参见 P109
北大计算机系多媒体与人机交互 6
Cohen-Sutherland 算法 (编码算法 )
算法步骤：
第一步 判别线段两端点是否都落在窗口内，如果是，
则线段 完全可见 ；否则进入第二步；
第二步 判别线段是否为 显然不可见,如果是，则裁
剪结束；否则进行第三步 ；
第三步 求线段与 窗口边延长线 的交点，这个交点将
线段分为两段，其中一段显然不可见，丢弃。
对余下的另一段重新进行第一步，第二步判断，
直至结束
裁剪过程是递归的。
北大计算机系多媒体与人机交互 7
Cohen-SutherLand算法 (编码算法 )
– 特点,对显然不可见线段的快速判别
– 编码方法,由窗口四条边所在直线把二维平面分成 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 当
北大计算机系多媒体与人机交互 8
Cohen-SutherLand算法 (编码算法 )
? 端点编码：定义为它所在区域的编码
结论：当线段的两个端点的编码的 逻辑“与”非
零 时,线段为显然不可见的
北大计算机系多媒体与人机交互 9
? 求交测试顺序固定 (左上右下）
? 最坏情形，线段求交四次。
Cohen-SutherLand算法 (编码算法 )
对于那些非完全可见、又非显然不可见的线段，需要
求交 （如，线段 AD)，求交前 先测试 与窗口哪条边所在
直线有交？ (按序判断端点编码中各位的值 ClCtCrCb）
1）特点：用编码方法可快速判断线段 --
完全可见和显然不可见。
2）特别适用二种场合：
大窗口场合；
窗口特别小的场合 (如,光标拾取图形时,
光标看作小的裁剪窗口。）
北大计算机系多媒体与人机交互 10
Nicholl-Lee-Nicholl算法
? 消除 C-S算法中多次求交的情况。
? 基本想法：对 2D平面的更细的划分。
北大计算机系多媒体与人机交互 11
Nicholl-Lee-Nicholl算法
假定待裁剪线段 P0P1为非完全可见且非显然不可见。
– 步骤：
第一步，窗口四边所在的直线将二维平面划分成 9
个区域，假定 落在区域 0,4,5 P0
北大计算机系多媒体与人机交互 12
Nicholl-Lee-Nicholl算法
第二步：从 P0点向窗
口的四个角点发出
射线，这四条射线
和窗口的四条边所
在的直线一起将二
维平面划分为更多
的小区域 。
此时 P1的位置决定了 P0P1
和窗口边的相交关系。
北大计算机系多媒体与人机交互 13
Nicholl-Lee-Nicholl算法
第三步，确定 P1所在的区域 （ 判断 P1所在区域位置，可判
定 P0,P1与窗口那条边求交 ) 。
根据窗口四边的坐标值及 P0P1和各射线的斜率可确定 P1
所在的区域。
第四步，求交点，确定 P0P1的可见部分 。
特点,效率较高，但仅适合二维矩形窗口。
北大计算机系多媒体与人机交互 14
中点分割法
? 想法,从 P0点出发找出
距 P0最近的可见点，从
P1点出发找出距 P1最近
的可见点。
? 取中点 Pm=(P1+P2)/2。
（算法见框图）
北大计算机系多媒体与人机交互 15
5.2 多边形裁剪
? 错觉,直线段裁剪的组合？
? 新的问题, 1）边界不再封闭，需要用窗口边界的恰
当部分来封闭它，如何确定其边界？
北大计算机系多媒体与人机交互 16
多边形裁剪（ 2/12）
2）一个凹多边形可能被裁剪成几个小的多边形，如何
确定这些小多边形的边界？
北大计算机系多媒体与人机交互 17
Sutherland-Hodgman算法
? 分割处理策略, 将多边形关于矩形窗口的裁剪分解
为多边形关于窗口四边所在直线的裁剪。
? 流水线过程 (左上右下 ),左边的结果是上边的开始 。
亦称 逐边裁
剪算法
北大计算机系多媒体与人机交互 18
Sutherland-Hodgman算法
– 内侧空间与外侧空间
– 多边形的边与半空间的关系
北大计算机系多媒体与人机交互 19
Sutherland-Hodgman算法
? 裁剪结果的顶点构成, 裁剪边内侧的原顶点；多
边形的边与裁剪边
的交点。
? 顺序连接。
几点说明：
?裁剪算法采用流水线方式，
适合硬件实现。
?可推广到任意凸多边形裁剪
窗口
北大计算机系多媒体与人机交互 20
Weiler-Athenton算法
裁剪窗口为任意多边形（ 凸、凹、带内环） 的
情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
北大计算机系多媒体与人机交互 21
? 主多边形和裁剪多边形把二维平面分成
两部分。
? 内裁剪, A∩B
? 外裁剪, A-B
Weiler-Athenton算法
裁剪结果区域的边界由 A的部
分边界和 B的部分边界两部分
构成，并且在交点处边界发生
交替，即由 A的边界转至 B的边
界，或由 B的边界转至 A的边界
北大计算机系多媒体与人机交互 22
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出
现,它们被分为如下两类：
? 进点,主多边形边界由此进入裁剪多边形内
如,I1,I3,I5,I7,I9,I11
? 出点,主多边形边界由
此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
北大计算机系多媒体与人机交互 23
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
Weiler_Athenton裁剪算法（内裁剪）步骤：
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。
在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪
如果存在没有被跟踪过的交点，执行以下步骤：
(1)建立裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至
遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪
方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上
一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点
北大计算机系多媒体与人机交互 24
Weiler-Athenton算法
北大计算机系多媒体与人机交互 25
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边的边，如果落
在该裁剪边的内侧，将该顶点算作交点；而如果这条边
落在该裁剪边的外侧，将该顶点不看作交点
北大计算机系多媒体与人机交互 26
5.3 字符裁剪
1)基于字符串
2)基于字符
北大计算机系多媒体与人机交互 27
5.3 字符裁剪
? 基于构成字符的最小元素
– 点阵字符：点裁剪
– 矢量字符：线裁剪
北大计算机系多媒体与人机交互 28
上机作业
? 实现一个裁剪算法。
