多边形裁剪算法研究与实现

多边形的裁剪算法在计算机图形学中占有很重要的地位,在其他领域也有重要应用。本文深入研究了多边形裁剪的两种典型算法,用C语言实现了算法,并列出具体实例来参照算法的执行。     

IPC平面裁剪算法的设计与实现

Sutherland—Hodgman算法是平面裁剪中常用的一种算法,其以顶点序列为基准,对多边形进行逐边裁剪,算法实现简单、效率高,但不适用于对凹多边形进行裁剪。文中以Sutherland-Hodgman算法（文中称为预处理算法）思想为基础,提出了一种亦可对凹多边形进行裁剪的综合多边形裁剪（Integrated Polygon Clip,IPC）算法,实现了对多边形裁剪的统一化操作。介绍了平面裁剪的使用对象,预处理裁剪算法的原理及实现关键步骤,分析了该算法用于对凹多边形裁剪的局限性,在此基础上提出一种适用于任意多边形裁剪的算法。以例证的方式演示了算法的过程,验证了算法的正确性。验证结果表明IPC算法实现了对多边形的统一裁剪。     

无重迭边的可重入多边形裁剪算法

本文提出一种在标准 Sutherland—Hodgman 多边形裁剪算法基础上扩充的重迭边消去算法。本算法在沿着窗口边沿直线对多边形的各边进行裁剪的时候,建立了一个中间结果顶点队列和一个交点队列,然后通过顶点追溯方法产生出作为裁剪结果的一列子多边形.这些子多边形的定义方式与输入多边形相同,不存在重迭的边,而且仍然保持可重入性.     

用VC++实现的任意多边形裁剪算法

提出了一个用VC++语言实现的凸多边形、凹多边形,也可以是带内环的多边形的裁剪算法,可以求上述多边形的"交"、"并"以及"差".首先,该算法使用VC++支持的CObList类和CArray类的对象存储数据,具有占用内存空间少及处理速度快的特点;再通过算法和数据结构的设计不仅使得多边形顶点可按顺时针方向或逆时针方向输入,而且减少了求解过程中对多边形顶点数据的遍历次数;基于判断和计算交点是裁剪算法的主要工作,文中引入了求交前的预处理,避免了大量不必要的求交,降低了算法的时间复杂度.最为重要的是该算法不需要对两多边形的边重合或两多边形在顶点处相交的情况作特殊处理.     

基于VC的任意不自相交多边型新裁剪算法

计算机图形学的基础经典裁剪算法的改进是添加一些附加的判断条件以提高效率或只是适用于某种特殊条件环境的应用。对常用的线段裁剪算法和多边形之间的裁剪算法进行简单的原理描述与比较,提出一个新的任意不自相交多边形之间的裁剪算法,该算法以基本线段单元为控制对象,在线段求交中使用梁友栋-barskey算法,然后从裁剪之后的线段单元组中寻找多边形的线段单元组合。分带环多边形之间的裁剪和不带环多边形之间的裁剪来详细描述算法的实施步骤和算法流程;最后用C++语言实现该裁剪算法,结合工程应用解决了多边形裁剪实例,通过测试证明该算法对不自相交多边形之间的裁剪是很有效的,同时使用该算法解决了多边形与折线之间的裁剪问题,改善工程应用。     

一种有效的任意多边形裁剪算法

介绍了一种基于改进的Weiler算法的任意多边形裁剪算法，该算法通过引入图形部件和合理的数据结构来组织裁剪后的多边形，减少了遍历多边形顶点链表的次数，并有效减少求交点的时间，具有占用存储空间少和处理速度快的特点。经过实例测试，算法对同时处理单个和多个任意多边形裁剪具有良好的稳定性、可靠性和较高的效率。     

介绍一种多边形裁剪算法

本文详细地介绍了一种多边形裁剪新算法，窗口可以是任意凸多边形，被裁剪的多边形可以是任意凹或凸的多边形，     

大规模等值线图的任意简单多边形窗口裁剪算法

针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数;同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点;同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.     

复杂多边形窗口的多边形裁剪的改进算法

多边形裁剪是计算机图形学中较为热点研究的问题,针对复杂多边形窗口的复杂多边形裁剪提出一个可靠有效算法。算法通过添加虚边来消去孔洞,并且为恢复裁剪结果的原貌改进了遍历方法。新的遍历算法只需遍历多边形一次就可巧妙地求得所有裁剪结果,并恢复带孔洞的裁剪结果的内外边界的拓扑结构,无需解环、并环,也不用对裁剪边界重新组合。     

具有拓扑关系的任意多边形裁剪算法

多边形－弧段－结点之间的联系是描述多边形空间拓扑关系的重要方法,为了维护裁剪前后这种拓扑关系的正确与继承性,本文在Ｗｄｉｌｅｒ－Ａｔｈｅｒｔｏｎ算法的基础上提出了一种新的算法。新算法中主要特点是将原算法中的交点表改为交点、弧段混合表,沿用原算法的追踪方式,但追踪目标由顶点序列改为弧段序列,使之适应具有空间拓扑关系的任意多边形的裁剪要求。     

A parallel polygon-clipping algorithm

We describe a new parallel polygonclipping algorithm based on a novel technique that allows a processor to compute output vertices independently of the results of the other processors. The basis for the method is a collision-free labeling scheme to compute the labels of the vertices of the output polygon. This labeling scheme depends only on the id of the vertices of the output polygon. This labeling scheme depends only on the id of the vertex in the input polygon. This procedure allows us to defer the synchronization between processors to the final stages of the algorithm, reduces the amount of overhead due to fine-grain synchronization, and helps makes the algorithm efficient.     

任意多边形窗口的圆裁剪算法

针对任意多边形窗口内圆的裁剪问题,本文提出一种更加全面、有效的裁剪算法.该方法提出借助x-扫描线算法来判断圆和多边形窗口的位置关系,排除圆完全在窗口内或者窗口外的情况;针对多边形窗口和圆相交的情况,按照逆时针方向依次求出多边形各边与圆的交点;最终,通过判断两点间的关系,决定两点之间画线还是画弧,完成圆的裁剪.实验结果表明,该方法能够有效全面的完成多边形窗口的圆裁剪.     

一般多边形窗口的线裁剪

已有的线裁剪算法都是针对矩形窗口或凸多边形窗口的。对于一般的多边形窗口(包括凹多边形)的线裁剪,目前尚无有效的算法。开发这种算法是很必要的,因为它在计算机图形学中有很广泛的应用,如物体的消隐处理等。因此,提出一个对于一般多边形窗口的线裁剪算法,并给出了最优实现。     

一种基于几何关系编码的高效凸多边形线裁剪算法

提出了基于直线与凸多边形几何位置关系编码的一种新的凸多边形线裁剪算法,用凸n边形窗口对m条直线进行裁剪.实验结果表明,当n较大时,该算法所用的时间大约是著名的Cyrus-Beck算法所用时间的1/3左右.如果m的数值也较大时,该算法的速度还将大大提高.所以在实际应用中,新算法提高了裁剪效率并具有很好的稳定性.     

圆形窗口的凸多边形裁剪

已有的多边形裁剪算法都是针对矩形窗口或凸多边形窗口进行的。但是，在实际应用中，也常常使用圆形窗口对多边形区域进行裁剪和填充。因此，本文提出一个对干圆形窗口的凸多边形区域裁剪法，并且给出作出凸多边形Ｐ在窗口Ｖ之内部分的定理。     

一个有效的多边形窗口的线裁剪算法

已有的线剪裁算法都是针对矩形窗口或凸多边形窗口的,对于一的多边形窗口（包括凹多边形）的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义。该文提出一个对于一般多边形窗口的线剪裁算法。该算法在被裁剪直线的延长线上取一固定点,然后求多边形窗口的每一顶点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间,就可判定直线与边是否相交,因此,每处理一     

适用于凹多边形的Cyrus-Beck改进算法

本文对目前常用的二维线段裁剪算法进行分析,提出了一种基于Cyrus-Beck算法的改进算法,使其能够扩展到对凹多边形的处理,通过对线段与裁剪窗口位置关系的严格判断将求交次数减到最少,并且通过对交点性质的判断来识别出线段的可见部分。理论分析和实验结果均表明该算法优于目前处理任意多边形裁剪框的算法。     

An algorithm for line clipping against a polygon based on shearing transformation

Line clipping against a polygon is widely used in computer graphics such as the hidden line problem. A newline‐clipping algorithm against a general polygon is presented in this paper. The basic idea of this algorithm is tochange the line to be clipped into a horizontal line by shearing transformation. Then each edge of the polygonalwindow is transformed by a shearing transformation with the same parameters as those used to the line. Eachedge of the polygon is processed against a horizontal line, which makes the clipping process simpler. The result inthis paper shows that less calculation is needed for the new algorithm with a higher speed compared to existingalgorithms.