基于线段与线段求交的矩形窗口裁剪算法

我们首先对线段是否完全可见进行判定 ,然后对被裁剪线段与矩形窗口四边所在的线段是否相交进行判定并求交。若交点存在则用替换法替换相应的点 ,最后连接被替换后的点得到被裁剪后的线段 ;若交点不存在则线段完全不可见 ,线段将被完全裁剪掉。     

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

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

改进的Cohen-Sutherland线段裁剪算法

针对目前Conhen-Sutherland线段裁剪算法不能有效地判断出线段是否完全在窗口外的问题,提出了一种改进算法,通过添加一个判断条件,使得所有完全位于窗口外的线段都能快速地过滤出来,从而减少了求交点的次数,提高了运算效率.     

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

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

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

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

一种快速的图形窗口裁剪算法

现有的图形窗口对线段的裁剪算法由于包含复杂的计算而难于提高速度,文中利用圆与外切正方形的线性关系制备规范化交点表,通过映射法查表实现圆形窗口对线段的裁剪,该方法避免了线－圆求交、点－线距离及点－点距离计算,因而大幅度地提高了裁剪速度。     

一种有效的圆形窗口线裁剪算法

根据线段两端点相对于圆形窗口的可能位置讨论裁剪结果。当两端点都在圆形窗口之外时,通过圆切线斜率与线段斜率的比较,及点区域判别来判断线段与窗口的相交情况。在确定线段与圆形窗口有交点的情况下,应用参数化形式求交运算,简化求交方程的构造。实验结果表明,新算法显著提高了裁剪效率。     

基于二重编码和坐标变换圆形窗口对直线裁剪的算法

直线裁剪是几何造型中的重要内容。提出一种通过二重编码和坐标变换实现圆形窗口裁剪直线的算法。该算法首先通过二重编码快速舍弃大部分位于窗口外的直线段,然后通过坐标变换判断出剩余直线段与圆形窗口的相对位置,并求出其交点。应用实例表明,与其他算法相比,该算法简化了裁剪的逻辑判断过程,且将求交过程简化为加减法的运算,避免了求解二次方程,故大大提高了算法效率。     

基于矩阵乘法的多边形窗口线裁剪算法

提出一种任意多边形窗口线裁剪新方法,它不解方程而通过矩阵乘法得到窗口和线段的交点.对于一组待裁剪线段,该方法先做简单的包围盒预处理,将那些和包围盒无交的线段排除在求交之外;然后引进齐次坐标,构造一组仿射变换矩阵,通过矩阵乘法对任意多边形窗口和待裁剪线段实施连续仿射变换,完成窗口和直线求交操作并从矩阵中获得交点;经过交点排序、配对等过程,得到多边形裁剪线段的结果.经实验对比,该新方法有效,并且速度得以提高.     

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

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

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

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

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

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

一种改进的Sutherland-Cohen裁剪算法

Cohen-Sutherland裁剪算法因直线与窗口边界求交点次数多而降低算法效率。提出了一种改进Sutherland-Cohen裁剪算法,将完全在窗口内和窗口外的直线判断出来,根据直线端点编码确定辅助线,利用平面上三点的关系判断直线与窗口的哪条边相交。改进的算法使得求交点次数降为最多两次,且避免计算斜率与距离,大大提高算法的效率。算法思想简单,操作方便,有利于硬件实现,对图形学的应用具有重要的实用价值。     

基于凸片段分解的多边形窗口线裁剪算法

将多边形窗口的边顺序地分割成一些片段,使得每个片段都能局部地形成一个凸多边形,称为凸片段,并建立一个二叉树来管理这些凸片段．在裁剪计算时,先根据二叉树快速地找到与被裁剪线段相交的凸片段,再利用高效的凸多边形线裁剪算法对这些凸片段进行裁剪操作．文中算法能有效地降低裁剪计算的时间复杂度,使其在O（logN）～O（N）之间自适应地变化,且大部分情况下时间复杂度小于O（N）．     

具有最少算术运算量的二维线裁剪算法

本文在分析现有二维线裁剪算法的基础上,提出了具最少算术运算量的算法.新算法充分利用了矩形裁剪窗口的凸性和窗口边界线平行于坐标轴的特性,沿两组平行的窗口边界线对线段进行裁剪.通过将被裁剪线段定义为有向线段、确定窗口边界的进出边,避免了不必要的求交计算.实际算例表明,这一算法比当前国际上最快的线裁剪算法省时约一年.     

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

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

三维空间的Nicholls-Lee-Nicholl裁剪算法

探讨了将传统一般平面中Nicholls-Lee-Nicholl(NLN)裁剪算法推广到三维空间。通过在窗口周围建立更多的分区,避免了一般线段裁剪算法中为求出线段对窗口的端点须进行许多无谓的计算的缺点,性能上有所提高,并与三维空间中常用的编码裁剪法,Liang_Barsky算法和Cyrus-Beck算法进行了性能比较。     

New algorithm for two-dimensional line clipping

Line segment clipping is a basic element of the visualization process in a graphics system. So far there exist two approaches for development of algorithms for clipping a line segment with respect to a rectangular window. According to the first approach the line segment locations with respect to the window are described by a certain generalized model. As a result all line segments are clipped identically. The second approach is based on the observation that the great diversity of line segment locations could by systematized in several basic cases. For each one of them the clipping is performed in a preliminary defined way. The algorithm described in the papers uses the second approach. The basic cases of the line segment locations with respect to the window are selected so that the time consuming computations as division and multiplication are reduced to a minimum. An analytical comparison is made with the other algorithms using this approach that are theoretically and experimentally proved to be more efficient than those developed on base of the first approach.