第4章二维图形变换.ppt

《第4章二维图形变换.ppt》由会员分享，可在线阅读，更多相关《第4章二维图形变换.ppt（91页珍藏版）》请在课桌文档上搜索。

1、1,第4章 二维变换及二维观察,2,4.5 二维图形变换,一、图形变换基本概念 1、定义 即对原图形进行平移、旋转、缩小或放大等变换操作。在计算机图形显示或绘图输入过程中，往往需要对图形指定部分的形状、尺寸大小及显示方向进行修改，以达到改变整幅图形的目的，这就需要对图形进行平移、旋转、缩小或放大等变换操作。因此，图形变换是计算机绘图基本技术之一，利用它可以用一些很简单的图组合成相当复杂的图，可以把用户坐标系下的图形变换到设备坐标系下。利用图形变换还可以实现二维图形和三维图形之间转换，甚至还可以把静态图形变为动态图形，从而实现景物画面的动态显示，下面主要讨论二维图形变换。,3,2、图形变换分类

2、图形变换有两种形式：视象变换:图形不动，而坐标系变动，即变换前与变换后的图形是针对不同的坐标而言的，也称之为坐标模式 几何变换:另一种是坐标系不动，而图形改变，即变换前与变换后的坐标值是针对同一坐标系而言的，也称之为图形模式变换，实际应用中后种图形变换更具有实际意义，我们讨论的图形变换主要是属于后一种变换,4,二、二维图形几何变换的基本原理,1几何变换 在计算机绘图应用中，经常要实现从一个几何图形到另一个几何图形的变换。例如，将图沿某一方向平移一段距离；将图形旋转一定的角度；或将图形放大；反之把图形缩小等等。这些图形变换的效果虽然各不相同，本质上却都是依照一定的规则，将一个几何图形的点都变为另

3、一个几何图形的确定的点，这种变换过程称为几何变换。几何变换的规则是可以用函数来表示的。由于一个二维图形可以分解成点、直线、曲线。把曲线离散化，它可以用一串短直线段来逼近；而直线段可以是一系列点的集合，因此点是构成图形的基本几何元素之一。我们先来讨论点的几何变换的函数表示。,5,二维平面图形的几何变换是指在不改变图形连线次序的情况下，对一个平面点集进行的线性变换。二维平面图形的轮廓线，不论是由直线段组成（多边形），还是由曲线段组成，都可以用它的轮廓线上顺序排列的平面点集来描述，例如长方形ABCD，是由四个角点A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4）顺序连接而成，为了

4、使画出的图形是闭合的，首尾两点必须连接。,6,二维平面图形变换的结果有两种，一是使图形产生位置的改变；另一种是使图形产生变形，例如把图形放大。对二维图形进行几何变形有五种基本变换形式，它们是：平移、旋转、比例、对称和错切。,7,2基本几何变换的解析表示（l）平移变换 平面上一点P（x，y），如果在X轴方向的平移增量为tx，在Y轴方向平移增量为ty时，则平移后所得新点P(x，y)坐标表达式为：x=x+tx，y=y+ty 我们把这一变换称为平移变换。如果对一图形的每个点都进行上述变换，即可得到该图形的平移变换。实际上，直线的平移变换，可以通过对其定义端点的平移变换来实现，对于其它类型的变换这种处理

5、方法也是可行的。平移变换只改变图形的位置，不改变图形的大小和形状,ty,tx,8,（2）比例变换 一个图形中的坐标点（x，y），若在X轴方向有一个比例系数Sx，在Y轴方向有一个比例系数Sy，则该图形的新坐标点（x，y）的表达式为 x=xSx y=ySy；这一变换称为比例变换。比例变换不仅改变图形的位置，而且改变图形的大小,9,（3）旋转变换 若图形中的坐标点（x，y）绕坐标原点逆时针旋转一个角度，则该点变换后的新坐标（x，y）与交换前的坐标(x，y)的关系为：x=xcos-ysiny=xsin+ycos 旋转变换只能改变图形的方位，而图形的大小和形状不变，,10,（4）对称变换如果经过变换后所

6、得到的图形与变换前的图形关于X坐标轴是对称的，则称此变换为关于X轴的对称变换。经过这一变换后的坐标点（x，y）与变换前的对应坐标点（x，y）的关系为：x=x，y=-y 与此类似，若变换前后的图形关于Y轴对称，则称为关于Y轴的对称变换。这一变换前后点的坐标间的关系：x=-x，y=y当图形对X轴和Y轴都进行对称变换时，即得相对于原点的中心对称变换。这一变换前后点的坐标之间的关系为：x=-x，y=-y对称变换只改变图形方位，不改变其形状和大小。,11,12,（5）错切变换如果变换前坐标点（x，y）与变换后对应的新坐标点（x，y）的关系为：x=x+cy，y=y我们称这一变换为沿X轴的错切变换，式中c为

7、错切系数与此类似，若变换前后对应点的坐标关系为：x=x，y=y+bx 则称此变换为沿Y轴的错切变换，其中b为错切系数。错切变换不仅改变图形的形状，而且改变图形的方位，但图形中的平行关系不变，,13,一般把上述变换统称为基本的图形变换，绝大部分复杂的图形变换都可以通过这些基本交换的适当组合来实现。,14,二、几何变换的矩阵表示形式,1.变换矩阵任何一个复杂图形都是由任意多个有序点集连线而成。在解析几何学中。在二维空间内，平面上的点可以用一行两列矩阵x y或两行一列矩阵来表示。由此，一个由n个点的坐标组成的复杂图形可以用n2阶矩阵表示：,这种图形的表示法称为二维图形的矩阵表示法。,15,由此可知，

8、图形的变换可用矩阵运算来实现。具体说就是由构成图形的点集的矩阵与T=矩阵乘法运算，即我们称T=为二维图形变换矩阵，其中点集中任意一点（x，y）变换后坐标为：,16,这是我们熟悉的关于直角坐标变换因子。由上式可知，变换矩阵 中各元素决定着图形各种不同变换。,17,2二维基本变换的矩阵表示（1）比例变换 若令变换矩阵 则写成矩阵形式为：,若取a=3 d=1 对点（2，3）做变换,则 可以看出，a1，d=1，变换后图形沿X方向放大，显然，当01时，则使图形沿Y方向放大,18,a1，d=1，变换后图形沿X方向放大,当a=1，d1时，则使图形沿Y方向放大,19,若取a=1，d=0，图形沿Y方向压缩成线段

9、，如下图所示当a=1，d=1变换后图形没有变化，称这种变换矩阵为恒等矩阵。,20,若取a=d=1.5对下图中（a）矩阵1 2 3 4做变换，则各点在X，Y两个方向产生相等的比例变换，即变换后图形和变换前图形相似，相似中心为坐标原点。若ad时，使图形在X和Y两个方向产生不相等比例变换。下图(b)是a=2,d=1.5时对(a)中矩阵1234变换结果。图(c)是取a=2,d=0.5对矩阵1234变换结果，变换后图形在X方向放大，在Y方向缩小。,21,（2）对称变换,令变换矩阵T 中a=-1,d=1,即 使图形对Y轴对称例如：如下图所示,22,当a=1，d=1时，图形对X轴对称即,当 时，图形对+45

10、度线对称 当 时，图形45度线对称,图形对+45度线对称,图形对-45度线对称,23,（3）错切变换 当变换矩阵中的a=d=1，b与c中一个为零，另一个为正 数或负数时，即，它对图形的作用是使图 形产生沿一个坐标方向错切。由此可见，点的X坐标不变。y=kx+y，即在原来坐标上加上kx，即沿+Y方向移动kx值。点（0，0）则是不移动的。K是一个常数，所以tg=kx/x=k，即平行X轴的线段对X轴倾斜角度。=45度时，k=1。,24,例如：由下图可见，图形沿+Y方向错切，这是对在第一象限内的点而言。当 时，它使第一象限内图形沿+X方向错切,第一像限内图形沿+Y方向错切,第一像限内图形沿+X方向错切

11、,25,（4）旋转变换 旋转变换是指坐标轴不动，点或图形绕坐标原点旋转角，以逆时针方向取正值。如下图所示，其变换矩阵则,26,逆时钟旋转=90度时，变换矩阵顺时针旋转=-90度时，=180度时，下图是矩阵旋转30度的情况，其坐标变换如下：,27,三、二维图形齐次坐标矩阵变换1、齐次坐标与平移变换前面四种变换都可以通过变换矩阵来实现，那么它是否适合于平移变换呢？若实现平移变换，变换前后的坐标必须满足下面的关系：这里tx，ty是平移量，应为常数，但是应用上述的变换矩阵对点进行变换：,28,而这里的cy，bx均非常量，因此用原来的22的变换矩阵是无法实现平移变换的，我们把22矩阵扩充为32矩阵，即令

12、：但这样又带来新的问题，二维图形的点集矩阵是n2阶的，而变换矩阵是32阶的，根据矩阵乘法规则，它们是无法相乘的。为此，我们把点向量也作扩充，将 扩展为,即把点集矩阵扩充为n3阶矩阵。这样，点集矩阵与变换矩阵即可以进行乘法运算：,29,对点进行平移变换：对点进行平移变换：这里L，m分别为x，y方向的平移量。为使二维变换矩阵具有更多的功能，可将32变换矩阵进一步扩充成33阶矩阵，即：则平移变换矩阵为：,30,对点进行平移变换：,31,例：设l=20，m=20，对下图中的字母T做平移变换得：,32,如上讨论，在平移变换中，我们将 扩充为，实际上是由二维向量变为三维向量，但 可以看作是z=1平面上的点

13、，也就是说，经此扩充后，图形落在了z=1的平面上，它对图形的形状没有影响。这种用三维向量表示二维向量的方法叫做齐次坐标法。进一步推广，用n+1维向量表示n维向量的方法称之为齐次坐标法。,33,2二维图形齐次坐标矩阵变换对于前面介绍基本变换可用二维图形齐次坐标变换矩阵一般表达式这33矩阵中各元素功能一共可分成四块，即 这个22子矩阵可以实现图形的比例、对称、错切、旋转等基本变换；可以实现图形平移变换；可以实现图形透视变换；可以实现图形全比例变换。,34,例如，用矩阵 对图形进行变换：当s1时，图形产生整体比例缩小。当s=1时，图形大小不变。由此表明，齐次坐标的应用，扩大了变换矩阵功能，只要对矩阵

14、中有关元素赋以不同的 值，即可达到预期变换目的。,35,36,对称变换,37,四、组合变换 上述的五种二维图形几何变换是二维图形几何变换中的最基本的几何变换，在进行这些基本的几何变换时，我们给定了一些特定的约束条件，如:旋转变换是指绕坐标原点的旋转，比例变换是关于坐标原点的放大或缩小等等，因而是几何变换中的一些简单情形。实际中的二维图形作几何变换时要复杂得多，往往是多种基本的几何变换复合而成的，因此我们把由若干个基本的几何变换复合而成为一个几何变换的过程称为组合变换也称为几何变换的级联。,38,1绕任意点旋转变换平面图形绕任意点p（xp，yp）旋转角，需要通过以下几个步骤来实现：（1）将旋转中

15、心平移到原点，变换矩阵为：,Y,p（xp，yp）,39,（2）将图形绕坐标系原点旋转角，变换矩阵为：,Y,X,（3）将旋转中心平移回到原来位置，变换矩阵为：,40,因此，绕任意点p的旋转变换矩阵为：显然，当xp=0，yp=0时，即为对原点的旋转变换矩阵。,41,2对任意点做比例变换 设任意一点p（xp，yp），作比例变换需通过以下步骤来完成：（1）将P点移到坐标原点，变换矩阵为：,Y,X,42,（2）作关于原点的比例变换，变换矩阵为：（3）对原点作反平移变换，移到原来的位置：,Y,X,43,对任意点P作比例变换，其变换矩阵为,44,3对任意直线对称变换如下图所示，设任意直线的方程为：Ax+By

16、+C=0，直线在X轴和Y轴上的截矩分别C/A和C/B，直线与X轴的夹角为，=arctg(A/B)。,Y,X,-C/B,-C/A,45,对任意直线的对称变换由以下几个步骤来完成：（1）平移直线，使其通过原点（可以沿X向和Y向平移，这里沿X向将直线平移到原点），变换矩阵为：,Y,X,46,（2）绕原点旋转，使直线与某坐标轴重合（这里以与X轴重合为例），变换矩阵如下：,Y,X,47,（3）对坐标轴对称变换（这里是对X轴），其变换矩阵为：,Y,X,48,（4）绕原点旋转，使直线回到原来与X轴成角的位置，变换矩阵为：,Y,X,49,（5）平移直线，使其回到原来的位置，变换矩阵为：,X,50,通过以上五个

17、步骤，即可实现图形对任意直线的对称变换，其组合变换矩阵如下：,51,综合上述，复杂变换是通过基本变换组合而成的，由于矩阵乘法不适用于交换律，即，因此，组合变换顺序不能颠倒，顺序不同，则变换结果不同。,52,例43 各顶点坐标A（3，0），B（4，2），C（6，0）使其绕原点转90度，再向X方向平移2，Y方向平移1。因=90O 则变换矩阵：,53,如果先进行平移变换，再进行旋转变换，则矩阵为：,由于变换顺序不同，其结果也不同。,54,例44 设有一三角形ABC，其三个顶点坐标为A（2，4），B（2，2），C（5，2），求对于直线2x+3y+3=0的对称变换后,其中=arcty(-A/B)=arc

18、ty(2/3)33041,55,变换后的如下图所示。,56,4.6 二维图像裁剪一、概述1、定义 为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口之内，而将窗口之外部“剪掉”，这个处理过程叫做裁剪。裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定计算方法实现的。裁剪就是将指定窗口作为图形边界，从一幅大的画面中抽取所需的具体信息，以显示某一局部画面或视图。,第四章 二维图形生成和变换技术 4.1 基本绘图元素 4.2 直线段的生成 4.3 曲线的生成 4.4 区域填充 4.5 二维图形变换 4.6 二维图像剪裁,

19、57,在实际应用中，经常会遇到一些大而复杂的图形，如集成电路布线图、建筑结构图、地形地貌图等。由于显示屏幕的尺寸及其分辨率限制，这样复杂的图形往往不能全部显示出来，即使将它们采用比例变换后全部显示在同一屏幕上，也只能表现一个大致轮廓，并且图形拥挤不清。因此对复杂图形，一般只能显示它的局部内容，我们在研究某复杂图形时，往往对某特定画面感兴趣，在这种情况下，我们将这一特定区域放大后显示出来，而把周围画面部分全部擦除，这样可清晰地观察其细节部分,58,我们假定裁剪是针对用户坐标中窗口边界进行的，裁剪完成后，再把窗口内图形映射到视区。所以裁剪的目的是显示可见点和可见部分，删除视区外的部分。例如，下图（

20、a）定义了一个矩形窗口ABCD，窗口内会有EFG的一部分，而直线段EG、FG都有一部分在窗口外。然后将落在窗口内这部分图形传送到视图区内显示，如图（b）所示。此时，窗口外那部分被裁剪掉。,59,二、窗口区和视图区用户域：在进行图形设计时，图形输出程序中的图形都 是在用户坐标系中定义的。此坐标系拥有的区 域在理论上是无限的，在使用时我们可以把它 当作是一个有限的矩形区，即用户域。窗口区：用户可以在用户域中指定任意区域输出到屏幕 上，这个指定区域称为窗口区，简称窗口（Window）如图所示的矩形 ABCD 就是我们定义的一个窗口。我们可用该矩形的左下角和右上角两点坐标来定义其大小和位置。因此，定义

21、窗口的目的就是选取用户所定义的图形中需要观察的那一部分图形。,窗口区，用左下角和右上角来定义,60,视图区：简称视图（Viewport），是在屏幕上定义的一个小于或等于屏幕区域一个矩形块。同样也是用该矩形左下角和右上角两点坐标来定义大小和位置。视图区可用来显示某一窗口内图形。所以人们利用窗口来选择需要观察那一部分图形，而利用视图区来指定这一部分图形在屏幕上显示位置。下图表示窗口与视图关系。,屏幕,视图区,窗口区,61,在交互式图形设计中，通常把一个屏幕分为几个视图区，每个视图区都有各自用途，如图所示，视图区1为用户图形区，视图区2为命令区，视图区3是信息区。同时用户图形区还可分为各个子区，以满

22、足用户显示多层窗口的需要。由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息送到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备（屏幕）坐标系的坐标值，这个变换称窗口视图变换。,62,如图所示，设在用户坐标系下定义的窗口为：左下角点坐标（Wxl，Wyb），右上角点坐标（Wxr，Wyt）；在设备坐标系中定义的视区为：左下角点坐标（Vxl，Vyb），右上角点坐标（Vxr，Vyt）。,63,由图可知：由（4-24）式得窗口中一点P(xW,yW)变换到视区中对应的点V(xV,yV)二者之间的关系为：设:,64,则（4.25）式可写成：写成矩阵形式：,65,由此可见窗口视图变换

23、是比例变换和平移变换的组合变换。先进行平移变换将窗口左下角坐标移到用户坐标原点，接着进行比例变换，使窗口中各点比例变换到设备坐标系（屏幕）中，最后再作平移交换，使原点移到视图左下角。通过窗口视图变换，我们就实现了将用户坐标系中窗口区中任意一点转换成设备坐标系中屏幕视图区中一点变换，从而就可以把实际物体图形显示在显示器上，但要注意：为了使经过窗口视图变换后的图形在视图区中输出时不产生失真现象，在定义窗口和视图时，必须保证使窗口和视图区高度和宽度之间比例相同。,66,三、直线段裁剪 1、点的剪裁 裁剪的过程就是对窗口内每个图形元素都得划分一下可见部分和不可见部分。裁剪可以在各种不同类型的图形元素上

24、实现，如点、向量、直线段、字符以及多边形等。裁剪算法中最基本的情况是点的裁剪。判断某一点P（x，y）是否可见，可以利用下列一对不等式来确定该点是否在窗口范围内。如图所示:Wxl xW Wxr Wyb yW Wyt 满足上述两个不等式的点即在窗口内，属于可见的点，应该保留；反之，则该点不可见，应予舍弃。,Wyt,Wyb,Wxl,Wxr,67,2、直线段与窗口关系 点的裁剪虽然很简单，但要把所有的图形元素转换成点，然后用上述不等式判别是否可见，那是很不现实的。这样的裁剪过程所在时间就会过长，不经济。因此，要求一种适合较大的图形元素，比较有效的裁剪方法。直线段是组成一切其它图形的基础。任何图形（包括

25、曲线、字符和多边形），一般都能用不同直线段组合形成 对于任意一条直线段，它相对于一个已定义的窗口位置关系不外乎有四种可能，如图所示。,直线段完全被排斥在窗口的边框之外,直线段完全被包含在窗口之内,直线段和窗口的一条边框相交，使得该直线段被相交点分成两截，其中的一个截段落在窗口之内，而另一个截段留在窗口之外,直线段贯穿整个窗口，这样，直线段就与窗口的两条边框相交，使得原直线段被分成三个截段，其中只能有一个截段落在窗口内，而另外的两段都处于窗口之外，,68,归纳以上四种情况，可以得出这样一个结论：对于任意一条直线段，它要么被完全排斥在窗口之外，如上述的情况（1）；要么在窗口内留下一个可见段，并且只

26、能有一个可见段,如上所述的情况（2）、（3）和（4）。因为一条直线段可以由它的两个端点来唯一地确定，所以，要确定一条直线段上位于窗口以内的可见段，仅需求得它的两个可见端点就行了。下面我们介绍几种直线剪裁法,69,3编码裁剪法（1）编码规则 这一方法是由库恩和萨瑟兰德（Cohen和Sutherland）提出的，该方法是把包含窗口的平面区域沿窗口的四条边线分成九个区域.每个区域用一个四位代码来表示，代码中每一位分别是0或1，是按照窗口边线来确定的，下面给出编码规则，其中 最右边的位是第一位，依次第 二、三、四位。第一位置 l:该端点位于窗口左侧 第二位置 l:该端点位于窗口右侧 第三位置 1:该端

27、点位于窗口下面 第四位置 l:该端点位于窗口上面 否则，相应位置置0。,70,由编码规则可知，若线段两端点编码均为零，则两点均在窗口内，线段完全可见。因此，要判断两端点线段与窗口对应关系，可用两个端点编码逐位取逻辑“与”，若线段两端点逻辑“与”不为0，必在窗口外，根据图形中直线两端点p1，p2按其所在区域赋予相应代码，以C1和C2表示，然后再根据端点对直线进行可见和不可见判断（2）算法步骤下面给出直线段裁剪编码算法步骤：当两端点P1(x1,y1)和P2(x2,y2)，在区域0000中，即满足点的裁剪不等式。Wxl(x1,x2)Wxr Wyb(y1,y2)Wyt则两端点代码C1C20 表示均在窗

28、口内，应全部保留,71,当两个端点在窗口边线外的同侧位置，则它们的四位代码中，有一相同位，同时为“1”，显然两个端点代码的逻辑乘不等于零。即C1C2 0。此检查判断直线在窗口外，应全部舍弃。如果直线两端点不符合上述两种情况，不能简单地全部保留或全部舍弃直线时，则需计算出直线与窗口边线的交点，将直线分段后继续进行检查判断。这样可以逐段地舍弃位于窗口外的线段，保留剩在窗口内的线段。,72,如图所示，用编码裁剪算法对 P1P2线段裁剪，可以在C点分割，对P2C，CP1进行判别，舍弃P2C，再分割CP1于D点，对CD，DP1作判别，舍弃CD，而DP1全部位于窗口内，算法即告结束。应该指出的是，分割线段

29、是从C点还是D点开始，这是难以确定的，因此只能随机的，但是最后结果是相同的。,73,（3）交点的求法下面介绍交点的求法。设直线的两端点坐标为P1（x1，y1）和P2（x2，y2）如图所示，直线与窗口四条边线的交点坐标，可分别由下列公式确定：（利用相似直角三角形比例关系）左交点:右交点:,74,下交点：上交点：,75,4.矢量裁剪法(略),76,5中点分割裁剪法上面介绍两种方法都要计算直线段与窗口边界交点，这不可避免地要进行大量乘除运算，势必会降低程序执行效率。而中点分割裁剪却只需用到加法和除2运算，而除2在计算机中可以简单地用右移一位来完成，从而提高算法的效率。（1）基本思想 中点分割算法基本

30、思想是：分别寻找直线段两个端点各自对应最远的可见点，只要该线段能在窗口内留下一个可见段，那么这个最远的可见点只有两种选择：要么是直线段一个相应端点；要么是在不断中点再分过程中产生的某个子段的中点。,77,图中直线段e说明，该线段处于窗口内的可见段部分是线段S1S2,S1和S2是可见段的两个端点，其中S2是距原线段端点P1最远的可见点；同样，S1是距原线段端点P2最远的可见点。下面，我们以找出直线段P1P2上离P1点最远的可见点为例，来对中点再分裁减算法加以说明。,78,算法步骤如下：（l）检验直线段P1P2是否完全被排斥在窗口之外。如果是，过程结束且无输出线段（如图中的线段b）；否则继续执行下

31、一步。（2）检验点P2是否可见。如果是，则P2点就是离P1点最远的可见点，过程结束（图中的线段a）。如果P2点是不可见的（如图中的线段c或线段d），那么继续执行下一步。,79,（3）分割直线段P1P2于中点Pm（这是为了估计离P1点最远的可见点,把它简单地取作中点）。如果线段PmP2被完全排斥在窗口之外，那么原估计还不足（如图 4.79 中的线段d），便以线段P1Pm作为新的P1P2线段从算法的第一步重新开始执行。反之，则以线段PmP2为新的线段P1P2（如图的线段c）从算法的第一步重新开始执行。,反复执行上述三步，直至找到离P1点最远的可见点为止。,分割直线段P1P2于中点Pm,线段PmP2

32、被完全排斥在窗口之外,以线段P1Pm作为新的P1P2再取中点,线段PmP2没有被完全排斥在窗口之外,以线段PmP2作为新的P1P2再取中点,80,这个过程确定了距离P1点最远的可见点。然后对调该线段的两个端点，以线段P2P1为新的P1P2线段，重新开始实施该算法过程，就可以确定出距离P2点最远的可见点。这样，位于窗口内可见段的两个可见端点就确定了。从这个算法中我们可以看到，整个裁剪过程总是在执行第一步或第二步时结束。这种结果表明：被裁剪的线段要么完全处于窗口之外而被排除掉；要么能在窗口内得到一个距对应端点最远的可见点，这个可见点可能是原直线段的一个端点，也可能是线段在被不断地中点再分过程中，最

33、终得到的刚好和窗口边框相重的那个中点。这里要注意的是：在判断中点和窗口边框相重时，一般不需要坐标值一定相等，也不大可能，只要在精度许可前提下，给出一个误差允许范围。,81,三、多边形裁剪1、概述 前面我们讨论了直线段剪裁，多边形裁剪是以线段裁剪为基础，但又不同于线段的裁剪。多边形裁剪要比一条线段裁剪复杂得多。如图所示，用一个矩形窗口去裁剪多边形将会遇到各种不同情况。裁剪多边形要解决两个问题。其一是一个完整的封闭多边形经裁剪后一般不再是封闭的，需要用窗口边界适当部分来封闭它。其二是矩形窗口的四个角点在裁剪中是否要与其它交点连线。由于这两个问题使得我们不能简单地应用直线段裁剪方法。而需要去研究适合

34、多边形裁剪特点的算法。,82,一个完整的多边形被裁剪成两个独立的多边形,一个凹多边形被裁剪成几个小多边形,多边形G经矩形窗口裁剪后出现G1和G2两个多边形,83,2、多边形剪裁原理 多边形裁剪方法很多，例如逐边裁剪法，双边裁剪法，分区编码裁剪法等，这里仅介绍逐边裁剪法。逐边裁剪法是萨瑟兰德（I.E.Sutherland）和霍德曼（Hodglhan）在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。算法的依据是：简单地通过对单一边或面的裁剪实现对多边形的裁剪。现讨论窗口为矩形的裁剪，先用窗口的第一条边界对要裁剪的多边形进行裁剪，去掉窗口外的图形，保留窗口内的图形，形成一个新的多边形。然

35、后，再用第二条边界对这个新的多边形进行裁剪，再次生成一个新的多边形。依次用第三、第四条边界重复进行裁剪，形成了最后裁剪出来的多边形，整个裁剪过程结束,84,先用窗口的第一条边界对要裁剪的多边形进行裁剪，去掉窗口外的图形，保留窗口内的图形,再用窗口的第二条边界对要裁剪的多边形进行裁剪，去掉窗口外的图形，保留窗口内的图形,85,逐边裁剪法实质是用窗口四条边分别对多边形一边进行剪取。剪取后结果是输出一个多边形的顶点表。由于在剪取过程中，实际是多边形的每一边与窗口的一边界进行比较，从而确定它们的位置关系。假定取多边形顶点表中的某一点Pi作为一边的终点，表中位于前面的一点Pi-1作为该边的起点,则边Pi

36、1 Pi被窗口的一边界剪取后输出一个或两个顶点，或者不输出顶点，若边Pi-1 Pi完全可见，则输点Pi，需要注意的是这里不必再输出边的起点Pi-1。因为输出顶点表中的点是依序处理的，Pi-1作为前一条边的终点输出。若边Pi-1 Pi完全不可见，则无输出。若边Pi-1Pi部分可见，则此边可能进入或离开窗口内部区域，若离开可见区，则必须计算并输出此边与窗口边界的交点。若进入可见区，同样需要计算并输出这一边与窗口边界的交点，由于此时边的终点Pi可见，故应输出点Pi。,86,起点,终点,边P4P5完全可见，则输点P5,边P6P7完全不可见，则无输出,边部分可见，则需计算此边与窗口边界的交点,87,对于

37、多边形的第一个顶点P1只需判断它是否可见。若可见，则输出并作为起点P1。若不可见，则无输出。但仍需作为点P1保存，以便对其它边进行处理。对于多边形的最后一条边PnP1需要另作处理。这时需将顶点表中第一点记为F，于是最后一边变为PnF，这样就可同其它边一样进行处理。确定点可见性和求多边形的边和窗口边界交点，可采取前面所述各种方法。例如编码裁剪法。由于在这一剪取方法中，被裁取多边形的每一边是依次处理的，故只需作少许变动，用同一子程序可以处理多边形的每一边。需要注意的是最后一个顶点需要作特殊处理。逐边剪取算法是一个通用的剪取算法，任一多边形无论是凸多边形还是凹多边形均可用这一算法进行剪取。这一算法简

38、单，易于程序实现，但计算量较大，需要比较大的存贮区来存放剪取过程中待剪取的多边形。,88,四、其它类型图形裁剪 1曲线的裁剪 绘制曲线通常采取用直线段逼近的办法，所以曲线的剪裁可用线段的剪裁来解决。由于逼近时总是将线段取得很短，所以，为了节省计算时间，可以免去计算剪裁的交点，只要线段端点中至少有一个在窗外，就将该线段略去不画，达到剪裁的结果。这当然是一种近似的办法，然而也能保证一定的精度，且提高了裁剪的效率。,89,2.字符裁剪 把每个字符看作是不可分割的整体，对每一个字符串就可用逐字裁剪的方法，把每个字符用一矩形（字符框）包围起来（见图），然后检测该字符框中的某一点（如顶点或中心点）的可见性，把该点与窗口进行比较，如果在窗口内，就显示该字符，否则就舍弃不显示，另外也可以用整个字符框的界线或其对角线与窗口进行比较，当字符框或对角线完全在窗口内时才显示该字符，不过用字符框顶点或用字符框界线（或对角线）裁剪的两种方法，只有当窗口边与字符框界线平行时才等效，否则必须以字符框界进行裁剪。,90,裁剪字符串的一种粗略方法，是把一个字符串作为不可分割的整体来处理，用一个字符串框封闭起来（见图），检测这个字符串框上的某一点、界线的对角线或者界线本身的可见性，若在窗口内，就显示整串字符，否则整串字符就不显示。,91,谢谢大家！,