计算机图形学(简单多边形裁剪算法).doc

简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理 简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。 以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。三、新算法设计1、算法的思想 本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。2、主要数据结构多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示，其涉及的数据结构主要如下：1）顶点或交点的数据结构：Vertex=double x，y；bool IslnPolygon；说明：Vertex用来存储多边形的顶点或交点，x，y表示顶点的坐标，IsInPolygon为true表示该点在多边形内部或在多边形边上，否则，表示该点在多边形外部。2）交点的前驱后继数据结构如下： CrossPointIndexint nPredecessorlndex=0前驱序号int nSuccessorIndex=0后继序号说明：CrossPointIndex用于记录交点在多边形中的前驱与后继的序号信息，以及记录同一交点在两个多边形中顶点序号。即若P为多边形S与多边形C的交点，为了表示P在S和C中为同一点，则可用CrossPointIndex记录用nPredecessorIndex记录P在S中的序号、用nSuccessorIndex记录P在C中序号。3）线段的数据结构如下：Segmentint 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=point1Elsep1=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;Else P1=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+ ;count+开始此点作一X轴正向射线选择一条边射线与此边有无交点是否多边形另一条边Count数值是奇数？IsInPolygon=trueIsInPolygon=False下一个被测点结束是否流程图如图1： 图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>CorrespondingCrossPointlndexSet，并用nPredecessorlndex记录S中顶点序号、nSuccessorlndex记录C中顶点序号。其中，以CrossPointlndexSetS和CrossPointlndexSetC中前驱序号为0的元素开始，交点序号在前驱序号的基础上顺序递增。根据交点的前驱后继集合信息，S和C点在S和C中的序号具有如下变化规律：NPredecessorIndex0=0Successorlndexi=nPredecessorlndexi+ni+1nPredecessorIndexi+1=nSuccessorIndexi+1i<N,N为原多边形顶点数式中：nPredecessorlndexi、nSuccessorIndexiS、C序号为i的顶点在S和C中序号，niS和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 第二阶段流程。第三阶段 对弧段集进行合并，生成并输出结果多边形。即：遍历SegmentSetS和SegmentSetC,利用CorrespondingCrossPointIndexSet交点在S和C的对应关系，将S和C互为相邻边或相交的线段连接起来。若SegmentSetS中某元素和SegmentSetC中某元素的值相等或者交叉相等，则表示为闭合多边形。将尾部元素放置到首部位置取交点集下一条元素开始正向遍历S与C并计算交点集CrossPointSet,生成前驱、后继信息并令IsInPolygon为true判断交点集中首尾元素是否相等？按倒序将交点集中元素插入到S和C中，建立多边形顶点序号关系释放交点集的空降，修改顶点序号集合中元素值按正向连接S和C中IsInPolygon为true的相邻点，生成线段集是否遍历线段集中元素，取线段i中点PP在C中或P在S中？删除线段集中第i号元素分别合并S和C中为相邻元素结束 图2 第二阶段流程线段连接算法如下：Int i,j;While（i<SegmentSetS.Size()） Segemnt seg1=SegmentSetSi+;Int nStart=seg1.nStartIndex;int nEnd=seg1.nEndIndex;for(j=0;j<CorrespondingCrossPointIndexSet.Size();j+)遍历CrossespondingCrossPointIndexSet,得到与S的nStart、nEnd序号相等顶点的C序号，用nStart和nEnd记录与S顶点相应的C顶点序号。此处，可以删除满足条件的CorrespondingCross PointIndexSet,减少下次循环次数 for(j=0；j<Polygon2segments.Count；j+)Segments seg2=SegmentSetCj；Segments seg3=SegmentsetCj+1；If(nStart=seg2.nStartIndex&nEnd=seg2.nEndIndex)若线段segl的起始节点与seg2的起始节点、segl的终止节点与seg2的终止节点相等，表示线段segl与seg2组成为一个相交多边形，那么只需将seg2中点倒序加入到segl点的后面即可，即点的顺序为：segl起始点segl中间点(顺序)segl终止点seg2中间点(倒序)。其中，括号中倒序则是按pIndexes元素序号从小到大的先后顺序插入，括号中的倒序则是按plndexes元素序号从大到小的顺序插入。后面的意义相同。else if(nStart=seg2.nEndIndex&nEnd=seg2.nStartlndex) 若线段segl的起始节点与seg2的终止节点、segl的终止节点与seg2的起始节点相等，表示线段seg1与seg2组成为相交多边形，那么只需将seg2中的点顺序加入到seg1点的后面即可，即点的顺序为：seg1的起始点seg1中间点（顺序）seg1终止点seg2中间点（顺序）。else if(nStart=seg2.nEndIndex&nEnd=seg3.nStartIndex)若线段seg1的起始节点与seg2的终止节点与seg3的起始节点相等，表示线段seg2-seg1-seg3为相交多边形的一部分，那么只需把线段seg1和seg3顶点和中间点追加到线段seg2后面即可，点的操作顺序为：seg1起始点（或seg2终止点）-seg1中间点（顺序）-seg1终止点（或seg3起始点）-seg3中间点（顺序）。同时，将seg3从SegmentSetC中删除。else if(nStart=seg2.nStartIndex&nEnd=seg3.nEndIndex) 若线段segl的起始节点与seg2的起始节点、segl的终止节点得到与seg3的终止节点相等，表示线段seg3一seglse92为相交多边形的一部分，那么只需把线段segl和seg2顶点和中间点追加到线段seg3后面即可，点的操作顺序为:seg1终止点（或seg3终止点）seg1中间点（倒序）seg起始点（或seg2起始点）seg2中间点（顺序）。同时，将seg2从SegmentSetC中删除。 至此算法结束，即可输出结果多边形。流程图如图3第三阶段流程J<CorrespondingCrossPointSet.Size()遍历顶点对应集合，得到与S的起始点相同的C中对应的序号，并删除顶点对应集合中满足条件的元素j=j+1开始i=0，j=0i<SegmentSetS.Size()Seg1=SegmentSetSi+nStart=seg1.nStartIndexnEnd=seg1.nEndIndexj=0i=i+1 将seg2中的点倒叙加入seg1点后面是是否是将seg1和seg3顶点和中间点追加到线段seg2后面，同时将seg3从SegmentSetC中删除否nStart=seg2.nStartIndex&nEnd=seg3.nEndIndex?将seg1和seg2顶点和中间点追加到线段seg3后面，将seg2从SegmentSetC中删除将seg2中点顺序加入到seg1点的后面nStart=seg2.nEndIndex&nEnd=seg2.nStartIndex?nStart=seg2.nEndIndex&nEnd=seg3.nStartIndex?是否j<Polygon2segments.Count?j =0Seg2=SegmentSetCiSeg3=SegmentSetj+1nStart=seg2.nStartIndex &nEnd=seg2.nEndIndex?输出结果多边形结束将seg2中的点倒叙加入seg1点后面是是否是将seg1和seg3顶点和中间点追加到线段seg2后面，同时将seg3从SegmentSetC中删除否nStart=seg2.nStartIndex&nEnd=seg3.nEndIndex?将seg1和seg2顶点和中间点追加到线段seg3后面，将seg2从SegmentSetC中删除将seg2中点顺序加入到seg1点的后面nStart=seg2.nEndIndex&nEnd=seg2.nStartIndex?nStart=seg2.nEndIndex&nEnd=seg3.nStartIndex?是否j<Polygon2segments.Count?j =0Seg2=SegmentSetCiSeg3=SegmentSetj+1nStart=seg2.nStartIndex &nEnd=seg2.nEndIndex?输出结果多边形结束是是否是将seg1和seg3顶点和中间点追加到线段seg2后面，同时将seg3从SegmentSetC中删除否nStart=seg2.nStartIndex&nEnd=seg3.nEndIndex?将seg1和seg2顶点和中间点追加到线段seg3后面，将seg2从SegmentSetC中删除将seg2中点顺序加入到seg1点的后面nStart=seg2.nEndIndex&nEnd=seg2.nStartIndex?nStart=seg2.nEndIndex&nEnd=seg3.nStartIndex?是否j<Polygon2segments.Count?j =0Seg2=SegmentSetCiSeg3=SegmentSetj+1nStart=seg2.nStartIndex &nEnd=seg2.nEndIndex?输出结果多边形结束图3 第三阶段流程四、总结 由于数据处理的需求、计算速度的需求和数据显示的需求，多边形裁剪算法对于提高图形的处理效率和质量将会产生重要的意义，由于其现实的需求问题，多边形裁剪算法必将会朝着更高效、更具适用性的方向发展。 纵观这几年多边行裁剪算法的发展，有Cohen-Sutherland算法、中点分割算法、Liang-Barsky算法、Foley算法、Sutherland-Hodgman算法、Maillot算法、Andereev算法等，以上几种算法只适用于矩形窗口的裁剪，而在具体的工程中，往往遇到的裁剪窗口都是任意多边形，这类裁剪算法主要有Weiler-Atherton算法、Vatti算法和Greiner-Hormann算法。其中，Weiler-Atherton算法最为成熟，并且功能比较强大，速度比较快，目前国内大多数多边形算法也都在它的基础上派生而来。而本文综合考虑现有多边形裁剪算法的优缺点，提出了一种基于多边形顶点遍历的简单多边形裁剪算法。本算法通过采用矢量数组结构、遍历多边形顶点并记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，而无需考虑输入多边形的方向、形状等，即可很好地处理多边形边重合、边顶点相交等特殊的情况，实现多边形裁剪。结果表明，本算法具有算法简单、易于实现、运行效率高的特点。参考文献1 赵红波，张涵，一种等值线图的任意复杂多边形窗口裁剪算法J.计算机工程与应用，2012,48（32）：170-175.2陈占龙，吴亮，刘焕焕.基于排序边表的简单要素模型多边形裁剪算法J.微电子与计算机，2012,29（9）：145-148.3刘勇奎，高云，黄有群.一个有效的多边形裁剪算法J.软件学报，2003,14（4）：845-856.4罗畏，邹峥嵘.一种基于圆形窗口的多边形裁剪算法J.测绘科学，2011,36（3）：234-235.5王结臣，、沈定涛，陈焱明等.一种有效复杂多边形裁剪算法J.武汉大学学报（信息科学版），2010,53（3）：369-372.6周海平，陈学工.大规模等值线图形任意多边形裁剪算法J.计算机与现代化，2012（4）：196-200.7刘民士，江平，射线法判断点与包含简单曲线多边形关系改善J.测绘科学，2009,34（5）:220-222.8刘民士，王春.射线法判断点与多边形内外关系的改进算法J.滁州学院学报，2010,12(2):14-16.9刘雪娜，侯宝明.复杂多边形窗口的多边形裁剪的改进算法J.计算机与现代化,2009（11）:36-38.10彭杰，刘南，唐远彬，等，一种基于交点排序的高效多边形裁剪算法J.浙江大学学报（理学版），2012,39(1):107-111.