基于交点参数的任意多边形窗口对圆裁剪

现有的任意多边形窗口的圆裁剪算法存在算法繁琐等问题, 且没有考虑多边形是带内环的情况, 本文提出了一种基于交点参数分析的多边形窗口的圆裁剪算法, 只需对多边形边与圆的交点在边所在直线的参数值进行比较, 即可判断出交点的进出点特性, 交点排序后, 通过进点$\Rightarrow $出点组合, 即可获得裁剪窗口内的圆弧, 完成裁剪. 编程实践的实例结果也证明本算法是切实可行的, 本文的方法既适用于仅有外环的一般多边形裁剪窗口, 也适用于带内环的任意多边形裁剪窗口的圆裁剪, 因此, 算法更具有通用性.     

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

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

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

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

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

圆的裁剪广泛应用于诸如计算机图形学、二维计算机动画以及机器人运动学等领域.讨论了圆关于任意多边形窗口的一个裁剪算法,按逆时针方向依次求出多边形裁剪窗口的每条边与圆的交点并且保证交点正确排序,对于交点序列中的任意两相邻的交点,采用"中点检测法"来判定以它们为端点的圆弧与裁剪窗口的位置关系,最后给出完整的裁剪算法.实现结果表明,不论从效率还是稳定性方面都取得了比较理想的效果.     

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

已有的矢量圆裁剪算法存在效率低和内存占用率高等问题,将会影响到图形处理和分析的速度,为此提出一种具有线性复杂度的任意多边形窗口的矢量圆裁剪算法.首先采用投影法对矢量圆线性映射,构造一个线性的射线函数,快速而准确地对圆与多边形进行相交性检测,同时通过线截断法,运用线性方程精确地求出圆与多边形的实交点;然后根据三点之间的叉积按照规定的方向对交点进行排序;最后采用中点检测法确定可见性的圆弧或圆绘制到内存,并输出绘制好的图像和统计的图形复杂度.实验结果表明,该算法可有效地避免虚交点的产生,降低裁剪显示过程中的时间和空间复杂度,提高矢量圆裁剪准确性.     

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

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

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

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

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

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

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

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

图形裁剪算法研究

本文介绍和研究直线、曲线和多边形的最新裁剪算法,包括作者近期的研究成果。首先对于矩形窗口,介绍了直线裁剪算法,圆和椭圆裁剪算法以及参数曲线的裁剪算法。然后,介绍了多边形窗口的直线裁剪算法和多边形窗口的多边形裁剪算法以及区域间的“交”、“差”和“并”操作。最后,介绍了圆形和椭圆形窗口的直线裁剪算法。     

圆形窗口上一般多边形的内/外裁剪算法

本文详尽地分析了圆形窗口上一般多边形（凹／凸）的内／外裁剪问题,并通过构造顶交表、圆交表、入点表、出点表等给出了一般多边形（凹／凸）的内／外裁剪算法。     

圆形窗口的凸多边形裁剪

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

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

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

一般多边形窗口的线裁剪

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

An efficient algorithm for line and polygon clipping

We present an algorithm for clipping a polygon or a line against a convex polygonal window. The algorithm demonstrates the practicality of various ideas from computational geometry. It spendsO(logp) time on each edge of the clipped polygon, wherep is the number of window edges, while the Sutherland-Hodgman algorithm spendsO(p) time per edge. Theoretical and experimental analyses show that the constants involved are small enough to make the algorithm competitive even for windows with four edges. The algorithm enables image-space clipping against windows whose boundaries are convex spline curves. The paper contains detailed pseudo-code implementation of the algorithm and an adaptation of the simulation of simplicity method for handling degenerate cases.     

采用区域编码的椭圆对直线裁剪算法

裁剪算法的核心问题是速度问题,而求裁剪窗口和裁剪对象的交点是影响裁剪速度的主要因素。特别是椭圆对线段的裁剪,由于椭圆的方程是二次的,求椭圆与线段的交点 需要求解一元二次方程,涉及开方运算,非常浪费机器时间。为提高裁剪速度,设计出5位的区域编码,利用此技术能够迅速而准确地判断出椭圆和线段的位置关系。对于完全可见 或显然完全不可见的线段立即做出保留或弃掉的决定,避免求交运算;对于能够明确断定与椭圆相交的线段,采用中点分割算法求椭圆和线段的近似交点,避免求解一元二次方程 和开方运算;对于其他情形的线段通过求解一元二次方程来完成裁剪。基于前述思想设计出的椭圆对线段裁剪算法与现有的同类算法相比,算法实现简单,裁剪速度具有较大提高 。     

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

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

凸多边形窗口线裁剪的折半查找算法

在Skala算法基础上,提出了一个更加快速的线裁剪算法．该算法将裁剪窗口分割成4条折线,依据折线的两个端点与被裁剪直线的位置关系,确定折线是否与直线相交;采用折半查找方法,快速确定与直线相交的窗口边界线,并求出交点位置．与Cyrus-Beck算法相比,该算法在乘除法次数和计算速度方面具有非常明显的优势,也比、Skala算法的效率更高。     

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.