计算机图形学-实验五 直线和多边形的裁剪【借鉴实操】

1、贵州大学实验报告学院： 计算机科学与信息学院 专业：软件工程 班级： 102班姓名学号实验组实验时间指导教师成绩实验项目名称实验五 直线和多边形的裁剪实验目的掌握直线段的裁剪算法以及多边形的裁剪算法实验要求熟练掌握直线段的裁剪算法以及多边形的裁剪算法的基本原理，并编写测试代码进行实验。实验原理Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围的，8个方向以4 bit的二进制数进行编码。右图所示的编码方法将窗口及其邻域分为5个区域： 内域：区域(0000)。 上域：区域(1001, 1000, 1010)。 下域：区域(0101, 0100, 0110)。 左域：区域(

2、1001, 0001, 0101)。 右域：区域(1010, 0010, 0110)。 当线段的两个端点的编码的逻辑“与”非零时 ，线段为显然不可见的，对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右；Cohen-Sutherland直线剪裁算法的算法思想是：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断

3、，采用如下编码方法：由窗口四条边所在直线把二维平面分成9个区域(右图)，每个区域赋予一个四位编码：CtCbCrCl（上下右左）；直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。各位编码含义：上：if yymax，Ct=1，else, 0;下：if yxmax，Cr=1，else, 0;左：if xxmax，Cl=1，else, 0;对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右； 如果两端点的编码均为0000，表示直线在窗口内。 如果两端点的编码相与不为0000，表示直线在窗口外。 如果两端点的编码不全为0000，但相与为00

4、00，则该直线部分可见，需计算直线与窗口的交点，确定哪一部分可见。裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口内，应取之。若按位与运算code1&code20，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。算法分析：本算法的优点在于简单，易于实现。

5、用编码方法可快速判断线段的完全可见和显然不可见，他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。本算法对于其他形状的窗口是否同样有效就值得讨论了，这也证明了在图形算法中，没有几个是对大多数情况有效的。特别适用二种情形：大窗口场合（线段大多数为完全可见）；窗口特别小场合(线段大多数为完全不可见。光标拾取图形，光标看作小的裁剪窗口)。多边形裁剪算法：Sutherland-Hodgema算法算法原理：通过对单一边或面的裁剪来实现多边形的裁剪分割处理策略：将多边形关于矩形窗口的裁剪分解为多边

6、形关于窗口四边所在直线的裁剪。一次用窗口的一条边裁剪多边形。流水线过程(左上右下)：前边的结果是后边的输入。亦称逐边裁剪算法。可见一侧PS全部可见输出点P可见一侧PS全部不可见无输出点可见一侧PS离开可见一侧输出点11可见一侧PS进入可见一侧，输出点1和点P1算法的每一次输出（包括中间结果）都是一个多边形的顶点表，且所有顶点均位于相应窗口裁剪边或面的可见一侧。由于多边形的每一条边需要与裁剪边或面分别进行比较，因此只需要讨论单条边和单个裁剪边或面之间可能的位置关系。假设S，P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与裁剪边或面之间只有4种可能的关系。如下图：由上可见，每

7、一次将多边形的边与裁剪边或面比较后，输出一个或两个顶点，也可能无输出点。如果SP边完全可见，则输出P点，不必输出起点S，因为顶点是按顺序处理的，S是作为前一边的终点输出的。如果SP边完全不可见，则无输出。如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。 如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面交点。如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。对于多边形的第一个顶点，只需判断其可见性。如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。对于最后一条边PnP1，其处理方法是：标志第一顶点为F，

8、这样最后一条边则为PnF，可与其他边作相同的处理。实现方法：设置二个表：输入顶点表：用于存放被裁剪多边形的顶点p1-pm。输出顶点表：用于存放裁剪过程中及结果的顶点q1-qn。输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪算法分析：对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形

9、。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。实验环境硬件平台：PC机软 件：Windows7平台，eclipse集成开发环境，java编程语言。实验步骤1. 掌握算法原理；2. 依据算法，编写源程序并进行调试；3. 对运行结果进行保存与分析；4. 把源程序以文件的形式提交；5. 按格式书写实验报告。实验内容一、直线段裁剪算法的核心代码为：计算（x,y）点的编码的方法：private int encode(double x, double y) / 求（x,y）点的编码int code = 0;if (x XR) / 点位于矩形的右边code |= RIGHT; / 并

10、上右边的编码0010 else if (y YT) / 点位于矩形的上边code |= TOP; / 并上上边的编码1000return code;直线段裁剪的方法：private void lineCut(double x1, double y1, double x2, double y2) / 直线的起点(x1,y1)和终点(x2,y2)double x = 0, y = 0;int code1, code2, code;code1 = this.encode(x1, y1);/ 起点的编码code2 = this.encode(x2, y2);/ 终点的编码while (code1 !=

11、 0 | code2 != 0) if (code1 & code2) != 0) / 两端点的编码相与不为0，表示直线在窗口外return;if (code1 != 0) code = code1; else code = code2;if (LEFT & code) != 0) / 直线的端点与矩形窗口的左边编码相与！=0x = XL;y = y1 + (y2 - y1) * (XL - x1) / (x2 - x1);/ 求直线与矩形窗口的左边界的交点 else if (RIGHT & code) != 0) / 直线的端点与矩形窗口的右边编码相与！=0x = XR;y = y1 + (

12、y2 - y1) * (XR - x1) / (x2 - x1);/ 求直线与矩形窗口的右边界的交点 else if (BOTTOM & code) != 0) / 直线的端点与矩形窗口的下边编码相与！=0y = YB;x = x1 + (x2 - x1) * (YB - y1) / (y2 - y1);/ 求直线与矩形窗口的下边界的交点 else if (TOP & code) != 0) / 直线的端点与矩形窗口的上边编码相与！=0y = YT;x = x1 + (x2 - x1) * (YT - y1) / (y2 - y1);/ 直线的端点与矩形窗口的上/ 边编码相与！=0if (co

13、de = code1) x1 = x;y1 = y;code1 = encode(x, y); else x2 = x;y2 = y;code2 = encode(x, y);g.drawLine(int) (x1 + 0.5), (int) (y1 + 0.5), (int) (x2 + 0.5),(int) (y2 + 0.5);二、多边形裁剪的核心代码为：通过点集画直线或者多边形：private void draw() /通过点集画直线或者多边形for (int i = 1; i points.size(); i+) Point p1 = new Point();p1 = points.

14、get(i);int x1 = (int) p1.getX();int y1 = (int) p1.getY();Point p2 = new Point();p2 = points.get(i - 1);int x2 = (int) p2.getX();int y2 = (int) p2.getY();g.drawLine(x1, y1, x2, y2);多边形的裁剪函数：private Point cutPicture(Point point, Point edge) / 剪裁函数，参数为（点集，边）Point intersectPoint = new Point20;/存放交点的集合fo

15、r (int j = 0; j 20; j+) intersectPointj = new Point();Point s = new Point();Point p = new Point();Point t = new Point();int i = 0;int length = point.length;s = pointlength - 1;for (int j = 0; j length; j+) p = pointj;if (inside(p, edge) / sp在窗口内，情况1if (inside(s, edge) intersectPointi = p;i += 1; els

16、e / s在窗口外，情况4t = intersect(s, p, edge);intersectPointi = t;i += 1;intersectPointi = p;i += 1; else if (inside(s, edge) / s在窗口内，p在窗口外，情况3t = intersect(s, p, edge);intersectPointi = t;i += 1;/ 情况2没有输出s = p;List tempList = new ArrayList();for (int k = 0; k i; k+) if (intersectPointk != null) Point pt =

17、 intersectPointk;tempList.add(pt);Point temp = new PointtempList.size();for (int j = 0; j tempList.size(); j+) tempj = new Point();tempj = tempList.get(j);intersectPoint = temp;return intersectPoint;判断点是否在裁剪边的可见侧：private boolean inside(Point point, Point edge) /判断点是否在裁剪边的可见侧/ 裁剪边为窗口下边if (edge0.y = e

18、dge1.y) & (edge0.x = edge0.y) return true;/ 裁剪边为窗口上边if (edge0.y = edge1.y) & (edge0.x edge1.x) if (point.y = edge0.y) return true;/ 裁剪边为窗口右边if (edge0.x = edge1.x) & (edge0.y edge1.y) if (point.x edge1.y) if (point.x = edge0.x) return true;return false;直线段与窗口边界求交：private Point intersect(Point s, Poin

19、t p, Point edge) /直线段与窗口边界求交，并返回交点Point t = new Point();if (edge0.y = edge1.y) / 水平裁剪边t.y = edge0.y;t.x = s.x + (edge0.y - s.y) * (p.x - s.x) / (p.y - s.y); else if (edge0.x = edge1.x) / 垂直裁剪边t.x = edge0.x;t.y = s.y + (edge0.x - s.x) * (p.y - s.y) / (p.x - s.x);return t;鼠标的监听类（内部类）：class MouseMonito

20、r extends MouseAdapter /通过鼠标的单击获取点，并画出直线或者多边形public void mouseClicked(MouseEvent e) points.add(e.getPoint();if (points.size() 1) draw();键盘的监听类（内部类）：class KeyMonitor extends KeyAdapter / 键盘控制public void keyPressed(KeyEvent e) switch (e.getKeyCode() case KeyEvent.VK_R:/ 清空画布和点集panel.repaint();points.r

21、emoveAll(points);break;case KeyEvent.VK_W:/对裁剪窗口的处理g.setColor(Color.RED);g.drawRect(XL, YB, XR - XL, YT - YB);/存放裁剪窗口的边top = new Point2;/ 存放裁剪窗口的上边top0 = new Point(XL, YB);top1 = new Point(XR, YB);right = new Point2;/存放裁剪窗口的右边right0 = new Point(XR, YB);right1 = new Point(XR, YT);bottom = new Point2;

22、/存放裁剪窗口的下边bottom0 = new Point(XR, YT);bottom1 = new Point(XL, YT);left = new Point2;/存放裁剪窗口的左边left0 = new Point(XL, YT);left1 = new Point(XL, YB);break;case KeyEvent.VK_A:/对直线段进行裁剪g.setColor(Color.GREEN);Point p1 = points.get(0);Point p2 = points.get(1);lineCut(p1.getX(), p1.getY(), p2.getX(), p2.ge

23、tY();break;case KeyEvent.VK_B:/对多边形进行裁剪source = new Pointpoints.size();/得到多边形的点for (int i = 0; i points.size(); i+) sourcei = points.get(i);g.setColor(Color.GREEN);wT = cutPicture(source, top);/得到多边形与裁剪窗口上边的交点wR = cutPicture(wT, right);/得到多边形与裁剪窗口右边的交点wB = cutPicture(wR, bottom);/得到多边形与裁剪窗口下边的交点wL = cutPicture(wB, left);/得到多边形与裁剪窗口左边的交点int length = wL.length;/ 得到剪裁后的顶点集合,并画出图形for (int j = 0; j