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

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

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

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

一种强鲁棒性自适应活性边表算法

为提升多边形的填充效率,在分析和比较常见填充算法后,以活性边表算法为基础,深入挖掘不同扫描方向上的求交次数及多边形自交特性,提出一种强鲁棒性自适应活性边表算法。新算法引入横度和纵度的概念表示横纵扫描方向上的求交次数,并以此为标准自适应选择扫描方向。此外,通过对活性边表中相邻交点的横坐标进行检测和纠正,正确而高效地填充了自交多边形。经实验验证,新算法灵活的自适应性和高效的自交纠正方法,大大提高了时间效率和鲁棒性。     

基于边方向角长度表示的多边形方向、凹凸性及点包含算法

提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题.给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0°增加到360°时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角.建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则.该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断.给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率.实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的.     

统一于NIP的多边形三角剖分算法

本文提出一个简洁的、完整的、统一于非自交多边形(NIP)的多边形三角剖分算法,该算法分成两部分:其一是将任意多边形转化为非自交多边形;其二是非自交多边形的三角剖分。最后给出该算法在三维立体造型中的应用。     

基于曲线积分的任意多边形填充算法

多边形域填充是图形图像处理中最基本的操作之一。文章结合代数曲线积分思想与活性边表技术,提出了一种新的任意多边形代数积分算法。与传统多边形域填充算法相比,新算法不但能实现任意多边形域(如带孔区域、自相交区域)的有效填充,而且具有速度快、效率高的特点。因此有效解决了任意矢量图形转换为光栅图形的技术困难,经过在手写字符填充及多边形区域特征值计算上大量应用证明,该算法在矢量与光栅转换、字符填充、多边形区域特征值计算上有很强的实用价值。     

圆与多边形重叠区域的判定算法

本文提出了一种实用的圆与多边形重叠区域的判定算法，它集判断与确定功能于一体。该算法将多边形的边视为有向线段，通过引入多边形顶点的入边，出边交点的概念，研究了圆与多边形重叠区域的确定问题，并给出了作出其重叠区域的定理。     

无重迭边的可重入多边形裁剪算法

本文提出一种在标准 Sutherland—Hodgman 多边形裁剪算法基础上扩充的重迭边消去算法。本算法在沿着窗口边沿直线对多边形的各边进行裁剪的时候,建立了一个中间结果顶点队列和一个交点队列,然后通过顶点追溯方法产生出作为裁剪结果的一列子多边形.这些子多边形的定义方式与输入多边形相同,不存在重迭的边,而且仍然保持可重入性.     

基于双向链表操作的多边形求交与并的算法改进

对两个多边形的各边依次求交,根据交点所在边起始点与另一多边形的包含关系确定交点的入出状态,并按交点所在边的序号及距边起始点的距离排序,再插入到双向链表中,利用链表中各交点的入出状态搜索其交集、并集.论文算法中对点重合、边重合等特殊情况,仅需对在求取交点时做简单的特殊处理,其后续操作均使用统一处理方式,相比其它传统的算法,论文提出的算法简单高效.     

矩形布局可行域的确定

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

基于像素的多边形等距区域子分算法

目的 多边形等距是计算机图形学、计算几何、计算机辅助几何设计领域的一个基础性问题,并且有着广泛的应用。为了有效地处理各种类型的多边形等距问题,提出一种基于像素的多边形等距区域子分算法。方法 利用四叉树数据结构对给定区域进行子分,再利用区间算术计算出符合等距要求的全体像素集。针对只是由线段组成的多边形采用点到线段的最短距离算子加快计算速度。结果 利用区域子分算法处理了不同类型的多边形等距问题,并与传统的基于像素的多边形等距膨胀算法进行了比较。本文算法能有效处理各种多边形的等距问题,相对于传统的基于像素的膨胀算法,在顶点处的处理效果上更好,并且耗时也更短。所提区域子分算法比传统边等距方法适用范围更广,能够有效地处理一些边等距算法不能处理的多边形等距问题。结论 本文算法其优点是不需要考虑自交和连接问题,并且可以处理其他许多常规方法处理不了的各种类型的多边形等距问题,包括带有弧段和孤岛的情况。     

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

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

基于退化多边形求交的多面体虚拟壳模型重构

三维模型的重建和表示是计算机图形和计算机视觉中一个重要的领域,其广泛应用于自动识别,工业自动化设计以及虚拟场景的重建。文中实现一个从照片序列重建三维物体多面体模型的系统,使用由轮廓恢复形体(SFS),通过经由轮廓光锥相交得到包围物体的虚拟壳。在系统中采用的共极线几何和增量运算把所有的三维的相交计算投射到二维平面的退化多边形求交来降低相交计算的复杂度。与传统多面体虚拟壳重构相比,算法有以下几点改进:在图像平面以退化多边形组织投影锥体和物体轮廓的交集,把任意锥面与物体轮廓的交集归一到一个退化多边形;基于退化多边形的二维平面上多边形快速相交算法。通过这些改进可以减少虚拟壳的生成时间并有助于实时绘制的实现。     

线目标缓冲区生成的矢栅混合算法研究

线目标的缓冲区生成是缓冲区分析的基础和关键。结合栅格算法与矢量算法的优势,提出矢栅混合算法解决线目标的缓冲区生成问题。采用Douglas-Peuker方法对线目标进行重采样以加快缓冲区建立速度,用扫描线方法将线目标矢量数据转化为栅格形式,再采用膨胀原理生成缓冲区,通过扫描缓冲区栅格边界,提取有效矢量数据,进行求交运算,对缓冲区生成中的自相交多边形进行处理。     

基于R＋树的地图叠加分析双重循环算法

地图叠加是非常重要的 GIS空间分析功能之一 ,为此 ,提出了一种新的基于 R 树空间索引的矢量地图叠加分析双重循环算法 ,首先采用多边形穷举求交方法计算出线段相交点 ;然后运用引入、引出交点交替配对的叠加结果弧线段生成原则 ,进一步实现了面面叠加和线面叠加的双重循环算法 ;最后引入 R 树空间索引对空间数据的高效存取机制 ,对算法进行改进 ,进一步提高了计算速度 .实践结果表明 ,该算法快速、有效 ,具有较强的应用价值 .     

加强局部简便计算的点在多边形内的高效判定

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求。已提 出许多方法减少要测试的多边形的边以加速。其中,均匀网格法具有很好的作用,因为各网格 中的边很少,而测试点可迅即定位于一个网格。我们曾提出一种均匀网格法,预计算各网格中 心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的 边的相交情况即可。其预处理和检测的复杂度分别为 O(N)和 O( N ),N 为多边形的边数。本 文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网 格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性。 实验结果表明,可将检测速度提高 2 倍多。     

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

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

VLSI systems for some problems of computational geometry

Fast solution of the computational geometry problems is important for computer graphics, image processing and pattern recognition. The capability of the network Mesh of Trees for application in VLSI systems solving fastly the computational geometry problems is shown on two examples: determination of the convex hull of a weakly externally visible polygon and determination of the visibility polygon of a polygon.     

计算机图形并行处理的研究与发展

本文概述了计算机图形并行处理研究的产生与发展,着重阐述了并行处理功能部件的研究和发展及多边形绘制、全局光照模型(光线跟踪与辐射度方法)、物理场数据与体介质数据绘制、动画、并行化图形标准等研究领域在并行处理方面的研究和发展.文中叙述了在这一领域的研究工作,并在最后展望了计算机图形并行处理的进一步发展方向.