Delaunay算法的实现与应用

Delaunay算法的实现与应用

摘  要

数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Delaunay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。

 

关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网

 

 

Abstract

...

Key words: Digital Elevation Model；Digital Terrain Model；Triangulated Irregular Network；Triangulated Delaunay Network

 

目  录

论文总页数：19页

1 引言 1

1.1 课题背景 1

1.2 国内外研究现状 1

1.3 本课题研究的意义 1

1.4 本课题的研究方法 2

2 Delaunay方法的基本原理 2

2.1 Voronoi图与Delaunay三角网的基本概念 2

2.2 Delaunay的重要性质 3

2.3 传统Delaunay生成步骤 3

3 三角剖分改进法 4

3.1 算法基本流程 4

3.2 Graham扫描法求凸包 5

3.3 详细算法描述 5

3.4 程序运行结果 7

4 Super三角改进算法 8

4.1 算法基本流程 8

4.2 Super三角形的生成 9

4.3 详细算法描述 9

4.4 程序运行结果 10

4.5 面向对象计算机的实现 11

4.6 测试结果与算法分析 12

5 Delaunay算法的应用 13

5.1 插值基本原理 13

5.2 笔者源程序 14

5.3 基于网格插值的等值线生成 15

结    论 16

参考文献 16

致    谢 18

声    明 19