单机多核环境下的TIN地形并行构建关键技术研究

发布时间：2017-04-25 05:07

  本文关键词：单机多核环境下的TIN地形并行构建关键技术研究，由笔耕文化传播整理发布。

【摘要】：不规则三角网(TIN)在表达地表形态方面具有很大的优势,它能精确的逼近地形表面,反应地形的原始细节,并且能够避免因地形的平坦陡峭造成的数据冗余,因而被广泛用于地形构建,Delaunay三角网剖分生成的TIN(简称D-TIN)由于具有许多突出的性质,如能避免出现狭长的三角形,因而相比其他剖分方式更具有实际应用价值,本文研究的基于多核下大地形并行构建就是以D-TIN的并行构建入手,D-TIN串行方面的构建经过几十年的发展已经相当成熟,然而在并行方面的研究虽然也有较多成果,但大多数都是针对分布式多处理机的集群环境进行的,很少有关于D-TIN在单机多核环境下的应用,为了充分利用有限的资源,挖掘单台计算机的并行潜能,本文设计出了一套适合多核环境下的D-TIN并行构建方案。主要的研究内容和成果包括以下几个方面:(1)本文对D-TIN并行构建过程所涉及到的包括矢量数据读取、可视化方法、无约束与约束情况下三角网的构建方法及数据结构、并行模型、并行方式、数据划分策略等理论都做了详细的介绍,为整个论文的研究奠定了良好的理论基础。(2)通过分析总结当前D-TIN并行研究现状,提出了基于分治算法结合四方边缘结构,以Open Mp为多核并行模型的并行设计方案。(3)对无约束域离散点三角网的并行构建中关于子凸包并行构建和并行合并算法进行了详细描述,并通过具体实验生成了并行与串行构建的结果,比较了时间效率、加速比和并行效率等,结果证明多核并行设计方案切实可行。(4)为了更加真实的表达地形实际情况,本文加入了约束地物(如房屋、河流等)来进行并行构建,主要通过插入以多边形为例的约束地物,研究了顶点插入、边插入和内部清空整个流程的算法,并对其并行改造做了介绍,同样通过具体实验生成了并行与串行的构建结果,评估了各指标。实验证明采用并行方式实现,能有效提高整体性能,节约时间成本。
【关键词】：D-TIN 多核并行 分治算法 四方边缘结构 OpenMP
【学位授予单位】：江西理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6
【目录】：

• 摘要3-4
• Abstract4-7
• 第一章 绪论7-16
• 1.1 研究背景及意义7-9
• 1.1.1 研究背景7-8
• 1.1.2 研究意义8-9
• 1.2 国内外研究现状9-13
• 1.2.1 D-TIN串行构建算法现状9-11
• 1.2.2 D-TIN并行构建算法现状11-13
• 1.3 研究内容及技术路线13-14
• 1.3.1 研究内容13
• 1.3.2 技术路线13-14
• 1.4 论文组织结构14-16
• 第二章 相关理论技术介绍16-35
• 2.1 矢量数据读取和处理16-17
• 2.1.1 GDAL简介16
• 2.1.2 OGR操作矢量数据16-17
• 2.2 OpenGL在三角网可视化中的应用17-19
• 2.2.1 OpenGL简介17-18
• 2.2.2 Qt中的OpenGL可视化模块18-19
• 2.3 Delaunay三角网剖分算法19-27
• 2.3.1 Delaunay三角网性质19-20
• 2.3.2 四方边缘结构Quad-Edge20-22
• 2.3.3 非约束Delaunay三角网剖分22-25
• 2.3.4 约束Delaunany三角网剖分25-27
• 2.4 多核并行计算理论27-31
• 2.4.1 并行计算概述27-28
• 2.4.2 多核并行方式28
• 2.4.3 D-TIN并行构建算法数据划分策略28-31
• 2.5 共享内存模型OpenMP31-34
• 2.6 本章小结34-35
• 第三章 无约束域离散点三角网并行构建35-52
• 3.1 实验环境与平台搭建35-37
• 3.2 基于四方边缘结构的分治算法并行实现37-47
• 3.2.1 数据分割生成子网凸包39-42
• 3.2.2 子网合并方法42-47
• 3.3 三角网并行构建动态绘制47-48
• 3.4 实验性能测试与分析48-51
• 3.5 本章小结51-52
• 第四章 约束地物并行插入构建52-68
• 4.1 非凸多边形网格化填充52-53
• 4.2 约束点逐点插入过程53-56
• 4.2.1 点快速定位53-55
• 4.2.2 Lop优化过程55-56
• 4.3 基于对角线交换法下约束边动态嵌入56-58
• 4.4 清空约束多边形内部边58-60
• 4.5 实验性能测试与分析60-62
• 4.6 三维地形可视化62-66
• 4.7 本章小结66-68
• 第五章 总结与展望68-70
• 5.1 研究结论68-69
• 5.2 问题与展望69-70
• 参考文献70-73
• 致谢73-74
• 攻读学位期间的研究成果74-75

【参考文献】

中国期刊全文数据库 前5条

1 颜林;朱永杰;;改进的构建约束Delaunay三角网的算法[J];北京石油化工学院学报;2010年02期

2 袁正午;侯林;彭军还;;点集收集分配的Delaunay三角网快速生成算法及实现[J];测绘科学;2011年05期

3 马洪滨;郭甲腾;何群;刘馨蕊;;带岛屿多边形Delaunay三角剖分算法[J];东北大学学报(自然科学版);2009年05期

4 宋晓眉;张晓东;李建林;;一种高准确度的约束Delaunay三角网生成算法研究[J];地理与地理信息科学;2009年01期

5 贾婷;魏祖宽;唐曙光;金在弘;;一种面向并行空间查询的数据划分方法[J];计算机科学;2010年08期

  本文关键词：单机多核环境下的TIN地形并行构建关键技术研究，由笔耕文化传播整理发布。

，

本文编号：325665