基于Delaunay三角网模型的等高线地形特征提取及谷地树结构化组织

基于Delaunay三角网模型在矢量等高线基础上通过弯曲特征分析 ,给出了一种地形结构特征提取及谷地树组织的方法 ,与传统的基于DEM或TIN数据结构提取地形特征的方法相比 ,该方法不仅得到了谷地系统在平面图上的拓扑结构 ,还获得了河谷在空间分布上的汇水范围 ,依托矢量线、多边形的几何关系判断 ,增强了谷地树组织中的结构化 ,避免了DEM方法中的噪音干扰 ,方法的核心是Delaunay三角网在单根等高线弯曲深度表达上的层次结构识别。基于系统地实验详细讨论了 3种树的结构化组织 :等高线弯曲特征嵌套结构表达的二叉树、谷地系统拓扑关系表达的平面结构树、水文意义上主支流河谷表达的语义层次树。

基于Delaunay三角网模型的点军标群聚合显示方法

从视觉分辨原则出发,以空间邻近图为支撑几何构造,提出点状军标群聚合显示新方法。该方法首先以Delaunay三角网为工具,计算点状军标群空间邻近关系,生成空间邻近图,而后基于利用视觉分辨原则,基于空间邻近图通过连接边剪枝、群组聚类和显示替换等步骤实现聚合显示。仿真实验结果表明,该方法能够有效解决点状军标空间占位冲突,而且在多比例尺聚合显示条件下,保持聚合结果层次性,符合视觉认知规律。

刍议基于一次性构建Delaunay三角网模型实现视域分析

任何军事行动都离不开对地形的分析和判断,视域分析作为地形分析的重要组成部分,在军事行动的许多方面都具有极其重要的应用价值。在一次性构建约束Delaunay三角网DEM模型的基础上,结合模型的数据结构特点,分析、研究了两点可视、范围可视以及区域可视的3种视域分析算法。

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

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

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

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

基于Delaunay三角网的水轮机模型效率计算

提出一种新型求取水轮机模型综合特性曲线中随机插值点的效率方法,将水轮机综合特性曲线中等效率η线类似为等高线,利用VB处理数据,将采样点单位统一后构建Delaunay三角网,应用三角形内插法可较精确地求得综合特性曲线中各随机插值点的效率。

三维网格模型的局部三角剖分算法

为了提高三维网格模型的渲染显示效率和提高网格质量以满足有限元分析,提出了一种新的三维网格模型的局部三角剖分方法。本方法的三角剖分基于Bowyer-Watson插点算法实现。通过在新插入点的邻域内搜索三角形来提高三角剖分的效率,通过对网格的几何形状和连通性进行局部修改来提高网格质量。通过尺寸场来约束控制三角剖分区域,使得生成的网格质量和算法性能有较好的综合表现。

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

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

Delaunay三角网的生成算法研究

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

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

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

快速构建三角网数字地形模型方法的研究

改进和优化了逐点插入算法 ,通过建立网格索引 ,实现了DTM数据的高效组织和管理 ,再结合有向查找技术 ,研究出了三角形的快速定位算法。采用Watson的空外接圆法优化构网 ,为减少优化时间 ,提出了按网格轮流取点的策略。在地性线的处理上 ,采用了先构建初级Delaunay三角网 ,再将地性线做为约束边嵌入初级网中的二级建网方案。经实践验证 ,该算法具有速度快、网形优、精度高。

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

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

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

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

基于Voronoi图和Delaunay三角网的林分空间结构量化分析

利用Voronoi图具有最近性、邻接性特点,以单株木视为平面点构建Voronoi图和Delaunay三角网,此结构具有以下特点:对象木的最近邻木株数与Voronoi图中相对应多边形边的数目相等;对象木与最近邻木的距离和Delaunay三角网的相对应边长相等;任意2个最近相邻木的夹角即为对应Delaunay三角网2条边的夹角。在广东湛江红树林国家自然保护区选择样地进行试验,把基于Voronoi图和Delaunay三角网计算林分空间结构指数的结果与最近邻木数取4的传统算法结果进行对比分析,结果表明:两者在计算混交度、大小比数时结果有较高的相关性和一致性,但两者在计算角尺度时结果差异较大,构建Voronoi图确定最近邻木时各个方向都有选取,角尺度的取值均小于传统计算方法,但是Delaunay三角网结构本身较好反映个体在水平地面的分布格局,且基于Voronoi图和Delaunay三角网林分空间结构研究不需要对象木与邻木距离量算和角度测量。

基于Voronoi图和Delaunay三角网的杉木游憩林空间结构

基于Voronoi图和Delaunay三角网建立空间结构单元的方法,采用聚集指数、混交度、大小比数、竞争指数和开敞度5个指数分析福建将乐国有林场典型游憩林的林分空间结构特征。结果表明:杉木游憩林以1株对象木周围6株最近邻木的构成形式最为常见,林分平均聚集指数R为1.05;林木空间分布格局呈均匀分布;林分平均混交度M-为0.48,树种空间相互隔离程度不高,处于中等混交状态;林分平均胸径和树高大小比数分别为0.49和0.51,林木胸径、树高分化不太明显,林分处于中等竞争状态;优势树种中,杉木竞争指数CI为346.27,具有较强竞争力;林分平均开敞度K-为0.21,林分内林木生长空间不足。在维持现有林分条件的基础上,应增大林内开敞度以便进一步优化林分空间结构,提升游憩林的游憩价值。

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

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

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

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

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

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

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。

Delaunay三角网支持下的多边形化简与合并

多边形的化简与合并运算是自动化制图综合中的重要算子 ,这类算子的设计要基于多边形几何特征、拓扑特征的分析 ,还需要一种有力的空间数据模型用于支持多边形各弯曲特征部位之间、多边形与多边形之间、多边形的各岛屿之间邻近关系探测 .鉴于 Delaunay三角网的“最大最小角规则”和“外接圆规则”,使得其成为空间邻近分析的一种强有力工具 ,因此在二维空间建立约束 Delaunay三角网模型和形式化检索机制的基础上 ,系统地讨论了多边形弯曲特征的化简、夸大 ,以及邻近多边形合并的方法 ,并将多边形化简分解为“岛屿”选取、凹部填充、狭长区域中轴化、保留凹部的夸大 ,以及凸部的弃除等几个步骤完成 ,又将多边形合并区分为吸收式、包络式、分解式等 3种情形 。