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

数字高程模型建模算法研究

作　者: 张咏
导　师: 刘长星
学　校: 西安科技大学
专　业: 大地测量与测量工程
关键词: 数字高程模型算法不规则三角网凸壳点定位点删除点插入多边形三角剖分
分类号: P209
类　型: 硕士论文
年　份: 2009年
下　载: 28次
引　用: 0次
阅　读: 论文下载

内容摘要

本文主要研究空间离散点的数字高程模型建模算法。首先基于Visual C++6.0和OpenGL编程实现了空间离散点的TIN建模;其次增加了任意点删除、插入、约束三角网的构建和等高线追踪等功能;最后对算法进行了验证。本文利用包容壳求解二维点集凸壳的方法,集目前各种算法之长,方法简单、易于实现,是一种高效的自适应算法;针对Delaunay三角网任意点定位,将三角形面积坐标、重心、点与有向线段的关系三者有机结合,构建了一种定位路径唯一、速度快、健壮高效的融和算法;对于局部编辑时用到的点删除,针对目前基于影响域多边形剖分的算法缺陷,首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成对点的删除;点的插入,则是动态扩展凸壳,弥补了一般算法不能插入凸壳外点的缺陷,并利用融和点定位算法,提高了插入效率;约束网的构建,首先利用改进的线段相交判断算法分离影响域多边形,然后以本文的任意多边形剖分和优化算法完成影响域多边形的Delaunay重构,最后将重构后的三角网镶嵌到原位置,向TIN网加入约束条件;等高线搜索则利用三角网的拓扑信息快速搜索出三角网的边界边,基于边界边高效完成开区线搜索,并改进现有三角网数据结构,追踪闭曲线。本文算法不仅对同类方法进行了完善改进,而且通过验证,算法效率高、切实可行,具有一定创新性。对三维建模研究有一定参考借鉴价值。

全文目录

摘要  3-4
Abstract  4-9
1 绪论  9-11
  1.1 研究意义  9
  1.2 研究内容  9-11
2 国内外研究现状及存在问题  11-14
  2.1 国内外研究现状  11-12
  2.2 存在问题  12-13
  2.3 技术路线  13-14
3 数字高程的建模算法  14-30
  3.1 数据预处理和TIN 的数据结构  15-17
    3.1.1 数据预处理  15
    3.1.2 数据结构  15-17
  3.2 相关的数学原理  17-18
    3.2.1 点与有向线段的关系  17
    3.2.2 三角形矢量面积  17-18
  3.3 TIN 的构建算法  18-27
    3.3.1 二维离散点凸壳求解  18-20
    3.3.2 多边形三角剖分  20-22
    3.3.3 点的融和定位算法  22-26
    3.3.4 逐点插入及LOP 算法  26-27
  3.4 本章小结  27-30
4 三角网编辑和等高线追踪算法  30-44
  4.1 点删除算法  30-33
    4.1.1 算法分析  30-31
    4.1.2 影响多边形搜索  31-32
    4.1.3 多边形三角剖分  32
    4.1.4 点删除算法步骤  32-33
    4.1.5 算法复杂度和效率分析  33
  4.2 点插入算法  33-36
    4.2.1 内外点分区  34
    4.2.2 外部点的插入  34-35
    4.2.3 点插入算法步骤  35
    4.2.4 算法复杂度和效率分析  35-36
  4.3 约束TIN 的构建算法  36-40
    4.3.1 首三角形的确定  37-38
    4.3.2 影响多边形的分离  38-39
    4.3.3 多边形的重构  39-40
    4.3.4 新三角网的镶嵌  40
  4.4 基于TIN 的等高线生成算法  40-43
    4.4.1 线性内插的基本原理  40-41
    4.4.2 等高点的追踪方法  41-42
    4.4.3 等高线的追踪步骤  42-43
  4.5 本章小结  43-44
5 实验系统功能简介  44-54
  5.1 系统模块简介  44-45
  5.2 数据模块系统  45-46
  5.3 三角网模块系统  46-49
    5.3.1 凸壳的追踪  46
    5.3.2 TIN 的构建  46-47
    5.3.3 约束三角网的构建  47-49
  5.4 功能模块系统  49-54
    5.4.1 点插入  49-50
    5.4.2 点删除  50
    5.4.3 等高线追踪  50-54
6 结论  54-56
  6.1 结论  54
  6.2 展望  54-56
致谢  56-57
参考文献  57-59
附录  59

数字高程模型建模算法研究

内容摘要

全文目录

相似论文