摘    要

本文首先论述了电子航海图系统的理论以及实际应用上的重大意义。而电子海图中有一类非常有用的数据——水深数据，对于未知的水深数据的提取，我们根据实际得到的水深数据通过插值算法来产生。
散乱点数据插值在地理、地质、医学和气象等领域有着广泛的应用。对于当前几种主要的散乱数据插值方法Kriging算法、B样条插值以及Delaunay三角网算法，首先分别对其进行了初步介绍，对各自的基本算法、适用领域进行对比分析，其中Delaunay算法的特点及应用范围比较适合本课题关于水深数据提取的研究。
经过20多年的研究，Delaunay三角网算法已趋于成熟。它们基本可分为分治算法、逐点插入法、三角网生长法三类。其中前两类在应用上更加广泛。不过这两类算法也分别存在着时间和空间效率上的缺陷，使他们受到了一定的限制。所以考虑不妨融这两种算法于一体，兼顾时间与空间性能的合成算法来实现对本课题的研究。
对于具体的算法设计我们通过VC语言来对其进行编程，并最终在Windows/VC环境下实现。

关键词：电子海图；Delaunay三角网；Voronoi图

ABSTRACT

This text expound the fact ECDIS-Electronic Chart Display and Information System the theory and great meaning who practical application pays of systems at first. There is a kind of very important data in Electronic Chart Display and Information System (ECDIS)——Water Depth Data. The unknown water depth data is gained by inserting numbers algorithm.
The disoedered points algorithm is widely used in Geography, Geology, Medical and Meteorology. We introduce the three of the most important algorithms today. Contrasting the three algorithms, we choose the Delaunay triangulation algorithm to research the Water Depth Data collecting.
A wide variety of algorithms have been proposed to construct triangulation．They fall into three broad categories: Divide-and-conquer, incremental  insertion and triangulation growth．The first two groups of the methods have been extensively applied to many disciplines because of their easiness in implementation. They are, however, constrained either by their computational inefficiency or by their stringent demand on computer memory．In this paper a hybridized method is proposed to take advantage of both algorithms’strengths so that these limitations could be overcome．
We use VC language to write program to achieve the algorithm in Windows/VC environment.
   
Keywords: ECDIS-Electronic Chart Display and Information System; Delaunay triangulation; Voronoi picture
 
目    录

第1章 绪论 1
1.1 电子海图水深数据提取的意义 1
1.2 当前关于水深测量的相关情况 1
1.2.1 20世纪水深测量技术的进展 1
1.2.2 21世纪水深测量技术的发展趋势 3
1.3 本文研究的内容和工作 5
第2章 电子海图及其相关算法简介 6
2.1 电子海图简介 6
2.1.1 电子海图的组成及特点 6
2.1.2 电子海图的相关术语 7
2.1.3 电子海图的现状及发展趋势 8
2.1.4 电子海图的数据结构格式 10
2.2 有关水深数据提取的几种插值算法的介绍 14
2.2.1 Kriging插值算法 14
2.2.2 B样条的散乱数据插值方法 17
2.2.3 Delaunay三角网算法 20
2.3 三种算法的比较 21
2.4 本章小结 21
第3章 Delaunay三角网及Voronoi图的详细介绍 22
3.1 Delaunay三角网与Voronoi图的关系 22
3.2 Delaunay三角网的定义及性质 23
3.3 Delaunay三角网的三种生成算法 24
3.3.1 分治算法(分割－归并法) 24
3.3.2 逐点插入法 25
3.3.3 三角网生长法 27
3.4  三种算法的比较 28
3.5  本章小结 29
第4章 合成算法模块的实现 30
4.1 面向对象程序设计技术 30
4.2 算法中涉及到的相关概念 33
4.2.1 凸壳 33
4.2.2 局部优化(LOP) 34
4.3 实现过程 35
4.3.1 开发思路 35
4.3.2 实现过程及程序流程 35
4.4 本章小结 41

结论 42
参考文献 43
致谢 44
 
第1章  绪论

1.1电子海图水深数据提取的意义
在人类社会逐渐进入数字化和信息化时代的今天，航海的方法和技术手段也正在发生巨大的变革。电子海图显示与信息系统（Electronic Chart Display and Information System，ECDIS）是随着航海事业及科技的发展而产生的一种集成式的实时导航信息系统，被认为是继雷达/ARPA之后近10年来在航海领域又一项伟大的技术革命。
电子海图数据中有一类非常有用的数据--------水深数据，它描述了当前海域的水深状况、分布，对船只航线的选择等都有着重要的影响；在军事上也有着极高的参考价值。

1.2当前关于水深测量的相关情况
1.2.1 20世纪水深测量技术的进展
1）.测量平台由船载向与机载、星载相结合发展，地理要素探测综合化
常规或传统的海洋深度测量主要以水面船只作为测量平台。由于其测量精度高、探测详细，今后仍将为海洋测量的主要作业模式。随着卫星遥感技术的应用，应用卫星遥感手段在浅水区修编海图方面达到实用化阶段。
机载激光水深测量技术在国外已经应用，我国正在进行研究，预计可实现浅于50m海区大面积快速测量。
20世纪90年代，我国开始将航空摄影测量手段应用于海洋测绘，主要解决浅水区或岛礁附近海岸地形测量。
在相当一段时期内，海洋测量的要素相对单一，最主要的为深度和底质测量。20世纪80年代，随着侧扫声纳、海洋重力仪的应用，海洋测量可同时获取海底地貌、海洋重力场数据。双频测深仪的应用，则可同时对深度、淤泥厚度和底质类型进行测量或判别，具有较好的实用性。
20世纪90年代以后，新造测量船只配备的测量设备发生了很大的变化，可同时完成多个任务剖面，包括水深测量、海底地形地貌测量、重力与磁力测量、浅地层剖面测量，以及水文气象调查，可最大程度地发挥测量船的效能，获取海洋环境的综合要素信息，提高经济效益和军事效益。
2).测量方式实现了由点、线到面的变化