下载文档原格式
![4.6.3 多边形裁剪_计算机图形学教程（第2版）_[共3页]](https://img.taocdn.com/s1/m/a0cbdc0749649b6649d74720.png)
153 作为新的P 1P 2线段从算法的第一步重新开始执行。
反之，则以线段P m P 2为新的线段P 1P 2（如图4.83中的线段c ）从算法的第一步重新开始执行。
反复执行上述3步，直至找到离P 1点最远的可见点为止。
这个过程确定了距离P 1点最远的可见点。
然后对调该线段的两个端点，以线段P 2P 1为新的P 1P 2线段，重新开始实施该算法过程，就可以确定出距离P 2点最远的可见点。
这样，位于窗口内可见段的两个可见端点就确定了。
从这个算法我们可以看到，整个裁剪过程总是在执行第一步或第二步时结束。
这种结果表明：被裁剪的线段要么完全处于窗口之外而被排除掉；要么能在窗口内得到一个距对应端点最远的可见点，这个可见点可能是原直线段的一个端点，也可能是线段在被不断地中点再分过程中，最终得到的刚好和窗口边框相重的那个中点。
这里要注意的是：在判断中点和窗口边框相重时，一般不需要坐标值一定相等，也不大可能，只要在精度许可的前提下，给出一个误差允许范围即可。
4.6.3 多边形裁剪前面我们讨论了直线段裁剪，多边形裁剪是以直线段裁剪为基础，但又不同于直线段的裁剪。
多边形裁剪要比一条直线段裁剪复杂得多。
图4.84所示为用一个矩形窗口去裁剪多边形将会遇到各种不同情况，其中图4.84（a ）所示为一个完整的多边形被裁剪成两个独立的多边形；图4.84（b ）所示为一个凹多边形被裁剪成几个小多边形；图4.84（c ）所示为多边形G 经矩形窗口裁剪后出现G 1和G 2两个多边形，究竟是G 1还是G 2呢？裁剪多边形要解决两个问题，一是一个完整的封闭多边形经裁剪后一般不再是封闭的，需要用窗口边界适当部分来封闭它；二是矩形窗口的4个角点在裁剪中是否要与其他交点连线。
由于这两个问题使得我们不能简单地应用直线段裁剪方法，而需要去研究适合多边形裁剪特点的算法。
图4.84 多边形裁剪多边形裁剪方法很多，例如逐边裁剪法、双边裁剪法、分区编码裁剪法等，这里仅介绍逐边裁剪法。
weiler-atherton多边形裁剪算法weileratherton多边形裁剪算法，又称为weiler-atherton算法，是一种用于对多边形进行裁剪的算法。
它可以被用于计算机图形学中的裁剪任务，如可视化、图像处理和计算机辅助设计等领域。
本文将详细介绍weileratherton多边形裁剪算法的原理、步骤和实现方法。
1. 算法原理：weileratherton多边形裁剪算法是基于边界点的引入和处理的。
该算法将两个多边形相互之间进行裁剪，并生成裁剪结果。
算法使用四个边界点集合，分别为输入多边形的边界点集合(输入多边形顶点经过一系列处理得到)，裁剪多边形的外部边界点集合和内部边界点集合，以及裁剪结果的边界点集合。
2. 算法步骤：weileratherton多边形裁剪算法的具体步骤如下：(1) 初始化：创建输入多边形的边界点集合、裁剪多边形的外部边界点集合和内部边界点集合，并将输入多边形的边界点添加至外部边界点集合中。
(2) 遍历输入多边形的每条边：对于输入多边形的每条边，判断其与裁剪多边形的相交情况。
(3) 相交情况处理：若相交情况为内部相交或外部相交，则根据交点生成新的内部边界点，并添加至相应的边界点集合中。
(4) 构造裁剪结果：根据输入多边形的边界点集合和裁剪多边形的内部边界点集合，生成裁剪结果的边界点集合。
(5) 根据边界点集合构造裁剪结果：根据裁剪结果的边界点集合，绘制裁剪结果多边形。
3. 算法实现：weileratherton多边形裁剪算法的实现可以使用编程语言来完成。
一种常用的实现方法是通过遍历输入多边形的每个边，利用线段与裁剪多边形的边界的相交情况判断是否产生交点，并根据交点生成新的边界点。
具体的实现步骤如下：(1) 初始化输入和裁剪多边形的边界点集合。
(2) 遍历输入多边形的每条边，对于每条边，判断其与裁剪多边形的每条边的相交情况。
(3) 根据相交情况，判断是否生成交点，如果有生成交点，则根据交点生成新的边界点，并添加至相应的边界点集合中。
简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。
本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。
通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。
关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。
其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。
二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。
因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。
以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。
为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。
它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。
三、新算法设计1、算法的思想本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。
了解电脑显卡的多边形剪裁和裁剪随着计算机图形学的不断发展，电脑显卡在图像处理方面的性能也逐渐提升。
而多边形剪裁和裁剪则是电脑显卡中重要的技术之一。
本文将介绍多边形剪裁和裁剪的定义、作用以及相关的算法与技术。
一、多边形剪裁和裁剪的定义多边形剪裁是指根据视口和裁剪窗口的位置，将位于裁剪窗口外的多边形剪除，只保留位于窗口内的部分。
而裁剪是指将多边形按照裁剪窗口的形状进行修剪，以适应显示设备的输出。
二、多边形剪裁的作用多边形剪裁的作用主要有以下几个方面：1. 提高渲染效率：多边形剪裁可以剔除位于屏幕外的多边形，避免不必要的计算和绘制，从而提高渲染效率。
2. 减少像素填充：在3D渲染中，所有多边形都要经过像素填充来生成最终的图像。
通过剪裁掉屏幕外的多边形，可以减少不必要的像素填充操作，提高渲染速度。
3. 实现可视化效果：多边形剪裁可以确保只显示用户所需的图像内容，可以实现视点的选择、物体的隐藏和透视等视觉效果。
三、多边形剪裁的算法与技术在实际应用中，多边形剪裁通常使用的算法包括：1. 逐边裁剪算法（Cohen-Sutherland算法）：该算法通过将裁剪窗口划分为9个区域，将多边形的每条边与裁剪窗口的边界相交，并根据交点位置来确定多边形是否可见以及如何修剪多边形。
2. 多边形切割算法（Sutherland-Hodgman算法）：该算法通过对多边形的每条边进行切割，生成新的多边形。
这些新的多边形通过裁剪窗口切割并连接，最终得到位于裁剪窗口内的多边形。
四、裁剪的应用和技术裁剪不仅可以应用于多边形，还可以应用于曲线、曲面和体素等图形对象的裁剪。
裁剪的技术也不仅仅局限于多边形剪裁算法，还包括对二维和三维对象的参数化、位图和文本的裁剪处理等。
在实际应用中，常用的裁剪技术包括：1. 区域编码算法：区域编码算法通过给定的区域码来标识物体所在的位置，从而对物体进行裁剪。
常见的算法有四叉树编码和八叉树编码。
2. 软件裁剪和硬件裁剪：软件裁剪是指在计算机的主机CPU上通过算法进行裁剪操作；而硬件裁剪则是指使用专门的图形处理器（GPU）来完成裁剪操作，通过并行计算提高裁剪效率。
河南理工大学万方科技学院课程设计报告2010 — 2011学年第二学期课程名称计算机图形学设计题目多边形裁剪算法学生姓名孙晓芳学号**********专业班级计算机科学与技术10升指导教师侯守明2011 年6 月29 日目录目录目录 (I)第1章程序运行环境................................................................................... 错误!未定义书签。
1.1 程序运行环境的简单介绍................................................................. 错误!未定义书签。
1.2 程序运行环境的安装......................................................................... 错误!未定义书签。
1.3 多边形裁剪算法设计的内容........................................................................... 第2章直线裁剪和多边形裁剪的简单比较 (4)2.1 直线裁剪的介绍 (4)2.1.1 直线裁剪的基本原理………………………………………......................................2.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算……………………………..2.2 多边形裁剪介绍 (9)2.2.1 多边形裁剪的基本思想……………………………………………………………..2.2.2 多边形和窗口相交的判定方法…………………………………………..第3章多边形裁剪方法的详细介绍 (12)3.1 Sutherland-Hodgman算法………………………………………………………………….3.2 多边形裁剪算法的流程图 (12)3.3多边形裁剪算法的实现 (13)第4章代码的实现 (14)第5章总结 (21)参考文献 (22)第1章程序的运行环境1.1 程序运行环境的简单介绍本次设计主要是运用了程序设计语言主要以C/C++语言为主，开发平台为Visual C++。
多边形裁剪刘世光天津大学计算机学院天津大学计算机科学与技术学院主要内容•多边形裁剪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算法•算法的不足之处：算法的不足之处裁剪凹多边形时，可能显示一条多余的直线，原因是该算法只有一个输出顶点队列。
多边形裁剪的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;求交点并放入新的多边形顶点序列Qj中；j++；}将当前顶点放入新的多边形顶点序列Qj中：Qj=Pi；j++；}else{if(flag==0){flag=1;求交点并放入新的多边形顶点序列Qj中；j++；}}将当前顶点赋给S：S=Pi；}4．做返回准备：将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中：P=Q；将新的多边形顶点数j放回原多边形顶点数n中：n=j；///////////////////////////////////////////////////////////////////// ///////////////////-----多边形裁剪的Sutherland—Hodgman算法---------/////////////////////////////////////////////////////////////////////// ////////////////void CMyClip_AView::ClipedgeL(CPoint polypoint[], CPoint clipwindow[], UINT polynum)/*其中参数polypoint[]为多边形顶点,clipwindow[]为裁剪窗口顶点,polynum 为多边形顶点数目*/{//找出裁剪窗口边界long xl,xr,yt,yb;UINT i;xl=clipwindow[0].x;xr=clipwindow[0].x;yt=clipwindow[0].y;yb=clipwindow[0].y;for(i=1;i<=4;i++){if(xl>clipwindow[i].x)xl=clipwindow[i].x;if(xr<clipwindow[i].x)xr=clipwindow[i].x;if(yb>clipwindow[i].y)yb=clipwindow[i].y;if(yt<clipwindow[i].y)yt=clipwindow[i].y;}//CPoint B[Polygon_Num],C[Polygon_Num];UINT m_nA,m_nB;int x,y;long tem1,tem2;m_nA=polynum;/*记载原始多边形顶点顶点个数*/m_nB=0;/*记载新生成多边形顶点顶点个数*/for(i=0;i<m_nA;i++){if(polypoint[i].x<xl && polypoint[i+1].x<xl) /*判断的多边形边两个端点都在外部，不做处理*/{continue;/*如果是这种情况，那么就对继续对下一条多边形边作判断，也就是说下面的判断不用做了*/}if(polypoint[i].x>=xl && polypoint[i+1].x>=xl) /*边两个端点都在内部，保留*//*因为每个保留的点在数组中只出现一次，且下一次判断时第二个端点一定会要取到，因此只保留的两个点中的第一个*/{B[m_nB].x =polypoint[i].x ;B[m_nB].y =polypoint[i].y ;m_nB=m_nB+1;continue;}if(polypoint[i].x<xl && polypoint[i+1].x>=xl)/*边两个端点起点在外部，终点在内部，求交点，然后交点，终点都应该送入临时数组*/{/*保留交点*/x=xl;tem1=(xl-polypoint[i].x);//tem2=(xl-x1)*dy/dx+y1;//y/x=dy/dx---->y=x*dy/dxtem2=tem1*(polypoint[i+1].y-polypoint[i].y)/(polypoint[i+1].x-polypoint[i].x)+polypoi nt[i].y;y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB=m_nB+1;continue;}if(polypoint[i].x>=xl && polypoint[i+1].x<xl)/*起点在内部，终点在外，求交点，然后起点，交点送入临时数组*/{ /*保留内部点*/B[m_nB].x =polypoint[i].x ;B[m_nB].y =polypoint[i].y ;m_nB=m_nB+1;/*保留交点*/tem1=(xl-polypoint[i].x);tem2=tem1*(polypoint[i+1].y-polypoint[i].y)/(polypoint[i+1].x-polypoint[i].x)+polypoi nt[i].y;y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB=m_nB+1;continue;}}//把第一个点的数据拷贝到最后//形成裁剪后的多边形if(i==m_nA){B[m_nB]=B[0];}//下------------------m_nA=0;for(i=0;i<m_nB;i++){if(B[i].y<yb && B[i+1].y<yb)//两个点全在下方{continue;//下一条边}if(B[i].y>=yb && B[i+1].y>=yb)//p1,p2都在yb上方{C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;continue;}if(B[i].y<yb && B[i+1].y>=yb)//p1在下，P2在上,留交点，外－＞内{y=yb;tem1=yb-B[i].y;//tem2=x1+(yb-y1)*dx/dytem2=tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y) + B[i].x;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}if(B[i].y>=yb && B[i+1].y<yb)//p1在上方，P2在下方，留P1和交点,内－外{//save p1C[m_nA].x=B[i].x;C[m_nA].y=B[i].y;m_nA++;//留交点y=yb;tem1=yb-B[i].y;//tem2=x1+(yb-y1)*dx/dytem2=tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y)+B[i].x;x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}}//形成第二次裁剪多边形if(i==m_nB){C[m_nA]=C[0];}//右------------------m_nB=0;for(i=0;i<m_nA;i++){if(C[i].x>xr && C[i+1].x>xr)//P1，P2都在右方--go next{continue;}if(C[i].x<=xr && C[i+1].x<=xr)//P1，P2都在左方，留P1{B[m_nB].x =C[i].x;B[m_nB].y =C[i].y;m_nB++;continue;}if(C[i].x>xr && C[i+1].x<=xr)//P1在右方，P2在左方，留交点{x=xr;tem1=C[i].x-xr;tem2=C[i].y-tem1*(C[i+1].y-C[i].y)/(C[i+1].x-C[i].x);y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB++;continue;}if(C[i].x<=xr && C[i+1].x>xr)//P1在内，P2在外，留P1和交点{//save p1B[m_nB].x =C[i].x;B[m_nB].y =C[i].y;m_nB++;//save 交点x=xr;tem1=C[i].x-xr;tem2=C[i].y-tem1*(C[i+1].y-C[i].y)/(C[i+1].x-C[i].x);y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB++;continue;}}//三次裁剪后的新多边形if(i==m_nA){B[m_nB]=B[0];}//上-------------------m_nA=0;for(i=0;i<m_nB;i++){if(B[i].y>yt && B[i+1].y>yt)//p1,p2都在上方,next{continue;}if(B[i].y<=yt && B[i+1].y<=yt)//p1,p2都在下方,留P1{C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;continue;}if(B[i].y>yt && B[i+1].y<=yt)//P1在上方，P2在下方外－＞内,留交点{y=yt;tem1=B[i].y-yt;//tem2=x1+(yb-y1)*dx/dytem2=B[i].x-tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y);x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}if(B[i].y<=yt && B[i+1].y>yt)//P1在下方，P2在上方，内－＞外，留P1和交点{//save p1,,,C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;//save 交点y=yt;tem1=B[i].y-yt;//tem2=x1+(yb-y1)*dx/dytem2=B[i].x-tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y);x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}}//形成裁剪后的多边形if(i==m_nB){C[m_nA]=C[0];}CClientDC dc(this);CPen tempen;tempen.CreatePen(PS_SOLID,1,RGB(255,0,0));dc.SelectObject(tempen);dc.MoveTo(C[0]);for(i=1;i<=m_nA;i++){dc.LineTo(C[i]);}}//.....。
简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。
本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。
通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。
关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。
其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。
二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。
因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。
以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。
为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。
它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。
三、新算法设计1、算法的思想本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。
算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。
2、主要数据结构多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。
兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。
裁剪多边形和被裁剪多边以下我们分别用S和C表示，其涉及的数据结构主要如下：1）顶点或交点的数据结构：Vertex={double x，y；bool IslnPolygon；}说明：Vertex用来存储多边形的顶点或交点，x，y表示顶点的坐标，IsInPolygon为true表示该点在多边形内部或在多边形边上，否则，表示该点在多边形外部。
2）交点的前驱后继数据结构如下：CrossPointIndex{int nPredecessorlndex=0／／前驱序号int nSuccessorIndex=0／／后继序号}说明：CrossPointIndex用于记录交点在多边形中的前驱与后继的序号信息，以及记录同一交点在两个多边形中顶点序号。
即若P为多边形S与多边形C的交点，为了表示P在S和C中为同一点，则可用CrossPointIndex记录用nPredecessorIndex记录P在S中的序号、用nSuccessorIndex记录P在C中序号。
3）线段的数据结构如下：Segment{int nStartIndex=0int nEndIndex=0int* pIndexes;int nIndexCount;}说明：Segment表示多边形在另一个多边形内(外)的线段，nStartaIndex 为Segment起始顶点的序号，nEndIndex为Segment终止顶点的序号，pIndexes 为起始顶点与终止顶点之间的顶点序号集合，nIndexCount为pIndexes中元素个数。
3、算法设计1）第一阶段：采用射线法计算并判断S（或C）在C（或S）内，并修改S（或C）顶点Vertex的IsInPolygon的值。
由于射线可以任意选取，为了方便可以将射线定为从被测点开始射向X轴坐标正方向的水平射线。
由于多边形的一条边与射线的交点最为1个，因此可以循环遍历每条边并判断边与射线有无交点，若有交点，计数器加1,。
最后得到的计数器的值即多边形与射线的交点个数。
若交点个数为奇数，则被测点在多边形内部，若交点个数为偶数，则被测点在多边形外部。
对于多边形的任意一条边，为了尽量避免求交点时用到乘除法，将判断该边与射线有无交点的算法可以包含3步：1)判断边的两个顶点是否均在被测点左方或者下方或者上方，若是则无交点，返回假并退出；2)若不满足第一条原则，且满足两个顶点均在被测点右方，则一定有顶点，返回真并退出；3)若以上两条都不满足，求出边与射线的交点，比较交点的X坐标与被测点的X坐标，若前者大于后者则返回真并退出，否则返回假并退出。
设边的两个顶点坐标分别为（x1,y1）和（x2,y2）,则边的直线方程可写为： X=m(y-y1)+x1其中，m=（x2-x1）/(y2-y1)为直线斜率的倒数。
使用该方程时需要两次乘除法，效率较低。
为了尽量避免求交点，第三部可以采用二分法将边分成两段，对其中两个端点分别跨过射线两侧的边段重新进行以上第一步和第二步的判断，若以上两步中还没有推出，再继续二分，直到能够被第一步和第二步判断并退出。
采用二分法则避免了乘除法，算法中只有除2运算和一些判断，适合于硬件处理，二分法的循环次数一般较少，当被测点位于边上时，循环次数组最多。
其具体的算法如下：（Point为被测点变量，point1、point2为一条边的两个端点变量）If(piont2.y<point1.y){P1=point2;p2=point1}Else{p1=point1;p2=point2;}if(p1.y>point.y||p2.y<point.y) //两个端点都在被测点上方或者下方Return false;//无交点Else If(p1.x<point.x&&p2.x<point.x) //当两个端点都在被测点左方时 Return false ；无交点Else if （p1.x>point.x&&p2.x>point.x）{Return true；有交点Count++；}Else {M=MyPoint((p1.x+p2.x)/2,(p1.y+p2.y)/2)//得到边的中点If（M.y>point.y）P2=M;ElseP1=M;If(p2.x>p1.x) //当p2在p1的右方时{If（p2.x<point.x） //当p2在被测点左方时，无交点Return false；If（P1.x>point.x）//当p1在被测点右方时，有交点{ Return true;count++；}}Else //当P2在P1右方时{If（P1.X<point.x）//当P1在被测点左方时，无交点Return false；If(p2.x>point.x)//当P2在被测点右方时，有交点{Return true;count++ ;}}}图1.射线法判断点的位置2）第二阶段按正方向遍历S与C，计算S与C的交点集，交点的前驱后继信息、交点在S 和C中的对应关系，以及相交多边形弧段集；﹡步骤1：按正向方向遍历S与C并计算交点集Vector<Vertex>CrossPointSet,同时生成交点在S和C中前驱，后继信息Vector<CrossPointIndex>CrossPointIndexSetS 和Vector<CrossPointIndex>CrossPointIndexSetC.其中，CrossPointSet中元素IsInPolygon的值为true。
﹡步骤2 ;判断CrossPointIndexSetS或CrossPointIndexSetC中首尾元素的nPredecessorIndex与nSuccessorIndex值是否相等。
若想等，则将尾部元素放置到首部位置。
重复判断操作，直到首尾元素值不相等为止。
﹡步骤3：按倒序将CrossPointIndexSetS和CrossPointIndexSetC中元素插入到S 和Czhong ,计算原多边形顶点的序号信息，并建立交点在两个多边形中顶点序号关系集合。
假设插入交点后的S和C成为S’和C’。
插入同时，建立交点在S’和C’中顶点序号对应集合Vector<CrossPointlndex>CorrespondingCrossPointlndexSe t，并用nPredecessorlndex记录S’中顶点序号、nSuccessorlndex记录C’中顶点序号。
其中，以CrossPointlndexSetS和CrossPointlndexSetC中前驱序号为0的元素开始，交点序号在前驱序号的基础上顺序递增。
根据交点的前驱后继集合信息，S和C点在S’和C’中的序号具有如下变化规律：NPredecessorIndex[0]=0Successorlndex[i]=nPredecessorlndex[i]+ni+1nPredecessorIndex[i+1]=nSuccessorIndex[i]+1i<N,N为原多边形顶点数式中：nPredecessorlndex[i]、nSuccessorIndex[i]——S、C序号为i的顶点在S’和C’中序号，ni——S和C中序号为i与i+1之间的交点个数﹡步骤4 :释放CrossPointIndexSetS和CrossPointIndexSetC空间，修改交点对应集合CorrespondingCrossPointIndexSet的元素值。
﹡步骤5 :按正方向分别连接S’和C’中Vertex的IsInPolygon为true且相邻的顶点，生成线段集Vector<Segnment>SegmentSetS和Vector<Segment>SegmentSetC.步骤6 遍历SegmentSetS元素并取第i号元素的中点Pi，采用射线法判断Pi是否在C中，若不在C中，则删除SegmentSetS中第i号元素。
同理，删除SegmentSetC 中元素的中点不在S’中的项，﹡步骤7 分别合并SegmentSetS和SegmentSetC中为相邻元素。
流程图如图2 第二阶段流程。
第三阶段对弧段集进行合并，生成并输出结果多边形。
