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

1简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。三、新算法设计1、算法的思想本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。算法数据结构简单，即没有用常用的数据结构，如线性链表结构、双向链表结构和树形结构，这样就节省了存储空间，增加算法的效率。2、主要数据结构多边形裁剪算法的核心是数据结构，它决定了算法的复杂度和计算效率。兼顾数据结构简单和节省存储空间的目的，简单多边形裁剪算法是基于矢量数组vector的数据结构进行裁剪的，多边形矢量数组的每个元素表示多边形顶点，且按顶点输入的顺序存储。裁剪多边形和被裁剪多边以下我们分别用S和C表示，2其涉及的数据结构主要如下：1）顶点或交点的数据结构：Vertex={doublex，y；boolIslnPolygon；}说明：Vertex用来存储多边形的顶点或交点，x，y表示顶点的坐标，IsInPolygon为true表示该点在多边形内部或在多边形边上，否则，表示该点在多边形外部。2）交点的前驱后继数据结构如下：CrossPointIndex{intnPredecessorlndex=0／／前驱序号intnSuccessorIndex=0／／后继序号}说明：CrossPointIndex用于记录交点在多边形中的前驱与后继的序号信息，以及记录同一交点在两个多边形中顶点序号。即若P为多边形S与多边形C的交点，为了表示P在S和C中为同一点，则可用CrossPointIndex记录用nPredecessorIndex记录P在S中的序号、用nSuccessorIndex记录P在C中序号。3）线段的数据结构如下：Segment{intnStartIndex=0intnEndIndex=0int*pIndexes;intnIndexCount;}说明：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回真并退出；3)若以上两条都不满足，求出边与射线的交点，比较交点的X坐标与被测点的X坐标，若前者大于后者则返回真并退出，否则返回假并退出。设边的两个顶点坐标分别为（x1,y1）和（x2,y2）,则边的直线方程可写为：X=m(y-y1)+x1其中，m=（x2-x1）/(y2-y1)为直线斜率的倒数。使用该方程时需要两次乘除法，效率较低。为了尽量避免求交点，第三部可以采用二分法将边分成两段，对其中两个端点分别跨过射线两侧的边段重新进行以上第一步和第二步的判断，若以上两步中还没有推出，再继续二分，直到能够被第一步和第二步判断并退出。采用二分法则避免了乘除法，算法中只有除2运算和一些判断，适合于硬件处理，二分法的循环次数一般较少，当被测点位于边上时，循环次数组最多。其具体的算法如下：（Point为被测点变量，point1、point2为一条边的两个端点变量）If(piont2.ypoint1.y){P1=point2;p2=point1}Else{p1=point1;p2=point2;}if(p1.ypoint.y||p2.ypoint.y)//两个端点都在被测点上方或者下方Returnfalse;//无交点ElseIf(p1.xpoint.x&&p2.xpoint.x)//当两个端点都在被测点左方时Returnfalse；无交点Elseif（p1.xpoint.x&&p2.xpoint.x）{Returntrue；有交点Count++；}Else{M=MyPoint((p1.x+p2.x)/2,(p1.y+p2.y)/2)//得到边的中点If（M.ypoint.y）P2=M;ElseP1=M;If(p2.xp1.x)//当p2在p1的右方时{If（p2.xpoint.x）//当p2在被测点左方时，无交点Returnfalse；If（P1.xpoint.x）//当p1在被测点右方时，有交点{Returntrue;count++；}4}Else//当P2在P1右方时{If（P1.Xpoint.x）//当P1在被测点左方时，无交点Returnfalse；If(p2.xpoint.x)//当P2在被测点右方时，有交点{Returntrue;count++;}}}流程图如图1：图1.射线法判断点的位置count++开始此点作一X轴正向射线选择一条边射线与此边有无交点是否多边形另一条边Count数值是奇数？IsInPolygon=trueIsInPolygon=False下一个被测点结束是否52）第二阶段按正方向遍历S与C，计算S与C的交点集，交点的前驱后继信息、交点在S和C中的对应关系，以及相交多边形弧段集；﹡步骤1：按正向方向遍历S与C并计算交点集VectorVertexCrossPointSet,同时生成交点在S和C中前驱，后继信息VectorCrossPointIndexCrossPointIndexSetS和VectorCrossPointIndexCrossPointIndexSetC.其中，CrossPointSet中元素IsInPolygon的值为true。﹡步骤2;判断CrossPointIndexSetS或CrossPointIndexSetC中首尾元素的nPredecessorIndex与nSuccessorIndex值是否相等。若想等，则将尾部元素放置到首部位置。重复判断操作，直到首尾元素值不相等为止。﹡步骤3：按倒序将CrossPointIndexSetS和CrossPointIndexSetC中元素插入到S和Czhong,计算原多边形顶点的序号信息，并建立交点在两个多边形中顶点序号关系集合。假设插入交点后的S和C成为S’和C’。插入同时，建立交点在S’和C’中顶点序号对应集合VectorCrossPointlndexCorrespondingCrossPointlndexSet，并用nPredecessorlndex记录S’中顶点序号、nSuccessorlndex记录C’中顶点序号。其中，以CrossPointlndexSetS和CrossPointlndexSetC中前驱序号为0的元素开始，交点序号在前驱序号的基础上顺序递增。根据交点的前驱后继集合信息，S和C点在S’和C’中的序号具有如下变化规律：NPredecessorIndex[0]=0Successorlndex[i]=nPredecessorlndex[i]+ni+1nPredecessorIndex[i+1]=nSuccessorIndex[i]+1iN,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且相邻的顶点，生成线段集VectorSegnmentSegmentSetS和VectorSegmentSegmentSetC.步骤6遍历SegmentSetS元素并取第i号元素的中点Pi，采用射线法判断Pi是否在C中，若不在C中，则删除SegmentSetS中第i号元素。同理，删除SegmentSetC中元素的中点不在S’中的项，﹡步骤7分别合并SegmentSetS和SegmentSetC中为相邻元素。流程图如图2第二阶段流程。第三阶段对弧段集进行合并，生成并输出结果多边形。即：遍历SegmentSetS和SegmentSetC,利用CorrespondingCrossPointIndexSet交点6在S’和C’的对应关系，将S’和C’互为相邻边或相交的线段连接起来。若SegmentSetS中某元素和SegmentSetC中某元素的值相等或者交叉相等，则表示为闭合多边形。是将尾部元素放置到首部位置取交点集下一条元素开始正向遍历S与C并计算交点集CrossPointSet,生成前驱、后继信息并令IsInPolygon为true判断交点集中首尾元素是否相等？按倒序将交点集中元素插入到S和C中，建立多边形顶点序号关系释放交点集的空降，修改顶点序号集合中元素值按正向连接S’和C’中IsInPolygon为true的相邻点，生成线段集否遍历线段集中元素，取线段i中点PP在C中或P在S中？删除线段集中第i号元素7图2第二阶段流程线段连接算法如下：Inti,j;While（iSegmentSetS.Size()）{Segemntseg1=SegmentSetS[i++];IntnStart=seg1.nStartIndex;intnEnd=seg1.nEndIndex;for(j=0;jCorrespondingCrossPointIndexSet.Size();j++){遍历CrossespondingCrossPointIndexSet,得到与S’的nStart、nEnd序号相