多边形简化算法及比较

用多边形简化提高工程分析效率,利用图形学中三维模型简化的相关思想,从顶点删除和边收缩2个角度,提出3种多边形简化算法,并对其简化效果进行比较。实验结果表明,该算法在对多边形进行简化的同时能够有效保持多边形的形状,已应用于地质高程分析软件中。     

SDS模型化简合并多边形的一个改进算法研究

作为自动制图综合中的重要组成部分，多边形化简与合并可用来解决由于制图比例尺减小而带来的多边形与多边形之间以及多边形内部的邻近冲突问题。该方法设计主要基于多边形几何特征、拓扑特征的分析，同时需要一种合适的空间数据模型用于支持多边形与多边形之间，多边形内部的邻近关系探测。为避免分离操作带来的多边形综合结果的不同，在分析了基于Delaunay三角网的SDS模型表达对象邻近关系的能力后，提出了一种统一解决多边形化简和合并的方案，同时对原有的邻近冲突检测方法进行了改进，从而解决了由于边缘尖锐三角形的引入而导致多边形合并和化简后面积大量增大和丢失某些特征点的问题。实验结果表明，该方法可以获得满意的多边形化简合并效果。     

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

通过对相交多边形交点的完备分类,给出了一个可靠的任意多边形裁剪算法.结果表明,该算法非常稳定可靠,且能处理各种奇异情况.     

用于二维不规则排样的离散临界多边形模型

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.     

平面多边形Newell 公式的运用与推广

Newell 公式在计算机图形学中常被用于计算多边形面积和平面法向量。 论文主要讨论了Newell 公式的运用与推广。首先将其推广三维空间中用于计算多面体体积 的公式。其次讨论了在异面多边形的情况下,Newell 公式的几何意义。最后,从数值计算 的角度分析了Newell 公式的计算方法。     

一般多边形网格模型的几何压缩方法

使用Face Fixer方法对由一般多边形网格构成的三维模型拓扑信息进行了压缩，采用3阶自适应算术编码进一步提高压缩比，通过把顶点位置坐标变换到局部坐标系中，结合量化、平行四边形顶点坐标预测以及算术编码来实现三维网格模型几何信息的压缩，在几何模型质量基本没有损失的情况下，获得了很好的压缩性能。     

基于图模型的多边形自动并行构建算法

目前GIS基础算法并行化成为高性能GIS进一步深入的前提,作为GIS空间分析基础算法的重点,有必要对多边形构建提出一种自动并行算法。为此,提出基于图模型的多边形自动并行构建算法。该算法根据图模型中有向闭合环的特点对一组线段的集合进行多边形构建,能有效提高多边形构建的自动化程度。将搜索、排序等耗时较多的操作进行并行化处理,能有效减少全局搜索次数及整体排序和逻辑操作时间。实验表明,在对大规模线性数据生成区域时,该算法能有效地实现效率提升,达到良好的效果。     

带孔洞多边形的求交算法

为简化已有任意简单多边形求交算法并提高算法效率,首先将交点分类并排序,然后采用不同的遍历方法得到多边形的交集、并集和差集,在该算法的基础上设计带孔洞多边形的求交算法．所有算法均被实现,且复杂度较低,鲁棒性较好．     

一种断层多边形自动平滑方法

提出了一种断层多边形平滑方法。该方法针对利用边界追踪算法提取断层多边形,利用断层多边形折线之间的角度,边长等因素,在保持断层多边形形态的前提下对断层多边形进行平滑,改善了断层多边形的视觉效果和美观,为地震资料解释提供了一种很好的方法。经过大庆油田多地区地震图像的验证,此断层多边形提取与平滑方法可以有效提取出断层多边形并去除断层多边形的毛刺,对断层多边形平滑效果显著。     

一般多边形的碰撞算法

文章首先对凸多边形碰撞问题进行了仔细的考查，然后对一般多边形碰撞问题进行了深入细致的研究，在此基础上提出了求解凸多边形碰撞问题和一般多边形碰撞问题的最优算法。     

简单多边形方向识别的健壮算法

极值顶点前后相邻边矢量叉积法是识别任意简单多边形方向的最优算法 该算法存在的问题是 :当极值顶点前后相邻边夹角接近 0°或 180°时 ,叉积结果接近 0 ,因此存在二义性 ,会导致错误的方向识别 针对现有算法对奇异情形方向判别解决不彻底的问题 定义了多边形极值顶点奇异情形 ,对相邻边夹角接近 0°和 180°两种奇异情形给出了判定方法 ;提出了极点前后点坐标比较法和极点序号大小比较法 ,有效地解决了所有奇异情形下的方向识别问题 ,它们都可以发展成为独立的方向判断算法 实验结果表明 ,该算法简单高效 ,健壮性强 ,时间复杂度为O(n)     

网格模型的简化算法研究

在计算机图形学中,常采用多边形网格描述物体模型.由于绘制时间和存储量与多边形的数量成正比,因此必须对网格模型进行简化.文章通过分析几类网格模型简化算法,研究了目前存在的主要问题,提出了解决的方法.     

多边形顶点的定位

在图象识别和机器人视觉中,多边形顶点的个数和边长是多边形的重要描述.本文在Freeman链码的基础上提出了差值链码算法.可以快速确定多边形顶点的位置坐标.在GKD-1机器人视觉系统的实际应用中取得了良好的效果,     

复杂多边形窗口的多边形裁剪的改进算法

多边形裁剪是计算机图形学中较为热点研究的问题,针对复杂多边形窗口的复杂多边形裁剪提出一个可靠有效算法。算法通过添加虚边来消去孔洞,并且为恢复裁剪结果的原貌改进了遍历方法。新的遍历算法只需遍历多边形一次就可巧妙地求得所有裁剪结果,并恢复带孔洞的裁剪结果的内外边界的拓扑结构,无需解环、并环,也不用对裁剪边界重新组合。     

判定一点是否落在简单多边形内

判定一点是否落在一个简单多边形内,是计算几何领域内的一个基本问题,本文详细讨论了解决该问题的奇偶法,给出了一个自然、简明的编程方法。     

一种断层多边形交互编辑方法

根据断层多边文件的特点,提供了一种很好的解释方法.经过大庆油田多地区地震图像的验证,这种方法提高了断层多边形解释的准确度.     

基于简化多边形类正切空间表示的图形渐变算法

采用多边形简化的方法提取出包含源图形主要特征点的多边形.在简化多边形的类正切空间表示下,利用图形对应边在渐变过程中所掠过面积总和最小这一特征构造相似度量函数,由动态规划算法求解实现初始和目标简化多边形之间的顶点对应,再进一步建立源图形顶点之间的整体对应,最后通过插值边和角的方法实现图形渐变.实验结果表明:该算法简单有效,对应效果自然、合理.     

高效的多边形布尔计算方法

针对计算机图形学中应用广泛的多边形布尔计算,提出了一种新的、适用于一般多边形的并集、交集和差集算法。算法主要分为计算交点、将交点插入多边形顶点序列、遍历三个步骤。通过采用循环单链表的数据结构、避开复杂的出入点计算、及预先的一些碰撞检测以避开复杂的求交运算与链表遍历等技巧,提高了算法的执行速度、减少了存储单元。算法能够很好地处理一些奇异情形（边界情形）,比如重叠边、交点为边的顶点等情形,具有很好的鲁棒性。与经典的Weiler算法、Vatti算法和Greiner-Hormann算法相比,该算法具有较低的时间复杂度O（（ m+n+k） log d））和空间复杂度。实验结果显示该算法在处理2222×2222个顶点、42个交点时比经典的Weiler算法速度提高了296倍。算法的主要思想对确定两个多面体的交、并、差问题亦有参考价值。     

一般多边形的切割

一般多边形的切割在计算机辅助设计中应用很广泛，如在服装ＣＡＤ中对衣片的裁剪等，本文给出对一般多边形切割的算法，同时给出了一个 般我边形裁剪的较为简便有效的算法。