基于Delaunay三角网法的土石方量计算精度探讨

土石方量的计算是工程施工预决算的依据,其直接关系到工程的费用概算和方案选择。本文介绍了基于Delaunay三角网的土石方计算方法。利用编程实现构建Delaunay三角网程序计算土石方量,通过仿真实验和实际数据计算土方量,与传统三角网法进行对比,说明该方法土方量计算的精度。

结合FREAK和Delaunay三角网的图像匹配算法

针对机器人搭配视觉对目标物进行检测、识别和抓取等作业,提出了一种结合FREAK和Delaunay三角网的图像匹配算法。该算法综合了FREAK特征检测算法能获取到快速稳定的获取特征点和Delaunay三角网算法,能够利用FREAK特征点的粗匹配点对构建三角网的优势,以颜色不变量模型作为FREAK的输入,利用K近邻算法解决FREAK算法引起的颜色特征信息丢失和特征点过于密集的问题。根据三角形相似度函数保留Delaunay三角网中三角形相似度大于0.75的三角形,剔除错误匹配对数,提高匹配精度。通过实验论证该算法的优势和可靠性,与当前匹配算法相比,该算法能有效的提高图像的匹配率。

Delaunay三角网的生成算法研究

Ｄｅｌａｕｎａｙ三角网作为一种主要的ＤＴＭ表示法，具有极其广泛的用途。经过二十多年来的研究，它的生成算法已趋于成熟。本文简要介绍了Ｄｅｌａｕｎａｙ三角网的定义及其特性，在简单回顾和评价了分割－归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。经测试，一般情况下它的运算速度远快于逐点插入法，与分割－归并法相当，较好的情况下快于分割－归并法。

高效构建Delaunay三角网数字地形模型算法研究

在对传统构建Delaunay三角剖分 (尤其是分割 合并 )算法进行分析的基础上 ,采用自适应格网划分方法对点集进行排序、分割 ,并按照逆序合并Delaunay子三角网 ,然后进行约束处理 ,快速、高效地实现了Delaunay三角网的构建 ;对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明 ,该算法的时间复杂度接近于O(n)。

基于Delaunay三角网的等值线绘制算法

提出了一种快速构建Delaunay三角网算法(QGDTN)。在每次迭代中,该算法从点集P最左边的两点中,选取离凸边中点距离最近的一点与凸边构成Delaunay三角形,并加入三角网中,算法实现简单,且时间复杂度为O(n)。基于Delaunay三角网,根据三角形的各边上是否有等值点,用内插值法求出等值点坐标,跟踪、连接等值点生成等值线;最后,采用三次方Bezier曲线平滑等值线。实验证明,基于Delaunay三角网的等值线绘制算法是高效的,并且具有一定的实用价值。

一种生成Delaunay三角网的合成算法

经过２０ 多年的研究，自动生成Ｄｅｌａｕｎａｙ 三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３ 类。其中前两类较第３ 类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。

快速构建Delaunay三角网算法研究

研究一种快速构建 Delaunay三角网的算法 ,该算法结合逐点插入算法和分治算法 ,具有建网速度快、耗费空间小的优点。采用多级自适应网格划分点集 ,对叶子网格内的点采用改进了的逐点插入算法生成子三角网 ,子三角网间利用分治算法的思想进行合并。经实践验证 ,算法复杂度与点数几乎成线性关系。

一种基于三角网扩张法的Delaunay三角网逐块归并算法

本文中提出一种基于三角网扩张法的不规则三角网的逐块归并算法,它采用按横向或纵向对离散点集切割分块,对各子块用三角网扩张法构建Delaunay三角网,最后用三角网扩张法依次将相邻的子网合并。该算法采用的子集分块的做法使构网时的搜索范围减小,在数据量较大时避免了计算时间随点数的指数次增加,同时在构网时也能保证三角形邻接关系的正确维护。

约束Delaunay三角网生成算法研究

对约束Delaunay三角网的构建算法进行研究,并提出一种约束Delaunay三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高构网速度。

构建Delaunay三角网的一种新型生长法——壳外插入法

基于逐点插入法中影响域的概念,提出一种新的三角网生长算法——壳外插入法。该算法以三角网外围的凸包生长为基础,通过查找生长边、内蚀既有网、重构三角网3个基本操作,达到既有网在保持Delaunay特性的同时纳入新点,从而实现三角网的生长。该算法克服了传统生长法需要查找第3点的缺陷,也避免了逐点内插法大量三角形定位的操作,因而算法的平均复杂度达到O(NlogN)。使用了大量的随机散点数据和常吉高速的实测地形点数据对算法进行测试,证实该算法快速有效。

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

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

基于分治策略的快速构建Delaunay三角网算法

目的降低构建Delaunay三角网的时间复杂度,提高构建Delaunay三角网的速度.方法首先递归分割点集,然后按照构网条件以分割线为轴线对其两侧的点进行构造三角网的操作,直至每个点都被包含进所构建的三角网,最后使其成为Delaunay三角网.结果通过1000～5000个点的测试,表明基于分治策略的快速构建Delaunay三角网的生成速度要快于传统基于分治策略生成Delaunay三角网的速度.结论该方法能够到边建网边优化,使程序一次成型,提高了建网速度,本算法的设计思想还可以推广到三维空间.

建筑物合并的Delaunay三角网分类过滤法

建筑物面合并的方法是大比例尺地图综合研究的重要内容之一,本文提出了一种借助三角网进行建筑物合并的方法:针对约束Delaunay三角网中三角形的形态特征,提出了6种度量参数,依据这些参数进行排除和修复筛选操作;然后自动识别保留下来三角形的外轮廓作为建筑物之间的桥接部分,并对其进行直角化处理;接下来通过桥接部分和建筑物面的融合实现建筑物的合并,同时保持其直角化特征。最后,以多样性的实际数据进行实际处理,验证了该方法的正确性和高效性。

Delaunay三角网的交互编辑算法设计与实现

本文在基于四叉树分块构建Delaunay三角网的基础上,设计与实现了面向大地形编辑的以四叉树为空间索引的三角网交互实时编辑系列算法,其中包括约束点的加入、约束线的加入以及共点三角形的快速查找算法。以上算法的设计与实现是地形编辑的基础算法,算法的执行效率对以地形为代表的三维实体的实时编辑以及相关地物模型的拟合具有重要意义。

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理。在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率。

基于Delaunay三角网的Shapefile几何纠正算法与实现

一般的商业软件只提供比较简单的算法,能够对矢量数据几何纠正实现简单的、全局意义上的处理。研究以Delaunay算法为基础,提出了基于二维平面剖分的、具有局部意义的矢量数据几何纠正算法。在Visual Studio2005开发环境下,使用C#2.0与C++分别实现相关功能,完成了算法的实现。文中提到的解决方法在东北地区2005年土地利用数据库更新项目的空间数据集成问题中得到了成功应用。

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

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

生成Delaunay三角网的快速合成算法

合成算法结合了传统的递归分割法和逐点插入法的优点,兼顾空间和时间性能.然而,该算法不可避免地继承了两种传统算法的不足,在执行效率上受到限制.为了解决执行效率问题,提出了快速合成算法,对合成算法进行了改进和优化.该算法基于面积坐标的点定位算法和简化的高效空外接圆判断算法,从而大大提高算法的整体执行效率;同时充分考虑平面点集的任意性,适用于对任意平面点集构建Delaunay三角网.

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

Delaunay三角网在GIS/VR中用途广泛,分割—归并法和逐点插入法是目前普遍用于生成Delaunay三角网的两种算法。在研究基于这两种算法的合成算法后,对其进行了两点改进。一是简化凸壳的生成;二是三角形快速定位,通过确定向量之间的关系来解决点的定位问题,避免了复杂运算。实验结果证明,改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高。

基于Delaunay三角网的等高线树生成方法

研究如何利用Delaunay三角网构建等高线树,提出一种新的等高线树生成方法。该方法充分利用Delaunay三角网在领域分析中的优势,通过两次利用Delaunay三角网来判明等高线的空间关系进而达到统一被图廓截断的等高线以生成等高线树的目的。本文将等高线作为约束边构建约束型Delaunay三角网,利用Delaunay三角网查找具有邻接关系的等高线,在此基础上结合邻近等高线的高程关系判明、识别,最终统一被截断的等高线;然后对统一后的等高线再次利用Delaunay三角网查找具有邻接关系的等高线对,利用等高线对的高程关系判断出其为父子关系或兄弟关系,据此将等高线插入到相应的位置,逐步生长成等高线树。同时给出了基于Delaunay三角网的等高线树生成方法的算法设计及试验结果。