[计算机软件及应用]二维图形裁剪课件.ppt

1、二维图形裁剪二维图形裁剪u裁剪概述裁剪概述u 线段裁剪线段裁剪直接求交算法；直接求交算法；Cohen-Sutherland算法；（重点，算法实现）算法；（重点，算法实现）梁友栋梁友栋-Barsky算法算法u 多边形裁剪多边形裁剪 Sutlerland_Hodgman算法（难点，算法实现）算法（难点，算法实现）Weiler-Athenton算法算法 u 字符裁剪字符裁剪裁裁 剪剪二维图形裁剪二维图形裁剪预备知识：求交预备知识：求交（矩形窗口）（矩形窗口）裁剪裁剪三维裁剪三维裁剪长方体裁剪体长方体裁剪体棱锥体体裁剪体棱锥体体裁剪体编码裁剪算法编码裁剪算法被裁剪对象：被裁剪对象：直线段、多边形直线段

2、、多边形、三维实体、三维实体一、裁剪概述一、裁剪概述 裁剪：裁剪：是裁去窗口之外物体或物体部分的一种操作。是裁去窗口之外物体或物体部分的一种操作。剪裁的应用剪裁的应用1 1、从定义的场景中抽取出用于观察的部分；、从定义的场景中抽取出用于观察的部分；2 2、在三维视图中标识出可见面；、在三维视图中标识出可见面；3 3、防止线段或对象的边界混淆；、防止线段或对象的边界混淆；4 4、用实体造型来创建对象；、用实体造型来创建对象；5 5、显示多窗口的环境；、显示多窗口的环境；6 6、允许选择图形的一部分来进行拷贝，移动和删除。、允许选择图形的一部分来进行拷贝，移动和删除。“取景器”=窗口l裁剪的目的裁

3、剪的目的判断图形元素是否落在裁剪窗口之内并找出其位判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分于内部的部分l裁剪处理的基础裁剪处理的基础图元关于窗口内外关系的判别图元关于窗口内外关系的判别图元与窗口的求交图元与窗口的求交l假定条件假定条件矩形裁剪窗口：矩形裁剪窗口：xmin,xmaxymin,ymax待裁剪点或线段：待裁剪点或线段：点裁剪点裁剪 点点(x,y)在窗口内的充分必要条件是：在窗口内的充分必要条件是：问题：对于任何多边形窗口，如何判别？问题：对于任何多边形窗口，如何判别？xxxminmaxyyyminmaxWytWybWxlWxrP1P2P3线段相对于该窗口的情况有线段相对

4、于该窗口的情况有:线段线段全部全部位于位于窗口的内部窗口的内部（A）；）；线段线段全部全部位于位于窗口外部窗口外部（B、C）；）；线段的线段的中间部分中间部分在在窗口内窗口内，而二端点在窗口外部，而二端点在窗口外部（D）；）；线段的线段的一端在窗口内一端在窗口内，而，而另一端在窗口外另一端在窗口外（E）。）。x=xLx=xRy=yBy=yTABCDE二、线段裁剪二、线段裁剪待裁剪线段和窗口的关系待裁剪线段和窗口的关系 线段完全可见线段完全可见显然不可见显然不可见 线段至少有一端点在窗口之外，但非显然不可见线段至少有一端点在窗口之外，但非显然不可见 保留丢弃裁剪为提高效率，算法设计时应考虑：为提

5、高效率，算法设计时应考虑：(一）快速判断线段完全在窗口内或外的情形；一）快速判断线段完全在窗口内或外的情形；(二二)设法减少裁剪情形中求交次数和每次求交时所需的计算量设法减少裁剪情形中求交次数和每次求交时所需的计算量。直接求交直接求交算法算法基本思想基本思想是：判断直线与窗口的位置关系，确定该直是：判断直线与窗口的位置关系，确定该直线是完全可见、部分可见或完全不可见，然后输出处线是完全可见、部分可见或完全不可见，然后输出处于窗口内线段的端点，并显示此线段。于窗口内线段的端点，并显示此线段。根据直线段和窗口的关系可知：根据直线段和窗口的关系可知：（1 1）整条线在窗口之内。此时，不需剪裁，显示整

6、条线段。）整条线在窗口之内。此时，不需剪裁，显示整条线段。（2 2）整条线在窗口之外，此时，不需剪裁，不显示整条线段。）整条线在窗口之外，此时，不需剪裁，不显示整条线段。（3 3）部分线在窗口之内，部分线在窗口之外。）部分线在窗口之内，部分线在窗口之外。此时，需要求出线段与窗口边界的交点，并将窗口外的线段部此时，需要求出线段与窗口边界的交点，并将窗口外的线段部分剪裁掉，显示窗口内的部分。分剪裁掉，显示窗口内的部分。例例1 设有直线段设有直线段P0P1，有一个矩形裁剪窗口，写出，有一个矩形裁剪窗口，写出对该线段裁剪的算法。对该线段裁剪的算法。1）求出直线）求出直线P0P1与窗口的交点与窗口的交点

7、I，如图（，如图（a）所示。）所示。2）取）取P0 I线段显示，擦除线段显示，擦除I P1线段，并将线段，并将P1替换替换I，即，即得得P0P1线段，裁剪结束。如图（线段，裁剪结束。如图（b）所示。）所示。P0P1IP0P1（a）（b）求线段与窗口交点求线段与窗口交点设线段两端点坐标为：和则过这两点设线段两端点坐标为：和则过这两点的直线方程为：的直线方程为：其中其中k为斜率。上述直线方程与窗口各边界的交点为：为斜率。上述直线方程与窗口各边界的交点为：左：左：右：右：下：下：上：上：11111212)()(yxxkyxxxxyyykyxxkyxxLL11)(kyxxkyxxRR11)(0)(/1

8、(11kyyyykxxBB0)(/1(11kyyyykxxTT)(111yxP，)(222yxP，基本思想基本思想：对于每条待裁剪的线段：对于每条待裁剪的线段P1P2分三种情况处理：分三种情况处理：若若P1P2完全在窗口内，则显示该线段完全在窗口内，则显示该线段P1P2，简称，简称“取取”之；之；若若P1P2完全在窗口外，则丢弃该线段，简称完全在窗口外，则丢弃该线段，简称“舍舍”之；之；若线段既不满足若线段既不满足“取取”的条件，也不满足的条件，也不满足“舍舍”的条件，的条件，则求线段与窗口边界的则求线段与窗口边界的交点交点，在交点处把线段分为两段，在交点处把线段分为两段，其中一段完全在窗口外

9、，可舍弃之，然后对另一段重复上其中一段完全在窗口外，可舍弃之，然后对另一段重复上述处理。述处理。核心思想：分区编码和线段分割核心思想：分区编码和线段分割。Cohen-Sutherland 算法算法(编码算法编码算法)分区编码方法：图形分区编码方法：图形区域划分成九个区域划分成九个区域。区域。四位编码四位编码 表示端点所处的位置：表示端点所处的位置：(-)(-)上上 下下 右右 左左第第一一位为位为“1”1”时，表示点在时，表示点在y=yy=yT T的上方的上方；第第二二位为位为“1”1”时，表示点在时，表示点在y=yy=yB B的下方的下方；第第三三位为位为“1”1”时，表示点在时，表示点在x

10、=xx=xR R的右方的右方；第第四四位为位为“1”1”时，表示点在时，表示点在x=xx=xL L的左方的左方。000000010010100001001001101001010110 x=xLx=xRy=yBy=yT11111 1 1 1 1 1 1 1#define LEFT 1#define RIGHT 2#define BOTTOM 4#define TOP 8编码原则编码原则每个区域赋予一个四位编码，每个区域赋予一个四位编码，CtCbCrCl，上下右左；，上下右左；elseyyCt0max1当elsexxCr0max1当elsexxCl0min1当elseyyCb0min1当编码方法

11、编码方法练习：请给出右图的线练习：请给出右图的线段端点编码（段端点编码（端点编码：端点编码：定义为它所在区域的编码）定义为它所在区域的编码）x=xLx=xRy=yBy=yTABCDE第一步第一步 判别线段两端点是否都落在窗口内，如果是，判别线段两端点是否都落在窗口内，如果是，则线段则线段完全可见完全可见；否则进入第二步；否则进入第二步；第二步第二步 判别线段是否为判别线段是否为显然不可见显然不可见，如果是，则裁，如果是，则裁 剪结束；否则进行第三步剪结束；否则进行第三步 ；第三步第三步 求线段与求线段与窗口边延长线窗口边延长线的交点，这个交点将的交点，这个交点将 线段分为两段，其中一段显然不可

12、见，丢弃。线段分为两段，其中一段显然不可见，丢弃。对余下的另一段重新进行第一步，第二步判断，对余下的另一段重新进行第一步，第二步判断，直至结束直至结束 Cohen-Sutherland 算法算法步骤编码判断编码判断当线段的两个端点的编码的当线段的两个端点的编码的逻辑逻辑“与与”非零非零时时，线段，线段为显然不可见的。为显然不可见的。也可以进行也可以进行“按位于按位于”运算运算，可知，可知这两个端点是否同在视区的上、下、左、右；这两个端点是否同在视区的上、下、左、右；如如code1=0101,code2=0110，则，则code1&code2=0100,表示表示在窗口下方。在窗口下方。问题：问题

13、：显然可见的编码如何判断？显然可见的编码如何判断？编码判断编码判断对一条线段的可见性测试方法：对一条线段的可见性测试方法：（1）若线段两个端点的四位二进制编码全为）若线段两个端点的四位二进制编码全为0000，即两端，即两端点编码逻辑或运算为点编码逻辑或运算为0，那么该线段完全位于窗口内，可直，那么该线段完全位于窗口内，可直接保留；接保留；（2）对两端点的四位二进制编码进行逻辑与运算，若结果）对两端点的四位二进制编码进行逻辑与运算，若结果不为零，那么整条线段必位于窗口外，可直接舍弃；不为零，那么整条线段必位于窗口外，可直接舍弃；（3）否则，这条线段既不能直接保留，也不能直接舍弃，）否则，这条线段

14、既不能直接保留，也不能直接舍弃，它可能与窗口相交。它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口边线的一个交此时，需要对线段进行再分割，即找到与窗口边线的一个交点，根据交点位置，赋予四位二进制编码，并对分割后的线点，根据交点位置，赋予四位二进制编码，并对分割后的线段按照一定的顺序（如左右下上）进行检查，决定保留、舍段按照一定的顺序（如左右下上）进行检查，决定保留、舍弃或再次进行分割。重复这一过程，直到全部线段均被舍弃弃或再次进行分割。重复这一过程，直到全部线段均被舍弃或保留为止。或保留为止。例：例：P1P2C1=0001C2=0000P1P2C1=0100C2=0101BCP1P2

15、C1=0101C2=1010P1P2ADC1=0000C2=0000例：例：Cohen-SutherLand算法过程：算法过程：过程：过程：1）输入线段）输入线段AB的两端点坐标的两端点坐标A（x0,y0）、）、B（x1,y1），以及裁剪窗口的四），以及裁剪窗口的四条边界：条边界：yt,yb,xl,xr。2）对）对AB编码，编码，A的编码的编码codeA=0001，B的编码为的编码为codeB=0110。3）线段线段AB裁剪的基本过程（按左右下上的顺序）裁剪的基本过程（按左右下上的顺序）：由于由于codeA|codeB0，对，对AB不能全部保留；又因为不能全部保留；又因为codeA&codeB

16、=0，对，对AB不能全部舍弃，因此要对不能全部舍弃，因此要对AB进行求交处理。进行求交处理。由由codeA=0001知知A在窗口左边外侧，按左右下上的顺序求在窗口左边外侧，按左右下上的顺序求AB与窗口左边与窗口左边交点为交点为P1，AP1必在窗口外，故裁剪掉，并用必在窗口外，故裁剪掉，并用A替换替换P1。如图（。如图（b）所示。）所示。（交点替换是为了方便编程循环）。（交点替换是为了方便编程循环）。对对P1B重复上述处理。重复上述处理。A（原（原P1）编码为）编码为0000，B编码为编码为0110；由于；由于A（原（原P1）已在窗口内，交换）已在窗口内，交换A和和B的坐标值与编码，则的坐标值与

17、编码，则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，全在窗口中，故全部

18、保留。，全在窗口中，故全部保留。最后得到裁剪后的线段为最后得到裁剪后的线段为AB，算法结束。，算法结束。求交测试顺序固定求交测试顺序固定(左上右下）左上右下）最坏情形，线段求交四次。最坏情形，线段求交四次。对于那些非完全可见、又非显然不可见的线段，需要对于那些非完全可见、又非显然不可见的线段，需要求交求交（如线段（如线段AD)，求交前，求交前先测试先测试与窗口哪条边所在与窗口哪条边所在直线有交？直线有交？(按序判断端点编码中各位的值按序判断端点编码中各位的值ClCtCrCb）1）特点：用编码方法可快速判断线段）特点：用编码方法可快速判断线段-完全可见和显然不可见。完全可见和显然不可见。2）特别

19、适用二种场合：）特别适用二种场合：大窗口场合；大窗口场合；窗口特别小的场合窗口特别小的场合(如如,光标拾取图形时光标拾取图形时,光标看作小的裁剪窗口。）光标看作小的裁剪窗口。）编码算法特点编码算法特点设要裁剪的线段是设要裁剪的线段是P P0 0P P1 1。P P0 0P P1 1和窗口边界交于和窗口边界交于A,B,C,DA,B,C,D四点，见图。四点，见图。算法的基本思想算法的基本思想是从是从A,BA,B和和P P0 0三点中找出最靠近的三点中找出最靠近的P P1 1点，图中要找的点是点，图中要找的点是P P0 0。从从C,DC,D和和P P1 1中找出最靠近中找出最靠近P P0 0的点。图

20、中要找的点是的点。图中要找的点是C C点。那么点。那么P P0 0C C就是就是P P0 0P P1 1线段线段上的可见部分。上的可见部分。梁友栋梁友栋-Barsky算法算法 线段的线段的参数表示参数表示x=x0+txy=y0+ty 0=t tl,则可见线段区间则可见线段区间 tl,tut0t1t2t3P01交点计算交点计算P13.始边和终边的确定及交点计算始边和终边的确定及交点计算：令令 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为与终边交点参数为与终边

21、交点参数当当Qi=0时时 若若Di 0 时时,线段不可见线段不可见（如图中（如图中AB，有，有QR=0，DR0 时时,分析另一分析另一D,（如图中的如图中的EF就是这种情况，它使就是这种情况，它使QL=0，DL0和和QR=0，DR0。这时由于。这时由于EF和和x=xL及及x=xR平行，故不必去求出平行，故不必去求出EF和和x=xL及及x=xR的交点，而让的交点，而让EF和和y=yT及及y=yB的交点的交点决定直线段上的可见部分。）决定直线段上的可见部分。）ABEFAB三、多边形裁剪三、多边形裁剪 错觉：直线段裁剪的组合？错觉：直线段裁剪的组合？关键：关键：要要保持窗口内多边形的边界部分，保持窗

22、口内多边形的边界部分，而且要将窗而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，框的有关部分按一定次序插入多边形的保留边界之间，从而从而使剪裁后的多边形的边仍然保持封闭状态。使剪裁后的多边形的边仍然保持封闭状态。新的问题新的问题：1）边界不再封闭，需要用窗口边界的恰当部分来封闭）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？它，如何确定其边界？2）一个凹多边形可能被裁剪成几个小的多边形，如何）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？确定这些小多边形的边界？Sutherland-Hodgman算法算法n思路思路：将多边形边界作为一个整体，分

23、而治之。：将多边形边界作为一个整体，分而治之。将多将多边形的各边先相对于窗口的某一条边界进行裁剪，然边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。次，便可得到最终结果。n流水线过程流水线过程(左上右下左上右下)：左边的结果是上边的开始。：左边的结果是上边的开始。亦称亦称逐边裁逐边裁剪算法剪算法 内侧空间与外侧空间内侧空间与外侧空间 多边形的边与半空间的关系多边形的边与半空间的关系PIS 可 见 侧PS 可 见 侧PIS 可 见 侧PS 可 见 侧(a)从外到内从外到内(b)从内到内

24、从内到内(c)从内到外从内到外(d)从外到外从外到外输出输出P和和I 输出输出P 输出输出I 不输出不输出p1p2p3p4p5q1q2q3q4需要设置二个表：需要设置二个表：输入顶点表输入顶点表(向量向量)存放被裁剪多边形的顶点存放被裁剪多边形的顶点p p1 1-p-pm m。输出顶点表输出顶点表(线性链表线性链表)存放裁剪过程中及结果的顶存放裁剪过程中及结果的顶点点 q q1 1-q-qn n。q5q6q7q8q1q2p3q7q8q5q6q4q3裁剪前：裁剪前：裁剪后：裁剪后：输入顶点表输入顶点表：p1p2p3p4p5 输入顶点表输入顶点表:不变不变输出顶点表：输出顶点表：空空 输出顶点表输

25、出顶点表:q1q2p3q7q8q5q6q4q3需要设置二个表：需要设置二个表：输入顶点表输入顶点表(向量向量)存放被裁剪多边形的顶点存放被裁剪多边形的顶点p p1 1-p-pm m。输出顶点表输出顶点表(线性链表线性链表)存放裁剪过程中及结果的顶点存放裁剪过程中及结果的顶点 q q1 1-q-qn n。实现方法：实现方法：设置二个表设置二个表 输入顶点表输入顶点表(向量向量)存放被裁剪多边形的顶点存放被裁剪多边形的顶点p p1 1-p-pm m。输出顶点表输出顶点表(线性链表线性链表)存放裁剪过程中及结果的顶点存放裁剪过程中及结果的顶点 q q1 1-q-qn n。输入顶点表中各顶点要求输入顶

26、点表中各顶点要求按一定顺序排列按一定顺序排列，一般可采用，一般可采用顺顺时针或逆时针时针或逆时针方向。方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。行裁剪。算法中相对于各窗口边界的裁剪过程相同，且每次都是相算法中相对于各窗口边界的裁剪过程相同，且每次都是相对于前一次的结果进行处理。对于前一次的结果进行处理。裁剪结果的顶点构成裁剪结果的顶点构成：裁剪边内侧的原顶点；裁剪边内侧的原顶点；多边形的边与裁剪边的交点。多边形的边与裁剪边的交点。顺序连接。顺序连接。特点：特点：l裁剪算法采用流水线方式，裁剪算法采用流水线方式，适合硬件实现

27、。适合硬件实现。l可推广到任意凸多边形裁剪可推广到任意凸多边形裁剪 窗口窗口问题：一个凹多边形可能被裁剪成几个小的多边形，问题：一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？如何确定这些小多边形的边界？AFEDCBV1V2V3V4AFEDCBV1V2V3V4AED Sutherland-Hodgman Sutherland-Hodgman多边形裁剪：输入顶点多边形裁剪：输入顶点BAFEDCBAFEDC，输出顶点：输出顶点：V1 A V2 V3 E D V4V1 A V2 V3 E D V4Sutherland-Hodgman算法算法Weiler-Athenton算法算法裁

28、剪窗口为任意多边形（凸、凹、带内环）的情况：裁剪窗口为任意多边形（凸、凹、带内环）的情况：主多边形：被裁剪多边形，记为主多边形：被裁剪多边形，记为A 裁剪多边形：裁剪窗口，记为裁剪多边形：裁剪窗口，记为B 主多边形和裁剪多边形把二维平面分成两部主多边形和裁剪多边形把二维平面分成两部分。分。内裁剪：内裁剪：ABAB 外裁剪外裁剪：A-BA-B裁剪结果区域的边界由裁剪结果区域的边界由A的部分边界和的部分边界和B的部分边界的部分边界两部分构成，并且在交点处边界发生交替，即由两部分构成，并且在交点处边界发生交替，即由A的的边界转至边界转至B的边界，或由的边界，或由B的边界转至的边界转至A的边界的边界

29、Weiler-Athenton算法算法 如果主多边形与裁剪多边形有交点，则如果主多边形与裁剪多边形有交点，则交点成对出现，交点成对出现，它们被分为如下两类：它们被分为如下两类：进点进点：主多边形边界由此进入裁剪多：主多边形边界由此进入裁剪多边形内边形内 如，如，I1,I3,I5,I7,I9,I11 出点出点：主多边形边界由：主多边形边界由此离开裁剪多边形区域此离开裁剪多边形区域.如，如，I0,I2,I4,I6,I8,I10 Weiler-Atherton（W-A）算法（双边裁剪法）算法（双边裁剪法）可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多可以用一个有内孔的凹多边形去裁剪另一个也有内

30、孔的凹多边形。边形。被裁剪的多边形被裁剪的多边形主多边形主多边形 裁剪区域裁剪区域裁剪多边形裁剪多边形 各多边形的各多边形的外部边界取外部边界取顺时针顺时针方向，而其方向，而其内部边界或孔取内部边界或孔取逆逆时针时针方向方向。思路：思路：主多边形和裁剪多边形均用它们的顶点表来定义。主多边形和裁剪多边形均用它们的顶点表来定义。这两类交点分别用这两类交点分别用进点表进点表和和出点表出点表来存放。来存放。主多边形和裁剪多边形的边界若相交，主多边形和裁剪多边形的边界若相交，交点必定成对地出现交点必定成对地出现，其中一个交点为主多边形边进入裁剪多边形内部时的交点（称其中一个交点为主多边形边进入裁剪多边形

31、内部时的交点（称进点进点），另一个交点则为离开时的交点（称），另一个交点则为离开时的交点（称出点出点）。）。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.1.分别建立主多边形和裁剪多边形的

32、顶点表；分别建立主多边形和裁剪多边形的顶点表；2.2.求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进求出主多边形与裁剪多边形的交点（进点和出点）并分别建立进点表和出点表；点表和出点表；3.3.将交点加入各顶点表中；将交点加入各顶点表中；4.4.if if 进点表为空进点表为空 then finishthen finish（1 1）取一进点作为始点；）取一进点作为始点；（2 2）跟踪主多边形顶点表，直至发现下一交点，复制这一段主）跟踪主多边形顶点表，直至发现下一交点，复制这一段主多边形顶点到内表中；多边形顶点到内表中；根据交点处指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多根据交点处

33、指针，转到裁剪多边形顶点表中的相应位置跟踪裁剪多边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中；边形顶点表，直至发现下一交点，复制这一段裁剪多边形顶点到内表中；if if 该交点不是起始点该交点不是起始点 then then （2 2）if if 进点表中还有未遍历到的交点进点表中还有未遍历到的交点 then then （1 1）（3 3）finishfinish复杂例复杂例5，分析裁剪过程，分别写出主多边形、裁剪多边形，分析裁剪过程，分别写出主多边形、裁剪多边形的顶点表，以及最终裁剪结果。的顶点表，以及最终裁剪结果。Weiler-Athenton算法算法交点的奇异情况处理交点

34、的奇异情况处理 1.与裁剪多边形边重合的主多边形的边不参与求交点；与裁剪多边形边重合的主多边形的边不参与求交点；2.对于顶点落在裁剪多边形的边上的主多边形的边，如果对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点边落在该裁剪边的外侧，将该顶点不看作交点 四、字符裁剪方法四、字符裁剪方法点阵字符每个字符用一个位图(掩膜)来表示，其大小由位图的尺寸来确定，如 7 9，9 16，16 24 等。1 1 1 1 0 0 0 0 1 0 0 1 0 00 1 0 0 1

35、 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 0 x2 y2 1x3 y3 0 x4 y4 1x5 y5 0 x6 y6 1 10表示不连线1表示连线字符

36、结束标志特点特点：除用直线段表示笔画外，还可采用二次三次曲线段。对矢量字符的变换是对其端点进行图形的几何变换。（一）字符的裁剪（一）字符的裁剪 1.1.简单裁剪简单裁剪方法：方法：用点阵字符的掩膜或矢量字符的网格大小作为字符的用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框，若该包围框在窗口内，则显示字符；否则，包围框，若该包围框在窗口内，则显示字符；否则，不予显示。不予显示。4.4.精确裁剪精确裁剪方法：方法：对于点阵字符，判断组成其笔画的每个像素点是否位对于点阵字符，判断组成其笔画的每个像素点是否位于窗口内。于窗口内。对于矢量字符，对组成其笔画的每条线段进行裁剪。对于矢量字符，对组成其笔画的每条线段进行裁剪。