论文部分内容阅读
作为重要的几何计算工具,Delaunay三角网(Delaunay Triangulated IrregularNetwork,以下简称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的快速构建。