Weiler－Atherton任意多边形裁剪
Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。
一、Weiler－Atherton任意多边形裁剪算法描述：
在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。
裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称：
1、被裁剪多边形为主多边形，记为A；
2、裁剪窗口为裁剪多边形，记为B。
主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：
1、A∩B（交：属于A且属于B）；
2、A－B（差：属于A不属于B）；
3、B－A（差：属于B不属于A）；
4、A∪B(并：属于A或属于B，取反；即：不属于A且
不属于B)。
内裁剪即通常意义上的裁剪，取图元位于窗口之内的部
分，结果为A∩B。
外裁剪取图元位于窗口之外的部分，结果为A－B。
观察右图不难发现裁剪结果区域的边界由被裁剪多边形的
部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边
界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界，
或者反之。由于多边形构成一个封闭的区域，所以，如果被裁
剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：
一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e；
一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。
二、Weiler－Atherton任意多边形裁剪算法思想：
假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。
算法从被裁剪多边形的一个入点开始，碰到入点，沿着被裁剪多边形按顺时针方向搜集顶点序列；
而当遇到出点时，则沿着裁剪窗口按顺时针方向搜集顶点序列。
按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。
由于可能存在分裂的多边形，因此算法要考虑：将搜集过的入点的入点记号删去，以免重复跟踪。将所有的入点搜集完毕后算法结束。
三、Weiler－Atherton任意多边形裁剪算法步骤：
1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。
2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。
3、求出被裁剪多边形和裁剪窗口相交的所有交点，并给每个交点打上“入”、“出”标记。
然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ，并放入数组3中；
同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ，放入数组4中；
4、初始化输出数组Q，令数组Q为空。接着从数组3中寻找“入”点。
如果“入”点没找到，程序结束。
5、如果找到“入”点，则将“入”点放入S中暂存。
6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。
7、沿数组3顺序取顶点：
如果顶点不是“出点”，则将顶点录入到输出数组Q中，流程转第7步。
否则，流程转第8步。
8、沿数组4顺序取顶点：
如果顶点不是“入点”，则将顶点录入到输出数组Q中，流程转第8步。
否则，流程转第9步。
9、如果顶点不等于起始点S，流程转第6步，继续跟踪数组3。
否则，将数组Q输出；
流程转第4步，寻找可能存在的分裂多边形。
算法在第4步：满足“入”点没找到的条件时，算法结束。算法的生成过程见下图所示。
四、Weiler－Atherton任意多边形裁剪算法实现：
1、算法在实现中，需要用到六个数组，分别用来存放：被裁剪多边形、裁剪窗口、交点数组、插入交点后的被裁剪多边形、插入交点后的裁剪窗口、输出多边形。
2、由于交点具有“入”、“出”标记，因此凡与交点有关的数组都要采用结构数组类型：
struct point
{
double x；
double y；
int flag；
}交点数组，数组3，数组4；
标记flag有三种状态：
0：非交点；
1：“入”点；
-1：“出”点。
3、求交点时，利用被裁剪多边形的各边去对裁剪窗口的各边求交点：
for（被裁剪多边形的各边）
{
…；
for（裁剪窗口的各边）
{
求有效交点；放入交点数组；
…；
}
}
4、交点的顺序插入，意味着要对交点数组排序后再分别插入到数组1、数组2的相应位置上。
5、所谓找“入”点、“出”点，必须根据flag找寻满足条件的顶点位置。不光数组3中要找“入”点、“出”点，而且找到后还要转到数组4的相应顶点位置处。对数组4的处理也同上。这种处理在本算法中大量遇到。
五、Weiler－Atherton任意多边形裁剪算法演示：（略）
六、Weiler－Atherton任意多边形裁剪算法特点：
1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。
2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁，即保留窗口内的图形或保留窗口外的图形，因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。
3、裁剪思想新颖，方法简洁，裁剪一次完成，与裁剪窗口的边数无关。
七、Weiler－Atherton任意多边形裁剪算法小结：
前面介绍的是内裁算法，即保留裁剪窗口内的图形。而外裁算法（保留裁剪窗口外的图形）同内裁算法差不多。
外裁算法与内裁算法不同的是：
1、从被裁剪多边形的一个“出点”开始，碰到出点，沿着被裁剪多边形按顺时针方向搜集顶点序列；
2、而当遇到“入点”时，则沿着裁剪窗口按逆时针方向搜集顶点序列。
按上述规则，如此交替地沿着两个多边形的边线行进，直到回到起始点为止。这时，收集到的全部顶点序列就是裁剪所得的一个多边形。
由于可能存在分裂的多边形，因此算法要考虑：将搜集过的“出点”的出点记号删去，以免重复跟踪。将所有的出点搜集完毕后算法结束。
Weiler－Atherton算法的的设计思想很巧妙，裁剪是一次完成，不象Sutherland-Hodgman 多边形裁剪算法，每次只对裁剪窗口的一条边界及其延长线进行裁剪，如裁剪窗口有n条边，则要调用n次S-H算法后才能最后得出裁剪结果。
但Weiler－Atherton算法的编程实现比Sutherland-Hodgman算法稍难，主要难在入、出点的查寻以及跨数组搜索上。
Weiler－Atherton任意多边形裁剪 Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。 一、Weiler－Atherton任意多边形裁剪算法描述： 在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。 裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 1、被裁剪多边形为主多边形，记为A； 2、裁剪窗口为裁剪多边形，记为B。 主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域： 1、A∩B（交：属于A且属于B）； 2、A－B（差：属于A不属于B）； 3、B－A（差：属于B不属于A）； 4、A∪B(并：属于A或属于B，取反；即：不属于A且 不属于B)。 内裁剪即通常意义上的裁剪，取图元位于窗口之内的部 分，结果为A∩B。 外裁剪取图元位于窗口之外的部分，结果为A－B。 观察右图不难发现裁剪结果区域的边界由被裁剪多边形的 部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边 界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界， 或者反之。由于多边形构成一个封闭的区域，所以，如果被裁 剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类： 一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e； 一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。 二、Weiler－Atherton任意多边形裁剪算法思想：
实验：直线段的裁剪 姓名：龙泽学号：20141090068 指导教师：吴昊 实验内容：采用Liang-Barsky算法对直线段进行裁剪。 实验设计：本次实验采用的是Liang-Barsky算法，根据这个算法需先定义直线段的起点坐标（x1,y1），终点坐标（x2,y2），以及裁剪框(矩形)的左边界(wxl)，右边界(wxr)，上边界(wyt)，下边界(wyb)，如void Line_Clipping(float x1, float y1, float x2, float y2,float Wxl,float Wxr,float Wyt,float Wyb)，再结合鼠标mouse函数，实现点击鼠标左键显示矩形框和待裁剪的直线段，点击鼠标右键进行裁剪并显示裁剪过后的直线段，最终显示出来。 由于在Line_Clipping函数下用到了line函数，所以我在上面定义了个line 函数来绘制直线段(绘制直线段所采用的算法为Bresenham算法)。 程序代码： #include
glVertex2i(x,y);//绘制点的坐标 glEnd ( ); } // 绘制直线的方法 void line (int x1,int y1,int x2,int y2)//输入线段的两个端点坐标和画线颜色 { int x,y,dx,dy,s1,s2,p,temp,interchange,i; x=x1; y=y1;//设置象素坐标初值 dx=abs(x2-x1); dy=abs(y2-y1);//分别计算之间的差值 if(x2>x1) s1=1; else s1=-1; if(y2>y1) s2=1; else s2=-1; //判断起点和终点的位置，以确定是该加一个单位还是该减一个单位 if(dy>dx)//y方向增长快，将总步数设为y2-y1，每一步的y值为:y=y+1 { temp=dx;
裁剪算法详解 在使用计算机处理图形信息时，计算机部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之，哪些落在显示区之外，以便只显示落在显示区的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法。 (a)裁剪前 (b) 裁剪后 图1.1 多边形裁剪 1直线段裁剪 直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。常
用的线段裁剪方法有三种：Cohen-Sutherland,中点分割算法和梁友栋－barskey 算法。 1.1 Cohen-Sutherland裁剪 该算法的思想是：对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。 为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。延长窗口的边，将二维平面分成九个区域。每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下：
图1.2 多边形裁剪区域编码图5.3线段裁剪 裁剪一条线段时，先求出P1P2所在的区号code1,code2。若code1=0,且code2=0，则线段P1P2在窗口，应取之。若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之。否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理。在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。 Cohen-Sutherland裁减算法 #define LEFT 1 #define RIGHT 2 #define BOTTOM 4
#python实现可视化的多边形裁剪 import matplotlib.pyplot as plt import copy import math from tkinter import * def cross_point(line1,line2,winx,winy):#计算交点函数 year1 = copy.deepcopy(line1) pop1 = copy.deepcopy(line2) winx1 = copy.deepcopy(winx) winy1 = copy.deepcopy(winy) node_class = [] minx = min(winx) maxx = max(winx) miny = min(winy) maxy = max(winy) count = 0 for i in range(len(line1)-1): count1=0 x1=line1[i]#取四点坐标 y1=line2[i] x2=line1[i+1] y2=line2[i+1] k1=(y2-y1)*1.0/(x2-x1)#计算k1,由于点均为整数，需要进行浮点数转化 b1=y1*1.0-x1*k1*1.0#整型转浮点型是关键 nodey = k1*minx*1.0+b1*1.0 if (y1<=nodey<=y2 or y2<=nodey<=y1) and (miny<=nodey<=maxy) and ([maxx,nodey] not in node_class): node_class.append([minx,nodey]) count=count+1 count1=count1+1 nodey1 = k1*maxx*1.0+b1*1.0 if (y1<=nodey1<=y2 or y2<=nodey1<=y1) and (miny<=nodey1<=maxy) and ([maxx,nodey1] not in node_class): node_class.append([maxx,nodey1]) count=count+1 count1=count1+1 nodex = (miny*0.1 - b1*0.1)/(k1*0.1)
在国际上，大部分先进国家的服装裁剪都是用原型法，但由于，原型在使用上不能直接裁剪，而且胸围放松量与袖笼深分两步确定，与我国传统习惯不符，因此，原型法不能全盘照搬，而且比例裁剪法在我国运用多年，也有不可抛弃的精华，对于一些传统款式，如西裙、西裤、卫衣、西装，套用公式，简单正确，并可以在布料上直接裁剪，方便快捷。因些，只有在传统的比例裁剪基础上，运用原型法的结构方法，才能将两者的优点结合，开拓一种裁剪的新路。 下面以女装基本衣片为例。 一、测量部位： 原型裁剪法的测量部位是：常见的日本文化式只需测量胸围、背长、袖长三个尺寸，领围与肩宽的确定不够准确，登丽美式测量的部位则过多，程序复杂，不利于使用。比例裁剪法的测量部位中没有背长，腰节线的确定不够科学。通过比较得出：选择领围、胸围、肩宽、背长、袖长这五个部位测量较为合适。 二、尺寸加放： 原型法裁剪的尺寸加放分两步进行，第一步先考虑人体基本合体松量加放10cm，第二步再根据款式继续加放。比例裁剪法习惯胸围净尺寸，直接裁剪，更为方便。通过比较得出：将胸围净尺寸，加放后得到成品尺寸，再进行制图。具体可参考如下：无吊带上装，胸围加放为0；紧身衬衣为4.8cm；普通衬衣为8-10cm；宽松衬衣12-20cm；西装8-10cm；大衣为15- 20cm。制图方法： 1、衣片： (1)、胸围是成品尺寸。 (2)、领口： 领围的框架有两种方法确定，一种用胸围计算，一种用颈围计算，后者适合做立领卫衣和旗袍领，更为科学。因此，选用1/5领围计算。 (3)、肩斜： 肩斜量可以用定量法、公式法或角度法确定，三者的结果相差甚微，而采用定量法可省去计算的麻烦。故采用定量法确定肩斜：普通衬衣前肩斜5cm，后肩斜4.5cm；有垫肩的外衣前肩斜4cm，后肩斜3.5cm。 (4)、肩宽： 根据从人体测量得出的总肩宽，按比例裁剪法的1/2肩宽，计算出前后衣片的肩宽。(5)、袖笼深： 袖笼深的计算有两种方法：一种计算上平线到胸围线的距离，包括肩斜量；另一种计算肩斜点到胸围线的距离，不包括肩斜量。前一种方便，后一种精确，本文采用后一种。袖笼深随款式不同而变化，夏天单衣为B/6+1；春秋上衣为B/6+3；冬季大衣为B/6+5 。(6)、胸高点： 在比例裁剪法中，确定胸高点的方法是：以胸围线和胸宽线为依据，确立相对的位置，但是，由于胸围线和胸宽线随款式而变化，所以这样并不准确。在原型裁剪法中，胸高点由乳高和乳距确定，以人体为本，既科学又准确。乳高是指从侧颈点到胸高点的距离，乳距是指左右胸高点的距离，根据体型的不同，可从下列数据中找出对应的胸高、乳距，然后确定胸高点。身高为155、160、165、170、175的分别对应乳高为23、24、25、26、27；净胸围为80、84 、88、92的分别对应乳距为17、18、19、20(cm)。 (7)、胸省： 胸省的大小通常根据人体确定：一般人的胸省量为2.5cm-3.5cm，取3cm较为合适。胸省量还可以按款式变化作出调整。胸省量与服装胸部造型的关系为：当胸省量为3cm时，胸部
课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日
湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日
一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。
计算机图形学 实验报告 实验（四） 实验题目：线段裁剪算法 指导老师：吴颖斌 专业：数字媒体技术 班级： 1306班 姓名： xx（20131006xx） 2014年 11月19日
一、实验类型 验证性。 二、实验目的和要求 目的：编写线段裁剪算法程序，验证算法的正确性。 要求：编写Cohen-Sutherland直线剪裁算法程序，编译、调试，查看运行结果。 三、实验中用到的硬件设备及软件环境 Microsoft Visual C++ 6.0和PC机 四、实验主要程序代码 Cohen-Sutherland直线剪裁算法 （1）主要步骤和代码： 步骤1：创建Code_Clip工程文件； 步骤2：在主程序的程序头部定义符号常量（鼠标双击“CCode_ClipView”，添 加至 “class CCode_ClipView : public …………”之前） #define LEFT 1 #define RIGHT 2 #define BOTTOM 4 #define TOP 8 步骤3：定义成员变量和成员函数（鼠标双击“CCode_ClipView”，添加至“class CCode_ClipView : public …………”之内）） int WT; int WB; int WR; int WL; 步骤4：在构造函数中为窗口边界变量赋初值 CCode_ClipView::CCode_ClipView() { // TODO: add construction code here WL=100;WR=400;WB=100;WT=300; } 步骤5：编写成员函数程序（在“CCode_ClipView”单击鼠标右键-->Add member function……） void CCode_ClipView::encode(int x, int y, int *code) {
大学实验报告 学院：计算机科学与信息学院专业：软件工程班级：102班 学号实验组实验时间指导教师成绩实验项目名称实验五直线和多边形的裁剪 实 验 目 的 掌握直线段的裁剪算法以及多边形的裁剪算法 实 验要求熟练掌握直线段的裁剪算法以及多边形的裁剪算法的基本原理，并编写测试代码进行实验。 实验原理 Cohen-Sutherland直线剪裁算法 以区域编码为基础，将窗口及其周围的，8个方向以4 bit的二进制数进行编码。 右图所示的编码方法将窗口及其邻域 分为5个区域： ⑴域：区域(0000)。 ⑵上域：区域(1001, 1000, 1010)。 ⑶下域：区域(0101, 0100, 0110)。 ⑷左域：区域(1001, 0001, 0101)。 ⑸右域：区域(1010, 0010, 0110)。 当线段的两个端点的编码的逻辑“与”非零时，线段为显然不可见的，对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右； Cohen-Sutherland直线剪裁算法的算法思想是： 对于每条线段P1P2分为三种情况处理。（1）若P1P2完全在窗口，则显示该线段P1P2简称“取”之。（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。其中
while (code1 != 0 || code2 != 0) { if ((code1 & code2) != 0) {// 两端点的编码相与不为0，表示直线在窗口外 return; } if (code1 != 0) { code = code1; } else { code = code2; } if ((LEFT & code) != 0) {// 直线的端点与矩形窗口的左边编码相与！=0 x = XL; y = y1 + (y2 - y1) * (XL - x1) / (x2 - x1);// 求直线与矩形窗口的左边界的交点 } else if ((RIGHT & code) != 0) {// 直线的端点与矩形窗口的右边编码相与！=0 x = XR; y = y1 + (y2 - y1) * (XR - x1) / (x2 - x1);// 求直线与矩形窗口的右边界的交点 } else if ((BOTTOM & code) != 0) {// 直线的端点与矩形窗口的下边编码相与！=0 y = YB; x = x1 + (x2 - x1) * (YB - y1) / (y2 - y1);// 求直线与矩形窗口的下边界的交点 } else if ((TOP & code) != 0) {// 直线的端点与矩形窗口的上边编码相与！=0 y = YT; x = x1 + (x2 - x1) * (YT - y1) / (y2 - y1);// 直线的端点与矩形窗口的
直线裁剪算法研究 摘要：直线裁剪是计算机图形学中的一个重要技术，在对常见的直经线裁剪的算法分析的基础上，针对Cohen-Sutherland算法和Liang-Barsky算法进行了分析研究。并对两种算法了计算直线与窗口边界的交点时，进行了有效有比较。 关键词：裁剪；算法；Cohen-Sutherland；Liang－Barsky； 1 引言 直线是图形系统中使用最多的一个基本元素。所以对于直线段的裁剪算法是被研究最深入的一类算法，目前在矩形窗口的直线裁剪算法中，出现了许多有效的算法。其中比较著名的有：Cohen-Sutherland算法、中点分割算法、Liang-Ba rsky算法、Sobkow-Pospisil-Yang算法，及Nicholl-Lee-Ncholl算法等。 2 直线裁剪的基本原理 图1所示的为直线与窗口边界之间可能出现的几种关系。可以通过检查直线的两个端点是否在窗口之内确定如何对此直线裁剪。如果一直线的两个端点均在窗口边界之内（如图1中P5到P6的直线），则此直线应保留。如果一条直线的一个端点在窗口外（如P9）另一个点在窗口内（如P10），则应从直线与边界的交点（P9）处裁剪掉边界之外的线段。如果直线的两个端点均在边界外，则可分为两种情况：一种情况是该直线全部在窗口之外；另一种情况是直线穿过两个窗口边界。图中从P3到P4的直线属于前一种情况，应全部裁剪掉；从P7到P8的直线属于后一种情况，应保留P7到P8的线段，其余部分均裁剪掉。 图1直线相对干窗口边界的栽剪 直线裁剪算法应首先确定哪些直线全部保留或全部裁剪，剩下的即为部分裁剪的直线。对于部分裁剪的直线则首先要求出这些直线与窗口边界的交点，把从交点开始在边界外的部分裁剪掉。一个复杂的画面中可能包含有几千条直线，为了提高算法效率，加快裁剪速度，应当采用计算量较小的算法求直线与窗口边界的交点。
简单多边形裁剪算法 摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前 裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。 关键词：多边形裁剪；交点；前驱；后继；矢量数组 一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。 二、发展研究现状 近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。 三、新算法设计 1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。 2、主要数据结构 多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示，
河南理工大学 万方科技学院 课程设计报告 2011 — 2012学年第二学期 课程名称计算机图形学 设计题目计算机图形学基本算法 演示系统设计 学生姓名 学号 专业班级网络11升—1班 指导教师徐文鹏 2012 年5 月28 日
目录 第1章设计内容与要求 (1) 1.1 总体目标和要求 (1) 1.2内容与要求 (1) 1.2.1 直线的生成 (1) 1.2.2 圆弧的生成 (1) 1.2.3 线段裁剪 (2) 1.2.4 多边形裁剪 (2) 1.2.5 综合 (2) 第2章总体设计 (3) 2.1 Bresenham算法画直线 (3) 2.1.1 Bresenham算法画直线理论基础 (3) 2.1.2 Bresenham算法画直线原理 (3) 2.2 Bresenham算法画圆 (4) 2.2.1 Bresenham算法画圆理论基础 (4) 2.2.2 Bresenham算法画圆原理 (5) 2.3 梁友栋-Barsky算法进行线段裁剪 (6) 2.3.1梁友栋-Barsky算法进行线段裁剪基本原理 (6) 2.4 Sutherland-Hodgman算法进行多边形裁剪 (8) 2.4.1 Sutherland—Hodgman多边形裁剪算法思想 (8) 2.4.2 点在边界内侧的判断方法 (8) 2.4.4 Sutherland-Hodgeman多边形裁剪算法特点 (8) 第3章详细设计 (9) 3.1 Bresenham算法画直线 (9) 3.1.1 Bresenham 算法画线算法具体实现过程 (9) 3.2 Bresenham算法画圆 (9) 3.2.1 Bresenham 算法画圆核心代码 (9)
图形裁剪算法 1.实验目的： 理解区域编码 设计直线裁剪算法 编程实现直线裁剪算法 2.实验描述： 设置裁剪窗口坐标为：wxl=250;wxr=850;wyb=250;wyt=450;裁剪前如下图所示： 裁剪后结果为： 3.算法设计： 直线裁剪算法： 假设裁剪窗口是标准矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边组成，如下图所示。延长窗口四条边形成9个区域。根据被裁剪直线的任一端点P(x，y)所处的窗口区域位置，可以赋予一组4位二进制区域码C4C3C2C1。
编码定义规则： 第一位C1：若端点位于窗口之左侧，即X
实验三图形裁剪算法 1.实验目的： 理解区域编码(Region Code，RC) 设计Cohen-Sutherland直线裁剪算法 编程实现Cohen-Sutherland直线裁剪算法 2.实验描述： 设置裁剪窗口坐标为：wxl=250;wxr=850;wyb=250;wyt=450;裁剪前如下图所示： 裁剪后结果为： 3.算法设计： Cohen-Sutherland 直线裁剪算法： 假设裁剪窗口是标准矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四条边组成，如下图所示。延长窗口四条边形成9个区域。根据被裁剪直线的任一端点P(x，y)所处的窗口区域位置，可以赋予一组4位二进制区域码C4C3C2C1。
为了保证窗口内直线端点的编码为零，编码规则定义如下： 第一位：若端点位于窗口之左侧，即x
PS二：移动、多边形、裁剪工具 前言：如果小工具后面带有小三角样式，即说明该种工具还有其他类似的小工具可以使用，方式是鼠标左键长按小工具图标，会自动跳出其他几个小工具，点击选择即可。 1：移动工具（v）：点击图层后可以选中图层进行编辑或移动图层至需要的位置。 先建立一个空白图层，大小像素任意。 打开一个文件夹，找任意图片，按住鼠标左键选中并拖动图片拉到PS图层界面中。拉动过程中鼠标不要松开。 此时右边图层面板就会出现两个图层（如果没有图层面板，可以在PS软件最上面的第一排菜单栏中点击“窗口”-“图层”，快捷键F7）。一开始新建的是背景层，另外一个是刚才拖进去的图片图层。
然后在这个状态下，可以使用“移动工具”随意拖动该图层，也可以对齐进行其他编辑（在编辑前必须先在图层上右键-栅格化图层，再进行编辑。以后将仔细介绍图层的编辑。）。 2：多边形套索工具：可以根据自己的意图来裁剪或选择图层上某个部分。 用上面的移动工具拖入一个需要修改的图层，这边就按刚才的图片举例，如果图片上的微信号换掉了，就需要把微信号删除掉，在PS里说裁剪掉。栅格化图层后，先点击多边形套索工具，然后在微信号的边缘依次点击鼠标左边选出需要裁切掉的地方。
点击第一点后，会出现一条直线，可以点击第二点，一直到收尾相连，这时的选框已经选出来。直接按键盘“Delete”键即可。 删除后图层上会出现一个虚线选框，按快捷键ctrl+d 取消选框即可。然后可以编辑自己需要的内容。 3：裁剪工具（C）：是裁剪画布大小的工具，就如同剪刀一样。裁剪掉的东西是不能再拼回去的哦。（原则上不可以，但是PS功能非常强大，以后会告诉大家如果来拼回去，嘻嘻...）点击“裁剪工具”后，画布四周会出现虚线框和八个小框。
《计算机图形学》实验报告 《实验名称》 直线段裁剪 姓名 学号 专业 班级 天津大学计算机科学与技术学院
一、实验目的 熟练掌握Cohen-Sutherland直线裁剪算法，并编程实现 二、实验内容 (1) 裁剪窗口为矩形窗口，且矩形边和坐标轴平行，长宽自己定。 (2) 待裁剪线段端点坐标自己定；裁剪线段涵盖完全可见、不完全可见、 完全不可见类型。 (3) 要求显示待裁剪线段并用不同颜色标示出裁剪结果。 实现方法：一般情况下，需要判断一条直线是全部可见，全部不可见，部分裁剪(一段裁剪)，全部裁剪(两端裁剪)。通过把裁剪区域分成许多部分，然后给每一段被裁剪的线段的两端分配一位代码，通过少量if语句和一个case语句就可以判断出具体情况。 伪代码如下： #define CLIP_CODE_C 0x0000 #define CLIP_CODE_N 0x0008 #define CLIP_CODE_S 0x0004 #define CLIP_CODE_E 0x0002 #define CLIP_CODE_W 0x0001 #define CLIP_CODE_NE 0x000a #define CLIP_CODE_SE 0x0006 #define CLIP_CODE_NW 0x0009 #define CLIP_CODE_SW 0x0005
实验步骤： 1）生成裁剪窗口，窗口由直线xl=250,xr=850,yb=250,yt=450 2）绘制直线段 3）编写Cohen-Sutherland直线裁剪算法，对直线段进行裁剪 编码定义规则： 第一位C1：若端点位于窗口之左侧，即 X
2017年 2月 图 学 学 报 February 2017第38卷 第1期 JOURNAL OF GRAPHICS V ol.38No.1 第一作者：于海燕(1974–)，女，黑龙江牡丹江人，副教授，博士。主要研究方向为CAD/CG 。E-mail ：yuhy@https://www.doczj.com/doc/1316047592.html, 通信作者：张 帅(1993–)，男，河南驻马店人，硕士研究生。主要研究方向为CAD/CG 。E-mail ：1543965553@https://www.doczj.com/doc/1316047592.html, 视锥体裁剪几何算法研究 于海燕1， 张 帅1， 余沛文1， 何援军2 (1. 东华大学机械工程学院，上海 201620；2. 上海交通大学计算机系，上海 200240) 摘要：从几何角度出发，以投影理论为指导，设计了一种降维投影的视锥体裁剪几何算法。基本思想是基于视锥体构建计算坐标系，在计算坐标系下，向两个投影平面做正投影。空间中被裁剪线段与视锥体的位置关系被简化为投影平面内线段与等腰梯形的关系。这种几何化的降维方法有利于解决空间几何奇异问题。构建了空间视锥体裁剪中线段与视锥体的各种位置关系的测试样本，特别是78种处于几何奇异状态的位置关系，用于综合评估算法的速度和稳定性。用C 语言在VC++平台上分别实现了投影降维的视锥体裁剪几何算法、经典的Liang-Barsky 算法和与6个面分别求交的一般算法。在定性分析基础上，利用测试样本对3种算法做了计算速度与稳定性方面的测试对比。 关键词：视锥体裁剪；几何算法；投影理论；几何奇异 中图分类号：TP 391.72 DOI ：10.11996/JG .j.2095-302X.2017010001 文献标识码：A 文 章 编 号：2095-302X(2017)01-0001-04 View Frustum Culling Geometric Algorithm YU Haiyan 1, ZHANG Shuai 1, YU Peiwen 1, HE Yuanjun 2 (1. College of Mechanical Engineering, Donghua University, Shanghai 201620, China; 2. Department of Computer Science & Engineering, Shanghai Jiao Tong University, Shanghai 200240, China) Abstract: From the point of view of geometry, a view frustum culling geometric algorithm is designed based on projective theory in descriptive geometry. The basic idea is that a proper computational coordinate system is built, where the space position relation of the view frustum and a line segment is transformed into the plane position relation of a trapezoid and the line segment by simple orthographic projection. This geometric dimension reduction method is beneficial to solve space geometric singular issue. A test sample is designed which includes all kinds of typical position relations of the view frustum and the line segment to comprehensively evaluate algorithm’s speed and stability. And especially, there are 78 kinds of geometric singular relations. At last, our view frustum culling geometric algorithm, classical Liang-Barsky algorithm and a basic algorithm to solvethe problem of intersection with 6 planes have been implemented on Visual C++ with C program. On the basement of qualitative analysis, these 3 algorithms have been tested on speed and stability. Keywords: view frustum culling; geometric algorithm; projection theory; geometric singular 随着三维几何模型愈发复杂、逼真，虚拟环 境的场景规模越来越大，如何有效减少绘制对象， 降低三维模型的复杂度，是三维显示系统中快速 稳定绘制复杂场景的关键所在。近年来，可见性的判断是一种有效方法，在大规模的复杂场景中，虽然需要绘制对象的数量大幅增加，但对于观察
多边形裁剪的Sutherland—Hodgman算法 1>. Sutherland—Hodgman多边形裁剪算法思想 该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，…，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。 当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）： 1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列； 2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列； 3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列； 4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。 2>. Sutherland—Hodgman多边形裁剪算法步骤 考虑多边形相对于一条边界及其延长线进行裁剪的算法： 1．从主函数得到待裁剪多边形的顶点序列P[][2]、顶点序列数n、窗口一条边界参数xl（假如为矩形窗口的左边界）； 2．赋初值： 将顶点序列中的最后一个顶点赋给前一顶点S； 设置初始标志flag： if(S在边界内侧)flag=0;
else flag=1； 设新的顶点序列数j=0； 3．对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列 Q[][2]中： for(对第一个顶点直到最后一个顶点，逐一处理）{if(Pi在边界内 侧){if(flag!=0){flag=0; 求交点并放入新的多边形顶点序列Qjxx； j++；}将当前顶点放入新的多边形顶点序列Qj中： Qj=Pi； j++；}else{if(flag==0){flag=1; 求交点并放入新的多边形顶点序列Qjxx； j++；}} 将当前顶点赋给S： S=Pi；} 4．做返回准备： 将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中： P=Q； 将新的多边形顶点数j放回原多边形顶点数n中： n=j； //////////////////////////////////////////////////////////////////////////////////// // //-----多边形裁剪的Sutherland—Hodgman算法---------//
一、实验目标 1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想； 2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现； 二、实验内容 本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。 Cohen-sutherland线段裁剪算法思想： 该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。 对剩余部分，把它作为新的线段看待，又从头开始考虑。两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。 Cohen-sutherland线段裁剪算法步骤： 1、分区编码 延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。各区代码值如图中所示。 四位二进制代码的编码规则是： (1)第一位置1：区域在左边界外侧
(2)第二位置1：区域在右边界外侧 (3)第三位置1：区域在下边界外侧 (4)第四位置1：区域在上边界外侧 裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。 设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。 2、判别 根据C1和C2的具体值，可以有三种情况： （1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。 （2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。 （3）不属于上面两种情况，均需要求交点。 3、求交点 假设算法按照：左、右、下、上边界的顺序进行求交处理，对每一个边界求完交点，并相关处理后，算法转向第2步，重新判断，如果需要接着进入下一边界的处理。 为了规范算法，令线段的端点P 1为外端点，如果不是这样，就需要P 1 和P 2 交换端点。 当条件(C1&0001≠0)成立时，表示端点P1位于窗口左边界外侧，按照求交公式，进行对左边界的求交运算。 依次类推，对位于右、下、上边界外侧的判别，应将条件式中的0001分别改为0010、0100、1000即可。 求出交点P后，用P1=P来舍去线段的窗外部分，并对P1重新编码得到C1，接下来算法转回第2步继续对其它边界进行判别。 Liang-Barsky线段裁剪算法思想： 我们知道，一条两端点为P1（x1，y1）、P2（x2，y2）的线段可以用参数方程形式表示： x= x1+ u·（x2-x1）= x1+ u·Δx y= y1+ u·（y2-y1）= y1+ u·Δy0≤u≤1式中，Δx=x2-x1，Δy=y2-y1，参数u在0～1之间取值，P（x，y）代表了该线段上的一个点，其值由参数u确定，由公式可知，当u=0时，该点为P1（x1，y1），当u=1时，该点为P2（x2，y2）。如果点P（x，y）位于由坐标（xw min，