第3章二维图形裁剪.ppt

计算机图形学基础计算机图形学基础计算机图形学基础计算机图形学基础第第3章章 二维图形裁剪二维图形裁剪本章主要内容本章主要内容3.1　裁剪概述　裁剪概述3.2　线段裁剪　线段裁剪直接求交算法；直接求交算法；Cohen-Sutherland算法；（重点，算法实现）算法；（重点，算法实现） 中点算法3.3　多边形裁剪　多边形裁剪 Sutlerland_Hodgman算法算法（难点，算法实现） Weiler-Athenton算法 ＊＊ 3. 4　字符裁剪　字符裁剪裁 剪二维图形裁剪二维图形裁剪预备知识：求交（矩形窗口）（矩形窗口）裁剪裁剪三维裁剪长方体裁剪体棱锥体体裁剪体直接求交算法直接求交算法编码裁剪算法编码裁剪算法中点分割算法中点分割算法…………被裁剪对象：直线段、多边形直线段、多边形、三维实体……1.裁剪：裁剪：是裁去窗口之外物体或物体部分的一种操作是裁去窗口之外物体或物体部分的一种操作3.1　裁剪概述　裁剪概述“取景器”=窗口视区视区视区视区1 1 视区视区视区视区2 2（（（（viewportviewport）））） 裁剪的目的裁剪的目的判断图形元素是否落在裁剪窗口之内并找出其位于内判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分部的部分裁剪处理的基础裁剪处理的基础图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元与窗口的求交图元与窗口的求交假定条件假定条件矩形裁剪窗口：矩形裁剪窗口：[xmin,xmax]×[ymin,ymax]待裁剪点或线段：待裁剪点或线段：2.裁剪概述裁剪概述•点裁剪点裁剪 –点点(x, y)在窗口内的充分必要条件是：在窗口内的充分必要条件是： 问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？WytWybWxlWxrP1P2P3线段相对于该窗口的情况有情况有:①①线段全部全部位于窗口的内部窗口的内部（A）；②②线段全部全部位于窗口外部窗口外部（B、C）；③③线段的中间部分中间部分在窗口内窗口内，而二端点在窗口外部（D）；④④线段的一端在窗口内一端在窗口内，而另一端在窗口外另一端在窗口外（E）。

x=xLx=xRy=yBy=yTABCDE3.2 线段裁剪线段裁剪待裁剪线段和窗口的关系待裁剪线段和窗口的关系 线段完全可见线段完全可见显然不可见显然不可见 线段至少有一端点在窗口之外，但非显然不可见线段至少有一端点在窗口之外，但非显然不可见 保留丢弃裁剪为提高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或处的情形；(二) 设法减少裁剪情形中求交次数和每次求交时所需的计算量3.2.1　直接求交算法基本思想基本思想是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段　根据直线段和窗口的关系可知：（1）整条线在窗口之内此时，不需剪裁，显示整条线段2）整条线在窗口之外，此时，不需剪裁，不显示整条线段3）部分线在窗口之内，部分线在窗口之外此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分例1 设有直线段P0P1，有一个矩形裁剪窗口，写出对该线段裁剪的算法1）判断线段端点的位置，由图4-2（a）可知：P0不在窗口内，P1在窗口内2）保持线段起始点在裁剪窗口内：交换两点，使P0在内，如图4-2（b）所示。

3）求出直线与窗口的交点I，如图4-2（c）所示4）取P0 I线段显示，擦除I P1线段，并将P1替换I，即得P0P1线段，裁剪结束如图4-2（d）所示 P1P0P0P1P0P1IP0P1求线段与窗口交点求线段与窗口交点设线段两端点坐标为：　　　和　　　　　则过这两点的直线方程为：其中k为斜率上述直线方程与窗口各边界的交点为：左：右：下：上：•基本思想基本思想：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段P1P2，简称“取取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍舍”之；③若线段既不满足“取”的条件，也不满足“舍”的条件，则求线段与窗口边界的交点交点，在交点处把线段分为两段，其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理• 核心思想：分区编码分区编码和线段分割线段分割 3.2.2　　Cohen-Sutherland 算法算法 (编码算法) 分区编码方法：图形区域划分成九个区域四位编码 表示端点所处的位置： (--->) 上上 下下 右右 左左第一一位为“1”时，表示点在y=y=y yT T的上方的上方；第二二位为“1”时，表示点在y=y=y yB B的下方的下方；第三三位为“1”时，表示点在x=x=x xR R的右方的右方；第四四位为“1”时，表示点在x=x=x xL L的左方的左方。

000000010010100001001001101001010110x=xLx=xRy=yBy=yT11111 1 1 1 1 1 1 1#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8编码原则编码原则每个区域赋予一个四位编码，每个区域赋予一个四位编码，CtCbCrCl，，上下右左；上下右左；编码方法编码方法练习：请给出右图的线练习：请给出右图的线段端点编码段端点编码（端点编码：（端点编码：（端点编码：（端点编码：定义为它所在区域的编码）定义为它所在区域的编码）定义为它所在区域的编码）定义为它所在区域的编码）x=xLx=xRy=yBy=yTABCDE第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是， 则线段则线段完全可见完全可见；否则进入第二步；；否则进入第二步；第二步第二步 判别线段是否为判别线段是否为显然不可见显然不可见，如果是，则裁，如果是，则裁 剪结束；否则进行第三步剪结束；否则进行第三步 ；；第三步第三步 求线段与求线段与窗口边延长线窗口边延长线的交点，这个交点将的交点，这个交点将 线段分为两段，其中一段显然不可见，丢弃。

线段分为两段，其中一段显然不可见，丢弃 对余下的另一段重新进行第一步，第二步判断，对余下的另一段重新进行第一步，第二步判断， 直至结束直至结束 Cohen-Sutherland 算法算法步骤当线段的两个端点的编码的当线段的两个端点的编码的当线段的两个端点的编码的当线段的两个端点的编码的逻辑逻辑逻辑逻辑“ “与与与与” ”非零非零非零非零时时时时 ，线段，线段，线段，线段为显然不可见的为显然不可见的为显然不可见的为显然不可见的也可以进行也可以进行也可以进行也可以进行“ “按位与按位与按位与按位与” ”运算运算运算运算，可知，可知，可知，可知这两个端点是否同在视区的上、下、左、右；这两个端点是否同在视区的上、下、左、右；这两个端点是否同在视区的上、下、左、右；这两个端点是否同在视区的上、下、左、右；如如如如code1=0101,code2=0110code1=0101,code2=0110，，，，则则则则code1&code2=0100,code1&code2=0100,表示表示表示表示在窗口下方在窗口下方在窗口下方在窗口下方问题：问题：问题：问题：显然可见的编码如何判断？？显然可见的编码如何判断？？显然可见的编码如何判断？？显然可见的编码如何判断？？编码判断编码判断对一条线段的可见性测试方法：对一条线段的可见性测试方法：（（1）若线段两个端点的四位二进制编码全为）若线段两个端点的四位二进制编码全为0000，即两端，即两端点编码逻辑或运算为点编码逻辑或运算为0，那么该线段完全位于窗口内，可直，那么该线段完全位于窗口内，可直接保留；接保留；（（2）对两端点的四位二进制编码进行逻辑与运算，若结果）对两端点的四位二进制编码进行逻辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃；不为零，那么整条线段必位于窗口外，可直接舍弃；（（3）否则，这条线段既不能直接保留，也不能直接舍弃，）否则，这条线段既不能直接保留，也不能直接舍弃，它可能与窗口相交。

此时，需要对线段进行再分割，即找它可能与窗口相交此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割重复这一过进行检查，决定保留、舍弃或再次进行分割重复这一过程，直到全部线段均被舍弃或保留为止程，直到全部线段均被舍弃或保留为止裁剪过程是递归的Cohen-Sutherland裁剪算法如何判定应该与窗口的哪条边求交呢？如何判定应该与窗口的哪条边求交呢？ 编码中对应位为1的边•计算线段P1(x1,y1)P2(x2,y2)与窗口边界的交点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);}左交点右交点下交点上交点例：分别给下列直线段编码，并判断是否需要剪裁。

分别给下列直线段编码，并判断是否需要剪裁P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2C1=0101C2=1010P1P2ADC1=0000C2=0000例：例：Cohen-SutherLand算法过程：过程： 1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr2）对AB编码，A的编码codeA=0001，B的编码为codeB=0110 3）线段线段AB裁剪的基本过程（按左右下上的顺序）裁剪的基本过程（按左右下上的顺序）： ①由于codeA | codeB≠0，对AB不能全部保留；又因为codeA & codeB=0，对AB不能全部舍弃，因此要对AB进行求交处理 ②由codeA=0001知A在窗口左边外侧，按左右下上的顺序求AB与窗口左边交点为P1，AP1必在窗口外，故裁剪掉，并用A替换P1如图（b）所示交点替换是为了方便编程循环） ③对P1B重复上述处理A（原P1）编码为0000，B编码为0110；由于A（原P1）已在窗口内，交换A和B的坐标值与编码，则B编码为0000，A编码变为0110，按左右下上顺序求得右交点为P3；A（原B）P3必在窗口外，故裁剪掉，并用A替换P3。

如图（c）所示 ④A的编码还没有达到0000，再求得下边交点为P2，AP2必定在窗口外，故裁剪掉，并用A替换P2如图（d）所示 ⑤对剩下的直线段AB再进行判断，现在A编码为0000，B编码为0000，由于codeA | codeB=0，全在窗口中，故全部保留最后得到裁剪后的线段为AB，算法结束 •求交测试顺序固定求交测试顺序固定(左上右下）左上右下）•最坏情形，线段求交四次最坏情形，线段求交四次对于那些非完全可见、又非显然不可见的线段，需要求交求交（如线段AD)，求交前先测试与窗口哪条边所在直线有交？(按序判断端点编码中各位的值ClCtCrCb） 1）特点：用编码方法可快速判断线段--完全可见和显然不可见 2）特别适用二种场合： 大窗口场合； 窗口特别小的场合(如, 光标拾取图形时, 光标看作小的裁剪窗口编码算法特点算法的思路：算法的思路： 采用与前相似的线段端点编码和相应的检查方法，采用与前相似的线段端点编码和相应的检查方法，先先判定完全可见线段和显然不可见线段判定完全可见线段和显然不可见线段 否则，将否则，将线段分割成相等的两段线段分割成相等的两段，然后对每一小段重，然后对每一小段重复上述的检查，复上述的检查，直至找到每段与窗口边界的交点或分割小直至找到每段与窗口边界的交点或分割小段的长度充分小段的长度充分小，可以视为一点时为止。

可以视为一点时为止 相当于：相当于：对分查找法求交，分割次数最多不超过线段端对分查找法求交，分割次数最多不超过线段端点的表示精度点的表示精度3.2.3 中点分割算法算法过程：1）输入线段AB的两端点坐标A（x0,y0）、B（x1,y1），以及裁剪窗口的四条边界：yt,yb,xl,xr2）对AB编码，A的编码codeA=0001，B的编码为codeB=0110 3）线段AB裁剪的基本过程： 例：中点例：中点算法裁剪过程：y=yTy=yBx=xLx=xRABBPm2Pm1Pm3y=yTy=yBx=xLx=xRBABPm2Pm1　①由于codeA | codeB≠0，对AB不能全部保留；又因为codeA & codeB=0，对AB不能全部舍弃，因此要对AB求中点处理；　②求AB中点　③判断中点Pm1是否在窗口内，若不在窗口内，则将中点和离窗口最远点构成的线段去掉，以线段另一端点和该中点再构成线段，求其中点；若中点Pm1在窗口内，如上页左图所示则以中点和最远点构成线段APm1，并求其中点Pm2，直至中点与窗口边界的坐标值在规定的误差范围内，则该中点就是线段落在窗口内的一个端点，用原线段端点A替代每一次保留的中点。

　④若另一端点在窗口内，则经③即可确定该线段在窗口内的部分；若不在窗口内，如右图，交换两端点，则该点和所求出的在窗口上的那一点构成一条线段AB，重复步骤③，即可求出落进窗口的另外一点并用原线段端点A替代每一次保留的中点　最后得到裁剪后的线段为AB，算法结束 •对分辩率为2N*2N的显示器，上述二分过程至多进行N次•主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度中点分割裁剪算法特点 设要裁剪的线段是P0P1 P0P1和窗口边界交于A,B,C,D四点，见图算法的基本思想是从A,B和P0三点中找出最靠近的P1点，图中要找的点是P0从C,D和P1中找出最靠近P0的点图中要找的点是C点那么P0C就是P0P1线段上的可见部分3.2.4 梁友栋-Barsky算法 线段的参数表示x=x0+t△xy=y0+t△y 0<=t<=1 △x=x1-x0 △y=y1-y0窗口边界的四条边分为两类：始边和终边1.求出P0P1与两条始边的交点参数t0, t1 , 令tl=max(t0 ,t1,0)，则tL即为三者中离p1最近的点的参数2.求出p0p1与两条终边的交点参数t2, t3, 令tu=min(t2,t3,1) ，则tU即为三者中离p0最近的点的参数若tu > tl,则可见线段区间 [tl , tu]t0t1t2t301交点计算3.始边和终边的确定及交点计算：令 QL= - △x DL= x0-xL QR= △x DR= xR-x0 QB= - △y DB= y0-yB QT= △y DT= yT-y0交点为: ti= Di / Qi i=L,R,B,TQi <0 ti为与始边交点参数Qi >0 ti为与终边交点参数Qi =0 Di <0 时,线段不可见 Di >0 时, 分析另一D, EFAB当Qi =0时 若Di <0 时,线段不可见（如图中AB，有QR=0，DR<0）若Di >0 时, 分析另一D, （如图中的EF就是这种情况，它使QL=0，DL>0和QR=0，DR>0。

这时由于EF和x=xL及x=xR平行，故不必去求出EF和x=xL及x=xR的交点，而让EF和y=yT及y=yB的交点决定直线段上的可见部分 EFAB3.始边和终边的确定及交点计算3.3 多边形裁剪•错觉错觉：直线段裁剪的组合？•关键关键：要保持窗口内多边形的边界部分保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态使剪裁后的多边形的边仍然保持封闭状态•新的问题新的问题：：1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？多边形裁剪多边形裁剪2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？3.3.1 Sutherland-Hodgman算法n思路思路：将多边形边界作为一个整体，分而治之将多边形边界作为一个整体，分而治之将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果n流水线过程流水线过程(左上右下左上右下)：：左边的结果是上边的开始亦称亦称逐边裁逐边裁剪算法剪算法Sutherland-Hodgman算法–内侧空间与外侧空间–多边形的边与半空间的关系PIS 可 见 侧PS 可 见 侧PIS 可 见 侧PS 可 见 侧(a)从外到内　　　　从外到内　　　　 (b)从内到内　　　从内到内　　　 (c)从内到外　　　　　从内到外　　　　　(d)从外到外从外到外　输出　输出P和和I 输出输出P 　　 输出输出I 　　　　不输出不输出p1p2p3p4p5q1q2q3q4需要设置二个表： 输入顶点表输入顶点表( (向量向量) )—存放被裁剪多边形的顶点p1-pm。

输出顶点表输出顶点表( (线性链表线性链表) )—存放裁剪过程中及结果的顶点 q1-qnSutherland-Hodgman算法q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前： 裁剪后：输入顶点表输入顶点表：p1p2p3p4p5 输入顶点表输入顶点表: 不变输出顶点表：输出顶点表： 空 输出顶点表输出顶点表: : q1q2p3q7q8q5q6q4q3需要设置二个表： 输入顶点表输入顶点表( (向量向量) )—存放被裁剪多边形的顶点p1- pm 输出顶点表输出顶点表( (线性链表线性链表) )—存放裁剪过程中及结果的顶点 q1- qnSutherland-Hodgman算法实现方法实现方法：①设置二个表 输入顶点表输入顶点表( (向量向量) )—存放被裁剪多边形的顶点p1-pm 输出顶点表输出顶点表( (线性链表线性链表) )—存放裁剪过程中及结果的顶点 q1-qn②输入顶点表中各顶点要求按一定顺序排列按一定顺序排列，一般可采用顺时针或逆顺时针或逆时针时针方向。

③相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理Sutherland-Hodgman算法Sutherland-Hodgman算法•裁剪结果的顶点构成裁剪结果的顶点构成：裁剪边内侧的原顶点；多边形的边与裁剪边的交点•顺序连接顺序连接特点：l裁剪算法采用流水线方式， 适合硬件实现l可推广到任意凸多边形裁剪 窗口问题：一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AED Sutherland-Hodgman多边形裁剪：输入顶点BAFEDCBAFEDC，，输出顶点：V1 A V2 V3 E D V4V1 A V2 V3 E D V4Sutherland-Hodgman算法3.3.2 Weiler-Athenton算法算法裁剪窗口为任意多边形（裁剪窗口为任意多边形（凸、凹、带内环）的情况：的情况：–主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A –裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B •主多边形和裁剪多边形把二维平面分成两部分。

•内裁剪内裁剪：A∩B•外裁剪外裁剪：A-BWeiler-Athenton算法算法裁剪结果区域的边界由裁剪结果区域的边界由A的部的部分边界和分边界和B的部分边界两部分构的部分边界两部分构成，并且在交点处边界发生交成，并且在交点处边界发生交替，即由替，即由A的边界转至的边界转至B的边界，的边界，或由或由B的边界转至的边界转至A的边界的边界 Weiler-Athenton算法算法–如果主多边形与裁剪多边形有交点，则如果主多边形与裁剪多边形有交点，则交点成对出现，交点成对出现，它们被分为如下两类：它们被分为如下两类：•进点进点：主多边形边界由此进入裁剪多：主多边形边界由此进入裁剪多边形内边形内 如，如，I1,I3, I5, I7, I9, I11•出点出点：主多边形边界由：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域. 如，如， I0,I2, I4, I6, I8, I10 WeilerWeiler-Atherton-Atherton（（W-AW-A））算法算法（双边裁剪法） 可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形 被裁剪的多边形被裁剪的多边形————主多边形主多边形 裁剪区域裁剪区域————裁剪多边形裁剪多边形 各多边形的各多边形的外部边界取外部边界取顺时针顺时针方向，而其方向，而其内部边界或孔取内部边界或孔取逆时针逆时针方向方向。

思路思路：主多边形和裁剪多边形均用它们的顶点表来定义 这两类交点分别用进点表进点表和出点表出点表来存放主多边形和裁剪多边形的边界若相交，交点必定成对地出现交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称进点进点），另一个交点则为离开时的交点（称出点出点）c1c2c3c4s1s2s3s4s5s6s7I1I2I3I4I5I6I7I8裁剪窗口多边形裁剪窗口多边形主多边形主多边形 裁剪窗口 顶点表 顶点表 s1 c1 I1 I8 I2 I1 s2 c2 I3 I2 s3 I3 I4 c3 s4 I4 I5 I5 I6 c4 s5 I6 I7 I7 s6 c1 I8 s7 s1起点简单例4 : W-AW-A算法进行算法进行多边形裁剪多边形裁剪进点进点出点出点算法算法： 1.分别建立主多边形和裁剪多边形的顶点表； 2.求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表； 3.将交点加入各顶点表中； 4. if 进点表为空 then finish（1）取一进点作为始点；（2）跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中； 根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中； if 该交点不是起始点 then （2） if 进点表中还有未遍历到的交点 then （1）（3）finish复杂例5，分析裁剪过程，分别写出主多边形、裁剪多边形的顶点表，以及最终裁剪结果。

Weiler-Athenton算法算法–交点的奇异情况处理交点的奇异情况处理 1.与裁剪多边形边重合的主多边形的边不参与求交点；与裁剪多边形边重合的主多边形的边不参与求交点；2.对于顶点落在裁剪多边形的边上的主多边的边，如果落在对于顶点落在裁剪多边形的边上的主多边的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点在该裁剪边的外侧，将该顶点不看作交点 3.3.3 3 字符裁剪方法字符裁剪方法点阵字符点阵字符——每个字符用一个位图(掩膜) 来表示，其大小由位图的尺寸来确定，如 7 × 9，9 × 16，16 × 24 等 1 1 1 1 0 0 0 0 1 0 0 1 0 00 1 0 0 1 0 00 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 01 1 1 0 0 0 0 0 0 0 0 0 0 0P在字库的表示P的显示结果 矢量字符矢量字符—— 选一个正方形网格网格，作为字符的局部坐局部坐标标空间，网格的大小可选16 × 16，32 × 32，64 × 64等。

每个字符由构成它的笔画笔画组成，每个笔画又由其两端确定每个端点端点保存它的坐标值坐标值及连线标志连线标志xyop1p2p3p4p5p66363字符的编码x1 y1 0x2 y2 1x3 y3 0x4 y4 1x5 y5 0x6 y6 1－ 10表示不连线1表示连线字符结束标志特点特点：除用直线段表示笔画外，还可采用二次三次曲线段 对矢量字符的变换是对其端点进行图形的几何变换（一）字符的裁剪 1.简单裁剪简单裁剪方法： 用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，不予显示 4.精确裁剪精确裁剪方法： 对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内 对于矢量字符，对组成其笔画的每条线段进行裁剪（二）（二） 字符串的剪裁字符串的剪裁 字符串剪裁3种可选择的方法 1.串精度裁剪⒉ 字符精度裁剪⒊ 字符的精密(笔画、像素精度)剪裁 （为了减少计算量，在进行真正的求交计算之前，往往先用凸包等先用凸包等辅助结构进行粗略地比较辅助结构进行粗略地比较，排除那些显然不相交的情形。

什么是凸包凸包？——一个图形的凸包，就是包含这个图形的凸区域（凸多边形、凸多面体），它不是唯一的　　　　　　　　　　　　 　求交计算：求交点、求交线求交计算：求交点、求交线 •线段的裁剪线段的裁剪–直接求交算法直接求交算法–Cohen-SutherLand算法算法(编码算法编码算法)–中点分割算法中点分割算法–LiangLiang( (梁友栋梁友栋)--)--BarskyBarsky 算法算法•多边形裁剪多边形裁剪–Sutherland-Sutherland-HodgmanHodgman算法算法–WeilerWeiler- -AthentonAthenton算法（适用于带内孔的各算法（适用于带内孔的各种多边形）种多边形） 　　　　　　　　　　　　 　本章小结本章小结 练习：1.已知P1、P2和Q1、Q2，（（的坐标值）的坐标值），写出两条线段求交点的算法（或C语言函数） （程序如何实现？）2.Cohen-SutherLand与中点分割法有什么异同？3.分别用Cohen-SutherLand、中点分割法（e=0.01）裁剪如下图所示线段AB2yB(-1,-2)A(3,3)窗口x25. 试用Sutherland-Hodgman算法对所示多边形进行裁剪，要求画出每次裁剪对应的图形，并标明输入和输出的顶点。

6. 试用Weiler-Atherton算法对所示多边形进行裁剪，标明输入和输出的顶点，与上面算法相比较上机作业：–编程实现中点线段裁剪算法–调试教材中的多边形裁剪算法，并改变多边形顶点数。