一种生成Delaunay三角网的合成算法_武晓波

时间：2025-07-10

第4卷第1期2000年2月

遥　感　学　报

Vol.4,No.1Feb.,2000

文章编号:1007-4619(2000)01-0032-04　　　

一种生成Delaunay三角网的合成算法

武晓波,王世新,肖春生

(中国科学院遥感应用研究所　北京　100101)

摘　要:　经过20多年的研究,自动生成Delaunay三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等3类。其中前两类较第3类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷,使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体,兼顾空间与时间性能的合成算法。经测试,它的运算效率大大高于逐点插入法,在大多数情况下,也高于分治算法,在分割阈值约为总数据量的十分之一时,效率最高。关键词:　Delaunay三角网;合成算法;分治算法;逐点插入法中图分类号:　TP79/TP393　　　文献标识码:　A

应用较广的两类算法。这两类算法所采用的实现方

1　引　言

在地学领域中存在着大量基于点的数据,如高程数据、气象观测数据、钻井资料、物化探资料等。

充分利用这些空间信息是许多地学研究的基础。1908年,俄国学者G.Voronoi完成了一项奠基性研究,从数学上定义了每个观测点所能代表的空间范围,并用Voronoi图(V-图)在二维平面上表示了它的几何意义。1911年,A.H.Thiessen应用V-图理论进行了区域降水量的研究[1]。1934年,B.Delaunay根据V-图推演出了更易于使用的Delaunay三角网(D-三角网)。此后,V-图和D-三角网在地学、图形图像等相关领域得到了极为广泛的应用。

D-三角网是由连接V-图中具有公共边相邻多边形的中心形成的网络。它具有两个显著的特征,即:

(1)空外接圆性质。任何一个三角形的外接圆均不包含其它数据点。(2)最大的最小内角性质。在所有可能形成的三角网中,D-三角网中三角形的最小内角是最大的。

这两个性质有效地保证了D-三角网是最接近等角或等边的三角网,同时它也是自动建立D-三角网的算法依据。

分治算法和逐点插入法由于易于实现,是当前

法决定了它们存在着明显的局限性,分治算法需要大量的内存,逐点插入法运行速度极慢。当数据量较大或计算机性能较差时,它们的使用都将遇到困难。

本文提出了一个成功地解决了上述问题的合成算法。该算法将逐点插入法嵌入到分治算法中,使它们优势互补,弥补了各自的缺陷。经过一个有2533个点数据测试,表明合成算法的运算效率大大高于逐点插入法,在大多数情况下也高于分治算法。

2　已有算法介绍

由于建立D-三角网需要进行大量的计算,所以电子计算机一经出现,人们很自然地就把繁重的计算任务交给了它。到目前为止,学者们提出的各种自动建立的算法基本可归为3类:分治算法、逐点插入法和三角网生长法。Tsai对此曾作了一个非常好的回顾

[2]

,现将其作一简要介绍。

2.1　分治算法

Shamos和Hoey首次提出了一个用分治算法的思想实现的生成V-图的算法。它后来被Lewis和Robinson加以改进并应用于生成D-三角网[4]。这一算法是不断地将数据分割为两个近似相等的子集,