球面Delaunay三角网的生成与索引方法

论文摘要

Global GIS(全球地理信息系统,GGIS)的研究变得日益重要,其主要技术可概括为：(1)球面矢量数据表达理论；(2)全球多尺度矢量数据集成理论；(3)全球矢量数据索引方法三个方面,其中,球面矢量数据表达理论作为GGIS的基础,引起国内外学者的高度关注.Delaunay三角网具有严格的数学理论基础,能形成形态优化的格网,具有动态性、层次性等特征,且在数据操作上具有结构灵活、算法成熟等特点,球面Delaunay三角网被认为是球面矢量数据表达的有力工具.基于球面Delaunay三角网构建的方法主要有三种类型：(1)四面体算法,基本思想是扩展2维单纯形剖分准则至3维单纯形,算法不仅包含点的四面体定位、外接球探测与LOP四面体分裂等较复杂数值计算步骤,且计算过程往往需要维护四面体的拓扑联接关系；(2)Voronoi图对偶算法,基本过程是以正多面体层次剖分结果(正三角形、正六边形)构建近似球面计算域,以形态学膨胀、侵蚀操作模拟目标生长,其本质属于栅格计算.(3)投影拼接算法,将球面问题简化为平面处理,球面目标间邻接关系被表示为平面Delaunay三角网的邻接关系,相对于前两种算法具有更高的效率,其问题在于拼接过程,即算法需要分块地将球面数据平行投影至平面,并且以像点重合为基础保留与建立各分块间的关联,以最终将各分块数据拼接构成球面网格.拼接过程导致算法实用性显著降低.本文为解决球面Delaunay构网中的拼接问题,顾及球面数据的位置特点,提出利用透视投影模型将球面构网整体平面化的思路,其核心是置投影中心于球面,通过球面位置(x,y与z坐标)共同约束,进而构成球面与投影平面位置间的一一映射.模拟实验结果表明,本文算法时间复杂度取决于所采用的平面Delaunay三角网构建算法.最后本文在针对处理大数据量的情况下,引进索引概念,在三维显示过程中,提取有用信息,提高三维显示速度,本文所提出的模型与算法有望为球面矢量数据表达理论提供新的补充.

论文目录

• 摘要
• ABSTRACT
• 插图和附表清单
• 第一章 绪论
• 1.1 问题的提出
• 1.1.1 全球矢量数据的表达方式
• 1.1.2 全球Delaunay三角网的格网剖分
• 1.2 球面Delaunay三角网剖分的研究现状及评述
• 1.2.1 基于四面体的球面Delaunay三角网剖分
• 1.2.2 基于Voronoi图的对偶剖分方法
• 1.2.3 基于投影拼接的剖分方法
• 1.3 本文研究内容及章节安排
• 第二章 平面离散点的DELAUNAY三角网的构建方法
• 2.1 凸包
• 2.1.1 凸包的基本概念
• 2.1.2 二维凸包
• 2.1.3 凸包增量构建算法
• 2.2 平面Delaunay三角网的构建算法
• 2.2.1 Delaunay三角网（D-TIN）
• 2.2.2 Delaunay三角剖分的特性
• 2.2.3 D-TIN构建算法
• 2.2.4 逐点插入算法
• 2.3 实验分析
• 2.3.1 实验算法
• 2.3.2 实验结果
• 2.4 本章小节
• 第三章 球面DELAUNAY三角网的生成
• 3.1 透视投影算法描述
• 3.1.1 数据预处理
• 3.1.2 投影点集合至平面
• 3.2 球面Delaunay三角网的生成算法
• 3.2.1 球面邻接与球面闭合
• 3.2.2 三角形法向一致化
• 3.3 实验结果
• 3.4 本章小结
• 第四章 球面DELAUNAY三角网的快速显示
• 4.1 隐藏线面的消除
• 4.2 可见面判别算法的分类
• 4.3 BSP树算法
• 4.3.1 构造BSP树
• 4.3.2 BSP树的遍历
• 4.3.3 背面剔除
• 4.4 实验结果
• 4.5 本章小节
• 第五章 实验程序的设计与实验
• 5.1 实验系统设计
• 5.1.1 实验工具的选择
• 5.1.2 系统设计
• 5.1.3 系统界面
• 5.2 Direct 3D可视化平台的构建
• 5.3 实验结果与分析
• 第六章 结论与展望
• 6.1 主要工作
• 6.2 创新点
• 6.3 展望
• 致谢
• 参考文献
• 附录A