1、 三角网数字地面模型及程序实现 袁功青 （华南理工大学 土木与交通学院 ，广东 广州 510640） 第一章 三角网数字地面模型基本原理及特点 1.1 数字地面模型的含义 数字地形模型（ Digital Terrain Model，简称 DTM 或“数模”）是一个表示地形特征的、空间分布的、有规则的数字阵列，也就是地表单元平面位置及其地形属性的数字化信息的有序集合。它是地表 2 维地理空间位置和其相关的地表属性信息的数字化表现，可表示为： i= ( i, i) =1, , （式 1-1） 式中 i 是 任一平面位置 ( i, i)的地表特有信息值，一般有： 1) 基本地貌信息如高程、坡度、坡向
2、等地貌因子； 2) 自然地理环境信息如土壤、植被、气候、地质分布等； 3) 自然构筑物如河流、水系等和人工构筑物如公路、铁路、居民地等； 4) 社会人文经济信息如人口分布、工农业产值等。根据不同的 i 值，其名称也稍有不同，如 i 为高程时，称为数字高程模型 (Digital Height(Elevation) Model, DHM(DEM)；当 i 为土壤分布时，称为数字土壤模型。然而，不管怎样，都是对叠加在 2 维地理位置上的地表属 性信息的数字描述，统称为数字地面模型，考虑到它的多样性，一般用 DTMs 表示。表达了平面位置 ( i, i)和 i的空间相关关系，从这一意义上讲， DTMs
3、 是 2.5 维的而非 3 维。 本质上讲， DTMs 是对地形表面在地形采样数据基础上的表面重构。因此，对于一个通用的 DTMs 系统，一般要经过数据采集、 DTM 建立和应用模型建立 3 个步骤，图 1.1 详细表达了 DTMs 系统的任务与建立步骤。 图 1.1 DTMs 系统的建立步骤与任务 地表的采样数据是一个无序的数据集合，为便 于计算机的管理及应用，需对该数据建立结构化的表达式，即隐式或显式的表达数据之间的拓扑关系，可用散点的形式和网格结构的形式来表达，目前主要是以网格结构的形式来表达。根据网格结构的不同，有规则网格 (矩形、正三角形、正六边形网格等 )和非规则网格 (三角形、四
4、边形网格等 )。 在规则网格中，矩形网格平面位置隐含于行列号中，称为网格或 rid，因网格结构简单而被普遍采用。三角形是平面图形中最简单 的几何图形，因而在不规则的网格中经常使用，一般称为不规则三角网 DTM 或 TIN。在应用中，数字地形模型一般又分为散点数模、规 则格网数模（ Regular Grid 简称 RG）、不规则三角网数模（ Triangulation Irregular Network，简称 TIN），它们具有各自的特点、内插方法不适用范围。 地形表面 信息解释 遥感卫星数据 航空摄影相片 地形图数字化 可视化 基本应用 地面测量数据 交互修改 1.2 数字地面模型的种类及特点
5、 由于数模原始数据点的分布形式不同，数据采集的方式不同，以及数据处理、内插的方法不同和最后的输出格式不同等原因，数字地面模型的种类较多。根据数模中已知数据点的分布形式并考虑到数据输出格式及数据处理方式，可将数字地面模型大致地分为规则数模、半规则数模和不规则数模三大类。各类数模的主要特点如下： 1.2.1 规则数模 规则数模是指原始地形点之间均有固定的联系，如方格网数模、矩形格网数模和正三角形格网数模等。在格网之间待定点的高程，常采用局部多项式进行内插。 由于每个已知点相对于周围已知点的位置是固定的，所以若按规则格网方式采集数据建立数模，量测地形点简单、客观，不需判读地形，易于实现数据采集的自动
6、化、半自动化。由于格网是规则等距的，在计算机中只需储存各个格网节点的高程值，而平面坐标只需记录第一个格网节点即可，其余节点的平面坐标根据其格网管理信息很容易在计算机中确定和恢复，这可大为节省计算 机内存。这种只记录节点高程的数模，也称为数字高程模型 (Digital Elevation Model 或 Digital Height Model，简称 DEM 或 DHM)。 该类数模的另一优点是输出形式简单、数据结构良好、便于应用，内插待定点高程时，检索与内插简单快速。 这种数模的最大缺点是原始数据不能适应地形的变化，除十分均匀的地形外，已知点没有与地形特征点联系起来，易遗漏地形变化点。由于数据
7、采集按规则格网方式进行，一旦间距给定，所有已知点平面位置就是固定的，从而导致地形变化大的地方地面信息不足，而地形 均匀、平缓的区域冗余数据点太多这种精度不一的现象，此外，由于规则格网节点不能兼顾地形变化线和地形特征点，格网中也就难于确定地面坡度的变化，从而导致高程内插精度降低。若要使规则格网数模更好地表示地形，则只有将格网间距缩小，这将导致原始数据的采集工作成倍增加。 规则格网数模一般适用于地形较平缓和变化均匀的区域，以及用于搜索地形等高线、绘制地形全景透视和对内插速度要求极高的路线平面优化中内插地面线等方面。 1.2.2 半规则数模 半规则数模是指各原始数据点之间均有一定联系，如用地形断面或
8、等高线串表示的数模。 当以断面线高程表示地形时，任一串原始地形点均表示某一个特定的地形剖面。各断面之间的距离及断面上点与点之间的距离可以是固定的，也可随地形变化而定。这种数模相当于用一批密集的、相互关联的地形剖面叠合在一起模拟地形，待定点的高程由相邻断面的已知点高程内插得到。如一种称为鱼骨式数模的数字地面模型就属于此类，这是在路线设计方案确定以后 ,沿路线纵、横断面采集地面点数据，用一批相互关联的横断面地形剖面叠合在一起而形成的数字地面模型。 沿等高线采集的一系列同一高程的 X、 Y 坐标的地形高程信息 (二维串线 )，以及沿地 形特征线、断裂线、地物、水系等各种信息采集的一系列 X、 Y、
9、Z 三维坐标信息 (三维串线 ) 所组成的数模，称串状数模。由于等高线具有在地形坡度大的地方密，在地形平缓处稀的特征，故地形点的分布与密度能很好地适应地形的变化。此外，由于各种断裂线、地物和水系信息可用三维串线在数模中表示，方便地进行处理，使程序功能大为加强，这是串状数模最为突出的优点。英国的 MOSS 系统所采用的就是串状数字地面模型。 半规则数模能较好地适应地形变化，内插精度较高，但数据采集不能实现自动化，原始数据的分布与密度易受操作人的主观影响， 建立数模过程中的程序处理较规则数模复杂。 1.2.3 不规则数模 不规则数模其原始地形数据点之间无任何联系，点的分布是随机的，一般常采集地形特
10、征点、变坡点、反坡点、山脊线、山谷线等处，常见的有散点数模、三角网数模等。 散点数模是将原始地形点看作一些随机分布的“离散点”，可认为点与点之间无任何联系。在这种已知点中直接进行内插其精度是不可靠的，因为不能确定由哪些点构成实际的地表面。所以内插时先得利用已知点拟合一个局部的或区域的内插表面，然后再由该内插表面确定待定点的高程，这是这一类散点数模的共同 特点。这种高程内插也称为移动曲面拟合法 ，在坡度 变化均匀的地形条件下，这种拟合较符合地形的实际情况，可达到较高的内插精度。在坡度变化大，地形起伏急剧改变的区域，特别是地物、地形断裂线附近，这种曲面拟合则明显地难于很好地描述出地形局部形状，而造
11、成内插点的高程误差偏大。所以，为提高散点数模的内插精度，使之满足工程设计需要，除原始数据点的分布必须符合地形变化，保持足够的密度外，程序中必须具备对地物、地形断裂线处理的功能。 从数模的精度和计算速度两方面来考察，散点数模不失为一种简单而有较的方法，具有很大的实用 价值，在国内外许多实用程序中广泛地得到应用。 不规则数模总的特点是：数据采集是随机的，一般都是取地形特征点，所以能较好地适应地形变化，内插精度较高。其缺点是采样需要人工判读地形，从而增加了数据采集的难度，此外构造数模较复杂，计算时间较长。由于该类数模优点较为明显，所以应用最为广泛。 1.3 三角网数字地面模型基本原理 三角网数字地面
12、模型 (Triangulated Irregular Network)TIN 是用一系列的互不交又、互不重复的三角形逼近地形表面，与 Grid 相比， TIN 在拟合地表上更灵活、更 精确。但由于结构的不同， Grid 许多成熟的技术并不能完全移植到 TIN 中。 从结构上讲， TIN 是一典型的矢量数据结构。它主要通过节点 (地表采样点 )、三角形 边和三角形面之间的关系来显式或隐式的表达底细功能散点的拓扑关系，因此设计一个高效 的、结构紧凑的、维护方便的 TIN 的存储与组织结构对 TIN 的应用与维护是至关重要的。 Tin 的基本单元三角形的几何形状直接决定着 TIN 的应用质量。由于地
13、形的自相关性，相 互越接近的地形采样点，其之间的关联程度越大 ;同时，理论与实践均证明，狭长的三角形 其插值精度比规则的三角形插 值精度可信度要低。因此，在 Tin 中对三角形的几何形状有着严格的要求。一般有三条原则 :l)尽量接近正三角形 ;2)保证最近的点形成三角形 ;3)三角形网络唯一。 一个良好的数据结构和三角划分准则，必须由一个高效的算法和程序实现。算法在具体应用中发挥的作用由算法本身的性能和实现它的程序质量共同决定，而程序的好坏在很大程度上依赖于算法的原理。对算法本身在理论上进行分析论证，寻求一种高效率、高精度、适用面广的算法是 TIN建立中的重要一环。 由上述的分析知， TIN的
14、数据组织 +三角划分准则 +算法和程序构成了 TIN 的基本理论 体系框架。图 2表示了这一结构。 三角划分准则 三角划分准 则 三角划分准则 三角划分准则 数据组织结构 图 2 TIN 模型的理论体系结构 第二章 三角网生成算法 目前国内外建立不规则三角形网的主要方法有三类：自动联结三角网法；径向扫描法（ Radial Sweeping Algorithm 简称 RSA）； 泰森三角形法（ Thiessen）。下面分别对这几种方法作一些介绍和评价。 1 自动联结三角网法 自动联结 三角形网，要求建立在可能获得最佳三角形的条件下。这个条件就是在使用周围邻近的离散点组成三角形网时，应尽可能地确保
15、每个三角形都是锐角三角形或三边的长度尽量相等， 避免出现过大的钝角和过小的的锐角。其判别法则是：最小距离和法则与最短外接圆半径法则。 最小距离和法则是指待插入点到基边两端点的距离和为最小，在用程序具体实现时，是用“该点对基边两端点张角 最大或其余弦值最小”原则来实现的。 最短外接圆半径法则是指三角形外接圆半径最小。从余弦定理公式： c2=r2+ r2-2 r2cos( ) （式 2-1） 可以看出： cos( ) -1/ r2。其中： c 代表基边的固定长度， r 代表外接圆半径。由于圆心角 2 ，即有 cos(2 ) -1/ r2，所以两种判别 法则是保持一致的。 自动联接三角形网法的具体思
16、路是： 1） 确定第一个三角形 在散点域中任取一离散点 A 作为第一个三角形的第一顶点，找出距离该点最近的点 B作为第一个三角形的第二顶点且构成基边 AB，应用余弦定理找出和该基边对角为最大的点作为第一个三角形的第三顶点。值得注意的是：为了顾及地形特征，找第三点时还必须遵守 两条规则：不跨越地形特征线条件；不进入禁区（封闭区域）条件。 2） 三角形的扩展 自动联结 三角形网法中的三角形扩展是从第一个三角形的三条边依次开始的，应用余弦定理来找到第三点。为了防止三角 形被遗漏、重复或发生交叉，每形成一个新的三角形，都要与己形成的三角形作一些比较判别，如果重复或交叉，则该三角形不记录。 自动联结 三
17、角形网法的优点是：原理明了，不考虑地形特征时编程简单。但其最大的缺点是：仅仅从最佳图形结构考虑，从而忽视了构网时的连续反复多次的三角形比较，使构网速度相当慢，导致数模的效率低下。而且一旦考虑地性线的介入，程序就变得复杂了。 2 径向扫描法（ Radial Sweeping Algorithm 简称 RSA） 径向扫描法（ RSA）是 Miratl 和 Weingartan 首次发表于一九八二 年，其基本思想是分成以下两个阶段来完成不规则三角形网的建立。 1） 建立稀疏的辐射三角网 首先是选择离区域形心最近的点作为辐射中心，由这一点向其它地形点作射线并计算其相对于辐射中心的距离和方位，对这些离散
18、点以方位作为关键词进行排序，若方位相同则按距离，再把这些排序好的点与它的后继点连一线段，形成一系列细而长的三角形。如果该点同前一点居于同一方位，则前一点、该点、后继点三点组成新的三角形。 在处理过程中，用一个链表或动态数组将每一个点的信息存储起来，形成一个外边界。然后依次从链表或动态数组中连续取出三点，判别是 否能形成内部三角形，若能，则记录该三角形，且把第二点从边界表中去掉。每当优点删去时，必须从头开始去进行点检验，最后得到一个凸形的闭合边界。 2） 优化初始三角网 径向扫描法（ RSA）法在优化三角网过程中考虑了两个因素，一是图形结构；二是地形起伏状况。显然，就图形结构而言，等边三角形是最
19、佳图形；就地形起伏情况而言，为使三角形网能很好地覆盖于地表，三角形边不应有“悬空”和“切割” 现象。具体到该法中，在考虑图形结构时，若相邻两个三角形组成凸四边形，应检查四边形两对角线之比，如果超过约定值，则以短边作为三角边；在考 虑地形起伏清况时，则检查两对角线高差之比，一般选取高差大的两对角点连线作为三角形边。当二者出现矛盾时，视其影响而定。经过优化处理后，所得的三角网就比较合理了。 径向扫描法（ RSA） 法思路简明，容易实现。但是，约定值若没有一个客观的衡量标准，导致 网形不唯一，特 别是引入地性结构线后，难免会出现三角网的“悬空”或“切割”边，致使歪曲地形；同时三角网的优化工作也是一个
20、相当复杂的过程，故该法在建立高精度的 DTM时是不可取的。 3 泰森（ Thiessen）三角形法 泰森多边形的概念是 :将分布在平面区域上的一组离散点用直 线分隔 ,使每个离散点都包含在一个多边形之内。进行分隔的规则是 ,每个多边形内只包含一个离散点 ,而且包含离散点 Pi 的多边形中 ,任意一点 Q 到 Pi 的距离都小于 Q 点到任一其他离散点 Pj 的距离。把每两个相邻的泰森多边形中的离散点用直线连结 ,生成三角形网 ,这样数模便完成。泰森模型的显著特点是 :每个三角形的外接圆内不包含其他离散点 ,而且三角形的最小内角达到最大值 ,又称 Delaunay 三角形和 Delaunay 三
21、角形格网。 泰森三角形法是基于图论学的表面三角剖分方法。该法数学理论体系严密且从图论角度出发，因而具有良好的图形结构 和网形唯一性。但是有两个限制条件：散点域必须为凸域；散点域中无四 点共圆。由于其优点明显，国内外对其研究也多，发明了许多算法。本文将在下一章 就改进的 Thiessen 三角形法，即： Delaunay 三角形法构网建立数模进行详细介绍。 第三章 三角网数字地面模型程序实现 在地学领域，经常需要处理大量分布于地域内的离散数据。为了合理利用一定地域内不均匀分布的离散地形点， 1908 年， G.Voronoi 首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的
22、范围，并定义了二维平面上的 Voronoi 图 (简称 为 V-图，也称为 Thiessen 图， Dirichlet 图， Vigner-Seithz 图 )。 1911 年，荷兰的 A.H.Thiessen 应用 V-图进行了大区域内的平均降水量研究。 1934 年， B.Delaunay 由 V-图演化出了更易于分析应用的 Delaunay 三角网。从此， V-图和 Delaunay 三角网就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具。当然，它的应用不仅适用于地学，而且活跃于所有与 2.5 维分析有关的领域。 3.1 Delaunay 三角网的 定义 1） Delaunay
23、 三角化的理论基础一 Vo ronoi 图 1908 年， M.G.Voronoi 首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的 Voronoi 图 (以下称为 v-图 )。 1934 年 Boly 由 v图演化出了更易于分析应用的 Delaunay 三角网 (以下称为 D 一三角网 )。从此， V 一图和 D一三角网就成了被普遍接受和广泛采用的分析离散数据的有力工具。在 TIN 的生成中， V一图和 D 一三角网有着广泛的应用。 Voronoi 图是由不规则网格定义的最基础和有用的结构之一。作为一个有着广泛用途的几何结构， V 一图可以应用
24、于 许多领域，并且经常以首先将它应用与某一特定领域的人的名字来命名它。 V 一图在地理方面的应用是从气象学家 A.H.Thiessen 开始的。他用 V 一图去解释那些有着不均匀天气状况分布的地区，因此在此领域 V 一图又称为 Thiessen 多边形。 在图 3.1 中可以看到， V 一图是通过切分一个中心点和它周围点之间的连线来定义的。切分线和连线之间的关系是互相垂直的。当我们对整个区域中的每一个点应用这种方法时，整个区域会被相邻的多边形所覆盖。图 3.2 是由一组自由分布的点组成的 V 一图。 图 3.1 Voronoi 多边形的构建 图 3.2 由一组自由分布的点 组成的 V 一图 V
25、oronoi 多边形有如下五点性质： 对于平面区域 V 上给定的 K 个离散点，将 S 分成 K 个 Voronoi 多边形的分法是唯一的。相应地，作为伴生图形的 Delaunay 三角网唯一。 任意两个 Voronoi 多边形不存在公共区域。相应地，作为伴生图形的 Delaunay 三角网中没有三角形重复、交叉。 Voronoi 多边形是一凸多边形。 点集 V 中任意三点 vi、 vj、 vk构成 Delaunay 三角形的充要条件是：过 vi、 vj、 vk三点的圆内不含有 V 中的其余任何 点。 由点集 V 中 N 个散点构成的 Delaunav 三角形数是： Nt=2(N-1)-Nb，
26、三角形的边数是： Ne=3(N-1)-Nb，其中 Nb 是 V-图外围边界顶点个数。 2） Delaunay 三角网的定义 作为 Voronoi 图的对偶， Delaunay 三角网与 Voronoi 图紧密相关，它以第一位发现这一对称关系的科学家 B.Delaunay 的名字命名。 Delaunay 三角网的定义是 : 连接所有相邻的 Voronoi 多边形的生长中心所形成的三角网称为 Delannay 三角网。 图 3.3 一个点集的 Voronoi 图 (虚线 )和它的 Delaunay 三角剖分 (实线 )。 3.2 Delaunay 三角网的 特性 Delaunay 三角网有几 个非
27、常重要的性质 ，如下所示： (l) 空外接圆性质 : 设 T 是平面有限点集 V 的一个三角剖分。 T 中的一个三角形的外接圆如果不包含 V 中的其它点，我们就称它满足空外接圆性质。 V 的一个三角剖分 :，当且仅当它的每一个三角形都满足空外接圆性质时，它才被称为一个 Delaunay 三角剖分 (见图 3.4)。 图 3.4 (a)不是 Delaunay 三角剖分 (b)是 Delaunay 三角剖分 (2) 最 大一最小角性质 : 设 T 是 V 的一个三角剖分， e 是 T 的一条边， Q 是 T 中和 e 相邻的两个三角形组成的四边形。当交换 Q 中的对角线不增加 6 个内角中的最小角
28、时，我们称边 e 满足最大一最小角性质。满足最大一最小角性质的边也被称为局部优化的边 (见图 3.5)。 V 的三角剖分 T，当且仅当 T 的每一条边都局部优化时，才是 Delaunay 三角剖分。 图 3.5 加深的边在 (a)中没有局部优化，在 (b)中被局部优化 (3) Delaunay 三角网网形唯一性 : Delaunay 三角网是建立在控制点周围最紧密相连的双重格网，这种网形只与离散 点的分布有关，而与建网的途径即离散点参加构网的先后顺序无关。所以，只要离散点平面位置相对固定，其网形都一样。 由于几个性质，决定了 Delaunay 三角网具有极大的应用价值。同时，它也是二维平面三角
29、网中唯一的、最好的。 3.3 Delaunay 三角网构网方法 在 GIS 中， 2.5 维的分析处理由 DTM(数字地形模型 )模型进行。由上节可知 DTM 主要由格网（ rid）与不规则三角网 (TIN)两种数据格式来表示，而以后者更为重要。 格网的优点是：充分表现了高程的细节变化，拓扑关系简单，算法实现容易，某些空间操纵及存 储方便；而它的局限性是：占用巨大的存储空间，不规则的地面特征与规则的数据表示之间的不协调。 不规则三角网的优点是：高效率的存储，数据结构简单，与不规则的地面特征和谐一致，可以表示线性特征和迭加任意形状的区域边界，易于更新，可适应各种分布密度的数据等；而它的局限性是：
30、算法实现比较复杂和困难。 在现今的 GIS 系统中，基本上均支持以上两种数据格式，以不规则三角网为主，格网为辅，并提供相互转换功能。历经二十余年的不懈努力， TIN 的许多算法难关已被攻克。 TIN的生成算法中，三种算法：分割 -归并法、逐点插入法和逐步生长 法最终被普遍接受和采用，而又以前二者更为流行。分割 -归并法时间效率高，但占用内存空间较多；逐点插入法时间效率较差，占用内存空 间较少。现在有人在这两种算法的基础上，提出了一种综合性能的算法 合成算法，它的 性能优于以上两种算法。 下面就 Delaunay 三角网的三类建网方法：分治算法、逐点插入法、逐步生长法作进一步介绍和评价。 3.3
31、.1 分治算法（ Divide-and-Conquer） Shamos 和 Hoey 提出了分治算法思想，并给出了一个生成 V-图的分治算法。 Lewis 和Robinson 于 1978 年提出了一 种建立三角网的方法，以处理限定边界的等高线和有限元分析应用，他们将分治算法思想应用于生成 Delaunay 三角网，他们给出了一个“问题简化”算法，递归地分割点集，直至子集中只包含三个点而形成三角形，然后自下而上地逐级合并生成最终的三角网。以后 Lee 和 Schachter 又改进和完善了 Lewis 和 Robinson 的算法，提出了对平面点建立 Delaunay 三角网的分而治之算法。这
32、种算法首先将数据排序，分成两个互不相交的子集，在每一子集建立三角网后，将两个三角网合并以生成最终的狄洛尼三角网。Dwyer（ 1987）对分 而治之算法作了一些改进。通过将数据分成垂直条块，进而用相交边界将条块再一次细分为区域，并应用带约束条件的 Lawson LOP 将对角线进行交换， Dwyer 的算法能处理带约束条件的数据。 Lee 和 Schachter 算法的基本步骤是： 1 把点集 V 以横坐标为主，纵坐标为辅按升序排序，然后递归地执行步骤 26； 2 把点集 V 分为近似相等的两个子集 VL和 VR； 3 在 VL和 VR 中生成三角网； 4 用 Lawson 提出的局部优化算法
33、（ LOP）优化所生成的三角网 ,使之成为 Delaunay 三角网； 5 找出连接 VL和 VR 中两个凸壳的底线和顶线； 6 由底线至顶线合并 VL和 VR 中两个三角网。 以上步骤显示，分治算法的基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用局部优化算法（ LOP）保证其成为 Delaunay 三角网。不同的实现方法可有不同的点集划分法、子三角网生成法及合并法。 3.3.2 逐点插入法（ Iteration） Lawson 提出了用逐点插入法建立 Delaunay 三角网的算法思想，它是将未处理的点加入到已经存在的 Delaun
34、ay 三角网中，每次插入一个点，然后将 Delaunay 三角网重 新定义。 Lee和 Schachter， Bowyer， Watson， Sloan， Macedonio 和 Pareschi， Floriani 和 Puppo， Tsai 先后进行了发展和完善。 逐点插入算法的基本步骤是： 1 定义一个包含所有数据点的初始多边形； 2 在初始多边形中建立初始三角网； 3 插入一个数据点 P，在已经存在的三角网中找出包含 P 的三角形 t，把 P 与 t 的三个顶点相连，生成三个新的三角形； 4 用 Lawson 的 LOP 算法优化局部三角网； 5 是否所有离散点都参与了构网？若是，构网
35、完毕；否则，转到 3。 从上述步骤可以看出，逐点插入算法的思路非常简单，清晰。先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用 LOP 算法确保其成为 Delaunay三角网。同时，该算法占用内存小，时间复杂度为 O(N5/4)，运算速度较快，是一种比较理想的 Delaunay 三角网构网方法。各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法不同。 3.3.3 逐步生长法 Green 和 Sibson 首次实现了一个生成 Dirichlet 多边形图的生长算法。他们在 1978 年提出的递归方法通过顺序扫描数据 点，计算平面 Dirichlet 多边形
36、。在此过程中随着新点的加入，以递归的方式改变新点周围 Dirichlet 多边形的邻接关系。 Brassel 和 Reif 稍后也发表了类似的算法。这种算法从任意一点开始，在一维排序链表中以循环搜索方式查找此任意点的泰森邻域点，将建模区域划分为泰森多边形，然后把这一点与其所有泰森邻域点连接以形成了 Delaunay 三角网，并由此生长，直至所有点都包含到三角网中。 McCullagh 和 Ross 通过把点集分块和排序改进了点搜索方法，减少了搜索时间。 Maus 也给出了一个非常相似的算法。 逐步生 长法的基本步骤是： 1以任一点为起始点，找出与起始点最近的数据点相互连接形成 Delaunay
37、 三角形的一条边作为基线； 2按 Delaunay 三角网的判别法则 (即它的两个基本性质 )，找出与基线构成 Delaunay 三角形的第三点； 3基线的两个端点与第三点相连，成为新的基线； 4迭代以上两步直至所有基线都被处理。 上述过程表明 , 逐步生长法的思路是，先找出点集中相距最短的两点连接成为一条Delaunay 边，然后按 Delaunay 三角网的判别法则找出包含此边的 Delaunay 三角形的另一端点，依次处理所有新 生成的边，直至最终完成。该算法时间复杂度为 0（ N3/2），时间效率较低，现已基本淘汰。各种不同的实现方法多在搜寻“第三点”上做文章。 Tsai 为比较算法性
38、能，给出了一张各种算法的时间复杂度对照表，如表 1 所示。 表 1 几种 Delaunay 三角网生成算法的时间复杂度 算 法 一般情况 最坏情况 Lawson(1977)2 O(N4/3) O(N2) Green 和 Sibson(1978)3 O(N3/2) O(N2) Lewis 和 and Robinson(1978)1 O(N logN) O(N2) Brassel 和 Re if(1979)3 O(N3/2) O(N2) MaCullagh 和 Ross(1980)3 O(N3/2) O(N2) Lee 和 Schachlter(1980)1 O(N logN) O(N logN)
39、 Lee 和 Schachlter(1980)2 O(N3/2) O(N2) Bowyer(1981)2 O(N3/2) O(N2) Watson(1981)2 O(N3/2) O(N2) Mirante 和 Weigarten(1982)3 O(N3/2) O(N2) Sloan(1987)2 O(N5/4) O(N2) Dwyer(1987)1 O(N logN) O(N logN) Chew(1989)1 O(N logN) O(N logN) Macedonio 和 Pareschi(1991)2 O(N3/2) O(N2) 上标说明： 1. 分割 -归并法； 2. 逐点插入法； 3.
40、 逐步生长法。表中 N 为数据点数， O(f(N)表示算法的时间复杂度，它以算法中频度最大的语句频度 f(N)来度量。 3.3.4 一种新的合成算法 由上面的介绍我们可以看到，目前采用较多的前两类 算法各具优势又有局限，同时，它们又具有明显的互补性。分治算法时间性能好，空间性能差；逐点插入法空间性能好，时间性能差。我们评价一个算法的优劣是看它对时间和空间的消耗，即时空性能的综合表现。因此，就产生了一种合成算法即把以上两种算法结合起来，取长补短，来提高算法的性能。这种结合的具体做法是：以分治算法为主体，当递归分割数据集的过程进行到子集中的数据量小于一个预定值 分割阈值时终止，然后用逐点插入法在子集中生成子三角网。这种算法就是合成算法。它的流程图见图 5。
