计算机图形学课程设计-Weiler-Atherton多边形裁剪.docVIP

《计算机图形学》课程设计 实验报告书 安徽工业大学数理学院 姓 名 鲍计炜 专 业 信息与计算科学 班 级 信112 学 号 119084177 指导教师 侯为根 2014年1月13日 Weiler－Atherton多边形裁剪 Weiler－Atherton算法Weiler－AthertonWeiler－Atherton裁剪窗口和被裁剪多边形处于完全对等的地位，这里我们称： 　　1、被裁剪多边形为主多边形，记为A； 　　2、裁剪窗口为裁剪多边形，记为B。 　　主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域：　　1、AB（交：属于A且属于B）；　　　2、A－B（差：属于A不属于B）；　　3、B－A（差：属于B不属于A）；　　4、AB(并：属于A或属于B，取反；即：不属于A且不属于B)。 　　内裁剪即通常意义上的裁剪，取图元位于窗口之内的部分，结果为AB。 　　外裁剪取图元位于窗口之外的部分，结果为A－B。 　　观察右图不难发现裁剪结果区域的边界由被裁剪多边形的部分边界和裁剪窗口的部分边界两部分构成，并且在交点处边界发生交替，即由被裁剪多边形的边界转至裁剪窗口的边界，或者反之。由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类： 　　一类称“入”点，即被裁剪多边形由此点进入裁剪窗口，如图中a、c、e；　　一类称“出”点，即被裁剪多边形由此点离开裁剪窗口，如图中b、d、f。 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步：满足“入”点没找到的条件时，算法结束。算法的生成过程见下图所示。 ： const int MAXVERT = 500; const int MAXPOLYV = 50; const int MAXH = 10; struct Point2D {float x,y; }; typedef Point2D Vertices[MAXVERT]; enum VerType = {Polygon, Intersection}; typedef struct ClipListRec * ClipPtr; struct ClipListRec { int Vindex; ClipPtr next; VerType Kind; float t; ClipPtr otherList; } struct Polygon { int nVertex; int vert[MAXPOLYV]; ClipPtr list; } struct GenPolygon { Polygon exterior; int numHoles; Polygon Holes[MAXH]; }