带约束条件的离散点不规则三角网生成

摘要

规则格网模型、不规则三角网模型和等高线模型是数字高程模型(DEM)的三种表示方法。其中不规则三角网(TIN)能以不同层次的分辨率来描述地形表面，被视为DEM中最基本和最重要的一种模型。因此本文主要研究了带约束条件的空间离散点的不规则三角网生成算法。 首先，本文对现有的不规则三角网各种生成算法进行对比。在所有可能的三角网中，Delaunay三角网是一种相互邻接且互不重叠的三角形集合，其中任一三角形的外接圆内不包含其他的点。在地形拟合方面表现最为出色，因此本文采用Delaunay三角网进行建模。 其次，本文结合了分割-合并算法和凸壳算法的优点，提出了一种生成Delaunay三角网的合成算法。该算法首先对离散点进行排序然后根据离散点密度使用四叉树进行分块。对每个叶节点内的数据点集，使用凸壳算法进行三角剖分，再通过凸壳合并算法将所有叶节点按层次遍历算法进行合并得到Delaunay三角网。经分析，整个算法的时间复杂度为O(nlogn)。 最后对空间约束条件的处理采用了嵌入约束边的方法。两步法是目前采用较多，效率较高的一种约束边嵌入的方法。本文使用边交换迭代算法进行了实现，达到了较好效果。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究内容与意义

1.2研究现状

1.3论文组织

第二章地理信息系统建模

2.1地理信息系统

2.1.1地理信息系统的概念

2.2.2地理信息系统的组成

2.1.3地理信息系统的发展

2.1.4地理信息系统的特征

2.2数字高程模型

2.2.1数字地面模型与数字高程模型的概念

2.2.2 DEM的数据源与采集方法

2.2.3 DEM的表示方法

第三章不规则三角网生成算法对比研究

3.1TIN的数据组织

3.2 TIN的三角化准则

3.3 TIN的三角化算法对比

3.3.1规格分布采样数据三角化算法

3.3.2基于等高线采样数据三角化算法

3.3.3不规则分布采样数据三角剖分

3.4 Delaunay三角网及三角剖分

3.4.1 Voronoi图和Delaunay三角网

3.4.2 Delaunay三角网的特性

3.4.3常见Delaunay三角算法对比

第四章离散点的Delaunay三角剖分算法研究

4.1本文中不规则三角网生成算法思想

4.2基于离散点集的空间分割算法

4.2.1离散点数据初始化

4.2.2离散点区域划分四叉树生成算法

4.2.3分割阈值的选取

4.3分割数据域的三角网生成算法

4.4三角网的合并算法

4.5算法复杂性分析

第五章带约束条件的不规则三角网构造算法研究

5.1约束数据域与不规则三角网

5.2带约束条件的三角网建构算法

5.3带约束条件的三角网的边交换迭代算法

第六章结论与展望

6.1研究工作及成果总结

6.2进一步研究方向

参考文献

致谢

攻读硕士期间的主要研究成果