下载文档原格式
weiler-atherton多边形裁剪算法weileratherton多边形裁剪算法，又称为weiler-atherton算法，是一种用于对多边形进行裁剪的算法。
它可以被用于计算机图形学中的裁剪任务，如可视化、图像处理和计算机辅助设计等领域。
本文将详细介绍weileratherton多边形裁剪算法的原理、步骤和实现方法。
1. 算法原理：weileratherton多边形裁剪算法是基于边界点的引入和处理的。
该算法将两个多边形相互之间进行裁剪，并生成裁剪结果。
算法使用四个边界点集合，分别为输入多边形的边界点集合(输入多边形顶点经过一系列处理得到)，裁剪多边形的外部边界点集合和内部边界点集合，以及裁剪结果的边界点集合。
2. 算法步骤：weileratherton多边形裁剪算法的具体步骤如下：(1) 初始化：创建输入多边形的边界点集合、裁剪多边形的外部边界点集合和内部边界点集合，并将输入多边形的边界点添加至外部边界点集合中。
(2) 遍历输入多边形的每条边：对于输入多边形的每条边，判断其与裁剪多边形的相交情况。
(3) 相交情况处理：若相交情况为内部相交或外部相交，则根据交点生成新的内部边界点，并添加至相应的边界点集合中。
(4) 构造裁剪结果：根据输入多边形的边界点集合和裁剪多边形的内部边界点集合，生成裁剪结果的边界点集合。
(5) 根据边界点集合构造裁剪结果：根据裁剪结果的边界点集合，绘制裁剪结果多边形。
3. 算法实现：weileratherton多边形裁剪算法的实现可以使用编程语言来完成。
一种常用的实现方法是通过遍历输入多边形的每个边，利用线段与裁剪多边形的边界的相交情况判断是否产生交点，并根据交点生成新的边界点。
具体的实现步骤如下：(1) 初始化输入和裁剪多边形的边界点集合。
(2) 遍历输入多边形的每条边，对于每条边，判断其与裁剪多边形的每条边的相交情况。
(3) 根据相交情况，判断是否生成交点，如果有生成交点，则根据交点生成新的边界点，并添加至相应的边界点集合中。
具有拓扑关系的任意多边形裁剪算法拓扑关系是指在空间中，几何对象之间的相对位置和连接关系。
任意多边形裁剪算法是指对于两个多边形A和B，确定A相对于B的位置关系，并将A裁剪成相对于B的部分。
常用的具有拓扑关系的任意多边形裁剪算法有Sutherland-Hodgman算法和Weiler-Atherton算法。
Sutherland-Hodgman算法是一种简单而直观的裁剪算法，它以多边形A为基础，对多边形A的每条边进行裁剪，最终得到所需的裁剪结果。
算法步骤如下：1.对于裁剪窗口的每条边界，确定其相对于多边形A的左侧。
2.对多边形A的每条边进行裁剪处理，生成新的顶点序列。
3.重复步骤2，直到对所有的边界完成处理。
4.返回裁剪结果。
其中，对于多边形A的每条边进行裁剪处理的具体步骤如下：1.对于多边形A的每条边，判断边的起点和终点是否在裁剪窗口内。
2.如果起点和终点都在窗口内，则将边加入新的顶点序列。
3.如果起点在窗口内，而终点在窗口外，则计算边与窗口边界的交点，并将交点加入新的顶点序列。
4.如果起点在窗口外，而终点在窗口内，则计算边与窗口边界的交点，并将交点作为起点加入新的顶点序列。
5.如果起点和终点都在窗口外，则忽略这条边。
Sutherland-Hodgman算法的优点在于简单易懂，对于凸多边形和凹多边形都适用，但由于其每条边都需要进行裁剪处理，效率较低。
Weiler-Atherton算法是一种基于点集的裁剪算法，它将两个多边形视为点的集合，并通过点集之间的拓扑关系进行裁剪操作。
算法步骤如下：1.对于多边形A和多边形B，找到它们的交点。
2.根据交点和各自的顺时针或逆时针顺序，将交点按序列分别加入多边形A和多边形B的顶点序列。
3.对多边形A和多边形B的顶点序列进行裁剪处理，得到裁剪结果。
Weiler-Atherton算法的优点在于避免了对每条边进行裁剪的操作，对于复杂多边形的裁剪效果好，但实现较为复杂。
以上是具有拓扑关系的任意多边形裁剪算法的简要介绍。
《计算机图形学》练习题(答案)《计算机图形学》练习题1．直线扫描转换的Bresenham算法(1) 请写出生成其斜率介于0和1之间的直线的Bresenham算法步骤。
(2) 设一直线段的起点和终点坐标分别为(1,1)和(8,5)，请用Bresenham算法生成此直线段，确定所有要绘制象素坐标。
(1)①输入线段的两个端点，并将左端点存储在(x0,y0)中②将(x0,y0)装入帧缓存，画出第一个点③计算常量∆x, ∆y, 2∆y, and 2∆y-2∆x,并得到决策参数的第一个值：p0 = 2∆y - ∆x④从k=0开始，在沿线路径的每个xk处，进行下列检测:如果pk < 0,下一个要绘制的点就是(xk +1,yk) ，并且pk+1 = pk + 2∆y否则下一个要绘制的点就是(xk +1, yk +1)，并且 pk+1 = pk + 2∆y- 2∆x⑤重复步骤4，共∆x-1次(2)m=(5-1)/(8-1)=0.57∆x=7 ∆y=4P0=2∆y-∆x=12∆y=8 2∆y-2∆x=-6 k pk (xk+1,yk+1)0 1 (2,2)1 -5 (3,2)2 3 (4,3)3 -3 (5,3)4 5 (6,4)5 -1 (7,4)6 7 (8,5)2．已知一多边形如图1所示，其顶点为V1、V2、V3、V4、V5、V6，边为E1、E2、E3、E4、E5、E6。
用多边形的扫描填充算法对此多边形进行填充时(扫描线从下到上)要建立边分类表(sorted edge table)并不断更新活化边表(active edge list)。
(1)在表1中填写边分类表中每条扫描线上包含的边(标明边号即可)；(2)在表2中写出边分类表中每条边结构中各成员变量的初始值(3) 指出位于扫描线y=6,7,8,9和10时活化边表中包含那些边，并写出这些边中的x值、ymax值、和斜率的倒数值1/m。
表1边分y1边 x y max 1/m 4 1 1 97 4 60 05 1 9 76 0 0 61 9 6 6 0 0Y 值(Scan Line Number ) 边(Edge Number ) 1 0 2 0 3 0 4 E1 5 E6,E2 6 E6 7 E3 8 E5,E3 9E4 10 01 2 3 4 5 6 7 8 9 1表 2 边的初7 1 18 7 790 1-18 2 7 9 9 1 -19 3 36 9 991-13. 二维变换(1) 记P(xf,yf)为固定点，sx、sy分别为沿x 轴和y轴方向的缩放系数，请用齐次坐标(Homogeneous Coordinate)表示写出二维固定点缩放变换的变换矩阵。
weiler-atherton多边形裁剪算法-回复标题：深入理解Weiler-Atherton多边形裁剪算法一、引言在计算机图形学中，多边形裁剪是一个常见的操作，用于处理复杂的几何形状。
其中，Weiler-Atherton多边形裁剪算法是一种广泛应用的算法，它能够有效地处理任意两个二维多边形之间的相交、相减和相加操作。
本文将详细解析Weiler-Atherton多边形裁剪算法的步骤和原理。
二、预备知识在深入探讨Weiler-Atherton算法之前，我们需要了解一些基本的预备知识。
1. 多边形表示：多边形通常通过其顶点序列来表示，每个顶点由其在笛卡尔坐标系中的(x, y)坐标确定。
2. 十字产品：在二维空间中，两个向量的十字产品可以用来判断它们的方向关系。
如果结果为正，那么一个向量在另一个向量的逆时针方向；如果结果为负，那么一个向量在另一个向量的顺时针方向；如果结果为零，那么两个向量平行或重合。
三、Weiler-Atherton多边形裁剪算法概述Weiler-Atherton算法主要包括以下四个步骤：1. 分析阶段：确定输入多边形的边缘和顶点的关系。
2. 前处理阶段：生成新的边和顶点，以准备后续的裁剪操作。
3. 裁剪阶段：根据分析阶段的结果，进行实际的裁剪操作。
4. 后处理阶段：清理和优化输出的多边形。
四、详细步骤解析1. 分析阶段：在这个阶段，我们需要对输入的两个多边形A和B的所有边进行遍历，确定每条边与其他边的关系。
具体来说，我们需要找到以下四种情况：- 共线边：两条边平行或重合。
- 相交边：两条边在某个点相交。
- 包含边：一条边完全包含在另一条边上。
- 不相交边：两条边不相交且不共线。
对于每种情况，我们都需要记录下相应的信息，以便在后续阶段使用。
2. 前处理阶段：在这个阶段，我们需要根据分析阶段的结果生成新的边和顶点。
具体来说，我们需要执行以下操作：- 对于每一对相交的边，我们在相交点处生成一个新的顶点，并连接这个新顶点与原来的两个顶点，形成两条新的边。
（完整版）Weiler-Atherton任意多边形裁剪算法预览说明:预览图片所展示的格式为文档的源格式展示,下载源文件没有水印,内容可编辑和复制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任意多边形裁剪算法思想：假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。
当两个多边形相交时，交点必然成对出现，其中一个是从被裁剪多边形进入裁剪窗口的交点，称为“入点”，另一个是从被裁剪多边形离开裁剪窗口的交点，称为“出点”。
多边形裁剪刘世光天津大学计算机学院天津大学计算机科学与技术学院主要内容•多边形裁剪Sutherland Hodgman多边形裁剪算法;Weiler Sutherland-Hodgman;Weiler-Atherton算法;•曲线裁剪、字符裁剪曲线裁剪字符裁剪天津大学计算机科学与技术学院多边形裁剪与线段裁剪•使用线段裁剪进行多边形裁剪，则裁剪后的边使用线段裁剪进行多边形裁剪则裁剪后的边界将显示为一系列不连接的线段，没有关于如何形成裁剪后的封闭多边形的完整信息何形成裁剪后的封闭多边形的完整信息。
天津大学计算机科学与技术学院多边形裁剪•新的问题：–边界不再封闭–产生多个部分天津大学计算机科学与技术学院多边形裁剪天津大学计算机科学与技术学院Sutherland-Hodgman算法•Sutherland和Hodgman提出的裁剪凸多边形由S therland填充区的高效算法。
•其总体策略是顺序地将每一线段的一对顶点送给一组裁剪器（左、右、下、上）。
一个裁剪器完成一对顶点的处理后，该边裁剪后留下的坐标值送给下一个裁剪器。
天津大学计算机科学与技术学院•用裁剪边界对多边形的边裁剪时的四种情况：外内输出'12,V V 内内输出2V 内外输出'1V 外外输出: 无天津大学计算机科学与技术学院:实现步骤输入边:左裁剪右裁剪下裁剪上裁剪天津大学计算机科学与技术学院Sutherland-Hodgmang算法小结:•:–逐边裁剪：两次分解•第一次分解：将多边形关于矩形窗口的裁剪分解第次分解将多边形关于矩形窗口的裁剪分解为它关于窗口四条边所在直线的裁剪；•第二次分解：将多边形关于一条直线的裁剪分解第二次分解将多边形关于条直线的裁剪分解为多边形各边关于该直线的裁剪。
天津大学计算机科学与技术学院:举例天津大学计算机科学与技术学院:其他例子天津大学计算机科学与技术学院Sutherland-Hodgman算法g–推广•关于任意凸多边形窗口的裁剪天津大学计算机科学与技术学院练习：天津大学计算机科学与技术学院Sutherland-Hodgman算法•算法的不足之处：算法的不足之处裁剪凹多边形时，可能显示一条多余的直线，原因是该算法只有一个输出顶点队列。
第一章概述1、计算机图形学研究的是什么？计算机图形学研究的是通过计算机将数据转换为图形，并在专门的设备上输出的原理、方法和技术。
2、计算机图形学处理的图形有哪些？计算机图形学处理的图形有：专题图件、类似于照片的三维逼真图形、实体的视图、抽象图等。
3、二维图形的基本操作和图形处理算法包含哪些内容？对图形的平移、缩放、旋转、镜像、错切等操作，此外还包括二维图形的裁剪、多边形填充以及二维图形的布尔运算（并、交、差）等。
4、什么叫科学计算可视化技术？这是20世纪90年代计算机图形学领域的前沿课题。
研究的是，将科学计算中大量难以理解的数据通过计算机图形显示出来，从而加深人们对科学过程的理解。
例如，有限元分析的结果，应力场、磁场的分布，各种复杂的运动学和动力学问题的图形仿真等。
5、计算机图形学的应用领域有哪些？计算机图形学处理图形的领域越来越广泛，主要的应用领域有：计算机辅助设计与制造（CAD/CAM）、科学计算可视化、地理信息系统与制图、事务管理和办公自动化、虚拟现实系统、过程控制和指挥系统、计算机动画。
6、计算机图形系统的硬件设备有哪些？硬件设备包括主机、输入设备和输出设备。
输入设备通常为键盘、鼠标、数字化仪、扫描仪和光笔等。
输出设备则为图形显示器、绘图仪和打印机。
7、在彩色CRT的荫罩法技术中，说说每个象素的组成结构？谈谈彩色是如何产生的？彩色CRT显示器中，每个象素位置上分布着呈三角形排列的三个荧光彩色点，三个荧光点分别发射红光、绿光和蓝光。
这样的彩色CRT有三支电子枪，分别与三个荧光点相对应，即每支电子枪发出的电子束专门用于轰击某一个荧光点。
屏幕上的荧光点、荫罩板上的小孔和电子枪被精确地安排处于一条直线上，使得由某一电子枪发出的电子束只能轰击到它所对应的荧光点上。
这样，只要调节各电子枪发出电子束的强弱，即可控制各象素中三个荧光点所发出的红、绿、蓝三色光的亮度。
于是我们可以根据彩色中所含红、绿、蓝三色的数量，以不同的强度激励三个荧光点，从而可以产生范围很广的彩色。
图形裁剪算法研究本文由天空乐园郑州大学生兼职网整理分享摘要在用户坐标系中定义的图形往往是大而复杂的，而输出设备如显示屏幕的尺寸及其分辨率却是有限的，为了能够清晰地观察某一部分或对其进行某些绘图操作，就需要将所关心的这一局部区域的图形从整个图形中区分出来,这个区分指定区域内和区域外的图形过程称为裁剪，所指定的区域称为裁剪窗口。
裁剪通常是对用户坐标系中窗口边界进行裁剪，然后把窗口内的部分映射到视区中，也可以首先将用户坐标系的图形映射到设备坐标系或规范化设备坐标系中，然后用视区边界裁剪。
关键词：矢量裁剪多边形裁剪圆裁剪双边裁剪法线段裁剪字符裁剪引言在人机交互编辑时，作业员往往要把某一区域放大到整个屏幕显示区，这要靠开窗裁剪来实现。
另外，地图的输出往往是分幅输出的，这也要靠开窗裁剪来实现。
裁剪是用于描述某一图形要素（如直线、圆等）是否与一多边形窗口（如矩形窗口）相交的过程，其主要用途是确定某些图形要素是否全部位于窗口之内，若只有部分在窗口内又如何裁剪去窗口外的图形，从而只显示窗口内的内容。
对于一个完整的图形要素，开窗口时可能使得其一部分在窗口之内，一部分位于窗口外，为了显示窗口内的内容，就需要用裁剪的方法对图形要素进行剪取处理。
裁剪时开取的窗口可以为任意多边形，但在实践工作中大多是开一个矩形窗口。
1窗口区和视图区1.1坐标系1.用户坐标系(World Coordinates)又称为世界坐标系、完全坐标系等，它可以是用户用来定义设计对象的各种标准坐标系，例直角坐标、极坐标、球坐标、对数坐标等。
用户坐标系所拥有的区域范围从理论上说是连续的、无限的。
2.观察坐标系(Viewing Coordinates)在用户坐标中设置观察坐标系，在观察坐标系中定义一个观察窗口。
观察坐标系用来任意设置矩形窗口的方向。
一旦建立了观察参考系，就可以将用户坐标系下的描述变换到观察坐标系下。
由于窗口和视图是在不同坐标系中定义的，因此，在把窗口中图形信息转换到视图区之前，必须进行坐标变换，即把用户坐标系的坐标值转化为设备坐标系的坐标值。
注意：答案仅供参考第一章 一、名词解释图形；图像；点阵表示法；参数表示法; 二、选择题：F 面哪个不是国际标准化组织（ISO ）批准的图形标准。
（D ）A. GKS三、判断题：计算机图形学和图像处理是两个近似互逆的学科。
计算机图形学处理的最基本的图元是线段。
（F ） 四、简答题：图形包括哪两方面的要素，在计算机中如何表示它们？阐述计算机图形学、数字图像处理和计算机视觉学科间的关系。
图形学作为一个学科得以确立的标志性事件是什么？试列举出几种图形学的软件标准？工业界事实上的标准有那些? 举例说明计算机图形学有哪些应用范围，解决的问题是什么？ 第二章 一、选择题:1. 触摸屏是一种（C ）A. 输入设备；B. 输出设备；C. 既是输入设备，又是输出设备；2. 3. 4. B. P HIGS C. CGM D. DXF下面哪一项不属于计算机图形学的应用范围？（A. 计算机动画；B. 从遥感图像中识别道路等线划数据；C. QuickTime 技术；D. 影视三维动画制作关于计算机图形标准化的论述，哪个是正确的（A. CGM 和CGI 是面向图形设备的接口标准B. GKS IGES STEP 匀是 ISO 标准；C. IGES 和STEP 是数据模型和文件格式的标准;D. P HIGS 具有模块化的功能结构； 与计算机图形学相关的学科有A. 图像处理B. 测量技术C. 模式识别D. 计算几何E. 生命科学F. 分子生物学A 、C 、D OB )1. (F )2.空间球最多能提供（D ）个自由度；A.一个；B.三个；C.五个；D.六个；3.等离子显示器属于（C）A.随机显示器；B.光栅扫描显示器；C.平板显示器；D.液晶显示器；4.对于一个1024 X 1024存储分辨率的设备来说，当有8个位平面时，显示一帧图像所需要的内存为（A、D）A.1M字节；B.8M字节；C.1M比特；D.8M比特；5.分辨率为1024*1024的显示器，其位平面数为24,则帧缓存的字节数应为（A）A.3MB ；B.2MB；C.1MB;D.512KB;6.下面对光栅扫描图形显示器描述正确的是：（A）A.荧光粉涂层均匀离散分布:B.是一种点画设备；C.电子束从顶到底扫描；D.通过控制电子束的强弱实现色彩的强弱；7.一个逻辑输入设备可以对应（C）物理输入设备。
一种有效的任意多边形裁剪算法
付迎春;袁修孝
【期刊名称】《计算机工程》
【年(卷),期】2006(32)7
【摘要】介绍了一种基于改进的Weiler 算法的任意多边形裁剪算法,该算法通过引入图形部件和合理的数据结构来组织裁剪后的多边形,减少了遍历多边形顶点链表的次数,并有效减少求交点的时间,具有占用存储空间少和处理速度快的特点.经过实例测试,算法对同时处理单个和多个任意多边形裁剪具有良好的稳定性、可靠性和较高的效率.
【总页数】3页(P278-280)
【作者】付迎春;袁修孝
【作者单位】武汉大学遥感信息工程学院,武汉,430079;武汉大学遥感信息工程学院,武汉,430079
【正文语种】中文
【中图分类】TP391
【相关文献】
1.GIS矩形网格中任意多边形裁剪算法 [J], 方志祥;李清泉;熊盛武
2.大规模等值线图任意多边形裁剪算法 [J], 周清平;陈学工
3.用VC＋＋实现的任意多边形裁剪算法 [J], 李海姣;张维锦
4.等值线图的任意多边形裁剪算法 [J], 陈学工;曹建;李源;张坤
5.一种任意多边形裁剪快速算法 [J], 杜月云;周子平;张云龙
因版权原因，仅展示原文概要，查看原文内容请购买。
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算法稍难，主要难在入、出点的查寻以及跨数组搜索上。
