基于A_算法的海底地形等深线模型构建方法研究

海　洋　测　绘

H YD RO GRA PH IC SU RV EY I N G AND CHA R T I N G

V ol 130,N o 13

M ay,2010

收稿日期:2009210218;修回日期:2010203222

作者简介:周艳霞(19732),女,河北保定人,工程师,主要从事海图制图研究。

基于A 3

算法的海底地形等深线模型构建方法研究

周艳霞,唐新春

(海军出版社,天津　300450)

　　摘要:介绍了DE M 原理和构建方法,利用现有矢量海图中的水深要素及海岸线岛屿要素,对生成电子海图海底规则网格数据进行研究。计算机辅助虚拟三维海底地形,运用线性八叉树场景进行分解寻求其规律性,用A 3算法最好最优地勾绘出等深线,从而建立海底地形等深线模型,为实现电子海图海底三维可视化奠定了基础。最后对算法进行分析与完善。

关键词:数字高程模型;电子海图;A 3算法

中图分类号:P208　　　文献标识码:B 　　　文章编号:167123044(2010)0320070203

1　引　言

数字高程模型(M )[1]

是重要的基础地理数据之一,也是地理信息系统核心数据库以及进行地学分析的基础数据。可以认为海底是地表的一个映射,也具有与地面相似的高山、平原、丘陵以及沟壑。因此将DE M 用于海底地形的表征是一种趋势与必然。矢量电子海图的三维可视化是航海模拟器视景仿真、航海虚拟现实的重要组成部分。因此,研究基于已知矢量数据和相关描述进行电子海图三维可视化对于现代航海技术的发展具有十分重要的意义。2　基于电子海图数据的海底地形表示方法

矢量电子海图只能以水深点和等深线等二维信息表达海底地形,存在表达不直观、不利于地形分析等缺陷。每一张矢量电子海图都能提供若干确定经纬度的、已知水深值的离散水深点(等深线可以看作是由一些水深值相等的水深点组成的)。基于电子海图进行海底地形三维可视化的关键就是如何利用已知的离散水深点生成海底地形DE M 。海底地形DE M 是对海底地形的数学表达及存储方式,需要对离散水深点进行重采样,进而重建地形表面。

海底DE M 有两种表示方法:(1)数学方法用数学方法来表达,可以采用整体拟合方法,用傅里叶级数和高次多项式拟合统一的海底地形曲面。也可用局部拟合方法,将海底复杂表面分成正方形规则区域或面积大致相等的不规则区域进行分块搜索,经过拟合形成曲面。

(2)图形方法

线模式:等深线是表示地形最常见的形式。点模式:用离散采样数据点建立DE M 是DE M 建立常用的方法之一。数据采样可以按规则格网采样,可以是密度一致的或不一致的;可以是不规则采样,如不规则三角网、邻近网模型等。3　海底地形等深线模型的构建

规则格网DE M (grid DE M )[2]

和不规则三角网DE M (TI N DE M )是目前两种主要的数据结构。本文将讲述另一种表示模式:等深线模型。每一条等深线对应一已知的水深值,等深线模型即是表示一系列等深线集合和它们的水深值,这就构成了一种

海底高程模型。311　A 3

算法基本原理31111　牛顿插值

等深线可以认为是一条带有水深值属性的简单多边形或多边形弧段,通常被存储为一系列有序的坐标点对。由于等深线模型只表达了区域的部分水深值,可以先运用线性八叉树[3]

场景进行分解,将区域分割成具有规律的小区域,在各个小区域中寻求等深线上的水深点。实际操作时需要一种插值方法来计算落在等深线外的其他点的水深,同样也可根据已知水深点用插值法先求出确定等深线的路径点。在每个小区域中确定水深点时选用牛顿插值法

[4]

。

牛顿插值:

N n (x )=C 0+C 1(x -x 0)+C 2(x -x 0)(x -x 1)+111

C n (x -x 0)(x -x 1)111(x -x n -1)

(1)

式中,N n (x )为插值点水深;C i 为待定系数;x 插值

第3期

周艳霞,等　基于A 3

算法的海底地形等深线模型构建方法研究

点坐标x i ,y i 。在已知所有测点坐标x i ,y i

i =0,1...,n -1,C i 可以根据n 个测点上水深值

N i (x )

i =0,1111,n -1来确定。因此N n (x )可根

据牛顿插值法来确定其坐标x,即所需的路径点。y 方向亦如此。

31112　A 3

算法基本原理

A 3(A -Star )[5]

算法是一种静态路网中求解最短路最有效的方法。公式为:

f (n )=

g (n )+

h (n )

(2)

式中,f (n )是节点n 从初始点到目标点的估价函数;g (n )是在状态空间中从初始节点到n 节点的实际代价;h (n )是从n 到目标节点最佳路径的估计代价。保证找到最优路径(最优解的)条件,关键在于估价函数h (n )的选取。

估价值h (n )≤n 到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。如果估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。估价值与实际值越接近,估价函数取得就越好。

搜索路径的代价一般都是由结点间的距离来衡量的,Euclidean 距离是实际距离的真实反映,有清晰的物理意义,精确度高。本文采用Euclidean 距离

(n =3)对路径代价进行估计。见式(3):

d (X,Y )=

∑

n

i =1

|x i -y i |

2

1/2

(3)

式中,d (X,Y )为n 到目标节点最佳路径的估计代

价;x i 、y i 为节点坐标;n 为节点数。312　等深线模型的构建海图是海洋的虚拟表示,在三维电子海图中根据虚拟场景漫游时视点贴近地面的特点,需要防止选择不合理的路径情况,先孤立出浅点,并对水深有一定的取舍表示。当然碰到断裂带或者海沟时需要

特殊对待。运用A 3

算法选择路径前,先对需要三维路径可视化的区域进行预处理,选择所求等深线上的路径点,搜索路径有两种情况。

一是在扩展后继结点时选择了垂直方向相同尺寸的上部邻域结点即纵向上的路径点,如图1;二是在扩展后继结点时选择水平方向不同尺寸的上部邻域结点即横向上的路径点,如图2。

解决方法是分别增加选择垂直方向相同尺寸上部邻域结点和水平方向不同尺寸上部邻域结点时的代价。即在计算g (n )时引入路径影响因子w,得到式(4):

g (n )=g (m )+w 3d (m ,n )

(4)

式中,g (n )为初始点到n 节点的实际代价;g (m )为

初始点到m 节点的实际代价;d (m ,n )为m 、n 节点之间的估计代价,具体函数见式(3)。

在上述两种选择路径的情况下,将w 设为通常情况下的两倍或多倍,从而达到路径最优,方便数据

量大时处理。应用A 3

算法在给定的起点和终点之间搜索一条合理路径,并实现自动漫游。

应用A 3

算法实现三维路径规划整体流程:在计算机辅助下,读取三维场景模型信息,使用线性八叉树场景进行分解并用牛顿插值法进行插值,确定

所绘等深线并选取其上的路径点,运用A 3

算法多线程对每条等深线进行路径搜索,继而生成路径和自动漫游,实现由等深线构建的海底地形DE M 。4　技术实现与结果分析411　技术实现

A 3

算法主要搜索过程:

创建两个表,OPE N 表保存所有已生成路径点,CLOSE 表中记录已访问过的节点。

遍历当前节点的各个节点,将n 节点放入CLOSE 中,取n 节点的子节点X,算X 的估价值

W hile (OPE N !=NULL )

{

从OPEN 表中取估价值f 最小的节点n;if (n 节点==目标节点)break;else {

if (X in OPE N )比较两个X 的估价值f if (X 的估价值小于OPEN 表的估价值)

更新OPE N 表中的估价值;//取最小路径的估价值

1

7

海　洋　测　绘

第30卷

if (X in CLOSE )比较两个X 的估价值if (X 的估价值小于CLOSE 表的估价值)

更新CLOSE 表中的估价值;把X 节点放入

OPEN //取最小路径的估价值

I f (X not in both )

求X 的估价值;

并将X 插入OPE N 表中;}

将n 节点插入CLOSE 表中;

412　结果分析

本文针对电子海图数据特点,使用前文所述技术,在尽量减少计算机执行损耗的前提下,构建出高精度、高分辨率的海底地形等深线模型。选择一幅

有水深点的海图。使用A 3

算法进行相同水深的路径搜索,可以得到图

3处理效果。

图3　基于A 3

算法的等深线数据模型

实验表明,本文提出的技术方法具有以下特点:

(1)虚拟三维海底地形,用A 3算法易于实现自动漫游,生成最优路径下的需要绘制的等深线,通过等深线将海底地形构建出来,对电子海图和三维海底数据完善有很大促进。

　　(2)二维方式的等深线模型自动构造,有助于模拟水下三维海底地形。

(3)海底地形跟陆地地貌类似,有很多不可预知的,当遇到特殊情况如:浅点、海沟,则需要单独处理,这对生成过程的快捷和数据的自动化有很大阻碍,还需要进一步改进。5　结束语

本文提出基于A 3

算法的海底地形等深线模型,以矢量电子海图已知的离散水深点数据构建虚拟三维海底地形模型,在找出绘制等深线的路径点

的情况下,通过A 3

算法实现路径自动漫游,形成海底地形数据,从而为实现电子海图海底三维可视化奠定了基础,这种算法所勾绘海底地貌基本上能够满足实际应用要求。本文实现了一个三维场景路径规划和自动漫游的实验原型,但是该原型还需要不断改进和完善。

参考文献:

[1]　周启鸣,刘学军.数字地形分析[M ].北京:科学出版

社,2006.

[2]　汤,刘学军,闾国年.数字高程模型及地学分析的

原理与方法[M ].北京:科学出版社,2005.

[3]　陈晓军,舒　宽,张　建,等.八叉树搜索算法在计算

机辅助手术中的应用[J ].计算机工程,2008,34(22):

16～18.

[4]　李庆扬,王能超,易大义.数值分析[M ].第4版.北

京:清华大学出版社,2001.

[5]　樊　莉,孙继银,王　勇.人工智能中的A 3

算法应用

及编程[J ].微机发展,2003,13(5):33～35.

R esearch on M ethods of C onstructing Seabed Topography

C ontour L ine M odel B ased on A

3

A lgorithm

ZHOU Yan 2xia,TAN G X in 2chun

(N avy Press,T ianjin,300450)

　　Ab s tra c t:This paper in troduces the p rincip le and constructing m ethod of D E M.B y using the sounding and

coastline islands and islets elem en ts of a vector nau tical chart available,w e have done som e researches on net w o rk data of generating electron ic navigational chart seabed regu larity .W ith the help of com pu ter 2aided virtual th ree 2d i m ensional seabed topograp hy,used linear octree scene to b reak it dow n for its regularity,A

3

algo rithm is the best w ay to p lot the con tour line w hich help ed to build seabed topography contour line m odel,and then help ed to lay a foundation for seabed three 2di m ensional visualization of electronic navigation chart .Finally,th is pap er m akes analysis and i m p rovem en t to the algorithm.

Ke y wo rd s:D E M ;electronic navigational chart ;A

3

algo rithm

2

7