基于自适应分块的TIN三角网建立算法

ＴＩＮ三角网在ＧＩＳ／ＶＲ中具有重要用途,在ＴＩＮ生成算法中,分割－归并法、三角网生长法各有其优缺点,为兼顾空间的时间性能,因而提出了一种基于自适应分块思想的ＴＩＮ三角网建立算法,它融合传统的分割－归并法、三角网生长等Ｄｅｌａｕｎａｙ三角网主流生成算法于一体。实验结果表明,算法建立的三角网无交叉和重复,并具有Ｄｅｌａｕｎａｙ三角网的特性,同时兼顾了空间的时间性能,具有较高的执行效率,算法的设计思想     

构建Delaunay三角网的改进算法

在编程实现利用凸壳三角剖分法构建Delaunay三角网时，原算法由于没有对一些特殊情况加以考虑和处理，可能会使算法的后继步骤无法进行。在分析介绍潜在问题出现原因的基础上，对特殊情况加以考虑和处理，并对生成凸壳和初始三角网的方法做了一些改进，使程序在编写和运行上都具有更高的效率。     

Delaunay 三角网生长算法改进与实现

对一般三角网生长法做了简要介绍和分析,针对限制算法效率提高的关键 步骤——“搜索符合条件的第三点”,提出了一种“第三点分区搜索法”的改进算法。通过 一系列的圆弧将离散点区域划分成多个分区,构网时规定只可在当前分区和相邻的下一分区 搜索第三点,当该分区的离散点搜索完毕后进入下一分区。在Microsoft Visual Studio 2008 的环境下使用C++进行编程测试,结果表明,该算法能够加快构网速度,生成的三角形形状 良好,具有一定的实际效用。     

一种改进的约束Delaunay三角网构建算法及其在快速立体解译平台中的应用

约束Delaunay三角网在土方量估算、三维表达、地形拟合等方面得到了广泛的应用。本文对传统的无约束三角网生长法进行了扩展,使扩展后的算法可以同时满足外部边界约束及其内部多线串约束。通过对构网过程中的主要判断法则进行优化,提高了算法的效率和鲁棒性。试验表明将本文算法应用于"快速立体解译平台"中的不规则实体体积估算可以取得很好的效果。     

海量数据Delaunay三角网的并行构建算法

对并行环境下Delaunay三角网的构建进行了研究。针对海量数据处理的高效性要求,提出了一种归并构网方法。该方法根据构网数据的实际分布特点,对数据点按x坐标进行排序,并将排序后的数据按给定的阈值点数依次分配给各工作线程,构建出一系列的初始子三角网,然后逐轮对相邻的子三角网进行两两归并,直至最终归并为一个三角网。该构网方法过程中子三角网间的相关性小,易于并行处理和流水线作业。该算法既适用于单机串行、多线程和多核并发环境处理,同时也适用于集群计算模式下的分布式并行处理。实验表明,该算法的时空效率较高,最坏的串行时间复杂度为O(nlogn),一般情况下不超过O(n2)。     

基于分治算法构建Delaunay三角网的研究

提出了一种构建Delaunay三角网的分治算法,该算法利用方格网管理离散点数据,仅需分别对每格中的点进行排序;此外,通过对凸包顶点数据进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的合并速度。     

基于自适应八叉树分割点云的表面模型重建

传统的三角网生长法进行点云数据表面模型重建时,搜索第三点耗时太长,导致重建效率很低。采用自适应八叉树划分算法将点云数据分割成相互覆盖的子域,在每个子域内进行三角网格重建,避免网格拼接的过程;采用最大角最小化原则进行三角网格优化;并运用三角面片定向的方法进行网格法向量一致化处理。实验结果表明,该方法极大地提高了表面模型重建的效率,形成的网格质量也很好,能够较好地体现模型的细节特征,鲁棒性好。     

一种基于插入法的Delaunay三角网生成算法

文章讨论了建立离散点Delaunay三角剖分算法的研究现状,针对＂逐点插入法＂采用网格分块的方法对构网离散点集和已生成的三角网建立索引,提高了点在三角网中的定位效率和三角网的生成效率。     

基于Delaunay三角网的模型拼合算法研究

模型拼合在地理建模、铁(公)路路线三维设计等领域应用十分广泛，研究如何快速高效地获得拼合模型的算法很有必要。基于Delaunay三角网模型的拼合算法，提出了一种快速获取模型拼合交线的方法和快速搜索交线范围内三角形的算法，采取拼合交线入网及初始D-三角网的裁剪2个关键步骤来实现D-三角网模型拼合。对模型拼合的整个过程进行了详细的阐述，采用VC^ 6．O语言实现了算法，并利用实验数据对算法进行测试，验证了算法的正确性与可行性。     

基于不规则三角网构建的网格生长算法

提出一种基于离散点Delaunay三角网快速构建的网格生长算法,采用分治算法将离散点表达为唯一网格,利用稀疏矩阵完成网格数据的压缩存储,通过标识码实现有值单元格与离散点之间的高效检索,从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间,并在三角网扩展时根据需要动态建立正方形搜索空间,从而保证网格生长的准确性。实验结果表明,该算法的时间复杂度为O(nlogn),对于少量或海量离散点均具有较好的适应性。     

四叉树高效Delaunay三角网生成算法

实现了一种以地形为应用背景的大规模离散点快速生成TIN的算法,该算法首先对大规模离散点按一定的阈值进行四叉树分割,然后对四叉树的每个叶子块分别以凸壳技术构三角网,而后再自底向上合并具有相同父亲节点的块,最后进行全局优化,生成Delaunay三角网.经实际地形数据验证结果表明：同样的算法,采用四叉树分块比采用平均分块策略有着更高的执行效率.     

一种改进的高效Delaunay三角网的生成算法

Delaunay三角网在GIS／VR中具有很广泛的用途，而分而治之算法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。本在研究了基于这两种算法的合成算法后，对其进行了修改和优化，形成了高效合成算法。高效合成算法中提出了通过确定点线关系来解决点的定位问题，优化了其LOP的算法，提高了算法的稳定性，使其执行效率得到很明显地提高，本算法的设计思想还可推广到三维空间。     

基于凸壳技术的Delaunay三角网生成算法

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。     

基于Voronoi 最小邻近点集的Delaunay 三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay 三角化 生成算法,该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础,通过在局部 搜索最小Voronoi 邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提 高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用 领域。     

三维约束Delaunay三角化的实现

分析了约束Delaunay三角化中存在的边界一致性问题,给出了约束Delaunay三角化的理论依据,重点探讨了三维约束Delaunay三角化的可行性条件和范围,同时,给出了三维有限域约束Delaunay三角化的实现方法及其在石油地质勘探数据和机械零件方面的网格剖分实例.这种算法在复杂对象的科学计算和工程分析中发挥了重要作用.     

生成Delaunay三角网的改进算法

算法以原“改进的自连接Delaunay三角网生成算法”为基础。其主要方法仍是三角网生长法,但同时采用了逐点插入法中的凸壳。在原封闭点的基础上提出了封闭的边界点的概念,并增加了对边界点和边界边的识别和处理,从而进一步提高了构网效率。另外,采用的用边的法向量对边的某侧的点进行判断的方法也简单实用。     

对构建Delaunay三角网中凸壳算法的研究与改进

在介绍Delaunay不规则三角网基本概念和TIN数据结构的基础上,主要对平面离散点构建凸壳的格雷厄姆算法进行了研究和改进,提出了一种“斜率扫描线法”,并进行了编程实现。实验表明改进后的算法实现简单,容易理解,对于D-TIN模型的生成行之有效。     

二维复杂限定Delaunay三角化算法

针对包括曲线边界和内部带有曲线限定条件的二维Delaunay三角化问题,提出了一种细化算法.首先给出了曲线段的逼近边定义,以保证限定曲线在网格中的存在;然后证明了该算法的收敛性和最终曲线的逼近边集合与原曲线的拓扑一致性,并且生成的网格符合Delaunay优化准则;最后给出了算法的应用实例,验证了其有效性.     

一种基于格子分块的快速Delaunay三角剖分算法

介绍了一种基于分块格子构造的快速Delaunay平面剖分算法,先对点集以方格为单位分组,每组分别进行Delaunay三角网生成,再把分组构成的网格合并成一个整体。该算法易于理解和实现,占用内存少,运算速度快,具有近优的线性时间复杂度。最后给出的实例也证明了算法的可靠性和实用性。