一种等值线图的任意复杂多边形窗口裁剪算法

给出了一种新的海量等值线图任意多边形窗口的快速裁剪算法。计算裁剪多边形的外包围盒并创建网格结构,利用网格结构对等值线进行快速预裁剪,通过链式结构对等值线进行细节裁剪得到最终裁剪结果。通过建立行链式结构可以实现以行扫描的方式快速判断点的内外属性,而且还能减少线段求交运算次数,基本能确定实际相交的线段时才进行求交运算。经过大量的实验,证明该算法非常高效且稳定。另外,新算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。该算法程序实现简单且符合工程需求。     

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

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

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

根据多边形窗口各顶点与被裁剪线段的两端点分别在x轴、y轴上的坐标,首次提出窗口边界与被裁剪线段相交的必要条件,有效地排除与被裁剪线段不相交的多边形窗口边界,避免了求交带来的大量乘除法运算.算法思想简单,极大地提高了裁剪的效率.     

一种高效的一般多边形线段裁剪算法

直线段的裁剪是图形绘制中的基本问题,针对当前主流的直线段裁剪算法,或者不能适应一般多边形窗口的裁剪,或者在复杂裁剪情况下裁剪效率低下的问题,提出了一种高效的一般多边形线段裁剪算法.该算法排除掉明显不在裁剪窗口内的直线段,以及相交于伪交点的情况,再利用改进的交点计数法确定位于窗口内的区间.实验结果表明,该算法不仅具有高效性,还能适应于复杂的裁剪情况.     

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发，首次提出窗口顶点编码的新概念。以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域，从而快速完成多边形窗口顶点编码。通过窗口顶点编码与传统的线段编码相结合，无须求交即可快速排除大部分窗外线段；进一步可以直接得到与直线相交的窗口边，加快了求交进程。更有意义的是，通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况：裁剪直线通过多边形的顶点、裁剪直线通过多边形的边。实验结果表明，新算法提高了裁剪效率并具有很好的稳定性。     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

大规模等值线图任意多边形裁剪算法

给出一种大规模等值线图任意多边形窗口的快速裁剪算法。首先进行传统算法的外包围盒裁剪,然后针对外包围盒创建一种约束网格结构,然后利用网格对等值线进行快速预裁剪,最后通过行扫描算法对等值线进行定位并进行局部细节裁剪得到最终裁剪结果。通过约束网格可以实现以行扫描的方式快速判断点的内外属性,而且基本能确定实际相交的线段时才进行求交运算,减少了大量的求交运算。另外,算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。经过大量的实验,证明本文算法非常高效且稳定。     

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

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

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

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

多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的"交"(多边形裁剪),而且可以求多边形的"并"和"差".它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.     

一般多边形窗口的线裁剪

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

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

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

2D line and polygon clipping based on space subdivision

This paper introduces a new approach to 2D line and polygon clipping against a rectangular clipping region, using space subdivision into cells, with the clipping region as the central cell. The line segment path is traced through the cells, and entries into and out of the cell corresponding to the clipping region enable computation of the intersection of the line segment with crossed cell edges. Tracing the line segment path is computationally very simple, leading to an algorithm that only computes intersections that the are part of the clipped line segment. The new algorithm is compared to other standard line clipping algorithms with simulations and operation counts.     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单 多边形,同时也支持多边形的“并”和“差”等布尔运算。首先,设计了算法所需的数据结构; 其次,基于直线扫描转换Bresenham 算法原理提出了边网格划分的有效算法,并应用一个简 单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这 两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处 理特殊情况时的稳定性。与其它同类算法的比较表明,新算法具有更高的效率。     

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

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

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.     

基于顶点与邻边相关性的多边形填充算法

为了加快多边形填充算法的运算速度，在深入挖掘顶点与相邻边关系对填充算法影响的基础上，提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的5种典型类型，然后依据顶点与邻边的相关性，对原有多边形进行了分割与重新组合，使其完全由简单的三角形和梯形这样的单元区域组成，这样就将复杂的多边形填充问题转化为这些单元区域的填充问题，并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析，新算法大大减少了运算的时间和复杂度，从而为多边形填充创造了一种有效的新途径。