第 4章 图形的观察运算
赵立强
4,1 图形的开窗
图形的开窗与裁剪是图形观察运算的基础, 它们在计算机图形学中占
有非常重要的地位 。 有了开窗与裁剪这些概念之后, 在图形系统的应用中,
用户定义的各种复杂图形不再受显示设备显示范围的限制, 同时又能非常
方便地观察各种图形的输出显示, 它使用户可以把图形的输入与图形的输
出两个不同的过程联系在一起 。
4,1 图形的开窗
一, 图形学中常用的坐标系
用计算机处理图形, 离不开各种坐标系, 这些坐标系决定了计算机处
理图形的原始数据来源与图形的最终显示位置 。
1,用户坐标系
在计算机图形学中, 人们常把选择坐标系测量图形, 并将图形数据存
人计算机中保存这一过程称为定义图形, 而把用户定义原始图形所用坐标
系称为用户坐标系 。 用户常用的坐标系有：极坐标系, 对数坐标系, 球面
坐标系, 直角坐标系等, 其中又把直角坐标系称为自然坐标系或世界坐标
系 。 显然不同的坐标系适合描述不同的图形对象 。
一、图形学中常用的坐标系 (2)
2,设备坐标系
设备坐标系一般是二维平面直角整数坐标系, 它决定了计算机在显
示设备的显示平面上画点, 画线的位置 。 对于一个具体可实现的坐标系
而言, 它通常有 4个因素：
① 设备坐标系的原点, 它常位于显示平面的左下角或左上角；
② 设备坐标系的坐标轴方向, 它的 X轴一般从左指向右边, 而 y轴一
般从下指向上方或从上指向下方；
③ 坐标轴的刻度, 它常用可见点之间的距离或脉冲步进当量来度量；
④ 坐标轴的取值范围 (显示范围 ),由于受设备的精度和显示平面的
大小等因素制约, 因此显示设备的显示范围是一个有限值, 而且各种不
同的显示设备, 其显示范围都不相同 。
一、图形学中常用的坐标系 (3)
3,规格化 (设备 )坐标系
规格化坐标系为一个二维平面直角坐标系, 它的原点位于显示平面的
左下角, X轴方向从左到右, y轴方向从下到上, 且 x[0,1],y[0,1],其刻
度为无量纲的单位长度 。
由于规格化坐标系能统一用户各种图形的显示范围, 故把用户图形转
换成规格化设备坐标系上统一大小的标准图形, 这一过程称图形的逻辑输
出, 其变换称为图形的规格化变换；而把规格化设备坐标系上的标准图形
送显示设备实际输出显示, 这一过程称图形的物理输出, 其变换称为图形
的工作站变换 。
O O
O
P(1.25,2.5)
P(2,3)
P(0.25,0.5)
1
1用户坐标系 设备 坐标系 规格化 坐标系
各坐标系间的关系
有了规格化设备坐标系之后, 图形的输出显示可以在抽象的显示设
备上进行讨论, 因而这种图形学又称为与具体设备无关的图形学 。 此时,
图形系统很容易实现在多个物理设备上同时显示用户指定的同一图形 。
4．设备坐标系刻度尺寸的调整
计算机显示图形时, 通常要求显示设备坐标系的水平刻度尺寸与垂
直刻度尺寸是等距的, 这样画出的图形看起来才不会出现畸变效应 。 对
于不能满足这一要求的设备坐标系, 应调整其水平与垂直刻度尺寸 。
例如：显示器输出
在 Matlab中, 有轴的刻度属性设置
在 C语言中, 有
getaspectratio(&xasp,&yasp );
/* read the hardwareaspect */
AspectRatio= (double)xasp/ (double)yasp;
/* Get correctionfactor */
5．坐标系变换中的误差及其消除
在不同坐标系中转换图形数据, 如果处理不当, 就会产生积累误差和非线性偏差,
这在用户坐标系到设备坐标系的数据转换中表现得尤为突出 。
(1)积累误差情况
对于增量式 (向量 )图形输出显示设备 (如随机扫描图形显示器, 绘图仪等 ),若
用当前用户坐标值和下一点的用户坐标值之差 (即用户坐标的相对增量 )作为本次设
备运动的增量来绘制直线, 从数学上看似乎是正确的, 但在实际绘图中, 由于它忽
略了当前用户坐标值 (实数 )和设备坐标值 (整数 )之间的绝对误差, 有时就会产生比
较大的误差 。 当连续输出的点越多时, 这种误差就会越大, 这种由于积累而造成的
误差称为积累误差 。
例如, 设有点列 [Pi] (i=1,2,...100),其 x,y值分别为
x,10.2,10.4,...,30.0
y,10.1,10.2,...,20.0
按用户坐标的相对增量输出, 其每一步的 x,y相对坐标增量为 0.2与 0.1,四舍
五入为 0,故光点或绘图笔只能停在第一点的位置上, 一步也不走 。
为了消除积累误差, 可采用当前的用户坐标与当前的设备坐标绝对值的增量来
代替用户坐标的相对增量, 作为本次设备的运动增量 。 这样处理之后, 可使得点列
几处的计算误差不 影响 Pi+l,Pi+2,…的正确输出, 从而消除了积累误差 。
5．坐标系变换中的误差及其消除
(2)非线性偏差情况
以圆的角度微分法画圆算法为例, 在该算法中, 当用 Bresenham直
线算法来逼近圆时, 无论如何调整 Bresenham直线算法, 都不能达到用
DDA直线算法逼近该圆所能达到的显示效果 (与 Bresenham画圆效果相比
较 )。 这是因为 DDA直线算法为实数算法, 它仅在最后输出时, 才对坐标
数据进行四舍五人处理, 因而可最大限度地消除每一显示点与理想圆之
间的非线性偏差 。 而 Bresenham直线算法为整数算法, 它先对直线端点
进行四舍五人处理, 故它在推算每一显示点之前, 已经人为地引入了计
算偏差, 因而它的显示效果不如 DDA直线算法 。
这一例子说明：整数算法较适合描绘整数图形, 而实数算法既能描
绘整数图形, 也能描绘实数图形 。 一般说来, 实数算法比整数算法的精
度高 (其精度仅受变量精度的影响 ),且适用性更广, 但它的实现较为复
杂 。
二、窗口、视区及窗视坐标变换
1,窗口
通常用户在自然坐标系中定义图形, 这个被定义图形的大小和复杂
程度是没有限制的 。 对于这类图形, 人们有时需要观察了解整个图形的
全貌, 这就要求把用户坐标系中较大指定范围 (见图 (a))中的图形全部送
显示屏中输出显示, 见图 (b)；有时需要详细地观察了解某一局部范围内
的图形, 如图 (a)中小虚线方框所示的局部图形此时最好把这一局部图形
进行放大并使其图形占满整个显示平面, 见图 (c)。 通常这个在用户坐标
系中指定的显示范围称为窗口, 显然此时窗口内的图形是用户希望出现
在显示屏幕上的, 窗口外的图形是用户不希望出现在显示屏幕上的, 因
此窗口是裁剪图形的标准参照物 。
2．视区
显示器屏幕的作用是用于显示图形与字符 。 但是人们为了提高屏幕的
利用率, 丰富屏幕的显示内容, 常把显示屏幕划分成几个不同的显示区域,
以实现显示内容的分类输出 。
3．窗口与视区的关系
窗口与视区是两个完全不同的概念, 它们之间既有联系又有区别 。 它们的联系
是, 一个窗口内的图形一定要送到一个相应的视区中显示出来 。 它们的区别是：
① 窗口定义在用户坐标系中, 而视区定义在屏幕坐标系中；
② 窗口能定义一个, 也能定义数个, 且多个窗口允许嵌套, 即窗口中还能再定
义窗口；而视区定义的个数一般由窗口的个数确定, 以保证窗口与视区之间具有一
一对应的关系；
③ 窗口能进行移动, 放大缩小与旋转等几何变换, 这一变换又称窗口漫游；而
视区一般不能进行几何变换 。
图形的观察运算
有了窗口与视区的概念之后, 图形的输入与图形的输出就可分开进
行 。
在图形的输入中, 用户定义图形摆脱了显示屏幕等因素的限制, 其
图形的大小与复杂程度等都是任意的 。 而图形的输出显示也显得非常灵
活, 用户需要看哪一部分图形, 只要适当地调整窗口的大小与位置就能
达到输出显示图形的目的 。
此时计算机扫描图形文件中保存的所有图形数据, 在经过裁剪之后,
只有那些位于窗口内的图形的图形数据通过窗视变换, 再变换成屏幕坐
标数据, 送往屏幕中相应的视区进行显示, 这一过程称为图形的 观察运
算 。
4．窗口与视区中图形的坐标变换
由于屏幕视区仅仅显示窗口中的图形, 因此有必要研究窗口内的图
形如何转换成视区中的图形, 即窗口与视区中图形的变换关系 。
已知在用户坐标系中定义的窗口左下角, 右上角坐标分别为
(xWmin,yWmin),(xWmax,yWmax)
而在屏幕坐标系中定义的视区左下角, 右上角坐标分别为
(xVmin,yVmin),(xVmax,yVmax)
利用相似原理, 可以把窗口中的一点 P(xW,yW)变换成视区中的一点
P’(xV,yV),即点 P在窗口中的相对位置等于点 P’在视区中的相对位置,
见图 4—5,这要求点 P在窗口中 x轴方向的相对位置与点 P’在视区中 x轴, y
轴方向的相对位置相等,
视窗变换
这个表达式称为窗视变换 。
由于视区一般不进行几何变换, 而窗口常作漫游, 因此读者可讨论
当窗口的参数发生变化时, 它对视区中图形显示效果的影响 。
4,2 图形的裁剪
只有位于窗口内的图形才能经过窗视变换送视区中输出显示, 而在用户坐标
系中究竟有哪些图形位于窗口内或窗口外, 只有通过裁剪过程才能判别出来, 由
此可见图形的裁剪在图形的输出显示过程中的重要地位 。
在一个基本的二维图形系统中, 至少应提供点, 字符, 直线, 曲线以及实面
积多边形等多种简单图形元素, 供用户生成各种复杂的应用图形, 因此图形系统
中对这些简单图形元素进行裁剪是必然的 。
一, 点与字符的裁剪
点的裁剪比较简单 。 当图形系统的窗口确定之后, 设被裁剪的点坐标为 (x,y)，
则只有当 该点的坐标满足下式：
时, 该点才位于窗口之内, 并经窗视变换送视区中显示；否则该点位于窗口之外
而被舍去 。
字符的裁剪，根据裁剪精度不同，
可分三种情况，如图。
二、直线的裁剪
要判别直线段与窗口是否相交, 通过求解该直线段与窗口
有效边框的联立方程得到其交点, 再判断交点是否位于被裁剪
的线段上, 同时又位于窗口的某条有效边框上 (简称先求交, 后
判有效性 )。 这样处理, 图形显示速度太慢, 下面介绍的直线编
码裁剪算法 (又称直线的 Gohen—Sutherland裁剪算法 )能有效地
提高裁剪速度 。
该算法的步骤是先简单地判别出直线是全部位于窗口内或
是在窗口外同一侧, 因而直线可以直接画出或直接舍弃；只有
不属这两种情况之后, 再去计算直线与窗口的有效交点, 直至
完成裁剪 (简称先粗判有效性, 后求交点 )。 这样能避免盲目地
求交点等费时运算, 从而提高裁剪图形的运算速度 。 这种处理
求交问题的思想, 将贯穿于整个图形学的求交算法过程中 。
1．直线的编码裁剪算法
直线的编码裁剪算法对直线的直接舍取测试用以下方法实现 。
① 定义编码状态表, 即延长窗口的各边, 使其把平面空间划分成九个区域,
每个区域有一个四位代码 (见图 )。 四位代码中各位的意义如下：
第一位：区域在窗口左边界之左侧, 代码为 l,否则代码为 0;
第二位：区域在窗口右边界之右侧, 代码为 l,否则代码为 0；
第三位：区域在窗口底边界之下, 代码为 1,否则代码为 0；
第四位：区域在窗口顶边界之上, 代码为 1,否则代码为 0
0110
0010
1010
0100
0000(窗口）
1000
0101
0001
1001
第四位代码 第一位代码裁剪空间编码状态表
② 直线的两端点按其所在区域被赋于相应代码, 称直线的端点状态
代码 。
③ 测试直线的端点状态, 排除直线段与窗口无交点的二种情况 。 当直
线的两端点状态代码都为零, 说明该线段全位于窗口之内；而当直线的两
端点状态代码的逻辑, 与, 不等于全零 (≠ 0000),说明该线段位于窗外同
一侧 。 这一结论读者不妨对照图 4—7所示的结果自己验算其正确性 。
④ 不能通过上述测试的线段, 再求它与窗口边框的有效交点 。 在具体
的求交过程中, 要求舍弃完全位于窗外部分的直线段, 而对剩余部分的直
线段, 主要通过再次赋给交点处的端点状态代码, 再次测试, 再次求交,
直至能判断出裁剪剩余的部分直线段是否位于窗口内或在窗外 。
0110
0010
1010
0100
0000(窗口）
1000
0101
0001
1001
第四位代码 第一位代码裁剪空间编码状态表
直线的编码裁减算法程序
2．直线的中点对分裁剪算法
实际上直线的裁剪过程既能在用户坐标系中进行, 也能在设备坐标
系中进行 。 由于设备坐标系是整数坐标系, 因此它非常适合于用中点对
分法来具体实现裁剪直线 。
直线的中点对分裁剪算法的原理与直线的编码裁剪算法原理类似,
它也是用直线的端点状态编码判断其端点位于窗口内外, 以便能先对直
线进行直接地舍取处理, 只有对那些不能通过测试的直线段才去求窗口
与直线的交点 。
中点对分裁剪算法与编码裁剪算法的区别仅在于：当求窗口与直线
的交点时, 本算法是用逐次求直线的中点来逼近其交点, 且求中点的次
数不超过 log2n次, 其中 n=max{|x|,|y|),x,y是直线两端点在 X,Y方
向上的增量 。
该算法的优点是便于用硬件实现, 求两个交点的过程可以并行进行 。
直线的中点对分裁剪算法程序
三、曲线的裁剪
计算机图形系统中常使用的曲线通常可分为两大类, 一类如圆弧,
椭圆弧等二次曲线；另一类是用分段方式描述定义的自由曲线如三次样
条曲线, 三次参数样条曲线, 贝齐埃曲线和 B样条曲线等 。
对于二次曲线, 既可采用, 先裁剪, 后生成,, 也可采用, 边生成,
边裁剪, 的方法来完成这类图形的输出显示处理 。
所谓, 先裁剪, 后生成, 是指对于圆弧这类二次曲线, 可利用公式,
先求窗口各边框与圆弧的有效交点, 只有位于窗口内的有效圆弧才能送
显示器视区进行显示, 位于窗外的无效圆弧不送视区显示 。 为了减少盲
目地求窗口边框与圆弧的交点的次数, 可先判断窗口与圆弧的最小外接
矩形是否相交, 若窗口与其最小外接矩形不相交, 说明圆弧位于窗内或
窗外, 因而可直接输出显示或舍弃, 只有不满足此条件的圆弧, 才去具
体求其与窗口的有效交点 。
所谓的, 边生成, 边裁剪, 由于三次样条曲线, 三次参数样条曲线,
贝齐埃曲线和 B样条曲线等自由曲线的生成, 都是在其参变量 t(或自变量
x)的区间中, 通过分割参变量 (或自变量 )来生成曲线上的各点, 然 后在
其两点之间用小段直线来逼近曲线, 因此对这类自由曲线的裁剪都可转
换成对这些小段直线的裁剪 。 这就是说, 对于分段的自由曲线裁剪是通
过在生成曲线的过程中, 裁剪其各个逼近曲线的小段直线来达到裁剪曲
线的目的 (即所谓的, 边生成, 边裁剪, )。
而且由于在这些曲线中, 一般大多数逼近曲线的小段直线或是位于
窗内或是位于窗外, 只有一小部分直线段正好位于窗口的边界上, 故对
这类曲线的裁剪输出与生成整条曲线相比较, 其速度一般不会使人感到
有很明显的下降 。 如果我们能利用这类曲线的最小外接矩形来减少盲目
求解窗口与曲线的交点的计算次数, 就能更有效地提高裁剪曲线的速度 。
对于这类曲线之所以不采用, 先裁剪, 后生成, 的输出处理方法, 是因
为对于这类分段自由曲线, 一是没有求解窗边直线与这些分段曲线交点
的简化公式 (三次曲线的反函数公式表达复杂 ),二是使用起来不够方便,
还不如采用, 边生成, 边裁剪, 的方法处理曲线裁剪的效率高 。
四、实面积多边形的裁剪
实面积多边形被裁剪之后仍为实面积图形, 这就要求裁剪之后实面积
图形的边界是自然封闭的 。 因此实面积多边形的裁剪不能简单地套用直线
的裁剪算法 。
实面积图形的裁剪有下述两种方法 。
1,利用两环的集合, 交, 运算来裁剪实面积多边形
这里可以假设窗口是一个封闭且透明的多边形, 而待裁剪实面积多边
形与窗口的顶点数据都按, 环, 的要求存放, 那么这两个多边形, 交, 运
算的结果即为实面积多边形被窗口裁剪之后所生成的多边形, 而且这个待
裁剪的实面积多边形既可以是一个凸多边形, 也可以是一个凹的或带孔的
多边形, 同时它还能避免退化边的处理 。 利用两环的, 交, 运算来裁剪实
面积多边形是一个通用而复杂的软件裁剪方法 。
2．多边形的逐边裁剪算法
多边形的逐边裁剪算法 (1974年由 Sutherland和 Hodgman提出 )的 。 出
发点是把解决复杂问题的全过程分解成几个简单的过程, 从而使该问题
的解决最终得到简化 。
逐边裁剪算法的原理是：先用窗口的一条边框对整个多边形进行裁
剪, 保留裁剪后位于该边框可见区域内的部分图形, 丢掉其不可见区域
内的部分图形, 得到一个或若干个新的封闭多边形 。 当用窗口的第一条
边框裁剪处理完之后, 再用第二条边框对那些新生成的多边形进行裁剪,
如此下去, 直至窗口的四条边框都裁剪完毕 。
显然窗口的一条边框 (两端无限延长 )与多边形之间的关系是：两者
或是不相交, 或是重叠, 或是相交, 或是相交且交于多边形边线的端点
处 。 对于这些情况可分别用窗, 口的一条边框与多边形边线的相互关系
来代替, 可以把窗边与多边形的边线之间的关系归纳成下述几种情况 。
第一种情况：多边形的顶点 S,P位于窗口边框 eA的可见侧, 如图 (a)
所示, 则多边形的一条边 SP也完全落于其可见侧, 因此顶点 S,P坐标应
存入新多边形的顶点序列中 。
第二种情况：多边形的边 SP与窗口边框 eA相交, 且交点为 I,而顶点
S位于其可见侧, 如图 (b)所示, 则 S点和 I点坐标应存人新多边形的顶点
序列中 。
第三种情况：多边形的顶点 S,P均位于窗口边框 cA的不可见侧, 如
图 (c)所示, 因此把 S,P点坐标都丢掉 。
第四种情况：多边形的边 SP与窗口边框 eA相交且交点为 I,而 P点位于窗口边框
的可见侧, 如图 (d)所示, 因此把 I点和 P点坐标存入新多边形的顶点序列中 。
多边形的边 SP与窗边 eA的关系除了上述四种典型关系之外, 还有下述几种特殊
关系要作相应特殊处理 。
第五种情况：多边形的边 SP与窗边 eA完全重合, 如图 (e)所示, 则 S,P点坐标
都丢掉, 这样处理不会影响最后新多边形的封闭性 (因为裁剪多边形后要用窗边去
进行封闭处理 )。
第六种情况：多边形的两点 SP,如果其中一点位于窗边的可见侧, 另一点正好
位于窗口的边框上 (即边 SP与窗边相切, 如图 (f)所示 ),则 S,P两点坐标都存人新
多边形的顶点序列中；如果 S,P两点中, 其中一点位于窗口边框的不可见侧, 而另
一点正好位于窗口的边框上, 如图 (f)所示, 则 S,P两点坐标都丢掉 。
该算法能有效
处理各种奇异
多边形的保证 。
这里的 k为窗
口的边框数 。
当多边形的所有顶点都按这几种情况处理完毕之后, 所保存的顶点与交点就
是所组成的数个新多边形的顶点 。 为使新多边形封闭, 注意还要裁剪 VnV1所组成
的边 (V1,Vn)分别是多边形的第一个与最后一个顶点 )。
算法特点：
(1)多边形的逐边裁剪算法实际上是一个通用的裁剪算法, 它既可以裁剪凸多
边形, 也可以裁剪凹多边形, 带孔多边形以及各种奇异多边形 。
(2)该算法的原理简单, 实现方便, 既能用硬件方法实现, 也可软件方法实现 。
(3)在实现该算法时, 如果保留每次裁剪之后的中间结果, 这一中间结果会占
用很大的存储空间, 但如果能用递归的方式实现该算法, 则不用保留每次裁剪之
后的中间结果 。 如果补充新规则使多边形自然封闭, 则不会出现退化边等问题,
这对于用硬件方式实现该算法非常有用 。 因为用硬件方式实现该算法时, 不可能
预留足够的空间去保存那些中间结果 。
所谓用 递归方式 实现该裁剪算法是指窗口对多边形的裁剪可这样进行：首先
按多边形的顶点次序依次裁剪多边形的每条边, 而对多边形的每条边先用窗口的
第一条边框去裁剪, 当这条边通过窗口的第一条边框裁剪之后, 再用窗口的第二
条边框去裁剪, 如果它通过第 二条边框的裁剪之后, 再用窗口的第三, 四条边框
去裁剪；最后通过第四条边框裁剪输出的顶点与交点, 就是被窗口裁剪之后新多
边形的顶点 。 不能通过 上 述四步裁剪的边线, 其顶点与交 点自然被舍掉, 因而对
应的边线也被裁掉 。
递归方式的结点数据格式
用递归方式实现多边形的逐边裁剪算法时, 它要求多边形的结点数
据格式为,
这里多边形的顶点, 交点与重合点统称多边形的结点, 此时暂不考虑对多
边形重合点也即第五, 第六种情况的处理 。
0：说明该点 P为多边形的顶点；
1：说明该点 P为多边形边线上的交点；
2：说明该点 P的坐标数据无意义，它仅用于通知算法流程应处
理多边形的最后一条边 VnV1，使多边形进入闭合处理 。
标志位 =
P点坐标数据 标志位①
② 此时多边形的顶点次序为 V1V2...V1，其中最后的 V1点的坐标无意义，
裁剪算法仅利用具标志位, 2”，使本级与下一级多边形的裁剪等流程进
入闭合处理。
递归方式多边形的逐边裁剪算法的流程
当被裁剪多边形
的各顶点数据转
化成上述约定的
数据格式之后，
可把结点 Vi(i=1，
2,…,n+1)依次
传递给 Pl变量包
括其标志位 )，
并调用第一条裁
剪边框 e1的裁剪
处理流程，并遂
一进行这一过程，
直至处理完多边
形的所有结点为
止。
二个多边形逐边裁剪的例题
逐边裁剪算法流程表
多边形被裁剪之后, 如果仅按照其输出各结点的先后次序, 把各结点依次连接
起来, 即 1‘一 4一 2’一 3‘一 4’一 5‘一 7一 6’一 8‘一 1’, 这时就会有退化边问题 (退化边是新
多边形的两条边界相互异向重叠且位于同一窗边上的结果, 此退化边即新多边形的
悬边 )。 为了消除多边形裁剪之后出现的退化边问题, 可以利用此时各结点中的顶点,
交点, 进入闭合等标志位, 提出新的补充规则, 使裁剪之后的多边形自然封闭又无
退化边 。
裁剪之后组成新多边形外环的规则如下 。
① 依次连接最后输出的交点与顶点, 顶点与顶点或顶点与交点的连线为新多边
形的有效边 。 此例有效边为 l’一 4,4一 2‘,5’一 7,7—6‘；
② 依次连接不在一条边框上出现的交点与交点的连线为新多边形的有效边 。 此
例有效边为 3‘一 4’；
③ 对每条窗口边框上出现的交点, 按环的环行方向进行排序, 成对交点之间的
连线即为新多边形的有效边 。 此例中 e1边框上的交点排序结果为 8‘,3’,2‘,l’,因此
其有效边为 8‘一 3’,2’一 1‘。 而 e2边框上的交点排序结果为 6’,5‘,4’,8‘,因此其有效
边为 6’一 5‘,4’一 8‘；
④ 多边形要封闭, 则其有效边必然首尾相连 。 针对上述各有效边, 可得新多边
形的各外环分别是 1‘一 4一 2’一 1‘,3’一 4‘一 8’一 3‘,5’一 7一 6‘一 5’。
例 4-2 对于图所示的带孔多边形，用递归方式
的逐边裁剪算法裁剪该多边形。
可以看出由于内环 2被窗口裁开, 因此内环 2与多边形被裁
开的外环一起组成新多边形的外环；而内环 l由于它没有被窗口
裁开, 故它是新多边形的内环根据上例组成新多边形外环的规
则, 此时有
① 不在一条窗口边框上的交点之间连线为有效边即 3‘—2‘，
9’—8‘；
② e1边框上的交点排序结果为 5‘,10’,8‘,6’,则有效边为
8‘--6’,而 5‘—10‘为一个退化角点舍去；
③ e2边框上的交点排序结果为 2‘,9’,5‘,10’,则有效边为
2‘—9‘,而 5’—10‘为一个退化角点舍去；
④ e4边框上只有两个交点, 则有效边为 6’--3’。
多边形封闭要求其有效边首尾相连, 故有 3‘—2‘—9‘—8‘—6‘—
3‘。 至此完成了该多边形的裁剪 。
赵立强
4,1 图形的开窗
图形的开窗与裁剪是图形观察运算的基础, 它们在计算机图形学中占
有非常重要的地位 。 有了开窗与裁剪这些概念之后, 在图形系统的应用中,
用户定义的各种复杂图形不再受显示设备显示范围的限制, 同时又能非常
方便地观察各种图形的输出显示, 它使用户可以把图形的输入与图形的输
出两个不同的过程联系在一起 。
4,1 图形的开窗
一, 图形学中常用的坐标系
用计算机处理图形, 离不开各种坐标系, 这些坐标系决定了计算机处
理图形的原始数据来源与图形的最终显示位置 。
1,用户坐标系
在计算机图形学中, 人们常把选择坐标系测量图形, 并将图形数据存
人计算机中保存这一过程称为定义图形, 而把用户定义原始图形所用坐标
系称为用户坐标系 。 用户常用的坐标系有：极坐标系, 对数坐标系, 球面
坐标系, 直角坐标系等, 其中又把直角坐标系称为自然坐标系或世界坐标
系 。 显然不同的坐标系适合描述不同的图形对象 。
一、图形学中常用的坐标系 (2)
2,设备坐标系
设备坐标系一般是二维平面直角整数坐标系, 它决定了计算机在显
示设备的显示平面上画点, 画线的位置 。 对于一个具体可实现的坐标系
而言, 它通常有 4个因素：
① 设备坐标系的原点, 它常位于显示平面的左下角或左上角；
② 设备坐标系的坐标轴方向, 它的 X轴一般从左指向右边, 而 y轴一
般从下指向上方或从上指向下方；
③ 坐标轴的刻度, 它常用可见点之间的距离或脉冲步进当量来度量；
④ 坐标轴的取值范围 (显示范围 ),由于受设备的精度和显示平面的
大小等因素制约, 因此显示设备的显示范围是一个有限值, 而且各种不
同的显示设备, 其显示范围都不相同 。
一、图形学中常用的坐标系 (3)
3,规格化 (设备 )坐标系
规格化坐标系为一个二维平面直角坐标系, 它的原点位于显示平面的
左下角, X轴方向从左到右, y轴方向从下到上, 且 x[0,1],y[0,1],其刻
度为无量纲的单位长度 。
由于规格化坐标系能统一用户各种图形的显示范围, 故把用户图形转
换成规格化设备坐标系上统一大小的标准图形, 这一过程称图形的逻辑输
出, 其变换称为图形的规格化变换；而把规格化设备坐标系上的标准图形
送显示设备实际输出显示, 这一过程称图形的物理输出, 其变换称为图形
的工作站变换 。
O O
O
P(1.25,2.5)
P(2,3)
P(0.25,0.5)
1
1用户坐标系 设备 坐标系 规格化 坐标系
各坐标系间的关系
有了规格化设备坐标系之后, 图形的输出显示可以在抽象的显示设
备上进行讨论, 因而这种图形学又称为与具体设备无关的图形学 。 此时,
图形系统很容易实现在多个物理设备上同时显示用户指定的同一图形 。
4．设备坐标系刻度尺寸的调整
计算机显示图形时, 通常要求显示设备坐标系的水平刻度尺寸与垂
直刻度尺寸是等距的, 这样画出的图形看起来才不会出现畸变效应 。 对
于不能满足这一要求的设备坐标系, 应调整其水平与垂直刻度尺寸 。
例如：显示器输出
在 Matlab中, 有轴的刻度属性设置
在 C语言中, 有
getaspectratio(&xasp,&yasp );
/* read the hardwareaspect */
AspectRatio= (double)xasp/ (double)yasp;
/* Get correctionfactor */
5．坐标系变换中的误差及其消除
在不同坐标系中转换图形数据, 如果处理不当, 就会产生积累误差和非线性偏差,
这在用户坐标系到设备坐标系的数据转换中表现得尤为突出 。
(1)积累误差情况
对于增量式 (向量 )图形输出显示设备 (如随机扫描图形显示器, 绘图仪等 ),若
用当前用户坐标值和下一点的用户坐标值之差 (即用户坐标的相对增量 )作为本次设
备运动的增量来绘制直线, 从数学上看似乎是正确的, 但在实际绘图中, 由于它忽
略了当前用户坐标值 (实数 )和设备坐标值 (整数 )之间的绝对误差, 有时就会产生比
较大的误差 。 当连续输出的点越多时, 这种误差就会越大, 这种由于积累而造成的
误差称为积累误差 。
例如, 设有点列 [Pi] (i=1,2,...100),其 x,y值分别为
x,10.2,10.4,...,30.0
y,10.1,10.2,...,20.0
按用户坐标的相对增量输出, 其每一步的 x,y相对坐标增量为 0.2与 0.1,四舍
五入为 0,故光点或绘图笔只能停在第一点的位置上, 一步也不走 。
为了消除积累误差, 可采用当前的用户坐标与当前的设备坐标绝对值的增量来
代替用户坐标的相对增量, 作为本次设备的运动增量 。 这样处理之后, 可使得点列
几处的计算误差不 影响 Pi+l,Pi+2,…的正确输出, 从而消除了积累误差 。
5．坐标系变换中的误差及其消除
(2)非线性偏差情况
以圆的角度微分法画圆算法为例, 在该算法中, 当用 Bresenham直
线算法来逼近圆时, 无论如何调整 Bresenham直线算法, 都不能达到用
DDA直线算法逼近该圆所能达到的显示效果 (与 Bresenham画圆效果相比
较 )。 这是因为 DDA直线算法为实数算法, 它仅在最后输出时, 才对坐标
数据进行四舍五人处理, 因而可最大限度地消除每一显示点与理想圆之
间的非线性偏差 。 而 Bresenham直线算法为整数算法, 它先对直线端点
进行四舍五人处理, 故它在推算每一显示点之前, 已经人为地引入了计
算偏差, 因而它的显示效果不如 DDA直线算法 。
这一例子说明：整数算法较适合描绘整数图形, 而实数算法既能描
绘整数图形, 也能描绘实数图形 。 一般说来, 实数算法比整数算法的精
度高 (其精度仅受变量精度的影响 ),且适用性更广, 但它的实现较为复
杂 。
二、窗口、视区及窗视坐标变换
1,窗口
通常用户在自然坐标系中定义图形, 这个被定义图形的大小和复杂
程度是没有限制的 。 对于这类图形, 人们有时需要观察了解整个图形的
全貌, 这就要求把用户坐标系中较大指定范围 (见图 (a))中的图形全部送
显示屏中输出显示, 见图 (b)；有时需要详细地观察了解某一局部范围内
的图形, 如图 (a)中小虚线方框所示的局部图形此时最好把这一局部图形
进行放大并使其图形占满整个显示平面, 见图 (c)。 通常这个在用户坐标
系中指定的显示范围称为窗口, 显然此时窗口内的图形是用户希望出现
在显示屏幕上的, 窗口外的图形是用户不希望出现在显示屏幕上的, 因
此窗口是裁剪图形的标准参照物 。
2．视区
显示器屏幕的作用是用于显示图形与字符 。 但是人们为了提高屏幕的
利用率, 丰富屏幕的显示内容, 常把显示屏幕划分成几个不同的显示区域,
以实现显示内容的分类输出 。
3．窗口与视区的关系
窗口与视区是两个完全不同的概念, 它们之间既有联系又有区别 。 它们的联系
是, 一个窗口内的图形一定要送到一个相应的视区中显示出来 。 它们的区别是：
① 窗口定义在用户坐标系中, 而视区定义在屏幕坐标系中；
② 窗口能定义一个, 也能定义数个, 且多个窗口允许嵌套, 即窗口中还能再定
义窗口；而视区定义的个数一般由窗口的个数确定, 以保证窗口与视区之间具有一
一对应的关系；
③ 窗口能进行移动, 放大缩小与旋转等几何变换, 这一变换又称窗口漫游；而
视区一般不能进行几何变换 。
图形的观察运算
有了窗口与视区的概念之后, 图形的输入与图形的输出就可分开进
行 。
在图形的输入中, 用户定义图形摆脱了显示屏幕等因素的限制, 其
图形的大小与复杂程度等都是任意的 。 而图形的输出显示也显得非常灵
活, 用户需要看哪一部分图形, 只要适当地调整窗口的大小与位置就能
达到输出显示图形的目的 。
此时计算机扫描图形文件中保存的所有图形数据, 在经过裁剪之后,
只有那些位于窗口内的图形的图形数据通过窗视变换, 再变换成屏幕坐
标数据, 送往屏幕中相应的视区进行显示, 这一过程称为图形的 观察运
算 。
4．窗口与视区中图形的坐标变换
由于屏幕视区仅仅显示窗口中的图形, 因此有必要研究窗口内的图
形如何转换成视区中的图形, 即窗口与视区中图形的变换关系 。
已知在用户坐标系中定义的窗口左下角, 右上角坐标分别为
(xWmin,yWmin),(xWmax,yWmax)
而在屏幕坐标系中定义的视区左下角, 右上角坐标分别为
(xVmin,yVmin),(xVmax,yVmax)
利用相似原理, 可以把窗口中的一点 P(xW,yW)变换成视区中的一点
P’(xV,yV),即点 P在窗口中的相对位置等于点 P’在视区中的相对位置,
见图 4—5,这要求点 P在窗口中 x轴方向的相对位置与点 P’在视区中 x轴, y
轴方向的相对位置相等,
视窗变换
这个表达式称为窗视变换 。
由于视区一般不进行几何变换, 而窗口常作漫游, 因此读者可讨论
当窗口的参数发生变化时, 它对视区中图形显示效果的影响 。
4,2 图形的裁剪
只有位于窗口内的图形才能经过窗视变换送视区中输出显示, 而在用户坐标
系中究竟有哪些图形位于窗口内或窗口外, 只有通过裁剪过程才能判别出来, 由
此可见图形的裁剪在图形的输出显示过程中的重要地位 。
在一个基本的二维图形系统中, 至少应提供点, 字符, 直线, 曲线以及实面
积多边形等多种简单图形元素, 供用户生成各种复杂的应用图形, 因此图形系统
中对这些简单图形元素进行裁剪是必然的 。
一, 点与字符的裁剪
点的裁剪比较简单 。 当图形系统的窗口确定之后, 设被裁剪的点坐标为 (x,y)，
则只有当 该点的坐标满足下式：
时, 该点才位于窗口之内, 并经窗视变换送视区中显示；否则该点位于窗口之外
而被舍去 。
字符的裁剪，根据裁剪精度不同，
可分三种情况，如图。
二、直线的裁剪
要判别直线段与窗口是否相交, 通过求解该直线段与窗口
有效边框的联立方程得到其交点, 再判断交点是否位于被裁剪
的线段上, 同时又位于窗口的某条有效边框上 (简称先求交, 后
判有效性 )。 这样处理, 图形显示速度太慢, 下面介绍的直线编
码裁剪算法 (又称直线的 Gohen—Sutherland裁剪算法 )能有效地
提高裁剪速度 。
该算法的步骤是先简单地判别出直线是全部位于窗口内或
是在窗口外同一侧, 因而直线可以直接画出或直接舍弃；只有
不属这两种情况之后, 再去计算直线与窗口的有效交点, 直至
完成裁剪 (简称先粗判有效性, 后求交点 )。 这样能避免盲目地
求交点等费时运算, 从而提高裁剪图形的运算速度 。 这种处理
求交问题的思想, 将贯穿于整个图形学的求交算法过程中 。
1．直线的编码裁剪算法
直线的编码裁剪算法对直线的直接舍取测试用以下方法实现 。
① 定义编码状态表, 即延长窗口的各边, 使其把平面空间划分成九个区域,
每个区域有一个四位代码 (见图 )。 四位代码中各位的意义如下：
第一位：区域在窗口左边界之左侧, 代码为 l,否则代码为 0;
第二位：区域在窗口右边界之右侧, 代码为 l,否则代码为 0；
第三位：区域在窗口底边界之下, 代码为 1,否则代码为 0；
第四位：区域在窗口顶边界之上, 代码为 1,否则代码为 0
0110
0010
1010
0100
0000(窗口）
1000
0101
0001
1001
第四位代码 第一位代码裁剪空间编码状态表
② 直线的两端点按其所在区域被赋于相应代码, 称直线的端点状态
代码 。
③ 测试直线的端点状态, 排除直线段与窗口无交点的二种情况 。 当直
线的两端点状态代码都为零, 说明该线段全位于窗口之内；而当直线的两
端点状态代码的逻辑, 与, 不等于全零 (≠ 0000),说明该线段位于窗外同
一侧 。 这一结论读者不妨对照图 4—7所示的结果自己验算其正确性 。
④ 不能通过上述测试的线段, 再求它与窗口边框的有效交点 。 在具体
的求交过程中, 要求舍弃完全位于窗外部分的直线段, 而对剩余部分的直
线段, 主要通过再次赋给交点处的端点状态代码, 再次测试, 再次求交,
直至能判断出裁剪剩余的部分直线段是否位于窗口内或在窗外 。
0110
0010
1010
0100
0000(窗口）
1000
0101
0001
1001
第四位代码 第一位代码裁剪空间编码状态表
直线的编码裁减算法程序
2．直线的中点对分裁剪算法
实际上直线的裁剪过程既能在用户坐标系中进行, 也能在设备坐标
系中进行 。 由于设备坐标系是整数坐标系, 因此它非常适合于用中点对
分法来具体实现裁剪直线 。
直线的中点对分裁剪算法的原理与直线的编码裁剪算法原理类似,
它也是用直线的端点状态编码判断其端点位于窗口内外, 以便能先对直
线进行直接地舍取处理, 只有对那些不能通过测试的直线段才去求窗口
与直线的交点 。
中点对分裁剪算法与编码裁剪算法的区别仅在于：当求窗口与直线
的交点时, 本算法是用逐次求直线的中点来逼近其交点, 且求中点的次
数不超过 log2n次, 其中 n=max{|x|,|y|),x,y是直线两端点在 X,Y方
向上的增量 。
该算法的优点是便于用硬件实现, 求两个交点的过程可以并行进行 。
直线的中点对分裁剪算法程序
三、曲线的裁剪
计算机图形系统中常使用的曲线通常可分为两大类, 一类如圆弧,
椭圆弧等二次曲线；另一类是用分段方式描述定义的自由曲线如三次样
条曲线, 三次参数样条曲线, 贝齐埃曲线和 B样条曲线等 。
对于二次曲线, 既可采用, 先裁剪, 后生成,, 也可采用, 边生成,
边裁剪, 的方法来完成这类图形的输出显示处理 。
所谓, 先裁剪, 后生成, 是指对于圆弧这类二次曲线, 可利用公式,
先求窗口各边框与圆弧的有效交点, 只有位于窗口内的有效圆弧才能送
显示器视区进行显示, 位于窗外的无效圆弧不送视区显示 。 为了减少盲
目地求窗口边框与圆弧的交点的次数, 可先判断窗口与圆弧的最小外接
矩形是否相交, 若窗口与其最小外接矩形不相交, 说明圆弧位于窗内或
窗外, 因而可直接输出显示或舍弃, 只有不满足此条件的圆弧, 才去具
体求其与窗口的有效交点 。
所谓的, 边生成, 边裁剪, 由于三次样条曲线, 三次参数样条曲线,
贝齐埃曲线和 B样条曲线等自由曲线的生成, 都是在其参变量 t(或自变量
x)的区间中, 通过分割参变量 (或自变量 )来生成曲线上的各点, 然 后在
其两点之间用小段直线来逼近曲线, 因此对这类自由曲线的裁剪都可转
换成对这些小段直线的裁剪 。 这就是说, 对于分段的自由曲线裁剪是通
过在生成曲线的过程中, 裁剪其各个逼近曲线的小段直线来达到裁剪曲
线的目的 (即所谓的, 边生成, 边裁剪, )。
而且由于在这些曲线中, 一般大多数逼近曲线的小段直线或是位于
窗内或是位于窗外, 只有一小部分直线段正好位于窗口的边界上, 故对
这类曲线的裁剪输出与生成整条曲线相比较, 其速度一般不会使人感到
有很明显的下降 。 如果我们能利用这类曲线的最小外接矩形来减少盲目
求解窗口与曲线的交点的计算次数, 就能更有效地提高裁剪曲线的速度 。
对于这类曲线之所以不采用, 先裁剪, 后生成, 的输出处理方法, 是因
为对于这类分段自由曲线, 一是没有求解窗边直线与这些分段曲线交点
的简化公式 (三次曲线的反函数公式表达复杂 ),二是使用起来不够方便,
还不如采用, 边生成, 边裁剪, 的方法处理曲线裁剪的效率高 。
四、实面积多边形的裁剪
实面积多边形被裁剪之后仍为实面积图形, 这就要求裁剪之后实面积
图形的边界是自然封闭的 。 因此实面积多边形的裁剪不能简单地套用直线
的裁剪算法 。
实面积图形的裁剪有下述两种方法 。
1,利用两环的集合, 交, 运算来裁剪实面积多边形
这里可以假设窗口是一个封闭且透明的多边形, 而待裁剪实面积多边
形与窗口的顶点数据都按, 环, 的要求存放, 那么这两个多边形, 交, 运
算的结果即为实面积多边形被窗口裁剪之后所生成的多边形, 而且这个待
裁剪的实面积多边形既可以是一个凸多边形, 也可以是一个凹的或带孔的
多边形, 同时它还能避免退化边的处理 。 利用两环的, 交, 运算来裁剪实
面积多边形是一个通用而复杂的软件裁剪方法 。
2．多边形的逐边裁剪算法
多边形的逐边裁剪算法 (1974年由 Sutherland和 Hodgman提出 )的 。 出
发点是把解决复杂问题的全过程分解成几个简单的过程, 从而使该问题
的解决最终得到简化 。
逐边裁剪算法的原理是：先用窗口的一条边框对整个多边形进行裁
剪, 保留裁剪后位于该边框可见区域内的部分图形, 丢掉其不可见区域
内的部分图形, 得到一个或若干个新的封闭多边形 。 当用窗口的第一条
边框裁剪处理完之后, 再用第二条边框对那些新生成的多边形进行裁剪,
如此下去, 直至窗口的四条边框都裁剪完毕 。
显然窗口的一条边框 (两端无限延长 )与多边形之间的关系是：两者
或是不相交, 或是重叠, 或是相交, 或是相交且交于多边形边线的端点
处 。 对于这些情况可分别用窗, 口的一条边框与多边形边线的相互关系
来代替, 可以把窗边与多边形的边线之间的关系归纳成下述几种情况 。
第一种情况：多边形的顶点 S,P位于窗口边框 eA的可见侧, 如图 (a)
所示, 则多边形的一条边 SP也完全落于其可见侧, 因此顶点 S,P坐标应
存入新多边形的顶点序列中 。
第二种情况：多边形的边 SP与窗口边框 eA相交, 且交点为 I,而顶点
S位于其可见侧, 如图 (b)所示, 则 S点和 I点坐标应存人新多边形的顶点
序列中 。
第三种情况：多边形的顶点 S,P均位于窗口边框 cA的不可见侧, 如
图 (c)所示, 因此把 S,P点坐标都丢掉 。
第四种情况：多边形的边 SP与窗口边框 eA相交且交点为 I,而 P点位于窗口边框
的可见侧, 如图 (d)所示, 因此把 I点和 P点坐标存入新多边形的顶点序列中 。
多边形的边 SP与窗边 eA的关系除了上述四种典型关系之外, 还有下述几种特殊
关系要作相应特殊处理 。
第五种情况：多边形的边 SP与窗边 eA完全重合, 如图 (e)所示, 则 S,P点坐标
都丢掉, 这样处理不会影响最后新多边形的封闭性 (因为裁剪多边形后要用窗边去
进行封闭处理 )。
第六种情况：多边形的两点 SP,如果其中一点位于窗边的可见侧, 另一点正好
位于窗口的边框上 (即边 SP与窗边相切, 如图 (f)所示 ),则 S,P两点坐标都存人新
多边形的顶点序列中；如果 S,P两点中, 其中一点位于窗口边框的不可见侧, 而另
一点正好位于窗口的边框上, 如图 (f)所示, 则 S,P两点坐标都丢掉 。
该算法能有效
处理各种奇异
多边形的保证 。
这里的 k为窗
口的边框数 。
当多边形的所有顶点都按这几种情况处理完毕之后, 所保存的顶点与交点就
是所组成的数个新多边形的顶点 。 为使新多边形封闭, 注意还要裁剪 VnV1所组成
的边 (V1,Vn)分别是多边形的第一个与最后一个顶点 )。
算法特点：
(1)多边形的逐边裁剪算法实际上是一个通用的裁剪算法, 它既可以裁剪凸多
边形, 也可以裁剪凹多边形, 带孔多边形以及各种奇异多边形 。
(2)该算法的原理简单, 实现方便, 既能用硬件方法实现, 也可软件方法实现 。
(3)在实现该算法时, 如果保留每次裁剪之后的中间结果, 这一中间结果会占
用很大的存储空间, 但如果能用递归的方式实现该算法, 则不用保留每次裁剪之
后的中间结果 。 如果补充新规则使多边形自然封闭, 则不会出现退化边等问题,
这对于用硬件方式实现该算法非常有用 。 因为用硬件方式实现该算法时, 不可能
预留足够的空间去保存那些中间结果 。
所谓用 递归方式 实现该裁剪算法是指窗口对多边形的裁剪可这样进行：首先
按多边形的顶点次序依次裁剪多边形的每条边, 而对多边形的每条边先用窗口的
第一条边框去裁剪, 当这条边通过窗口的第一条边框裁剪之后, 再用窗口的第二
条边框去裁剪, 如果它通过第 二条边框的裁剪之后, 再用窗口的第三, 四条边框
去裁剪；最后通过第四条边框裁剪输出的顶点与交点, 就是被窗口裁剪之后新多
边形的顶点 。 不能通过 上 述四步裁剪的边线, 其顶点与交 点自然被舍掉, 因而对
应的边线也被裁掉 。
递归方式的结点数据格式
用递归方式实现多边形的逐边裁剪算法时, 它要求多边形的结点数
据格式为,
这里多边形的顶点, 交点与重合点统称多边形的结点, 此时暂不考虑对多
边形重合点也即第五, 第六种情况的处理 。
0：说明该点 P为多边形的顶点；
1：说明该点 P为多边形边线上的交点；
2：说明该点 P的坐标数据无意义，它仅用于通知算法流程应处
理多边形的最后一条边 VnV1，使多边形进入闭合处理 。
标志位 =
P点坐标数据 标志位①
② 此时多边形的顶点次序为 V1V2...V1，其中最后的 V1点的坐标无意义，
裁剪算法仅利用具标志位, 2”，使本级与下一级多边形的裁剪等流程进
入闭合处理。
递归方式多边形的逐边裁剪算法的流程
当被裁剪多边形
的各顶点数据转
化成上述约定的
数据格式之后，
可把结点 Vi(i=1，
2,…,n+1)依次
传递给 Pl变量包
括其标志位 )，
并调用第一条裁
剪边框 e1的裁剪
处理流程，并遂
一进行这一过程，
直至处理完多边
形的所有结点为
止。
二个多边形逐边裁剪的例题
逐边裁剪算法流程表
多边形被裁剪之后, 如果仅按照其输出各结点的先后次序, 把各结点依次连接
起来, 即 1‘一 4一 2’一 3‘一 4’一 5‘一 7一 6’一 8‘一 1’, 这时就会有退化边问题 (退化边是新
多边形的两条边界相互异向重叠且位于同一窗边上的结果, 此退化边即新多边形的
悬边 )。 为了消除多边形裁剪之后出现的退化边问题, 可以利用此时各结点中的顶点,
交点, 进入闭合等标志位, 提出新的补充规则, 使裁剪之后的多边形自然封闭又无
退化边 。
裁剪之后组成新多边形外环的规则如下 。
① 依次连接最后输出的交点与顶点, 顶点与顶点或顶点与交点的连线为新多边
形的有效边 。 此例有效边为 l’一 4,4一 2‘,5’一 7,7—6‘；
② 依次连接不在一条边框上出现的交点与交点的连线为新多边形的有效边 。 此
例有效边为 3‘一 4’；
③ 对每条窗口边框上出现的交点, 按环的环行方向进行排序, 成对交点之间的
连线即为新多边形的有效边 。 此例中 e1边框上的交点排序结果为 8‘,3’,2‘,l’,因此
其有效边为 8‘一 3’,2’一 1‘。 而 e2边框上的交点排序结果为 6’,5‘,4’,8‘,因此其有效
边为 6’一 5‘,4’一 8‘；
④ 多边形要封闭, 则其有效边必然首尾相连 。 针对上述各有效边, 可得新多边
形的各外环分别是 1‘一 4一 2’一 1‘,3’一 4‘一 8’一 3‘,5’一 7一 6‘一 5’。
例 4-2 对于图所示的带孔多边形，用递归方式
的逐边裁剪算法裁剪该多边形。
可以看出由于内环 2被窗口裁开, 因此内环 2与多边形被裁
开的外环一起组成新多边形的外环；而内环 l由于它没有被窗口
裁开, 故它是新多边形的内环根据上例组成新多边形外环的规
则, 此时有
① 不在一条窗口边框上的交点之间连线为有效边即 3‘—2‘，
9’—8‘；
② e1边框上的交点排序结果为 5‘,10’,8‘,6’,则有效边为
8‘--6’,而 5‘—10‘为一个退化角点舍去；
③ e2边框上的交点排序结果为 2‘,9’,5‘,10’,则有效边为
2‘—9‘,而 5’—10‘为一个退化角点舍去；
④ e4边框上只有两个交点, 则有效边为 6’--3’。
多边形封闭要求其有效边首尾相连, 故有 3‘—2‘—9‘—8‘—6‘—
3‘。 至此完成了该多边形的裁剪 。
