一种基于Graham三角剖分生成Delaunay三角网的算法

目的提出一种基于Graham三角剖分生成Delaunay三角网的算法,加快Delaunay三角网的生成速度.方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序的点通过可见点的判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网.结果通过500至10000个点的测试,表明这种基于Graham三角剖分生成Delaunay三角网的生成速度快于传统基于凸包生成Delaunay三角网的生成速度.结论采用可见点表的数据结构以及利用点、边、三角形的有序性的特点构建Delaunay三角网,是提高建网速度的关键.     

基于最大外接圆的约束Delaunay三角剖分算法

目的 研究构建约束Delaunay三角网的方法 ,提高构建约束Delaunay三角网的速度.方法 基于生长法并利用分治法的思想,以约束边为基边分别向两侧重新构网,先构建Delaunay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,最后使其成为约束Delaunay三角网.结果 实验测试表明,在地形点数为5 000时,传统算法构建CDT时间为6 195 ms,笔者算法构建CDT时间为6 007ms,速度明显优于传统算法.结论 算法简单、运算速度快、内存开销小且易于实现.     

一种确定高阶Delaunay三角网中可用k—OD边的算法

目的构建高阶Delaunay三角剖分方法的数字地形模型,有效地减少局部极值问题,使得地形模型能更好地反映原始地形的真实面貌．方法提出了一种确定高阶Delaunay三角网中可用k-OD边的方法,该方法首先在任意边uv的两侧分别确定两点,使每个点与uv边形成的三角形的外接圆不包含同侧的点,若这两三角形都为k—OD三角形,则uv边是可用k—OD边．结果用Visual C＋＋实现算法,通过实验验证了算法的有效性,对于具有n个点的点集P,在时间O（nk^2＋nklogn）内可以计算出所有的可用k—OD边．结论选择合适的可用k—OD边生成相应的高阶Delaunay三角网来模拟实际地形,可以有效地减少局部极小的数量,使地形模型更接近于实际地形．     

基于半边数据结构的逐点插入Delaunay三角剖分算法

目的 根据传统的三角剖分算法,提出一种基于半边数据结构的逐点插入Delaunay三角剖分算法,提高三角网的构网效率.方法 在逐点插入Delaunay三角剖分算法中引入半边数据结构,在半边数据结构基础上定义Dart三元组,并为Dart三元组定义一组拓扑和几何操作,实现基于半边数据结构的逐点插入Delaunay三角剖分算法.结果 结合随机生成数据,通过实验结果 比较,证明基于半边数据结构的逐点插入Delaunay三角剖分算法具有较好的执行效率,并且随着点个数的增多,这种优势越加明显.结论 半边数据结构及其拓扑和几何操作能够较好地适应Delaunay三角剖分,提高了构网效率.     

基于矩形环分区的Delaunay三角网生长算法

针对传统三角网生长算法需要花费大量时间检索第三点的问题,对三角网生长算法进行改进,即对离散点集所在的区域由外到内进行矩形环式的分区,而后从内环到外环逐渐生成Delaunay三角形。每次查询第三点时,在当前环和其相邻的下一个环中进行,以减少第三点的查询范围并尽量保证第三点的正确查找。同时根据Delaunay三角形生成的顺序采取三角形基边先进先出的策略,保证当前矩形环状区域内的大部分点被加载至三角网中。在当前区域构网完成后,进入下一个相邻区域,如此循环构网,而后对三角网进行整体优化。采用C#语言进行算法的实现,结果表明,改进后的算法保证了构网的正确性、唯一性,也提高了构网的效率,对生产实践具有一定应用价值。     

基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网（TIN）是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明：本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.     

基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网(TIN)是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明:本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.     

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

Delaunay三角网在地理信息系统等领域有着广泛的应用,通常被用于生成不规则三角网(Triangular Irregular Network,TIN)模型,并被用于描述地表的形态.基于传统的逐点插入法,提出一种改进的Delaunay三角网生成算法,通过合理的数据结构与拓扑关系,建立新生成的三角形之间以及点插入前后三角形之间的联系,优化三角形定位过程.首先通过点集凸包生成若干个初始三角形,然后依次插入各点,新点的三角形定位从前一插入点所在的三角形开始,可大幅缩短三角形定位过程的搜索路径,快速定位到新点所在的三角形,当所有点均插入后,最后对整个三角网进行局部优化.实践表明了该算法的高效性和稳定性.     

在ImageJ中实现DEM建模及三维可视化

目的 针对DEM建模及三维可视化时间过长的问题,提出一种缩短DEM建模及三维可视化时间的方法.方法 采用改进Delaunay三角网构建DEM,在ImageJ中实现其三维可视化.结果 笔者提出的改进算法建模时间低于基于分治算法和基于凸包算法建模,在实现DEM三维可视化上,利用ImageJ完成的速度快于利用OpenGL、Direct3D和VRML实现的三维可视化.结论 通过对不同数量样本点的测试分析,该算法缩短了DEM建模时间,同时加快了DEM三维可视化的速度.     

应用一级邻近点生成加权Voronoi图的思想

加权Voronoi图是普通Voronoi图的一种扩展形式,在Voronoi图中各Voronoi边是在2个互为一级邻近点的点之间形成的,基于该理论,给出了一种生成加权Voronoi图的思想:用Delaunay三角网先找出各点的一级邻近点,再按加权Voronoi图的性质计算出各点的Voronoi边的数据,最后根据数据画出加权Voronoi图.     

基于不规则三角网的分块地形网格生成算法

利用不规则三角网(TIN）拓扑灵活性,研究了一类基于TIN的分块地形网格生成算法.经典分块层次细节（LOD）程序采用基于半规则三角网（SRN）的网格生成算法,存在冗余顶点过多的缺陷.新算法基于Delaunay网格生成技术,可生成不包含任何冗余顶点的TIN.给出地形绘制算法总体框架以及基于SRN的分块地形网格生成算法,指出冗余节点的产生机理,讨论基于TIN的分块地形网格生成算法,重点研究基于Bowyer-Watson增量插点内核的Delaunay网格生成算法及其健壮性问题,同时给出三角形条带化的技术途径.实验结果表明,在典型的应用中,新算法能使简化后的分块地形网格规模降低3 成左右,这不仅减少了中间文件大小,也有利于提升后续的绘制效率.     

面向矿区复杂地质体的四面体生成算法

地质学及矿山研究对象主要特点是结构复杂、非均质、各向异性，四面体网格生成面临的关键技术难题是生成的四面体网格必须保证各个单一地质体边界的一致性．为解决以上问题，本文提出了一种基于面扩展的快速Delaunay四面体网格生成的分治算法，算法首先将地质模型分解为多个简单地质体，利用给定的边界数据样点将这些单一地质体边界进行三角剖分，然后从边界三角形开始递归生成各个简单地质体的四面体网格，最后再将各个简单地质体网格合并为一体．本算法生成的四面体网格可保证多个地质体边界一致，避免四面体单元重叠，且大部分四面体网格符合Delaunay法则．     

地形三维可视化方案

采用生成Delaunay三角网的改进算法进行地形建模,以达到提高构网效率的目的,然后在DirectX9中用CJHJ 2005实现了川西某地域的三维可视化,并在此基础上,讨论了基于三角网的应用分析功能的实现,为三维地形的实施提出了有效的方案.     

不规则区域内基于D-TIN的等值线生成算法

以基于Delaunay不规则三角网络的算法为基础,提出一种在不规则区域内,使用离散点数据生成等值线的改进算法.算法包括三角网生成、等值线追踪等过程.应用结果表明,这种算法是相当实用和有效的.     

Delaunay三角剖分的快速重建算法

本文描述了一种Delaunay三角剖分的快速重建算法,用以节省三角网格存储和传输时间.该算法既可以在基于均匀网格的Delaunay三角化过程中,直接生成点集序列,也可以推广到其他Delaunay三角剖分方法的输出结果,在O(n)的时间内生成点集序列.简单遍历这个点集序列就可以在O(n)的时间内重建Delaunay三角剖分.与以前的算法相比,该算法具有重建操作简单、执行速度快、拓扑信息完全隐藏在点集序列中、不需要增量插入操作等特点.     

改进的构建约束Delaunay三角网的算法

当前构建约束Delaunay三角网的算法在影响域为凹多边形的情况下不是很稳定,甚至失效。在介绍了Delaunay三角网的相关的概念和算法基础上,重点研究了约束Delaunay三角网生成算法以及影响域为凹多边形的相关问题,提出基于对角线交换的改进算法。实验表明,该算法能够解决影响域为凹多边形等的各种特殊情况,程序稳定简单,易实现。     

相容线性系统的行投影块迭代算法

探讨了一种行投影块迭代算法来求解大型相容线性系统.该算法基于Kaczmarz算法,主要思想是首先对系数矩阵A进行分块,然后通过选取离当前迭代点距离最远的块来进行投影,并将投影作为下一个迭代点.数值结果显示,行投影迭代算法对坏条件问题非常有效,所提出的算法与经典的C imm ino算法相比,收敛速度更快.另外还提出一种新的对系数矩阵A分块的列分解策略,该策略基于每块的列相关性估计而得出.