学位论文 > 优秀研究生学位论文题录展示

D-TIN并行构建方法及其在地图综合中的应用研究

作　者: 齐琳
导　师: 沈婕
学　校: 南京师范大学
专　业: 地图制图学与地理信息工程
关键词: Delaunay三角网并行算法数据划分负载均衡地图综合
分类号: P283
类　型: 硕士论文
年　份: 2011年
下　载: 58次
引　用: 0次
阅　读: 论文下载

内容摘要

作为重要的几何计算工具,Delaunay三角网(Delaunay Triangulated Irregular Network,以下简称D-TIN)已被广泛应用于各个领域。近年来,随着计算机的发展,D-TIN在地图自动综合中也发挥了越来越重要的作用,逐渐成为了一项不可或缺的工具。经过几十年的研究,D-TIN生成算法已趋于成熟,但用于大数据量的处理时,目前的D-TIN构建效率仍不能够满足需求,因此,使用并行计算技术来提高构建效率是一条有效途径。D-TIN并行构建算法(以下统称D-TIN并行算法)的研究开始于20世纪80年代末,经过二十几年的探索,国内外学者提出了诸多的并行设计方案,其中,基于数据划分方式的D-TIN并行算法是最为常用的方法。数据划分结果的均衡性是保证负载均衡,从而提升此类并行算法性能的重要前提,传统D-TIN并行算法中的数据划分方法用于分布密度均匀的点集时可以获得相对平衡的划分结果和较高的划分效率,但用于分布密度不均匀的点集时,只能以牺牲划分效率为代价来获取划分结果的均衡性。针对此问题,本文提出了基于动态条带数据划分方法的D-TIN并行算法,并基于此将其应用于河流、等高线协同综合算中。本文的研究内容与成果主要包括以下几部分：1、分类总结了D-TIN生成算法、D-TIN并行算法以及D-TIN在地图综合的应用。对比并行算法设计模式的优缺点,选择了基于数据划分的方式进行D-TIN并行构建,并根据D-TIN生成算法的特点和研究现状,选取了经过改进的逐点插入算法作为本研究的基础算法。2、针对目前D-TIN并行算法研究中存在的负载均衡的问题与需求,提出了面向D-TIN并行构建的数据划分原则,并依据此原则设计了动态条带数据划分方法,满足了能够适用于包括集聚点集等多种分布类型点集数据,划分结果相对平衡且高效的数据划分需求。实验证明此方法有助于提高D-TIN并行算法性能。3、设计了D-TIN并行构建方法的实验平台,基于此平台编程实现了基于动态条带划分的D-TIN并行算法,使用不同规模的点集数据对算法进行了测试、统计与分析,对算法的运行时间、加速比、并行效率等指标做出了评估,结果证明该并行算法具有较好的时间性能和可扩展性。4、分析了地图综合对D-TIN构建的特殊需求,基于D-TIN并行构建方法,选取河流、等高线协同综合的D-TIN构建实验,将公共点求取、约束线段嵌入等主要过程进行了并行化设计,实现了面向河流、等高线协同综合的D-TIN的快速构建。

全文目录

摘要  4-5
Abstract  5-7
目录  7-10
图表索引  10-12
第1章绪论  12-21
  1.1 研究背景  12-13
  1.2 国内外研究现状  13-18
    1.2.1 D-TIN算法及其在地图综合中的应用研究  13-16
    1.2.2 D-TIN并行算法研究  16-18
  1.3 当前研究中存在的主要问题  18
  1.4 本研究意义  18
  1.5 本文研究内容、技术路线及章节安排  18-21
    1.5.1 研究内容  19
    1.5.2 技术路线  19-20
    1.5.3 章节安排  20-21
第2章相关理论基础  21-31
  2.1 基本概念  21-23
    2.1.1 D-TIN的相关概念  21-22
    2.1.2 D-TIN的特性  22
    2.1.3 并行计算相关概念  22-23
  2.2 D-TIN算法分类  23-25
    2.2.1 分治算法  23
    2.2.2 逐点插入算法  23-24
    2.2.3 三角网生长算法  24-25
  2.3 D-TIN在地图综合中的应用  25-28
    2.3.1 邻接关系识别  25-26
    2.3.2 冲突关系探测  26-27
    2.3.3 特征线提取  27-28
  2.4 并行算法设计方法及其评价方法  28-30
    2.4.1 并行算法设计方法  28-29
    2.4.2 并行算法性能评价指标  29-30
  2.5 本章小结  30-31
第3章 D-TIN并行算法数据划分方法与合并方法  31-41
  3.1 数据划分概述  31-36
    3.1.1 D-TIN串行算法中的数据划分  31-32
    3.1.2 D-TIN并行算法中的数据划分方法  32-34
    3.1.3 针对空间矢量数据的数据划分方法  34-36
  3.2 面向D-TIN并行构建的动态条带数据划分方法  36-39
    3.2.1 面向D-TIN并行构建的数据划分原则  36
    3.2.2 动态条带划分方法思想与过程  36-39
  3.3 D-TIN子网合并方法  39-40
  3.4 本章小结  40-41
第4章 D-TIN并行算法实验与分析  41-58
  4.1 并行编程环境概述  41-46
    4.1.1 并行计算机概述  41
    4.1.2 OpenMP概述  41-44
    4.1.3 实验平台与实验数据  44-46
  4.2 D-TIN并行算法概述  46-48
    4.2.1 基础D-TIN算法基本思想  46-47
    4.2.2 基于数据划分的D-TIN并行算法设计  47-48
  4.3 实验结果与分析  48-56
    4.3.1 动态条带数据划分实验  48-51
    4.3.2 D-TIN并行算法评估  51-56
  4.4 本章小结  56-58
第5章 D-TIN并行构建在地图综合中的应用  58-66
  5.1 地图综合算法中D-TIN构建特点  58-59
  5.2 D-TIN并行构建方法在河流、等高线协同化简中的应用  59-63
    5.2.1 基于约束D-TIN的河流、等高线协同化简概述  59-60
    5.2.2 多要素约束D-TIN并行构建方法  60-63
  5.3 实验结果与分析  63-65
  5.4 本章小结  65-66
第6章结论与展望  66-68
  6.1 本文结论  66
  6.2 存在问题与展望  66-68
参考文献  68-73
攻读硕士期间科研成果  73-74
致谢  74

相似论文

频繁图结构并行挖掘算法的研究与实现,TP311.13
基于并行算法的模糊综合评价模型的设计与应用,TP18
随机路由在无线传感器网络中的研究与应用,TN929.5
基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
高校教务管理网上选课系统优化研究,TP393.09
基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
LTE-A异构网络中的自组网技术研究,TN929.5
基于一种新经济模型的异构网络选择算法,TN929.5
基于QoS的无线Mesh网络路由协议及相关技术的研究,TN929.5
构建分布式系统的关键技术研究与实现,TP338.8
基于S2SH框架的雅砻江虚拟研究中心系统研究与设计,TP311.52
基于负载均衡的混合型应用层组播模型研究,TP393.02
异构网络联合接纳与切换控制技术研究,TN929.5
基于逻辑卷的分级存储系统设计与实现,TP333
虚拟环境中多网络接口卡I/O调度系统的研究,TP334.7
RFID数据清洗处理策略与算法,TP391.44
基于分布式实时数据库的事务调度策略研究与改进,TP311.13
分布式内存数据库存储研究,TP311.13
负载均衡调度系统的设计与实现,TP393.02
GPU加速的仿射算术在几何设计中的应用研究,TP391.41
基于CDN和P2P技术的混合流媒体内容分发机制研究,TN919.8