第五章 二维图形裁剪
计算机内部存储的图形数据
量往往比较大，而屏幕显示
的只是图的局部部分。因此
需要确定图形中哪些部分落
在显示区之内，哪些落在显
示区之外，以便只显示落在
显示区内的那部分图形。这
个选择过程称为 裁剪 。一般，
因为有些图形组成部分全部
在窗口外，可以完全排除，
不必进行扫描转换。 所以
采用 先裁剪再扫描转
换的方法。
主要内容
直线段的 Cohen-Sutherland算法、
Nicholl-Lee-Nicholl算法、中点分割算法、
梁友栋 -Barskey算法，裁剪多边形的
Sutherland-Hodgman算法,Weiler-
Atherton算法，字符裁剪。
5.1 直线段裁剪
直线段裁剪算法比较简单，但非常重要，
是复杂图元裁剪的基础。因为 复杂的曲
线可以通过 折线段 来近似，从而裁剪问
题也可以化为直线段的裁剪问题。
常用的线段裁剪方法
? Cohen-Sutherland、
? 中点分割算法
? 梁友栋－ barskey算法。
直线段裁剪前提和假设
n裁剪的目的,判断图形元素是否落在裁剪窗口
之内并找出其位于内部的部分
裁剪处理的基础,
? 图元关于窗口内外关系的判别
? 图元与窗口的求交
假定条件, （１）矩形裁剪窗口 ----
[xmin,xmax]X[ymin,ymax]
（２） 待裁剪线段 ----
待裁剪线段和窗口的关系,(1)线段完全可见 ; (2)
显然不可见 ; (3)线段至少有一端点在窗口之外，
但非显然不可见,
例子
线段
AB,CD,EF,
GH,IJ等
简单的点
裁剪,点
(x,y)在窗
口内的充
分必要条
件是,
5.1.1 直线裁剪的 直接求交算法
5.1.2 直线段的 Cohen-Sutherland裁
剪算法
该算法的思想是,对于每条线段
P1P2分为三种情况处理。
? （ 1） 若两端点 P1P2完全在窗口
内，则完全可见该线段 P1P2。 否
则进入下一步；
? （ 2） 若线段 P1P2明显在窗口外，
即显然不可见，则丢弃该线段，否
则进入下一步；
? （ 3） 若线段既不满足（ 1）的条
件，也不满足（ 2）的条件，则在
交点处把线段分为两段。其中一段
完全在窗口外，可弃之。然后对另
一段重复上述处理。
算法实现
为使计算机能够快速判断一条直线段与
窗口属何种关系，采用如下编码方法。
延长窗口的边，将二维平面分成九个区
域。每个区域赋予 4位编码 CtCbCrCl.其
中各位编码的定义如下：
算法过程
裁剪一条线段时，先求出 P1P2所在的区号
code1,code2。
? （１） 若 code1=0,且 code2=0,则线段 P1P2在窗口内，应
取之。
? （２）若 按位与 运算 code1&code2≠0,则说明两个端点同
在窗口的上方、下方、左方或右方。可判断线段完全在窗
口外，可弃之。
? （３）否则，按第三种情况处理。求出线段与窗口某边的
交点，在交点处把线段一分为二，其中必有一段在窗口外，
可弃之。在对另一段重复上述处理。
在实现本算法时，不必把线段与每条窗口边界依次
求交，只要按顺序检测到端点的编码不为 0，才把线
段与对应的窗口边界求交。
特点：对显然不可见线段的快速判别
Cohen-Sutherland裁减算法
#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
int encode(float x,float y)
{ int c=0;
if(x<XL) c|=LEFT;
if(x>XR) c|=RIGHT;
if(x<YB) c|=BOTTOM;
if(x<YT) c|=TOP;
retrun c;
}
void
CS_LineClip(x1,y1,x2,y2,XL,XR,Y
B,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
//(x1,y1)(x2,y2)为线段的端点坐标，
其他四个参数定义窗口的边界
{ int code1,code2,code;
code1=encode(x1,y1);//端点编码
code2=encode(x2,y2);//端点编码
Cohen-Sutherland裁减算法
while(code1!=0
||code2!=0)
{ if(code1&code2 !=0)
return;
code = code1;
if(code1==0) code =
code2;
if(LEFT&code !=0)
{ x=XL;
y=y1+(y2-y1)*(XL-
x1)/(x2-x1);
}
else if(RIGHT&code !=0)
{ x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-
x1);
}
else if(BOTTOM&code !=0)
{ y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1);
}
else if(TOP & code !=0)
{ y=YT;
x=x1+(x2-x1)*(YT-y1)/(y2-y1);
}
Cohen-Sutherland裁减算法
if(code ==code1)
{ x1=x;y1=y; code1
=encode(x,y);}
else
{ x2=x;y2=y; code2
=encode(x,y);}
}
displayline
（ x1,y1,x2,y2);
}
example
5.1.3 直线段的 中点分割裁剪算法
中点分割算法思路,与 Cohen-Sutherland算法一样，（１）
对线段端点进行编码，并把线段与窗口的关系分为三种情况
（ 全在、完全不在和线段和窗口有交）来处理（２）对前两
种情况，进行一样的处理。（３ ）对于第三种情况，用中点分
割的方法求出线段与窗口的交点。 即从 p0点出发找出距 p0最近
的可见点 A和从 p1点出发找出距 p1最近的可见点 B,两个可见
点之间的连线即为线段 p0p1的可见部分。从 p0出发找最近可
见点采用中点分割方法：先求出 p0p1的中点 pm,若 p0pm不是
显然不可见的，并且 p0p1在窗口中有可见部分，则距 p0最近
的可见点一定落在 p0pm上，所以用 p0pm代替 p0p1； 否则取
pmp1代替 p0p1。 再对新的 p0p1求中点 pm。 重复上述过程，
直到 pmp1长度小于给定的控制常数为止，此时 pm收敛于交点。
由于该算法的主要计算过程只用到加法和除 2运算，所以特别
适合硬件实现，同时也适合于并行计算。
直线段的 中点分割裁剪算法
中点分割算法示意图：
说明,A,B分别为距 p0,p1最近的可见点,Pm为 p0p1中
点．
算法
5.1.4 Nicholl-Lee-Nicholl算法
目标：通过对二维平面的更详细划分，消除
Cohen_Sutherland算法中线段在被裁剪时需多
次求交的情况
步骤：
? 第一步,窗口四边所在的直线将二维平面划分成 9
个区域，假定 P0 落在区域 0,4,5 区域；
? 第二步,从 P0点向窗口的四个角点发出射线，这
四条射和窗口的四条边所在的直线一起将二维平面
划分为更多的小区域；
? 第三步,确定 P1所在的区域；
? 第四步,求交点，确定 P0P1的可见部分
5.1.5 梁友栋－ Barskey算法
梁友栋和 Barskey提出了更快的参数化裁剪算法。首
先按参数化形式写出裁剪条件
这四个不等式可以
表示为形式：
其中,参数 pk,qk定义
为
任何平行于裁剪边界之一的直线 pk=0,其中 k对应于
裁剪边界（ k=1,2,3,4对应于左、右、下、上边界）
如果还满足 qk<0,则线段完全在边界外，舍弃该线
段。如果 qk≥0,则该线段平行于裁剪边界并且在窗
口内。
当 pk<0,线段从裁剪边界延长线的外部延伸到内部。
当 pk>0,线段从裁剪边界延长线的内部延伸到外部。
当 pk≠0,可以计算出线段与边界 k的延长线的交点的
u值,u=qk/pk
对于每条直线，可以计算出参数 u1和 u2,它们
定义了在裁剪矩形内的线段部分。 u1的值由线段从
外到内遇到的矩形边界所决定（ p<0）。 对这些边界
计算 rk=qk/pk 。 u1取 0和各个 rk值之中的最大值。 u2
的值由线段从内到外遇到的矩形边界所决定（ p>0）。
对这些边界计算 rk=qk/pk 。 u2取 1和各个 rk值之中的
最小值。如果 u1>u2,则线段完全落在裁剪窗口之外，
被舍弃。否则裁剪线段由参数 u的两个值 u1,u2计算出
来。
算法
void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
{ float dx,dy,u1,u2;
tl=0;tu=1;
dx =x2-x1;
dy =y2-y1;
if(ClipT(-dx,x1-Xl,&u1,&u2)
if(ClipT(dx,XR-x1,&u1,&u2)
if(ClipT(-dy,y1-YB,&u1,&u2)
if(ClipT(dy,YT-y1,&u1,&u2)
{ displayline(x1+u1*dx,
y1+u1*dy,
x1+u2*dx,y1+u2*dy)
return;
}
}
bool ClipT(p,q,u1,u2)
float p,q,*u1,*u2;
{ float r;
if(p<0)
{ r=q/p;
if(r>*u2) return
FALSE;
else if(r>*u1)
{ *u1=r;
return TRUE;
}
}
else if(p>0)
{ r=p/q;
if(r<*u1) return FALSE;
else if(r<*u2)
{ *u2=r;
return TRUE;
}
}
else if(q<0) return FALSE;
return TRUE;
}
5.2 多边形裁剪
多边形的组成：多个 直线段
自然想法与思路：把多边形分解为 边界的线段
逐段进行裁剪。
问题：
（ 1）原来封闭的多边 ?不封闭的、或者一些离
散的线段。
导致当多边形作为实区域考虑时，封闭的多边形裁
剪后仍应当是封闭的多边形，以便进行填充。
（ 2）多边形 ?几个隔离的新多边形区域。
裁剪问题图示
5.2.1 多边形裁剪的
Sutherland-Hodgman算法
基本思想,逐边裁剪、两次分解、流水
线作业。
（ Step 1） 将多边形对于矩形窗口的裁剪
分解为对窗口四边所在直线的裁剪，
(Step 2)将多边形对一条直线的裁剪分解
为各边对直线的裁剪。
算法示意图
算法细节
在算法的 每一步 中，考虑 窗口的一条边以及
延长线构成的裁剪线 。
? 该线把平面分成两个部分：
? 一部分包含窗口，称为可见一侧；
? 另一部分称为不可见一侧。
? 依序考虑多边形的各条边的两端点 S,P。 它们与
裁剪线的位置关系只有四种。
? (1) S,P均在可见一侧
? (2) S,P均在不可见一侧
? (3) S可见,P不可见
? (4) S不可见,P可见。
S,P与裁剪线
的四种位置关
系示意图：
每条线段端点 S,P与裁剪线比较之后，可输出 0至 2个顶点。
情况（ 1） 仅输出顶点 P；
情况（ 2） 输出 0个顶点；
情况（ 3） 输出线段 SP与裁剪线的交点 I；
情况（ 4） 输出线段 SP与裁剪线的交点 I和终点 P
算法小结,仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下
一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图一样，只是判断
点在窗口哪一侧以及求线段 SP与裁剪边的交点算法应随之改变。
算法
流程
一条边裁剪
多边形的算
法框图
基于 divide and conquer策略的 Sutherland-
Hodgman算法,几个数据结构，几个函数及其流程
typedef struct
{ float x; float y; } Vertex;//顶点
typedef Vertex Edge[2];//边
typedef Vertex VertexArray[MAX]; //顶点数组
SutherlandHodgmanClip（ VertexArray
InVertexArray,VertexArray OutVertexArray,Edge
ClipBoundary,int &Inlength,int &Outlength）
{ Vertex s,p,ip;
int j;
Outlength = 0;
S = InVertexArray [InLength -1];
For (j = 0; j < Inlength; j++)
{
P = InVertexArray [j];
if(Inside (P,ClipBoundary))
{ if(Inside (S,ClipBoundary)) //SP在窗口内，情况 1
Output(p,OutLength,OutVertex Array)
else{ //S在窗口外,情况 4
Intersect (S,P,ClipBoundary,&ip);
Output (ip,OutLength,OutVertexArray);
Output (P,OutLength,OutVertexArray);
}
}
else if (Inside (S,WindowsBoundary))
{ //S在窗口内,P在窗口外,情况 3
Intersect (S,P,ClipBoundary,&ip);
Output (ip,OutLength,OutVertexArray);
} //情况 2没有输出
S = P;
}
}
//判点在窗口内
bool Inside (Vertex &TestPt,Edge ClipBoundary)
{ if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边
if(testpt.y>= ClipBoundary[0].y)
return TRUE;
else if(ClipBoundary[1].x< ClipBoundary[0].x)
//裁剪边为窗口上边
if(testpt.y<= ClipBoundary[0].y)
return TRUE;
else if(ClipBoundary[1].y> ClipBoundary[0].y)
//裁剪边为窗口右边
if(testpt.x<= ClipBoundary[0].x)
return TRUE;
else if(ClipBoundary[1].y< ClipBoundary[0].y)
//裁剪边为窗口左边
if(testpt.x>= ClipBoundary[0].x)
return TRUE;
Return FALSE;
}
5.2.2 算法推广 ----
任意凸多边形作裁剪窗口的情形
依次
用多
边形
的每
条边
裁剪
5.2.3 Weiler-Athenton算法
应用范围：
? 裁剪窗口可以为任意多边形
假定：
1,主多边形：被裁剪多边形，记为 A
2,裁剪多边形：裁剪窗口，记为 B
3,多边形顶点的排列顺序（使多边形区域位于有向
边的左侧 ）
1,n外环：逆时针
2,内环：顺时针
4,n内裁剪结果,AnB
5,n外裁剪结果,A-B
观察
裁剪结果区域的边界
由 A的部分边界和 B的
部分边界两部分构成，
并且在交点处边界发
生交替，即由 A的边界
转至 B的边界，或由 B
的边界转至 A的边界
成对出现的两类交点 --
--
? 进点,主多边形边界由
此进入裁剪多边形内
? 出点,主多边形边界由
此离开裁剪多边形区域
Weiler_Athenton裁剪算法（内裁剪）步骤
Step 1,建立主多边形和裁剪多边的 顶点表 ；
Step 2,求主多边形和裁剪多边形的 交点,并将这些交点按顺序插
入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立
双向指针；
Step 3,裁剪：如果存在没有被跟踪过的交点，执行以下步骤：
? (1) 建立裁剪结果多边形的顶点表 ;
? (2) 选取任一没有被跟踪过的交点为始点，将其输出到结果多
边形顶点表中 ;
? (3) 如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪
多边形边界 ;
? (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多
边形顶点表中，直至遇到新的交点．
? (5) 将该交点输出到结果多边形顶点表中，并通过连接该交点
的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在
改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改
为跟踪主多边形边界） ;
? (6) 重复 (4),(5)直至回到起点,
Example
算法
算法分析
交点的奇异
情况处理：
1,重合边,与
裁剪多边形边重合
的主多边形的边不
参与求交点；
2,对于顶点落在
裁剪多边形的边上
的主多边的边,如
果落在该裁剪边的
内侧，将该顶点算
作交点；而如果这
条边落在该裁剪边
的外侧，将该顶点
不看作交点。
5.3 字符裁剪
问题背景,当字符和文本部分在
窗口内，部分在窗口外时，就提
出了字符裁剪问题。
字符串裁剪的三个精度：
? 串精度
? 字符精度
? 笔画 \象素精度
串精度裁剪,将包围字串的外接矩形
对窗口作裁剪。当字符串方框整个在
窗口内时予以显示，否则不显示。
字符精度裁剪,将包围字的外接矩形
对窗口作裁剪，某个字符方框整个落
在窗口内予以显示，否则不显示。
笔画 \象素精度裁剪,将笔划分解成直
线段对窗口作裁剪，处理方法同上。
?(a)待裁剪字符串
?(b)串精度裁剪
?(c)字符精度裁剪
? (d)象素精度裁剪
计算机内部存储的图形数据
量往往比较大，而屏幕显示
的只是图的局部部分。因此
需要确定图形中哪些部分落
在显示区之内，哪些落在显
示区之外，以便只显示落在
显示区内的那部分图形。这
个选择过程称为 裁剪 。一般，
因为有些图形组成部分全部
在窗口外，可以完全排除，
不必进行扫描转换。 所以
采用 先裁剪再扫描转
换的方法。
主要内容
直线段的 Cohen-Sutherland算法、
Nicholl-Lee-Nicholl算法、中点分割算法、
梁友栋 -Barskey算法，裁剪多边形的
Sutherland-Hodgman算法,Weiler-
Atherton算法，字符裁剪。
5.1 直线段裁剪
直线段裁剪算法比较简单，但非常重要，
是复杂图元裁剪的基础。因为 复杂的曲
线可以通过 折线段 来近似，从而裁剪问
题也可以化为直线段的裁剪问题。
常用的线段裁剪方法
? Cohen-Sutherland、
? 中点分割算法
? 梁友栋－ barskey算法。
直线段裁剪前提和假设
n裁剪的目的,判断图形元素是否落在裁剪窗口
之内并找出其位于内部的部分
裁剪处理的基础,
? 图元关于窗口内外关系的判别
? 图元与窗口的求交
假定条件, （１）矩形裁剪窗口 ----
[xmin,xmax]X[ymin,ymax]
（２） 待裁剪线段 ----
待裁剪线段和窗口的关系,(1)线段完全可见 ; (2)
显然不可见 ; (3)线段至少有一端点在窗口之外，
但非显然不可见,
例子
线段
AB,CD,EF,
GH,IJ等
简单的点
裁剪,点
(x,y)在窗
口内的充
分必要条
件是,
5.1.1 直线裁剪的 直接求交算法
5.1.2 直线段的 Cohen-Sutherland裁
剪算法
该算法的思想是,对于每条线段
P1P2分为三种情况处理。
? （ 1） 若两端点 P1P2完全在窗口
内，则完全可见该线段 P1P2。 否
则进入下一步；
? （ 2） 若线段 P1P2明显在窗口外，
即显然不可见，则丢弃该线段，否
则进入下一步；
? （ 3） 若线段既不满足（ 1）的条
件，也不满足（ 2）的条件，则在
交点处把线段分为两段。其中一段
完全在窗口外，可弃之。然后对另
一段重复上述处理。
算法实现
为使计算机能够快速判断一条直线段与
窗口属何种关系，采用如下编码方法。
延长窗口的边，将二维平面分成九个区
域。每个区域赋予 4位编码 CtCbCrCl.其
中各位编码的定义如下：
算法过程
裁剪一条线段时，先求出 P1P2所在的区号
code1,code2。
? （１） 若 code1=0,且 code2=0,则线段 P1P2在窗口内，应
取之。
? （２）若 按位与 运算 code1&code2≠0,则说明两个端点同
在窗口的上方、下方、左方或右方。可判断线段完全在窗
口外，可弃之。
? （３）否则，按第三种情况处理。求出线段与窗口某边的
交点，在交点处把线段一分为二，其中必有一段在窗口外，
可弃之。在对另一段重复上述处理。
在实现本算法时，不必把线段与每条窗口边界依次
求交，只要按顺序检测到端点的编码不为 0，才把线
段与对应的窗口边界求交。
特点：对显然不可见线段的快速判别
Cohen-Sutherland裁减算法
#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
int encode(float x,float y)
{ int c=0;
if(x<XL) c|=LEFT;
if(x>XR) c|=RIGHT;
if(x<YB) c|=BOTTOM;
if(x<YT) c|=TOP;
retrun c;
}
void
CS_LineClip(x1,y1,x2,y2,XL,XR,Y
B,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
//(x1,y1)(x2,y2)为线段的端点坐标，
其他四个参数定义窗口的边界
{ int code1,code2,code;
code1=encode(x1,y1);//端点编码
code2=encode(x2,y2);//端点编码
Cohen-Sutherland裁减算法
while(code1!=0
||code2!=0)
{ if(code1&code2 !=0)
return;
code = code1;
if(code1==0) code =
code2;
if(LEFT&code !=0)
{ x=XL;
y=y1+(y2-y1)*(XL-
x1)/(x2-x1);
}
else if(RIGHT&code !=0)
{ x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-
x1);
}
else if(BOTTOM&code !=0)
{ y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1);
}
else if(TOP & code !=0)
{ y=YT;
x=x1+(x2-x1)*(YT-y1)/(y2-y1);
}
Cohen-Sutherland裁减算法
if(code ==code1)
{ x1=x;y1=y; code1
=encode(x,y);}
else
{ x2=x;y2=y; code2
=encode(x,y);}
}
displayline
（ x1,y1,x2,y2);
}
example
5.1.3 直线段的 中点分割裁剪算法
中点分割算法思路,与 Cohen-Sutherland算法一样，（１）
对线段端点进行编码，并把线段与窗口的关系分为三种情况
（ 全在、完全不在和线段和窗口有交）来处理（２）对前两
种情况，进行一样的处理。（３ ）对于第三种情况，用中点分
割的方法求出线段与窗口的交点。 即从 p0点出发找出距 p0最近
的可见点 A和从 p1点出发找出距 p1最近的可见点 B,两个可见
点之间的连线即为线段 p0p1的可见部分。从 p0出发找最近可
见点采用中点分割方法：先求出 p0p1的中点 pm,若 p0pm不是
显然不可见的，并且 p0p1在窗口中有可见部分，则距 p0最近
的可见点一定落在 p0pm上，所以用 p0pm代替 p0p1； 否则取
pmp1代替 p0p1。 再对新的 p0p1求中点 pm。 重复上述过程，
直到 pmp1长度小于给定的控制常数为止，此时 pm收敛于交点。
由于该算法的主要计算过程只用到加法和除 2运算，所以特别
适合硬件实现，同时也适合于并行计算。
直线段的 中点分割裁剪算法
中点分割算法示意图：
说明,A,B分别为距 p0,p1最近的可见点,Pm为 p0p1中
点．
算法
5.1.4 Nicholl-Lee-Nicholl算法
目标：通过对二维平面的更详细划分，消除
Cohen_Sutherland算法中线段在被裁剪时需多
次求交的情况
步骤：
? 第一步,窗口四边所在的直线将二维平面划分成 9
个区域，假定 P0 落在区域 0,4,5 区域；
? 第二步,从 P0点向窗口的四个角点发出射线，这
四条射和窗口的四条边所在的直线一起将二维平面
划分为更多的小区域；
? 第三步,确定 P1所在的区域；
? 第四步,求交点，确定 P0P1的可见部分
5.1.5 梁友栋－ Barskey算法
梁友栋和 Barskey提出了更快的参数化裁剪算法。首
先按参数化形式写出裁剪条件
这四个不等式可以
表示为形式：
其中,参数 pk,qk定义
为
任何平行于裁剪边界之一的直线 pk=0,其中 k对应于
裁剪边界（ k=1,2,3,4对应于左、右、下、上边界）
如果还满足 qk<0,则线段完全在边界外，舍弃该线
段。如果 qk≥0,则该线段平行于裁剪边界并且在窗
口内。
当 pk<0,线段从裁剪边界延长线的外部延伸到内部。
当 pk>0,线段从裁剪边界延长线的内部延伸到外部。
当 pk≠0,可以计算出线段与边界 k的延长线的交点的
u值,u=qk/pk
对于每条直线，可以计算出参数 u1和 u2,它们
定义了在裁剪矩形内的线段部分。 u1的值由线段从
外到内遇到的矩形边界所决定（ p<0）。 对这些边界
计算 rk=qk/pk 。 u1取 0和各个 rk值之中的最大值。 u2
的值由线段从内到外遇到的矩形边界所决定（ p>0）。
对这些边界计算 rk=qk/pk 。 u2取 1和各个 rk值之中的
最小值。如果 u1>u2,则线段完全落在裁剪窗口之外，
被舍弃。否则裁剪线段由参数 u的两个值 u1,u2计算出
来。
算法
void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
{ float dx,dy,u1,u2;
tl=0;tu=1;
dx =x2-x1;
dy =y2-y1;
if(ClipT(-dx,x1-Xl,&u1,&u2)
if(ClipT(dx,XR-x1,&u1,&u2)
if(ClipT(-dy,y1-YB,&u1,&u2)
if(ClipT(dy,YT-y1,&u1,&u2)
{ displayline(x1+u1*dx,
y1+u1*dy,
x1+u2*dx,y1+u2*dy)
return;
}
}
bool ClipT(p,q,u1,u2)
float p,q,*u1,*u2;
{ float r;
if(p<0)
{ r=q/p;
if(r>*u2) return
FALSE;
else if(r>*u1)
{ *u1=r;
return TRUE;
}
}
else if(p>0)
{ r=p/q;
if(r<*u1) return FALSE;
else if(r<*u2)
{ *u2=r;
return TRUE;
}
}
else if(q<0) return FALSE;
return TRUE;
}
5.2 多边形裁剪
多边形的组成：多个 直线段
自然想法与思路：把多边形分解为 边界的线段
逐段进行裁剪。
问题：
（ 1）原来封闭的多边 ?不封闭的、或者一些离
散的线段。
导致当多边形作为实区域考虑时，封闭的多边形裁
剪后仍应当是封闭的多边形，以便进行填充。
（ 2）多边形 ?几个隔离的新多边形区域。
裁剪问题图示
5.2.1 多边形裁剪的
Sutherland-Hodgman算法
基本思想,逐边裁剪、两次分解、流水
线作业。
（ Step 1） 将多边形对于矩形窗口的裁剪
分解为对窗口四边所在直线的裁剪，
(Step 2)将多边形对一条直线的裁剪分解
为各边对直线的裁剪。
算法示意图
算法细节
在算法的 每一步 中，考虑 窗口的一条边以及
延长线构成的裁剪线 。
? 该线把平面分成两个部分：
? 一部分包含窗口，称为可见一侧；
? 另一部分称为不可见一侧。
? 依序考虑多边形的各条边的两端点 S,P。 它们与
裁剪线的位置关系只有四种。
? (1) S,P均在可见一侧
? (2) S,P均在不可见一侧
? (3) S可见,P不可见
? (4) S不可见,P可见。
S,P与裁剪线
的四种位置关
系示意图：
每条线段端点 S,P与裁剪线比较之后，可输出 0至 2个顶点。
情况（ 1） 仅输出顶点 P；
情况（ 2） 输出 0个顶点；
情况（ 3） 输出线段 SP与裁剪线的交点 I；
情况（ 4） 输出线段 SP与裁剪线的交点 I和终点 P
算法小结,仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下
一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图一样，只是判断
点在窗口哪一侧以及求线段 SP与裁剪边的交点算法应随之改变。
算法
流程
一条边裁剪
多边形的算
法框图
基于 divide and conquer策略的 Sutherland-
Hodgman算法,几个数据结构，几个函数及其流程
typedef struct
{ float x; float y; } Vertex;//顶点
typedef Vertex Edge[2];//边
typedef Vertex VertexArray[MAX]; //顶点数组
SutherlandHodgmanClip（ VertexArray
InVertexArray,VertexArray OutVertexArray,Edge
ClipBoundary,int &Inlength,int &Outlength）
{ Vertex s,p,ip;
int j;
Outlength = 0;
S = InVertexArray [InLength -1];
For (j = 0; j < Inlength; j++)
{
P = InVertexArray [j];
if(Inside (P,ClipBoundary))
{ if(Inside (S,ClipBoundary)) //SP在窗口内，情况 1
Output(p,OutLength,OutVertex Array)
else{ //S在窗口外,情况 4
Intersect (S,P,ClipBoundary,&ip);
Output (ip,OutLength,OutVertexArray);
Output (P,OutLength,OutVertexArray);
}
}
else if (Inside (S,WindowsBoundary))
{ //S在窗口内,P在窗口外,情况 3
Intersect (S,P,ClipBoundary,&ip);
Output (ip,OutLength,OutVertexArray);
} //情况 2没有输出
S = P;
}
}
//判点在窗口内
bool Inside (Vertex &TestPt,Edge ClipBoundary)
{ if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边
if(testpt.y>= ClipBoundary[0].y)
return TRUE;
else if(ClipBoundary[1].x< ClipBoundary[0].x)
//裁剪边为窗口上边
if(testpt.y<= ClipBoundary[0].y)
return TRUE;
else if(ClipBoundary[1].y> ClipBoundary[0].y)
//裁剪边为窗口右边
if(testpt.x<= ClipBoundary[0].x)
return TRUE;
else if(ClipBoundary[1].y< ClipBoundary[0].y)
//裁剪边为窗口左边
if(testpt.x>= ClipBoundary[0].x)
return TRUE;
Return FALSE;
}
5.2.2 算法推广 ----
任意凸多边形作裁剪窗口的情形
依次
用多
边形
的每
条边
裁剪
5.2.3 Weiler-Athenton算法
应用范围：
? 裁剪窗口可以为任意多边形
假定：
1,主多边形：被裁剪多边形，记为 A
2,裁剪多边形：裁剪窗口，记为 B
3,多边形顶点的排列顺序（使多边形区域位于有向
边的左侧 ）
1,n外环：逆时针
2,内环：顺时针
4,n内裁剪结果,AnB
5,n外裁剪结果,A-B
观察
裁剪结果区域的边界
由 A的部分边界和 B的
部分边界两部分构成，
并且在交点处边界发
生交替，即由 A的边界
转至 B的边界，或由 B
的边界转至 A的边界
成对出现的两类交点 --
--
? 进点,主多边形边界由
此进入裁剪多边形内
? 出点,主多边形边界由
此离开裁剪多边形区域
Weiler_Athenton裁剪算法（内裁剪）步骤
Step 1,建立主多边形和裁剪多边的 顶点表 ；
Step 2,求主多边形和裁剪多边形的 交点,并将这些交点按顺序插
入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立
双向指针；
Step 3,裁剪：如果存在没有被跟踪过的交点，执行以下步骤：
? (1) 建立裁剪结果多边形的顶点表 ;
? (2) 选取任一没有被跟踪过的交点为始点，将其输出到结果多
边形顶点表中 ;
? (3) 如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪
多边形边界 ;
? (4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多
边形顶点表中，直至遇到新的交点．
? (5) 将该交点输出到结果多边形顶点表中，并通过连接该交点
的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在
改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改
为跟踪主多边形边界） ;
? (6) 重复 (4),(5)直至回到起点,
Example
算法
算法分析
交点的奇异
情况处理：
1,重合边,与
裁剪多边形边重合
的主多边形的边不
参与求交点；
2,对于顶点落在
裁剪多边形的边上
的主多边的边,如
果落在该裁剪边的
内侧，将该顶点算
作交点；而如果这
条边落在该裁剪边
的外侧，将该顶点
不看作交点。
5.3 字符裁剪
问题背景,当字符和文本部分在
窗口内，部分在窗口外时，就提
出了字符裁剪问题。
字符串裁剪的三个精度：
? 串精度
? 字符精度
? 笔画 \象素精度
串精度裁剪,将包围字串的外接矩形
对窗口作裁剪。当字符串方框整个在
窗口内时予以显示，否则不显示。
字符精度裁剪,将包围字的外接矩形
对窗口作裁剪，某个字符方框整个落
在窗口内予以显示，否则不显示。
笔画 \象素精度裁剪,将笔划分解成直
线段对窗口作裁剪，处理方法同上。
?(a)待裁剪字符串
?(b)串精度裁剪
?(c)字符精度裁剪
? (d)象素精度裁剪
