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

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

基于继承性的圆形窗口多边形裁剪新算法

在深入挖掘多边形的边与圆形窗口的几何特性以及二者相对位置的基础上，提出了可继承的正方形编码以及可继承的广义距离两种新技术以及裁剪新算法。可继承的正方形编码技术包括完全可继承编码和部分可继承编码，其可以快速舍弃绝大部分完全位于圆形窗口外部的多边形的边，而可继承的广义距离技术可以快速获取所有完全位于圆形窗口内部的边，并可进一步用于交点的快速求取。实验结果和算法比较表明，本算法具有较高的运算效率，稳定性良好。     

基于窗口与线段双重几何变换的线段裁剪新算法

鉴于裁剪算法中求交的时间复杂性和求交的技术必要性,如何尽快舍弃与窗口根本不相交的冗余线段成为提高裁剪效率的关键。鉴于传统编码技术取舍线段的高效性,引入一次编码技术;针对一次编码技术的局限性,文章首次提出窗口几何变换的概念,并引入二次编码技术,通过广义窗口高效舍弃冗余线段,尽量避免求交运算;后续流程引入线段几何变换技术实施裁剪,尽可能加快求交进程。窗口变换与线段变换集成的双重变换技术,将线段重新划分为六类,分别采取高效的处理策略,算法实现表明裁剪算法效率显著提高。该文算法具有一定的理论意义和普遍的应用意义。     

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

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

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

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

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

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

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

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

基于变窗口过滤技术的线段裁剪中点分割算法

提出变窗口裁剪的新概念，通过改变线段与变窗口的相对位置，从而快速滤去冗余线段，避免没有必要的求交运算。变窗口由变化斜率的窗口边构成，窗口对边保持平行。单层过渡技术的窗口边斜率分别为 1和-1，适合于软件和硬件实现；在此基础上，多层过渡技术的窗口边斜率分别以2的负整数次幂改变，以充分发挥硬件实现的特点，不断地快速舍弃冗余线段。算法既保持了传统中点分割算法的特有优点：无需乘除、硬件实现简单，又大大降低了冗余顷段的裁剪计算量。软件实现清楚地表明该算法能量提高线段裁剪效率。可以推断，若用硬件并行结构实现该算法，裁剪效率的提高将更为显著。     

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

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

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

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

基于圆形窗口的简单多边形裁剪算法

提出了一种新颖而实用的圆形窗口Ｖ对多边形Ｐ的裁剪算法。它将多边形Ｐ的边视为有向线段，通过引入多边形顶点的入边和出边交点的概念，深入研究了Ｐ被Ｖ裁剪后的区域确定问题，给出了作出Ｐ在Ｖ内部分的定理     

矩形布局可行域的确定

通过研究布局问题,提出一种求解矩形布局问题可行域的方法.首先根据当前布局空间中顶点的形态,按待布矩形的尺寸对各顶点进行偏移计算,获得当前布局空间的偏移多边形;然后遍历偏移多边形各边,求解并标识所有交点;最后根据偏移多边形各边的方向,通过沿边界搜索直接获得可行域上的各点.该方法通过搜索偏移多边形边界,避免了处理偏移多边形中多条边互交的复杂情况.分析及实例表明该方法思路简洁、快速而高效.     

基于单调链的判断点是否在多边形内的方法

提出了一种判断点是否在多边形内的新方法，该方法由两部分组成：(1)预处理，即先求出多边形的所有极点；(2)检测，即采用折半查找找到相关点和相关边，根据被检测线穿过的相关边数来判断检测点是否在多边形内。该方法解决了射线法无法解决的奇异情况，且在检测过程中不必处理多边形的所有边。实验结果证明，该方法简单、易实现、快速。     

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

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

确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

基于圆形窗口的简单多边形填充算法

提出了一种新颖而实用的圆形窗口简单多边形填充算法，它具有快速裁剪与填充双重功能，也可完成单纯地裁剪功能，该算法将多边形的边视为有向线段，通过引入多边形顶点的入边和出边产我点的概念，深入研究了多这形被圆形窗口裁剪后区域的确定性填充问题，使截剪功能隐含于填充过程中，从而节省了填充之前的裁剪过程。     

二维图形最狭长包络矩形的求解原理及方法

最狭长包络矩形是二维图形的一个潜在几何属性,可作为平面外形智能设 计、板料优化排样及图像自动识别的重要依据。目前国内外尚无此课题的专门深入研究。提 出了最狭长包络矩形的概念,将任意二维图形的最狭长包络矩形的求解转化为对其凸包的最 狭长包络矩形的求解。明确给出了过凸包上给定4 个顶点的包络矩形的包络角及长宽比求解 公式,并通过分析包络角及长宽比求解公式之间的关系,证明了凸多边形至少存在一条边与 其最狭长包络矩形的一条边共线。基于该定理,求解并比较与二维图形的凸包的n 条边分别 共线的n 个包络矩形的长宽比,得到了二维图形的最狭长包络矩形。最后用实例验证了定理 和求解方法的正确性和应用效率。     

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

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