基于顶点存储类型的多边形填充算法

提出了一种基于顶点存储类型的多边形填充算法。该算法将多边形顶点和新生成的交点划分为三种类型进行存储,然后由过顶点的扫描线将多边形分割成若干个梯形区域分别进行填充。此算法只涉及过顶点的扫描线,且多边行边上的像素点坐标可以直接从边的直线方程中获得,从而使得该算法大大降低了计算的复杂性。     

多边形链求交的改进算法

多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况     

通用扫描线多边形填充算法

传统的扫描线多边形填充算法只适用于水平扫描线的逐行填充。文章提出通用扫描线多边形填充算法,该算法可以有效地解决任意间距、任意倾角的扫描线对多边形的填充问题。通用扫描线多边形算法采用了坐标变换、浮点数舍入策略等重要方法。顶点扫描线号是该算法中的核心概念。     

一种改进的扫描线多边形填充算法

典型的多边形填充算法主要包括扫描线填充算法和轮廓标志域填充算法,适用于矢量多边形文件的填充算法为扫描线填充算法。论文对原有的多边形扫描线填充算法中的最常用的活性边表和传统扫描线算法进行了分析,结合活性边表和传统的扫描线填充算法的特点,针对复杂的大数据量的多边形填充时间效率较低的问题,提出了一种改进的扫描线多边形填充算法—混合填充算法。该算法采用链表和数组结合的数据结构,形成连续的填充轨迹,有效地提高了时间效率。     

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

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

基于矢量游走的任意非自交图形合并算法

图形处理软件中,常常需要将许多非自交图形合并成一个图形,提出一种基于矢量游走的任意非自交多边形合并算法,提出了适合于多边形合并运算的改进矢量游走规则及交点转移条件.通过将交点和两相交矢量边联合处理,对交点分类,有效地去除了“伪交点”,进而简化了重合交点处理.提出用带凸度线段的方式来表示圆和舍圆弧边的多边形,成功地将矢量游走规则运用到这些复杂多边形的快速合并当中.     

移动设备上富媒体场景渲染优化策略

随着移动设备上越来越多的富媒体应用,对富媒体引擎提出了更高的要求.为了提高引擎性能,提出移动设备上富媒体场景渲染优化策略.该优化策略从局部渲染和多边形填充2个方面进行:通过跟踪场景变化的失效区域来体现局部渲染;在多边形填充方面提出一种Grid算法,通过记录多边形的边与屏幕扫描线的交点信息来进行边的反走样计算以及多边形光栅化填充,且支持复杂自交多边形填充.经过推导证明,Grid算法在时间复杂度与空间复杂度两方面比传统的活性边填充算法和扫描线种子填充算法更优,更适合于移动设备的图形填充.最后通过仿真测试验证了以上两个方面优化的良好效果.     

基于扫描线的任意多边形填充算法

本文在基于扫描线的多边形填充算法基础上,通过建立活性边表、Y桶链表,以简化扫描线与边相交的判断,保留了基于扫描线填充适用于任意多边形的优点。     

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

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

一种改进的活性边表区域填充算法

为提高区域填充效率,对三种常见的区域填充算法进行了介绍和分析,并对其中优势较为明显的活性边表区域填充算法进行了进一步改进。改进算法针对原始算法的不足,充分利用多边形顶点信息,建立了活性边动态发现机制,使得算法时间效率和空间效率都得到提高;同时,为填充自相交多边形,又提出一种简单有效的基于扫描线的多边形自相交点探测方法,使得算法的适用性得到进一步增强。实验结果表明,算法的改进取得了很好的效果。     

一种新的快速复杂连通区域扫描线填充算法

提出一种快速求取扫描线与轮廓线交点的算法,只需遍历2次轮廓线即可求得所有交点,显著降低了算法复杂度。基于该求交算法得到的扫描线填充算法,可以填充任意的复杂连通区域。与同类算法犤2,4,5犦相比,该文算法流程简单,填充速度快。     

一种基于矢量游走的复域多边形合并算法

电磁仿真工具中,常常将许多具有相同属性的多边形合并成一个多边形,以便对图形进行整体操作和网格划分。本文提出了适用于多边形合并的矢量游走规则及交点转移条件,通过交点与相交矢量边的联合处理,简化了重合交点处理,从而实现一种基于矢量游走规则的带内孔复域多边形合并算法。     

多边形填充的扫描线算法及其实现

多变形填充算法是图形学中一个比较复杂的算法。对多边形填充算法进行了介绍,用VC 实现了X-Y扫描线算法,该算法可以对任意形状的多边形(包括自相交的多边形)进行填充。     

基于扫描线的线段求交算法

本文以基于扫描线算法求线段的交点,首先设有一条扫描线l,从高于所有线段的位置起,自上而下地扫描整个平面,与当前扫描线相交的线段构成一个扫描线状态结构,在扫描线从上个事件点移到下个事件点时,要根据事件点的不同来更新扫描线的状态结构。该算法能避免盲目求交时大量无效求交测试。     

基于矩形包围盒的多边形碰撞检测算法

碰撞检测是计算机图形学领域中的一个普遍存在的问题。为了提高多边形碰撞检测的效率 ,针对简单形式刚性运动的多边形对象 ,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法。该算法基于坐标轴的单调性对多边形进行分割 ,并通过矩形包围盒之间的预检来减少无关边对的相交测试 ,以加速算法的终止。由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量 ,所以 ,经过少量的“边 -边”相交判断就能求解到所有交点 ,同时能快速地获得两多边形干涉发生的第 1位置。试验表明 :(1)对于一般多边形 ,该算法的复杂度也远远低于 O(NP× NQ) ;(2 )对于凸多边形对象 ,该算法的复杂度为 O(NP NQ) ,其中 NP,NQ 为多边形 P,Q的顶点数。由此可见 ,算法能够获得较好的运算效率     

相交多边形轮廓线的获取

提出获取相关多边形轮廓线的一种算法，利用线段求交法求取相交多边形交点，利用 对位置判断交点处轮廓走向。该算法适用于任意多边形。     

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

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

矢量地图叠加分析算法研究

提出了一整套矢量地图叠加分析算法：提出了大量点与多边形关系的包含性测试方法,首先对多边形进行预处理,然后采用射线法对单个点进行包含性测试;提出了基于双索引的大量线裁剪方法,分别以线、线段为基础建立两层索引,有效去除不必要的求交运算;面面叠加,基于改进的扫描线方法求取交点;通过对过同一点的线段分布情形的完备分类,涵盖了所有特殊类型的交点;在构造环的过程中,保存整型ID信息,并利用ID完成内环外环的匹配以及属性继承。以上几何计算方法及对应的叠加分析功能都已经实现,与最新研究成果的对比以及与ArcGIS对应功能的对比,都证明了其正确鲁棒、高效可用。上述实现已经应用于实际的GIS系统中,取得了良好的效果。     

基于扫描线算法的多边形区域填充图案

讨论了基于扫描线填充算法实现多边形区域填充图案问题。首先,讨论位图图案(二值图像)的填充问题。文章从下面三个方面展开:位图相对于多边形区域的两种位置关系(对齐方式),透明与非透明填充问题以及含有内孔的位图图案的填充问题。然后,讨论了RGB图像的扫描线填充问题。对每一种情况,都给出了相应的算法与实现代码。     

保细节平面形状编辑

提出了由顶点转角和相邻边长比例构成的多边形伸缩内在量表示的方法,多边形从整体上由一个伸缩内在矩阵来表示,该表示方法具有平移、旋转和伸缩等几何不变性.将伸缩内在量表示方法应用于多边形编辑,从整体上优化调整邻边的长度比例和有向转角,将多边形编辑问题转化为一个稀疏线性方程组的求解.实例比较表明,该算法能在形状编辑时尽量保持形状的几何细节,优于现有的多种多边形编辑算法.