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

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

一种Delaunay三角剖分的改进算法

Delaunay三角网的构建算法和设计在GIS分析管理以及可视化等方面有着重要的作用。本文将逐点插入法和凸包法进行融合,利用Akl-Toussaint启发式函数来剔除原始数据点集中的多余点以便快速高效的实现凸包的构建,利用角度判别对角线法来对生成的初始三角网进行优化,在此基础之上提出了生成Delaunay三角网的改进算法。实践表明,该算法对于小量或大量数据集均有较好的适应性,不仅具有与分治算法一致的高效性,还具有易于理解和实现的算法思路。     

基于分治算法与逐点插入法的Delaunay三角网建立算法的改进

Delaunay三角化在诸多应用领域都具有极其广泛的用途,也一直是GIS领域的重要研究内容。本文针对在Delaunay三角网建立中比较常用的分治算法即逐点插入法的缺点提出一些改进方案,在对逐点插入法改进的前提下提出将分治算法与逐点插入法相结合的综合算法。该综合算法既具有分治算法的高效率又具有逐点插入法的内存消耗小的优点,同时又较好地解决了分治算法与逐点插入法各自的缺点。     

Delaunay三角网建立的改进算法

本文深入研究了Delaunay三角网建立算法中的逐点插入法,详细介绍了算法的实现步骤,分析了其中影响算法效率的关键环节,并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化,对三角形快速定位方法进行了改进。测试实验的结果说明,算法改进后Delaunay三角网建立的效率提高了4~6倍。     

一种快速二维 Delaunay 三角网点定位算法

在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。     

基于格网和方向法索引的Delaunay三角网生成算法

Delaunay三角网在地形表达、表面对象重建、数字城市等GIS领域有着广泛的应用。常见的三角网构建算法中的逐点插入法算法简单、灵活,但是其效率受查找三角形的约束。文中提出一种用虚拟格网索引和方向法相结合的方法,改进对三角形的索引、对点定位的算法,能有效提高构建三角网效率。通过实验证明,这种方法对计算机硬件配置要求较低,且效率高,构建Delaunay三角网的效果好。     

基于格网和方向法索引的Delaunay三角网生成算法

Delaunay三角网在地形表达、表面对象重建、数字城市等GIS领域有着广泛的应用。常见的三角网构建算法中的逐点插入法算法简单、灵活,但是其效率受查找三角形的约束。文中提出一种用虚拟格网索引和方向法相结合的方法,改进对三角形的索引、对点定位的算法,能有效提高构建三角网效率。通过实验证明,这种方法对计算机硬件配置要求较低,且效率高,构建Delaunay三角网的效果好。     

Delaunay三角网的并行构网算法

针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。     

基于VTK的Delaunay三角网生成研究

Delaunay三角网作为一种主要的DTM表示法,具有极其广泛的用途.经过20多年来的研究,它的生成算法已趋于成熟.本文简要介绍了Delaunay三角网的定义及其特性,在简单回顾和评价分割一归并法、逐点插入法、三角网生长法等三类主流算法的基础之上,初步探索了基于vtk类库的De1aunay三角网生成过程,并以实例显示了效果.     

一种Delaunay三角网的快速生成算法

本文以Lawson提出的逐点插入法为基础，借鉴方向搜索的思想，在确定插入点的影响凸包时，采用递归的局部搜索策略，形成了一种Delaunay三角网的快速生成算法。实验证明，新算法构网时间与点数基本成线性增长关系，具有较高的效率。     

Delaunay三角网中点目标快速定位算法研究

为了提高内插法的构网速度及方便数字地面模型的后续应用,本文对三角形定位算法进行了研究,对基于点-线关系的方向定位算法和基于线-线关系的方向定位算法进行了改进,算法极大地减少了定位目标三角形的时间,由于定位三角形的速度是影响内插构网速度的一个关键因素,从而提高了构网速度。同时对两种算法进行了分析比较,得出最速方向定位算法更健壮,其定位路径唯一,效率更高。     

Delaunay三角形构网的分治扫描线算法

Delaunay三角网作为一种主要的DTM表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。     

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

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

顾及局部差异的航海图线要素复杂度度量EI北大核心CSCD

针对当前线要素复杂度的度量多基于单一线要素求取整体复杂程度,难以顾及局部差异变化这一现状,提出一种用于航海图线要素复杂程度的度量方法。首先,分析了线要素节点所构三角网边长与线要素复杂程度的关联性;然后,通过构建约束Delaunay三角网、计算线要素数据点复杂度并内插等操作,得到了航海图线要素复杂场;最后,选取两组不同的典型海域航海图作为试验数据,并通过统计试验验证了本文方法的合理性。试验结果表明:本文方法在顾及局部差异的基础上,能较好地定义航海图线要素的复杂度,并可精细化地定量评估航海图线要素在各区域的复杂程度。     

约束Delaunay三角剖分的“岛屿”类图斑符号填充

针对传统方法对“岛屿”类图斑进行符号填充会造成敏感区域符号布局不合理或符号空间冲突的问题，本文提出了一种约束Delaunay三角剖分的“岛屿”类图斑符号填充方法。首先，对“岛屿”类图斑对应的离散点群进行规则网格化和不规则三角剖分，用于计算等值点；然后，依据附加准则增加“凸”形和“凹”形附加点，顺次连接等值点和附加点作为Delaunay三角剖分的约束边界；最后，构建均匀变化的约束Delaunay三角网，在三角网内进行图元积分，填充“岛屿”类图斑符号。利用电子海图中岛屿边界点数据进行试验分析，与传统方法相比，本文方法填充的“岛屿”类图斑符号变化均匀，交互性较强，便于用户修改和切换，进行二次填充。试验结果表明，本文方法适用于“岛屿”类图斑的符号填充。     

三角形增长算法构建Delaunay三角网DEM的原理与实现

本文主要论述了三角形增长算法建立Delaunay三角网DEM.首先通过最优边找首三角形,其次通过直线与点几何关系来寻找可能扩展点,通过找最大夹角来判断满足狄洛尼法则的扩展点,最后通过新加入边与已扩展边的数目来判断是否为重复狄洛尼扩展点,符合条件则构建三角网.然后通过空外接圆法则验证了所构三角网符合狄洛尼三角网的条件.狄洛尼三角网的建立和空外接圆的验证程序采用M语言来编写.     

露天矿精细DEM模型的建立及更新方法

由于露天矿复杂特殊的地形特征,在建模过程中应充分考虑相应的约束条件,否则会出现台阶被削平等现象。本文提出一次性约束三角网生成算法,经过空间数据提取、拓扑关系建立以及空间索引建立,最终建立起边界约束线以内的约束不规则三角网;并提出扩展边界概念,利用扩展边界及上述三角网生成算法,可实现局部模型建立以及局部模型与整体模型间的无缝拼接,最终完成整体DEM模型的更新。