共查询到20条相似文献,搜索用时 62 毫秒
1.
Delaunay三角网建立的改进算法 总被引:5,自引:0,他引:5
本文深入研究了Delaunay三角网建立算法中的逐点插入法,详细介绍了算法的实现步骤,分析了其中影响算法效率的关键环节,并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化,对三角形快速定位方法进行了改进。测试实验的结果说明,算法改进后Delaunay三角网建立的效率提高了4~6倍。 相似文献
2.
利用局部动态最优Delaunay三角网改进逐点内插算法 总被引:3,自引:0,他引:3
针对传统的基于Delaunay三角网的逐点内插算法难以同时兼顾精度和效率的问题,依据Voronoi单胞和Delaunay三角形的几何特性,提出了一种基于局部动态最优Delaunay三角网的逐点内插算法,并在格网数字水深模型(grid digital depth model,Grid-DDM)中进行应用。实验结果表明,该改进算法能保证插值精度并明显提高执行效率。 相似文献
3.
4.
针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。 相似文献
5.
6.
Delaunay三角形构网的分治扫描线算法 总被引:2,自引:0,他引:2
Delaunay三角网作为一种主要的DTM表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。 相似文献
7.
分析常规三角网生长算法的优缺点,提出点角概念,在生成Delaunay三角形的过程中,逐步缩小离散点的搜索范围,克服常规算法时间效率低的缺点。构网过程中,完全遵守Delaunay三角网的剖分准则,验证算法的稳定性和高效性。 相似文献
8.
9.
10.
针对常见的三角网构建算法效率受查找三角形的约束的问题,该文提出了一种基于格网划分的Delaunay三角网快速生成算法,对传统逐点插入算法的点定位及LOP算法进行了优化。通过对离散点数据进行格网划分,将三角形面积坐标法与直线行走算法相结合,在点定位过程中可大幅度缩短搜索路径,快速定位到插入点所在的目标三角形。实验结果表明,改进后的算法兼顾了时间和空间的性能,执行效率明显提高,定位路径惟一且为最佳路径。 相似文献
11.
基于格网划分的海量数据Delaunay三角剖分 总被引:7,自引:1,他引:7
提出基于格网划分、面向海量数据的Delaunay三角剖分方法,它首先把数据集划分为若干格网块,按照格网划分的逆序对每个格网块采用基于自适应格网划分的分割-合并算法进行Delaunav三角剖分,把格网块Delaunay三角网中不受边界影响的三角形进行存储并释放内存,然后顺序合并相邻格网块Delaunav三角网,形成全局或类全局Delaunay三角网.该方法对计算机硬件配置要求较低,适合于并行处理,可以实现面向海量数据的Delaunay三角剖分. 相似文献
12.
约束数据域的Delaunay三角剖分与修改算法 总被引:63,自引:1,他引:63
顾及地形特征线的散点域(约束数据域)三角剖分是建立高精度数字地面模型的基础,在GIS、地学分析、计算几何、多分辨率DTM等领域中有着广泛的应用。本文研究了约束数据域的Delaunay三角剖分剖,简要分析了现存的算法特点并提出了约束数据域的Delaunay三角剖分的迭代算法和删除算法。 相似文献
13.
本文在分析现存算法特点的基础上,研究了影响约束数据域Delaunay三角剖分算法效率提高的因素,提出了优化算法,并进行了详细的程序流程设计。同时以优化算法在公路定线中的应用为例,证明了该算法能更好地处理带线约束、区域约束的构网问题,且具有构网速度快、网形优、精度高、算法稳定等特点。 相似文献
14.
岛屿就是由一条或多条首尾闭合有向的弧段组成的区域,弧段与弧段之间彼此不相交,岛屿间彼此可以多层嵌套也可以相互独立。经过对岛屿间的关系进行分析后,将组成岛屿的弧段分为4种基本类型,并给出分类算法,根据弧段的类型自动识别岛屿的"内部"和"外部",凡是"外部"就约定为岛屿的"空洞"。围成岛屿的弧段就构成了岛屿的约束条件,在岛屿内部先进行弧段上CDT的构造,然后在CDT的基础上构造DT,以实现在岛屿"内部"带有约束条件的三角网剖分,从而可以构造出任意复杂的带岛屿群的三角网,经过编制相关程序验证该算法的效率主要取决于构造DT的效率。 相似文献
15.
随着三维激光扫描技术应用领域的不断拓展,对点云数据三维建模的需求越来越迫切。曲面重建技术作为三维建模的核心技术之一,在逆向工程、计算机视觉、计算机制图以及虚拟现实等技术领域都有着非常广泛的应用前景。本文提出一种基于三维狄洛尼三角网的曲面重建算法,其本质是一种结合了曲面生长算法思想的贪心算法,即在一定约束条件下,按照最优三角形选择标准,算法从预先构建好的三维狄洛尼三角网中,逐个筛选出最优三角形添加到生长曲面上,最终输出由一系列显式三角形所组成的流形曲面。这种方法对比目前主流的隐式曲面重建算法具有参数依赖性较小、不需要计算法线等优点,并且能够重建地形扫描、建筑物扫描和精细化扫描的点云模型。利用此算法对多种点云模型进行曲面重建试验,结果表明该算法生成曲面质量好、重建效率高、实用性强,能够很好地应用于三维建模领域。 相似文献
16.
提出了一种基于Delaunay三角网的栅格线划矢量化方法。通过运用Delaunay三角网对栅格线划要素进行空间剖分,并根据单个Delaunay三角形的形状特征,提取线划要素骨架线。以栅格地图预处理、线划要素实体识别、线划要素边缘点集生成、线划要素边缘点集Delaunay三角网生成,以及基于Delaunay三角形公共边中点追踪的线划要素骨架线提取为技术路线,详细介绍栅格线划矢量化的具体实现过程,并进行若干实验,以验证方法的准确性与时效性。 相似文献
17.
基于TIN的半自动多影像同名线段匹配算法研究 总被引:1,自引:0,他引:1
刘亚文 《武汉大学学报(信息科学版)》2004,29(4):342-345
提出了根据同名像点构成三角网 (TIN)来进行同名直线的匹配。依据TIN预测左影像上一条给定直线在右影像上同名直线的搜索范围,计算给定直线与候选直线的灰度相关系数,取最大相关系数所对应的直线为同名直线。实验证明,该算法简单、可行。 相似文献
18.
19.
众源开放街道地图(OpenStreetMap,OSM)作为志愿者地理信息的典型代表,其数据质量制约了城市主干道提取。为此,引入约束Delaunay三角网,运用类似Voronoi图的空间等剖分几何构造表达道路线密度,通过线密度变化与三角形边长表征主干道形态特征,并集成两个指标构建主干道识别模型;类比林火蔓延扩展过程,提出了基于Delaunay三角网的OSM主干道多边形提取方法。运用5个城市的OSM数据进行实验,结果表明,该方法能有效提取主干道多边形,并且与OSM路网中的道路等级属性趋于一致。 相似文献