三角网数字地面模型及程序实现
三角网数字地面模型及程序实现
袁功青
（华南理工大学土木与交通学院，广东广州510640）
第一章三角网数字地面模型基本原理及特点
1.1 数字地面模型的含义
数字地形模型（Digital Terrain Model，简称DTM或“数模”）是一个表示地形特征的、空间分布的、有规则的数字阵列，也就是地表单元平面位置及其地形属性的数字化信息的有序集合。它是地表2维地理空间位置和其相关的地表属性信息的数字化表现，可表示为：
Ａi=Ｆ(ｘi,ｙi)ｉ=1,…,Ｎ（式1-1）
式中Ａi是任一平面位置(ｘi,ｙi)的地表特有信息值，一般有：1) 基本地貌信息如高程、坡度、坡向等地貌因子；2) 自然地理环境信息如土壤、植被、气候、地质分布等；3) 自然构筑物如河流、水系等和人工构筑物如公路、铁路、居民地等；4) 社会人文经济信息如人口分布、工农业产值等。根据不同的Ａi值，其名称也稍有不同，如Ａi为高程时，称为数字高程模型(Digital Height(Elevation) Model, DHM(DEM))；当Ａi为土壤分布时，称为数字土壤模型。然而，不管怎样，都是对叠加在2维地理位置上的地表属性信息的数字描述，统称为数字地面模型，考虑到它的多样性，一般用DTMs表示。Ｆ表达了平面位置(ｘi,ｙi)和Ａi 的空间相关关系，从这一意义上讲，DTMs是2.5维的而非3维。
本质上讲，DTMs是对地形表面在地形采样数据基础上的表面重构。因此，对于一个通用的DTMs系统，一般要经过数据采集、DTM建立和应用模型建立3个步骤，图1.1详细表达了DTMs系统的任务与建立步骤。
图1.1 DTMs系统的建立步骤与任务
地表的采样数据是一个无序的数据集合，为便于计算机的管理及应用，需对该数据建立结构化的表达式，即隐式或显式的表达数据之间的拓扑关系，可用散点的形式和网格结构的形式来表达，目前主要是以网格结构的形式来表达。根据网格结构的不同，有规则网格(矩形、正三角形、正六边形网格等)和非规则网格(三角形、四边形网格等)。
在规则网格中，矩形网格平面位置隐含于行列号中，称为网格ＤＴＭ或Ｇrid，因网格结构简单而被普遍采用。三角形是平面图形中最简单的几何图形，因而在不规则的网格中经常使用，一般称为不规则三角网DTM或TIN。在应用中，数字地形模型一般又分为散点数模、规则格网数模（Regular Grid简称RG）、不规则三角网数模（Triangulation Irregular Network，简称TIN），它们具有各自的特点、内插方法不适用范围。
1.2 数字地面模型的种类及特点
由于数模原始数据点的分布形式不同，数据采集的方式不同，以及数据处理、内插的方法不同和最后的输出格式不同等原因，数字地面模型的种类较多。根据数模中已知数据点的分布形式并考虑到数据输出格式及数据处理方式，可将数字地面模型大致地分为规则数模、半规则数模和不规则数模三大类。各类数模的主要特点如下：
1.2.1 规则数模
规则数模是指原始地形点之间均有固定的联系，如方格网数模、矩形格网数模和正三角形格网数模等。在格网之间待定点的高程，常采用局部多项式进行内插。
由于每个已知点相对于周围已知点的位置是固定的，所以若按规则格网方式采集数据建立数模，量测地形点简单、客观，不需判读地形，易于实现数据采集的自动化、半自动化。由于格网是规则等距的，在计算机中只需储存各个格网节点的高程值，而平面坐标只需记录第一个格网节点即可，其余节点的平面坐标根据其格网管理信息很容易在计算机中确定和恢复，这可大为节省计算机内存。这种只记录节点高程的数模，也称为数字高程模型(Digital Elevation Model 或 Digital Height Model，简称DEM或DHM)。?该类数模的另一优点是输出形式简单、数据结构良好、便于应用，内插待定点高程时，检索与内插简单快速。
这种数模的最大缺点是原始数据不能适应地形的变化，除十分均匀的地形外，已知点没有与地形特征点联系起来，易遗漏地形变化点。由于数据采集按规则格网方式进行，一旦间距给定，所有已知点平面位置就是固定的，从而导致地形变化大的地方地面信息不足，而地形均匀、平缓的区域冗余数据点太多这种精度不一的现象，此外，由于规则格网节点不能兼顾地形变化线和地形特征点，格网中也就难于确定地面坡度的变化，从而导致高程内插精度降低。若要使规则格网数模更好地表示地形，则只有将格网间距缩小，这将导致原始数据的采集工作成倍增加。
规则格网数模一般适用于地形较平缓和变化均匀的区域，以及用于搜索地形等高线、绘制地形全景透视和对内插速度要求极高的路线平面优化中内插地面线等方面。
1.2.2 半规则数模
半规则数模是指各原始数据点之间均有一定联系，如用地形断面或等高线串表示的数模。
当以断面线高程表示地形时，任一串原始地形点均表示某一个特定的地形剖面。各断面之间的距离及断面上点与点之间的距离可以是固定的，也可随地形变化而定。这种数模相当于用一批密集的、相互关联的地形剖面叠合在一起模拟地形，待定点的高程由相邻断面的已知点高程内插得到。如一种称为鱼骨式数模的数字地面模型就属于此类，这是在路线设计方案确定以后,沿路线纵、横断面采集地面点数据，用一批相互关联的横断面地形剖面叠合在一起而形成的数字地面模型。
沿等高线采集的一系列同一高程的X、Y坐标的地形高程信息(二维串线)，以及沿地形特征线、断裂线、地物、水系等各种信息采集的一系列X、Y、Z三维坐标信息(三维串线)?所组成的数模，称串状数模。由于等高线具有在地形坡度大的地方密，在地形平缓处稀的特征，故地形点的分布与密度能很好地适应地形的变化。此外，由于各种断裂线、地物和水系信息可用三维串线在数模中表示，方便地进行处理，使程序功能大为加强，这是串状数模最为突出的优点。英国的MOSS系统所采用的就是串状数字地面模型。
半规则数模能较好地适应地形变化，内插精度较高，但数据采集不能实现自动化，原始数据的分布与密度易受操作人的主观影响，建立数模过程中的程序处理较规则数模复杂。
1.2.3 不规则数模
不规则数模其原始地形数据点之间无任何联系，点的分布是随机的，一般常采集地形特征点、变坡点、反坡点、山脊线、山谷线等处，常见的有散点数模、三角网数模等。
散点数模是将原始地形点看作一些随机分布的“离散点”，可认为点与点之间无任何联系。在这种已知点中直接进行内插其精度是不可靠的，因为不能确定由哪些点构成实际的地表面。所以内插时先得利用已知点拟合一个局部的或区域的内插表面，然后再由该内插表面确定待定点的高程，这是这一类散点数模的共同特点。这种高程内插也称为移动曲面拟合法，在坡度变化均匀的地形条件下，这种拟合较符合地形的实际情况，可达到较高的内插精度。在坡度变化大，地形起伏急剧改变的区域，特别是地物、地形断裂线附近，这种曲面拟合则明显地难于很好地描述出地形局部形状，而造成内插点的高程误差偏大。所以，为提高散点数模的内插精度，使之满足工程设计需要，除原始数据点的分布必须符合地形变化，保持足够的密度外，程序中必须具备对地物、地形断裂线处理的功能。
从数模的精度和计算速度两方面来考察，散点数模不失为一种简单而有较的方法，具有很大的实用价值，在国内外许多实用程序中广泛地得到应用。
不规则数模总的特点是：数据采集是随机的，一般都是取地形特征点，所以能较好地适应地形变化，内插精度较高。其缺点是采样需要人工判读地形，从而增加了数据采集的难度，此外构造数模较复杂，计算时间较长。由于该类数模优点较为明显，所以应用最为广泛。
1.3 三角网数字地面模型基本原理
三角网数字地面模型(Triangulated Irregular Network)TIN是用一系列的互不交又、互不重复的三角形逼近地形表面，与Grid相比，TIN在拟合地表上更灵活、更精确。但由于结构的不同，Grid许多成熟的技术并不能完全移植到TIN中。
从结构上讲，TIN是一典型的矢量数据结构。它主要通过节点(地表采样点)、三角形
边和三角形面之间的关系来显式或隐式的表达底细功能散点的拓扑关系，因此设计一个高效的、结构紧凑的、维护方便的TIN的存储与组织结构对TIN的应用与维护是至关重要的。Tin的基本单元三角形的几何形状直接决定着TIN的应用质量。由于地形的自相关性，相
互越接近的地形采样点，其之间的关联程度越大;同时，理论与实践均证明，狭长的三角形其插值精度比规则的三角形插值精度可信度要低。因此，在Tin中对三角形的几何形状有着严格的要求。一般有三条原则:l)尽量接近正三角形;2)保证最近的点形成三角形;3)三角形网络唯一。
一个良好的数据结构和三角划分准则，必须由一个高效的算法和程序实现。算法在具体应用中发挥的作用由算法本身的性能和实现它的程序质量共同决定，而程序的好坏在很大程度上依赖于算法的原理。对算法本身在理论上进行分析论证，寻求一种高效率、高精度、适用面广的算法是TIN建立中的重要一环。
由上述的分析知，TIN的数据组织+三角划分准则+算法和程序构成了TIN的基本理论体系框架。图2表示了这一结构。
图2 TIN模型的理论体系结构
第二章三角网生成算法
目前国内外建立不规则三角形网的主要方法有三类：自动联结三角网法；径向扫描法（Radial Sweeping Algorithm简称RSA）；泰森三角形法（Thiessen）。下面分别对这几种方法作一些介绍和评价。
1 自动联结三角网法
自动联结三角形网，要求建立在可能获得最佳三角形的条件下。这个条件就是在使用周围邻近的离散点组成三角形网时，应尽可能地确保每个三角形都是锐角三角形或三边的长度尽量相等，避免出现过大的钝角和过小的的锐角。其判别法则是：最小距离和法则与最短外接圆半径法则。
最小距离和法则是指待插入点到基边两端点的距离和为最小，在用程序具体实现时，是用“该点对基边两端点张角а最大或其余弦值最小”原则来实现的。
最短外接圆半径法则是指三角形外接圆半径最小。从余弦定理公式：
c2=r2+ r2-2 r2cos(γ) （式2-1）
可以看出：cos(γ)∝-1/ r2。其中：c代表基边的固定长度，r代表外接圆半径。由于圆心角γ＝2а，即有cos(2а)∝-1/ r2，所以两种判别法则是保持一致的。
自动联接三角形网法的具体思路是：
1）确定第一个三角形
在散点域中任取一离散点A作为第一个三角形的第一顶点，找出距离该点最近的点B 作为第一个三角形的第二顶点且构成基边AB，应用余弦定理找出和该基边对角为最大的点作为第一个三角形的第三顶点。值得注意的是：为了顾及地形特征，找第三点时还必须遵守两条规则：①不跨越地形特征线条件；②不进入禁区（封闭区域）条件。
2）三角形的扩展
自动联结三角形网法中的三角形扩展是从第一个三角形的三条边依次开始的，应用余弦定理来找到第三点。为了防止三角形被遗漏、重复或发生交叉，每形成一个新的三角形，都要与己形成的三角形作一些比较判别，如果重复或交叉，则该三角形不记录。
自动联结三角形网法的优点是：原理明了，不考虑地形特征时编程简单。但其最大的缺点是：仅仅从最佳图形结构考虑，从而忽视了构网时的连续反复多次的三角形比较，使构网速度相当慢，导致数模的效率低下。而且一旦考虑地性线的介入，程序就变得复杂了。
2 径向扫描法（Radial Sweeping Algorithm简称RSA）
径向扫描法（RSA）是Miratl和Weingartan首次发表于一九八二年，其基本思想是分成以下两个阶段来完成不规则三角形网的建立。
1）建立稀疏的辐射三角网
首先是选择离区域形心最近的点作为辐射中心，由这一点向其它地形点作射线并计算其相对于辐射中心的距离和方位，对这些离散点以方位作为关键词进行排序，若方位相同则按距离，再把这些排序好的点与它的后继点连一线段，形成一系列细而长的三角形。如果该点同前一点居于同一方位，则前一点、该点、后继点三点组成新的三角形。
在处理过程中，用一个链表或动态数组将每一个点的信息存储起来，形成一个外边界。然后依次从链表或动态数组中连续取出三点，判别是否能形成内部三角形，若能，则记录该三角形，且把第二点从边界表中去掉。每当优点删去时，必须从头开始去进行点检验，最后得到一个凸形的闭合边界。
2）优化初始三角网
径向扫描法（RSA）法在优化三角网过程中考虑了两个因素，一是图形结构；二是地形起伏状况。显然，就图形结构而言，等边三角形是最佳图形；就地形起伏情况而言，为使三角形网能很好地覆盖于地表，三角形边不应有“悬空”和“切割”现象。具体到该法中，在考虑图形结构时，若相邻两个三角形组成凸四边形，应检查四边形两对角线之比，如果超过约定值，则以短边作为三角边；在考虑地形起伏清况时，则检查两对角线高差之比，一般选取高差大的两对角点连线作为三角形边。当二者出现矛盾时，视其影响而定。经过优化处理后，所得的三角网就比较合理了。
径向扫描法（RSA）法思路简明，容易实现。但是，约定值若没有一个客观的衡量标准，导致网形不唯一，特别是引入地性结构线后，难免会出现三角网的“悬空”或“切割”边，致使歪曲地形；同时三角网的优化工作也是一个相当复杂的过程，故该法在建立高精度的DTM 时是不可取的。
3 泰森（Thiessen）三角形法
泰森多边形的概念是:将分布在平面区域上的一组离散点用直线分隔,使每个离散点都包含在一个多边形之内。进行分隔的规则是,每个多边形内只包含一个离散点,而且包含离散点Pi的多边形中,任意一点Q到Pi的距离都小于Q点到任一其他离散点Pj的距离。把每两个相邻的泰森多边形中的离散点用直线连结,生成三角形网,这样数模便完成。泰森模型的显著特点是:每个三角形的外接圆内不包含其他离散点,而且三角形的最小内角达到最大值,又称Delaunay三角形和Delaunay三角形格网。
泰森三角形法是基于图论学的表面三角剖分方法。该法数学理论体系严密且从图论角度出发，因而具有良好的图形结构和网形唯一性。但是有两个限制条件：散点域必须为凸域；散点域中无四点共圆。由于其优点明显，国内外对其研究也多，发明了许多算法。本文将在下一章就改进的Thiessen三角形法，即：Delaunay三角形法构网建立数模进行详细介绍。
第三章三角网数字地面模型程序实现
在地学领域，经常需要处理大量分布于地域内的离散数据。为了合理利用一定地域内不均匀分布的离散地形点，1908年，G.V oronoi首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的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三角化的理论基础一Voronoi图
1908年，M.G.V oronoi首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的V oronoi图(以下称为v-图)。1934年Boly由v 图演化出了更易于分析应用的Delaunay三角网(以下称为D一三角网)。从此，V一图和D 一三角网就成了被普遍接受和广泛采用的分析离散数据的有力工具。在TIN的生成中，V 一图和D一三角网有着广泛的应用。
V oronoi图是由不规则网格定义的最基础和有用的结构之一。作为一个有着广泛用途的几何结构，V一图可以应用于许多领域，并且经常以首先将它应用与某一特定领域的人的名字来命名它。V一图在地理方面的应用是从气象学家A.H.Thiessen开始的。他用V一图去解释那些有着不均匀天气状况分布的地区，因此在此领域V一图又称为Thiessen多边形。
在图3.1中可以看到，V一图是通过切分一个中心点和它周围点之间的连线来定义的。切分线和连线之间的关系是互相垂直的。当我们对整个区域中的每一个点应用这种方法时，整个区域会被相邻的多边形所覆盖。图3.2是由一组自由分布的点组成的V一图。
图3.1 Voronoi多边形的构建图3.2 由一组自由分布的点
组成的V一图
V oronoi多边形有如下五点性质：
●对于平面区域V上给定的K个离散点，将S分成K个Voronoi多边形的分法是唯
一的。相应地，作为伴生图形的Delaunay三角网唯一。
●任意两个Voronoi多边形不存在公共区域。相应地，作为伴生图形的Delaunay三角
网中没有三角形重复、交叉。
●Voronoi多边形是一凸多边形。
●点集V中任意三点v i、v j、v k构成Delaunay三角形的充要条件是：过v i、v j、v k三
点的圆内不含有V中的其余任何点。
●由点集V中N个散点构成的Delaunav三角形数是：N t=2(N-1)-N b，三角形的边数
是：N e=3(N-1)-N b，其中N b是V-图外围边界顶点个数。
2）Delaunay三角网的定义
作为Voronoi图的对偶，Delaunay三角网与Voronoi图紧密相关，它以第一位发现这一对称关系的科学家B.Delaunay的名字命名。
Delaunay三角网的定义是:
连接所有相邻的V oronoi多边形的生长中心所形成的三角网称为Delannay三角网。
图3.3 一个点集的Voronoi图(虚线)和它的Delaunay三角剖分(实线)。
3.2 Delaunay三角网的特性
Delaunay三角网有几个非常重要的性质，如下所示：
(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个内角中的最小角时，我们称边e满足最大一最小角性质。满足最大一最小角性质的边也被称为局部优化的边(见图3.5)。V的三角剖分T，当且仅当T的每一条边都局部优化时，才是Delaunay三角剖分。
图3.5加深的边在(a)中没有局部优化，在(b)中被局部优化
(3) Delaunay三角网网形唯一性:
Delaunay三角网是建立在控制点周围最紧密相连的双重格网，这种网形只与离散点的分布有关，而与建网的途径即离散点参加构网的先后顺序无关。所以，只要离散点平面位置相对固定，其网形都一样。
由于几个性质，决定了Delaunay三角网具有极大的应用价值。同时，它也是二维平面三角网中唯一的、最好的。
3.3 Delaunay三角网构网方法
在GIS中，2.5维的分析处理由DTM(数字地形模型)模型进行。由上节可知DTM主要由格网（Ｇrid）与不规则三角网(TIN)两种数据格式来表示，而以后者更为重要。
格网的优点是：充分表现了高程的细节变化，拓扑关系简单，算法实现容易，某些空间操纵及存储方便；而它的局限性是：占用巨大的存储空间，不规则的地面特征与规则的数据表示之间的不协调。
不规则三角网的优点是：高效率的存储，数据结构简单，与不规则的地面特征和谐一致，可以表示线性特征和迭加任意形状的区域边界，易于更新，可适应各种分布密度的数据等；而它的局限性是：算法实现比较复杂和困难。
在现今的GIS系统中，基本上均支持以上两种数据格式，以不规则三角网为主，格网为辅，并提供相互转换功能。历经二十余年的不懈努力，TIN的许多算法难关已被攻克。TIN 的生成算法中，三种算法：分割-归并法、逐点插入法和逐步生长法最终被普遍接受和采用，而又以前二者更为流行。分割-归并法时间效率高，但占用内存空间较多；逐点插入法时间效率较差，占用内存空间较少。现在有人在这两种算法的基础上，提出了一种综合性能的算法—合成算法，它的性能优于以上两种算法。
下面就Delaunay三角网的三类建网方法：分治算法、逐点插入法、逐步生长法作进一步介绍和评价。
3.3.1 分治算法（Divide-and-Conquer）
Shamos和Hoey提出了分治算法思想，并给出了一个生成V-图的分治算法。Lewis和Robinson于1978年提出了一种建立三角网的方法，以处理限定边界的等高线和有限元分析应用，他们将分治算法思想应用于生成Delaunay三角网，他们给出了一个“问题简化”算法，递归地分割点集，直至子集中只包含三个点而形成三角形，然后自下而上地逐级合并生成最终的三角网。以后Lee和Schachter又改进和完善了Lewis和Robinson的算法，提出了对平面点建立Delaunay三角网的分而治之算法。这种算法首先将数据排序，分成两个互不相交的子集，在每一子集建立三角网后，将两个三角网合并以生成最终的狄洛尼三角网。Dwyer（1987）对分而治之算法作了一些改进。通过将数据分成垂直条块，进而用相交边界将条块再一次细分为区域，并应用带约束条件的Lawson LOP将对角线进行交换，Dwyer的算法能处理带约束条件的数据。
Lee和Schachter算法的基本步骤是：
1．把点集V以横坐标为主，纵坐标为辅按升序排序，然后递归地执行步骤2~6；
2．把点集V分为近似相等的两个子集V L和V R；
3．在V L和V R中生成三角网；
4．用Lawson提出的局部优化算法（LOP）优化所生成的三角网,使之成为Delaunay三角网；
5．找出连接V L和V R中两个凸壳的底线和顶线；
6．由底线至顶线合并V L和V R中两个三角网。
以上步骤显示，分治算法的基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用局部优化算法（LOP）保证其成为Delaunay三角网。不同的实现方法可有不同的点集划分法、子三角网生成法及合并法。
3.3.2 逐点插入法（Iteration）
Lawson提出了用逐点插入法建立Delaunay三角网的算法思想，它是将未处理的点加入到已经存在的Delaunay三角网中，每次插入一个点，然后将Delaunay三角网重新定义。Lee 和Schachter，Bowyer，Watson，Sloan，Macedonio和Pareschi，Floriani和Puppo，Tsai先后进行了发展和完善。
逐点插入算法的基本步骤是：
1．定义一个包含所有数据点的初始多边形；
2．在初始多边形中建立初始三角网；
3．插入一个数据点P，在已经存在的三角网中找出包含P的三角形t，把P与t的三个顶点相连，生成三个新的三角形；
4．用Lawson的LOP算法优化局部三角网；
5．是否所有离散点都参与了构网？若是，构网完毕；否则，转到3。
从上述步骤可以看出，逐点插入算法的思路非常简单，清晰。先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为Delaunay 三角网。同时，该算法占用内存小，时间复杂度为O(N5/4)，运算速度较快，是一种比较理想的Delaunay三角网构网方法。各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法不同。
3.3.3 逐步生长法
Green和Sibson首次实现了一个生成Dirichlet多边形图的生长算法。他们在1978年提出的递归方法通过顺序扫描数据点，计算平面Dirichlet多边形。在此过程中随着新点的加入，以递归的方式改变新点周围Dirichlet多边形的邻接关系。Brassel和Reif稍后也发表了类似的算法。这种算法从任意一点开始，在一维排序链表中以循环搜索方式查找此任意点的泰森邻域点，将建模区域划分为泰森多边形，然后把这一点与其所有泰森邻域点连接以形成了Delaunay三角网，并由此生长，直至所有点都包含到三角网中。McCullagh和Ross通过把点集分块和排序改进了点搜索方法，减少了搜索时间。Maus也给出了一个非常相似的算法。
逐步生长法的基本步骤是：
1．以任一点为起始点，找出与起始点最近的数据点相互连接形成Delaunay三角形的一条边作为基线；
2．按Delaunay三角网的判别法则(即它的两个基本性质)，找出与基线构成Delaunay三角形的第三点；
3．基线的两个端点与第三点相连，成为新的基线；
4．迭代以上两步直至所有基线都被处理。
上述过程表明, 逐步生长法的思路是，先找出点集中相距最短的两点连接成为一条Delaunay边，然后按Delaunay三角网的判别法则找出包含此边的Delaunay三角形的另一端点，依次处理所有新生成的边，直至最终完成。该算法时间复杂度为0（N3/2），时间效率较低，现已基本淘汰。各种不同的实现方法多在搜寻“第三点”上做文章。
Tsai为比较算法性能，给出了一张各种算法的时间复杂度对照表，如表1所示。
表1几种Delaunay三角网生成算法的时间复杂度
上标说明：1. 分割-归并法；2. 逐点插入法；3. 逐步生长法。表中N为数据点数，O(f(N))表示算法的时间复杂度，它以算法中频度最大的语句频度f(N)来度量。
3.3.4 一种新的合成算法
由上面的介绍我们可以看到，目前采用较多的前两类算法各具优势又有局限，同时，它们又具有明显的互补性。分治算法时间性能好，空间性能差；逐点插入法空间性能好，时间性能差。我们评价一个算法的优劣是看它对时间和空间的消耗，即时空性能的综合表现。因此，就产生了一种合成算法即把以上两种算法结合起来，取长补短，来提高算法的性能。这种结合的具体做法是：以分治算法为主体，当递归分割数据集的过程进行到子集中的数据量小于一个预定值——分割阈值时终止，然后用逐点插入法在子集中生成子三角网。这种算法就是合成算法。它的流程图见图5。
图3.6 合成算法主程序流程图
其中Ｖ表示数据集：ＮＶ是Ｖ的数据量；Ｎｄ是分割阈值；ＮＬ,ＮＲ分别表示两个子集的数据量；ＴＬ,ＴＲ分别表示在子集中建立的两个子三角网。
图3.6表明，为便于分割，首先按升序以横坐标ｘ为主，纵坐标ｙ为辅把数据排序。然后比较ＮＶ与Ｎｄ，如ＮＶ>Ｎｄ则分割数据集，否则用逐点插入法生成三角网。
合成算法包含3个模块：逐点插入法模块、寻找上下切线模块以及合并模块。
1．逐点插入法模块
逐点插入法有多种实现方法，该算法选用Ｍacedonio和Ｐareschi提出的方法。在这个方法中，把数据中的凸壳作为超级多边形。凸壳就是由数据中的凸集顺序相连形成的多边形。逐点插入法模块由以下4个步骤完成。
(1)找出凸壳。
这一步用Ｌarkin 在1991年提出的算法来做。为提高搜索效率，先将数据集划分为矩形栅格。设每个栅格单元内包含的数据为4，则栅格的行列数为ＮＶ/4。因具有ｘ,ｙ,ｘ+ｙ,
ｘ-ｙ的最大值及最小值的点是凸集中的点，把它们按逆时针方向顺序相连作为初始凸壳。然后用递归函数convex (Ｉ,Ｊ)完成整个凸壳。Ｉ,Ｊ是凸壳上的相邻点。convex (Ｉ,Ｊ)找出凸壳上Ｉ,Ｊ间的另一点Ｋ。如果不存在,则返回空。Ｋ是与ＩＪ相交的栅格中位于ＩＪ右侧且与ＩＪ距离最大的点，或当ＩＪ右侧无点，但ＩＪ上有点，且位于Ｉ,Ｊ之间的点。
(2)建立初始三角网。
以凸壳上ｘ值最小的点为出发点，按序与其余点相连。
(3)插入点。
先找出包含要插入的点Ｐ的三角形ｔ，然后连接Ｐ与ｔ的3个顶点。
(4)优化。
用Delaunay三角网的空心圆性质考查新生成的三角形，如不满足，则调换与相邻三角形所组成的四边形中相连的对角线。向相邻三角形扩展此过程直到满足条件为止。
后两步循环执行直到插入全部数据。
2寻找上下切线模块
这个模块找出连接左右两个子三角网的凸壳ＨＬ和ＨＲ的上切线和下切线。设Ｘ是ＨＬ中ｘ值最大的点；Ｙ是ＨＲ中ｘ值最小的点；Ｚ′是ＨＲ上Ｙ逆时针方向的邻点；Ｚ″是ＨＬ上Ｘ顺时针方向的邻点。寻找ＨＬ和ＨＲ的下切线过程由两个循环完成。
(1) 如Ｚ′位于ＸＹ右侧，则Ｚ′成为新的Ｙ，Ｙ逆时针方向的邻点成为新的Ｚ′，否则退出。
(2) 如Ｚ″位于ＸＹ右侧，则Ｚ″成为新的Ｘ，Ｘ逆时针方向的邻点成为新的Ｚ″，否则退出。
用类似的方法可以生成ＨＬ和ＨＲ的上切线。
3合并模块
子三角网ＴＬ和ＴＲ的合并由一个循环完成。以ＨＬ和ＨＲ的下切线为起始基线，分别在ＴＬ和ＴＲ中找出与它构成Delaunay三角形的第3个顶点Ｌ1和Ｒ1，在这两个三角形中选择外接圆半径小的连接到三角网中。新生成的边作为新的基线继续这个过程，当基线成为ＨＬ和ＨＲ的上切线时终止。在寻找上下切线模块和合并模块中，要频繁用到两个函数pred (Ｖｉ,Ｖｊ)和succ (Ｖｉ,Ｖｊ)。pred (Ｖｉ,Ｖｊ)是在包含公共端点Ｖｉ的一簇线段中，得到与边ＶｉＶｊ顺时针方向邻边的另一个端点。succ (Ｖｉ,Ｖｊ)相反，是得到与边ＶｉＶｊ逆时针方向邻边的另一个端点。
3.4 局部优化过程（LOP-Local Optimization Procedure）
Lawson提出的局部优化过程是所有生成Delaunay三角网算法都要用到的关键过程，其理论依据就是Delaunay三角网的空外接圆性质。前面所讲到的采用逐步插入法插入一个点P时，局部三角网优化过程是：三角形入栈→出栈→Delaunay三角化→入栈→出栈，直到栈空为止，其步骤如下（示意图如图3.7所示）：
图3.7 局部优化过程
（1）、建立堆栈A和B；
（2）、连接点P与其所在三角形（t4）的三顶点，构成三个三角形（t4、t5和t6）；
(3)、初始化堆栈。把以P为顶点的三角形（t4、t5和t6）放入堆栈A中，把与P相对的
三角形（t3、t1和t2）放入堆栈B中，且必须保证两组三角形中处于同一位置的两个三角形相邻；
(4)、出栈。检查A、B（其实A、B是同步的）是否为空，若是，则过程完毕；否则分
别从栈A、B中取出一个三角形（t4、t3）；
(5)、Delaunay三角化。检查P是否在从栈B中取出的三角形（t3）的外接圆内（不包
括刚好在圆上）。若不是，转4；否则，由这两个三角形形成凸四边形，交换其对角线形成新的三角形且赋与相同的编号（t4、t3）；
(6)、入栈。把刚形成的三角形（t4、t3）放入栈A，把新的与P相对的两个三角形（t7、
t8）放入栈B，且注意次序。再转4。
3.5 初始多边形及三角形的形成
Delaunay三角网的外边界是凸多边形，采用逐点插入法首先得建立初始多边形，即“凸壳”及初始三角网。生成凸壳的方法、凸壳的形状多种多样，相应地生成的初始三角形也不一样。
3.5.1 构造三角形作为凸壳
这里介绍一种采用三角形作为初始多边形的方法，其方法大致如下：
1．计算d max的值。
d x=x max-x min，d y=y max-y min，d max=max（d x，d y）
2．标准化坐标值。目的是使点的x、y值限定在0~1的范围内。
x′=（x-x min）/d max，y′=（y-y min）/d max
3．构造凸壳。
有关文献中非常形象地采用了术语“supertriangle”，意思是“特大三角形”。方法是在原有点集中增加三个点，用标准化坐标表示分别为（-100，-100）、（100，-100）和（0，100）。这三点构成的三角形包容了整个点集，既是初始多边形，又是初始三角网。
其实为构造凸壳增加的三点可任意取值，条件是包容整个点集。该法的缺点是标准化坐标会影响数据精度。
3.5.2 找边界点构造凸壳
该方法是首先定义初始凸壳，用程序递规找出其余边界点，构成凸壳。然后，用凸壳上某一点为固定点，与其他点连直线构成初始三角网。最后借助Lawson的LOP算法优化初始三角网成为新的初始三角网。该算法麻烦，比较费时。
3.5.3 构造四边形作为凸壳
如果采用四边形作为初始凸多边形，其过程如下：
1．计算散点集的向最小值x min、最大值x max和y向最小值y min、最大值y max，且进行修正。
x min=x min-TOL；x max=x max+TOL；
y min=y min-TOL；y max=y max+TOL；
2．构造凸多边形
构造四个虚点并增加到散点集中：A（x min，y min，0），B（x max，y min，0），C（x max，y max，0）和D（x min，y max，0）。
3．构造初始三角网
首先按逆时针顺序构造两个三角形：一个由A、B、C三点构成，三角形编号为0；另
一个由A、C、D构成，三角形编号为1。然后利用LOP算法优化初始三角网。
3.6 点所在三角形的判别方法
采用逐点插入法时，程序首先需要找到包含该点的三角形。在空间分析学中，将点元素与面元素的空间拓扑计算归结为著名的“点在多边形中（Point-in-polygon）”的识别问题。三角形是一个凸多边形，判别方法更多，目前主要有以下几种：面积法、交点法、方向角法和循环法。
3.6.1 面积法
基本原理：根据三角形之间的面积关系来判定。如图3.8（a）所示，把待判定点P与三角形t的三个顶点A、B、C直线相连，形成四个三角形，由数学上的“图解法”可得出如下结论：
1．若SΔABC=SΔABP+SΔBCP+SΔCAP，则点P在三角形t内；
2．若SΔABC＜SΔABP+SΔBCP+SΔCAP，则点P在三角形t外；
评述：该法搜索三角形的量大，计算量也大，因而速度也慢。
（a）面积法（b）交点法（c）循环法
图3.8 包含点P的三角形的判定方法
3.6.2 交点法
有的资料上称作“垂线法”或“半线理论”，其基本原理：计算并根据过点的某一射线与三角形相交的交点的分布情况来判定。如图3.8（b）所示，由点P向右作平行于x轴或向下作平行于y轴的射线，（不用计算）判定该射线与三角形t的边的交点个数，并根据交点个数得出如下结论：
1)、若交点数为奇数，则点P在三角形t内；
2)、若交点数为偶数，则点P在三角形t外；
需注意的是：在统计交点数时，当交点为三角形t的一顶点时，采取“舍下取上”的原则，即：当某线两端点的y坐标均小于等于y P时，不计交点；当某线两端点的y坐标只要一个大于y P时，就计交点。
该方法在明确判定指定的三角形时还比较简单，且对凹凸多边形均适用，特别在基于闭合特征线的网形调整时非常实用。但在未明确对象时，搜索的三角形数会很多，计算量很大，导致速度慢。
3.6.3 方向角法
有的资料上也称为“夹角和法则”。基本原理是待定点P与三角形t的三个顶点连线段，按顶点次序各线段的夹角值代数和为一常数，如图3.9所示，其中各夹角规定逆时针为正，
顺时针为负。
（a）P在t内（b）P在t外
图3.9 包含点P的三角形的判定方法（二）——方向角法
由图可以得出以下结论：
若方向角之和等于360o，则点P在三角形t内；
若方向角之和等于0o，则点P在三角形t外；
该方向交的计算复杂，运行速度慢，且不便于识别三角形边界的点。
3.6.4 循环法
循环法的基本原理是根据三角形的数据组织结构中顶点是按顺时针（clockwise）还是逆时针（anti-clockwise）排列及点P在三角形边的左右来判定。如图3.10所示，结论如下：当三角形顶点为逆时针排列时，若点P都在三角形三边的左侧，则点P在三角形t内；换个角度来看，若点P在某一边的右侧，则点P有可能在该边右侧的三角形内，使得搜寻三角形有某种方向性，如图3.10所示；
图3.10 循环法定位点P所处三角形
循环法只适用于凸多边形，对TIN是适宜的。该法搜寻方向明确，提高了查找速度；思路明确，公式简单，计算量不大。
3.7 数据组织结构的原则
数据组织结构是DTM的基石，它的功能强弱将左右着整个数模系统的功能和性能。数据组织结构原则如下：
数据结构的设计必须服务于系统功能的设计。它要为系统提供完整的数据信息，以利于
各种应用；
在满足系统功能的前提下，数据组织结构必须尽量简单，仅仅占用最小的存贮空间； 快速查询功能。数据查询是DTM 的各项功能中使用最为频繁的，但是DTM 的数据量极大且杂，遍历数据是不可取的。快速查询意味着要付出一定的空间代价，须建立各种辅助索引，以换取查询速度的提高；
动态拓扑结构。早期拓扑数据只是用于检查图形正确性的冗余数据，现在拓扑查询之需已成为DTM 的必备成分，原先拓扑数据结构是静态的，对任何图形的局部修改都需重建全局的拓扑关系，动态拓扑结构则能实时地响应局部拓扑关系的修改，而无需全局重新建立，提高了系统的速度。
3.8 三角网数模的排序与检索
目前，带状数字地面模型的数据检索有三级检索和二级检索机制两种。
三级检索是把整个路段作为一个整体模型，建立“子区→子块→点、三角形链表”的检索机制，子区是沿路线划分建立的，如图3.11所示。
图3.11 三级索引的子区划分
有时候我们一方面整个路段的数据量很大，需很大计算机空间；另一方面，考虑到路线设计一般是分段设计的，没有必要这样做。也可以采用二级索引机制，以文件的形式分成几个子区，各子区用均匀（正方形）格网建立“子块→点、三角形链表”的索引。子区内数据组织如下所述。
1．计算子区地形散点的包容盒。
Xmin=Xmin-TOL ；
Xmax=Xmax+TOL ；
Ymin=Ymin-TOL ；
Ymax=Ymax+TOL ；
其中：TOL 为修正值，解决点落在格网线上的问题。
2．计算格网边长大小。
经检验每个格网中约放√n 个散点时，速度较好。则格网边长size 为：
size ＝N y y x x )
)((min max min max -- （式3-1）
计算x 、y 轴向各自的格网数x_res,y_res 。
x_res ＝ int (1min max +-size
x x ) （式3-2）
y_res ＝ int (
1min max +-size
y y ) （式3-3） 则总的格网数为： allres ＝ x_res ×y_res （式3-4）
3.格网排序。
为了减小空间及加快搜寻速度，可以对格网的组织由二维转换为一维连续排序。排序过程见图3.12所示。
图3.12 格网排序过程
4．确定点P （x ，y ）所在的格网号。
i ＝ int (
1min +-size x x ) （式3-5） j ＝ int (1min +-size
y y ) （式3-6） 根据i 、j 计算格网号m_nBin:
(i) 若i 为奇数，则有：
m_nBin=(i-1)*y_res+j
(ii)若ｉ为偶数，则有：
m_nBin=i*y_res-j+1
3.9 顾及地形特征线的网形调整
地形特征线，包括山脊线、山谷线、陡坎等地形线及河流、房屋等地物轮廓线。在把这些特征线数据点与一般地形点一起完成初级网的建立之后，再用其信息进行网形调整，将
使建立高精度的数字地面模型成为可能。
3.9.1 基本原理
（1）、多边形的Ｎ次三角剖分
对一任意多边形的Ｎ次三角剖分，虽然各次的三角形形状不同，但是其数目相等，不含边界的内部边数也相等。如图3.13所示。
图3.13 多边形的N 次三角剖分
（2）、凹凸点判别原则
对于按给定方向（顺时针或逆时针）组成的多边形Ｐ0Ｐ1…Ｐi-1Ｐi Ｐi+1…Ｐ0，其中Ｐi 相对于Ｐi-1，Ｐi+1的凹凸性为：（参见下图3.14）
图3.14 凹凸点判别法则
det ＝i i i i i i i i x x x x y y y y ----+-+-1111
（式3-7）
当Ｐi-1、Ｐi 、Ｐi+1为顺时针排列时：
det ＞0 Ｐi 为凸点
det ＜0 Ｐi 为凹点
det ＝0 Ｐi-1、Ｐi 、Ｐi+1 三点共线
当Ｐi-1、Ｐi 、Ｐi+1为逆时针排列时：
det ＞0 Ｐi 为凹点
det＜0 Ｐi为凸点
det＝0 Ｐi-1、Ｐi、Ｐi+1 三点共线
3.9.2 对地形特征线的预处理
（1）、加密地形特征线上的点
一条地形特征线上的数据采集是在转折处（水平和竖向）发生的。因此，有可能在地形特征线上相邻两个点（Ｐ１、Ｐ２）之间的直线距离很大，从而导致网形调整时，产生瘦长的不良三角形。为了避免这种情况发生，在数据预处理阶段，根据采用点的密度沿地形特征线内插加密，并使这些点参加初级三角网的建立。参见图3.15。
（a）加密前的网形（b）加密后的网形
图3.15 地形特征线加密前后的网形对比
（2）、对陡坎地形存贮结构的处理
对于坡度陡峭的地形，特别是陡坎处，地形发生了剧烈的突变。当构造ＴＩＮ时，只有顾及陡坎地形的影响，才能使ＤＴＭ最大限度地正确反映出实际地形。出于网形调整阶段的需要，在数据预处理阶段建立地形特征结构时，要规定陡坎地形线的起讫方向，添加哪侧（左侧还是右侧）为坎上（坎下）的属性数据，目的是为了在网形调整时，给陡坎处分别属于陡坎两侧三角形的同一平面点赋不同的高程值。
3.9.3 网形调整
1）、基于一般地形特征线的网形调整
（1）检查特征线（ＶｉＶｊ）是否已成为某个Delaunay三角形的边。若是，则转下一段或下一条特征线；否则转（２）。
（2）建立两个链表list１和list２。把特征线起点（Ｖｉ）作为表头。查找与特征线相交的三角形边。首先从包含特征线起点（Ｖｉ）的任一三角形开始，查找到包含该点且与特征线相交的三角形及相交的边（Ｖ２Ｖ１）。然后查找共享该边的相邻三角形，直到全部找到相交边，并把这些边的起讫点（Ｖ２和Ｖ４、Ｖ１和Ｖ３）分别存入链表list１和list２。同时记录下这些三角形号。参见图3.16。
图3.16 搜索与特征线相交的三角形边
由链表list１和list２分别形成逆时针和顺时针两个多边形。参见图3.17。
图3.17 生成特征多边形
三角剖分两个多边形。三角形的编号就是刚记录的编号。
其具体方法是：从链表中第一点开始依次连续地取出三点，根据“凹凸性判别法则”判定第二点的凹凸性，如果为凸点，则形成三角形并编号，同时从链表中删去第二点形成新的链表；如果为凹点，则后移一个点，再取连续三点执行。反复循环，直到链表中只剩三点构成一个三角形，则过程完毕。参见图3.18。
图3.18 特征多边形的三角剖分
不规则三角网的算法设计与实现10页word文档
1 引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM （Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。
基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。 2 TIN的算法种类及各算法特点 在介绍构成TIN各种算法之前我们要来了解认识一下一个重要法则——Delaunay三角网法则。通常构建三角网并不考虑地性线（山脊线，山谷线）的骨架作用，但是，由于用等高线数据构建三角网时，由于地形的复杂多样，有的地区存在因地形突变而形成的断裂线等特殊地貌。另外一些地区存在大面积水域等内部不需要构网的区域，因此，在精度要求较高的TIN中，必须考虑以上问题。因此此时应顾及地性线，断裂线，水域线等特殊情况，也就是应构建约束—Delaunay三角网。约束法是基于约束图计算约束D—三角剖分[1,9]（简称CDT，即Constrained Delaunay Triangulation）构造算法[8]，这种Delaunay三角网满足这样的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的
边角三角网平差程序的设计书
边角三角网平差程序设计书 一、课程设计的目的 学生在学习完误差理论与测量平差基础、测量平差程序设计基础等课程的基础上，设计一个完整的测量数据处理程序，培养学生综合应用量数据处理与计算机应用能力，培养学生主动学习，创新设计能力。 二、课程设计的任务和内容 1.课程设计任务： 在两周的时间内应用者Matlab程序设计语言编制一个完整的边角网严密平差程序,要求有简易的界面，数据输入采用文本输入，采用间接平差模型完成平差的基本计算，能够画出控制网图，输出基本的计算结果，并根据设计过程完成设计报告。 程序设计主要内容包括： 系统功能设计 界面设计 流程设计 代码书写 程序调试 三、课程设计阶段 准备阶段 研究设计任务书，分析设计题目，熟悉原始数据，明确设计内容和要求；制定课程设计计划和进度。 熟悉算法模型 阅读误差理论与测量平差基础教材，掌握平面控制网数据处理的数学模型，
这里主要是指方向观测量、角度观测量、边长观测量的观测方程和误差方程的构成，研究平面观测数据的组织方法，设计Matlab算法，实现计算的自动表达。 功能设计阶段设计程序要实现的功能 平差程序的基本功能包括数据的输入，平差计算，精度评定、成果输出等； 4.流程和界面设计阶段 根据平差计算的过程和程序功能，画出流程图，设计简易界面实现数据的输入和平差计算和成果输出。在此基础上，根据功能要求，设计简便的界面。 5．代码书写和调试阶段 按照计算流程图和界面设计，根据方向观测值，边长观测值的误差方程的组成，设计Matlab算法，实现误差方程的自动构成，分阶段书写代码，调试实现各个阶段的功能。 6.设计报告撰写阶段 设计报告是对整个设计过程进行综合总结提高，内容包括课设的目的意义、程序设计的内容、算法设计、设计心得等根据设计过程和对测量数据处理以及程序设计的理解进行独立撰写。 四、组织方式进度安排 以小组为单位，每小组5-6人，分工合作共同完成程序设计任务，时间两周， 进度安 排如下：
不规则三角网(TIN)
不规则三角网（TIN） Ⅰ 数字高程模型（DEM）地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已被普遍广泛采用。数字 高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。DEM有三 种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。Ⅱ TIN的基本知识在TIN中，满足最佳三角形的条件为：尽可能的保证三角形的
三个角都是锐角，三角形的三条边近似相等，最小角最大化。 TIN 是基于矢量的数字地理数据的一种形式，通过将一系列折点（点）组成三角形来构建。形成这些三角形的插值方法有很多种，例如Delaunay 三角测量法或距离排序法。ArcGIS 支持Delaunay 三角测量方法。 TIN 的单位是英尺或米等长度单位，而不是度分秒。当使用地理坐标系的角度坐标进行构建时，Delaunay 三角 测量无效。创建TIN 时，应使用投影坐标系（PCS）。 TIN 模型的适用范围不及栅格表面模型那么广泛，且构建和处理所需的开销更大。获得优良源数据的成本可能会很高，并且，由于数据结构非常复杂，处理TIN 的效率 要比处理栅格数据低。 TIN 通常用于较小区域的高精度建模（如在工程应用中），此时TIN 非常有用，因为它们允许计算平面面积、表面积和体积。Ⅲ TIN在ArcGIS中的存储TIN 表面数据模型由结点（Node）、边（Edge）、三角形（Triangle）、包面（Hull）和拓扑（Topology）组成。 与coverage 类似，TIN 以文件目录形式存储。但TIN没有关联的INFO 文件。TIN 目录由七个包含TIN 表面信息的文件组成。这些文件以二进制格式编码，因此无法通过标准文本显示或编辑程序读取。 TIN 的最大允许大小视连续可用内存资源而定。对
第三章 不规则三角网
第三章不规则三角网 教学目的与要求 通过本章的学习，让大家了解ArcView GIS 3D Analyst扩展模块，熟悉不规则三角网的生成方法，掌握工程填挖方的计算方法，掌握从3D Shapefile生成三维纵剖面和根据线状图形生成纵剖面的方法，能够进行视线与视域分析。 内容提要 5.1地表模型生成、显示 5.2工程中的土方、纵坡 5.3视线与视域分析 教学重点 工程土方量的计算方法 视域与视线分析方法 三维纵剖面图的创建方法 教学难点 不规则三角网的生成方法 5.1 地表模型生成、显示 一、由点状要素产生不规则三角网 所需数据： 点状专题 所用扩展模块： 3D Analyst 所用命令： Surface/Create TIN (Triangulated Irregular Network) from Features... 属性数据表中必须添加高程字段。 详见演示 等高线专题图的生成： 选用菜单命令Surface/Create Contours… 二、不规则三角网和距离倒数权重法插值比较 所需数据： 点状专题 所用扩展模块： Spatial Analyst 所用命令： Surface/Interpolate Grid... 属性数据表中必须添加高程字段，用于高程的计算。
详见演示 等高线专题图的生成： 选用菜单命令Surface/Create Contours… 通过比较，可知不规则三角网比较符合地形特征。 三、建立设计场地的三角网高程模型 所需数据： 设计场地高程控制点专题，并具有各个点的高程属性。 所用扩展模块： 3D Analyst 所用命令： Surface/Create TIN (Triangulated Irregular Network) from Features... 详见演示 四、在场地上添加其他要素 已知数据： 三个AutoCAD的立体图形文件。 Bldg.dwg 选polygon，多边形，建筑物 Road.dwg 选line，线，道路 Water.dwg 选polygon，多边形，水面 所用扩展模块： Cad Reader 所用命令： View/Add Theme 详见演示 五、三维显示 命令：View/3D Scene…，对系统的提示选择Themes，按OK键后系统产生3D Scenes Themes Document，该子系统具有自己的三维视图窗口和图例框，可用鼠标点击按钮Navigate(形状像帆船)，再用鼠标在三维窗口中控制观察地形的三维视角。 在三维场景中，选用菜单命令Theme/3D Properties… 详见演示 小结 不规则三角网络是描述三维表面的常用方法，除了在地形方面，还可以用于其他各种领域。在不规则三角网上还可以叠加其它空间要素，同时以三维方式显示。 5.2 工程中的土方、纵坡 一、由等高线产生不规则三角网 使用数据：设计等高线、现状等高线、场地边界线 扩展模块：3D Analyst 所用命令：Surface/Create TIN from Features 操作步骤：
12.1三角网坐标平差
§12.1三角网坐标平差 第十二章概述 间接平差又称参数平差。水平控制网按间接平差时，通常选取待定点的坐标平差值作为未知数(按方向平差时，还增加测站定向角未知数)，平差后直接求得各待定点的坐标平差值，故这种以待定点坐标作为未知数的间接平差法也称为坐标平差法。参加平差的量可以是网中的直接观测量，例如方向、边长等；也可以是直接观测量的函数，例如角度等。由于三角网的水平角一般是采用方向观测法观测，并由相邻方向相减而得，故它们是相关观测值。此时，若不顾及函数间的相关性，平差结果将受到一定的曲解。因此，坐标平差法都按方向平差。 间接平差的函数模型是误差方程，它是表达观测量与未知数之间关系的方程式。一般工程测量平面控制网的观测对象主要是方向(或角度)和相邻点间的距离(即边长)因此坐标平差时主要列立各观测方向及观测边长的误差方程式，再按照间接平差法的原理和步骤，由误差方程和观测值的权组成未知数法方程去解算待定点坐标平差值，并进行精度评定。 本章主要研究（测）方向网、测边网以及测边测角网的严密坐标平差。 水平控制网按坐标平差法进行平差时，为降低法方程的阶数以便于解算，定向角未知数可采用一定的法则予以消掉。由于误差方程式的组成简单且有规律，便于由程序实现全部计算，因此，在近代测量平差实践中，控制网按间接平差法得到了广泛的应用。平面控制网按坐标平差时，网中每一观测值都应列立一个误差方程式。
为便于计算，通常总是将观测值改正数表示为对应待定点坐标近似值改正数的线性式。坐标平差的第一步是列组误差方程式。对于方向网而言,参与平差的观测值是未定向的方向，选定的未知数是待定点的纵、横坐标值。误差方程式就是方向观测值改正数表达为待定点纵横坐标值的函数式，可以通过坐标方位角来建立方向值与未知 数之间的联系。 12.1.1方向误差方程式的建立和组成 在测站k 上观测了n i k k k ,,,0 等方向 其方向观测值为kn ki k N N N ,,,0 它们的改正数为kn ki k V V V ,,,0 0k 为测站的零方向（起始方向），则任意方向i k 的坐标方位角平差值方程 为 ki ki k k ki k ki V N Z N Z +++=+=?α （12-1） 式中：ki N 为ki 方向的平差值， k Z 为0k 方向的坐标方位角，通常称测站定向角， k Z 为定向角k Z 的近似值， k ?为定向角k Z 的改正数，是个未知参数， k k k Z Z ?+=，ki ki ki V N N += 如果令i k ,两点的近似坐标分别为00,k k y x 和0 0,i i y x ， 其相应的改正数分别为k k y x δδ,和i i y x δδ,， 则有关系：
基于不规则三角网的DTM若干问题的探讨
第23卷 第2期重 庆 交 通 学 院 学 报2004年4月Vo1 23No 2JOURNAL OF C HONGQI NG JIAOTONG UNIVE RSI TY Apr.,2004 基于不规则三角网的DTM若干问题的探讨 赖鸿斌, 李永树 (西南交通大学测量工程系,四川成都610031) 摘要:介绍了用不规则三角网(TIN)建立数字地面模型(DTM)的基本思路,讨论了在建模过程中所遇到问题的解决方法,分析了混合模型的应用问题及TIN数据结构.最后,运用实例说明了由TIN生成的DTM在工程中的应用方法. 关 键 词:不规则三角网;数字地面模型;数据结构 中图分类号:U412 24 文献标识码:A 文章编号:1001 716X(2004)02 0090 04 数字地形模型(Digital Terrain Mode,简称D TM)是表示地形表面的数学(数字)模型.从数学的观点看,地面模型是一个空间连续函数,或是地形模型的离散化表示.对地形表面进行表达的各种处理可称为表面重建或表面建模,重建的表面通常被认为是DTM表面[1]. DTM的核心是地面特征点的三维坐标数据和一套对地表提供连续描述的算法,最基本的DTM至少包含了相关区域内平面坐标(X,Y)与高程Z之间的映射关系,即 Z=F(X,Y) (X,Y) DTM所在区域[2]. 目前,DTM模型的建立和利用已成为地理信息系统的重要组成部分. 1 基于不规则三角网建立DTM 地形表面的建模主要有4种方法:基于点的建模方法、基于不规则三角形的建模方法、基于规则格网的建模方法和混合建模方法[1],其中用得较多的是基于不规则三角形的建模方法和基于规则格网的建模方法. 基于不规则三角形建模是直接利用野外实测的地形特征点(离散点)构造出邻接的三角形,从而组成不规则三角网结构.相对于规则格网,不规则三角网具有以下优点:利用原始资料作为网格结点;不改变原始数据和精度;能够插入地性线以保存原有关键的地形特征,以及能很好地适应复杂、不规则地形等. 不规则三角网(TI N)作为一种主要的DTM表示法,虽然其生成算法比较复杂,但却有许多优点.根据生成三角网算法的不同,可以将生成三角网的算法分为以下三种:分而治之算法、数据点逐次插入算法和三角网生长算法[1].分而治之算法的思想以及生成V 图的分治算法最先是由Shamos和Hoey提出的.Le wis和Robinson将分而治之算法思想应用于生成三角网并给出了一个简化算法:即递归地分割点集,直至子集中只包含三个点而形成三角形,然后自上而下地逐级合并生成最终的三角网;数据点逐次插入算法的思想是由Lawson提出的,以后,Lee和Schachter、Sloan、Watson、Pareschi和Macedonio、Puppo 和Floriani等人先后对这一算法做进一步的改进和完善;三角网生长算法是由Green和Sibson在1978年首先给出的.后来,Reif 、Maus和Brassel等人也发表了类似的算法.下面主要讨论利用三角网生长算法来构建不规则三角网. 如图1所示,在数据点集中任取一点A,查找距 图1 其始三角形的确定 收稿日期:2003 02 21;修订日期:2003 06 19 基金项目:国家自然科学基金项目(40371098)资助 作者简介:赖鸿斌(1978-),男,福建莆田人,硕士生,从事3S的应用研究.
基于不规则三角网构建的网格生长算法
基于基于不规则三角网不规则三角网不规则三角网构建构建构建的的网格生长算法 刘 刚，李永树李永树，，张水舰 (西南交通大学地理信息工程中心，成都 610031) 摘 要：提出一种基于离散点Delaunay 三角网快速构建的网格生长算法，采用分治算法将离散点表达为唯一网格，利用稀疏矩阵完成网格数据的压缩存储，通过标识码实现有值单元格与离散点之间的高效检索，从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间，并在三角网扩展时根据需要动态建立正方形搜索空间，从而保证网格生长的准确性。实验结果表明，该算法的时间复杂度为O (n log n )，对于少量或海量离散点均具有较好的适应性。 关键词关键词：：Delaunay 三角网；不规则三角网；离散点；正方形搜素空间；网格生长算法 Grid Growing Algorithm Based on Triangular Irregular Network Construction LIU Gang, LI Yong-shu, ZHANG Shui-jian (Geography Information Engineering Center, Southwest Jiaotong University, Chengdu 610031, China) 【Abstract 】This paper presents a grid growing algorithm for fast construction of Delaunay irregular network based on discrete point. In this algorithm, a grid is achieved to express discrete point uniquely based on the divide-and-conquer method, which is compressed storage in a sparse matrix, and an efficient retrieval method is established between value cell and discrete point by identification code, which is effectively to improve the efficiency of the construction of Triangular Irregular Network(TIN). According to the density of value cells, a default square search space is acquired, and it is allowed to create the square search space dynamically in the expansion process of TIN, which ensures the accuracy of the grid growing. Experimental results show that the time complexity of the proposed algorithm is O (n log n ), and the algorithm is available to both small and massive amount of discrete points. 【Key words 】Delaunay triangular network; Triangular Irregular Network(TIN); discrete point; square search space; grid growing algorithm DOI: 10.3969/j.issn.1000-3428.2011.12.019 计 算 机 工 程 Computer Engineering 第37卷 第12期 V ol.37 No.12 2011年6月 June 2011 ·软件技术与数据库软件技术与数据库·· 文章编号文章编号：：1000—3428(2011)12—0056—03 文献标识码文献标识码：：A 中图分类号中图分类号：：P209 1 概述 不规则三角网(Triangular Irregular Network, TIN)表面建模是一种很重要的表面建模方法[1-2]。在所有生成TIN 的方法中，Delaunay 三角网最优，它尽可能避免了病态三角形的出现，常被用来生成TIN 。 目前，利用离散点构建Delaunay 三角网的方法有很多，主要有逐点插入法、三角网生长法、分治算法等[1]。逐点插入算法是Lawson C L [3]提出的，之后Bowyer A [4]、Watson D F [5]等人对其进行发展。该算法的时间复杂度一般在3/2()O n ~ (log ) O n n [6-7] ，在处理过程中每插入一个点都要判断插入点 所在的三角形，随着数据点的不断插入，三角形的个数成倍增加，将花费大量的时间在三角形的定位上，从而直接影响算法效率。三角网生长法、分治法等算法的时间复杂度的下界为(log )O n n 。三角网生长法将大部分时间花费在搜索符合 要求的给定基线的邻域点过程中，分治算法由于递归执行，算法需要较大内存空间[8]，对海量数据而言，两者的效率都 较低。 为提高不规则三角网的构建效率，本文提出一种基于离 散点构建不规则三角网的网格生长算法，重点研究如何由离 散点生成规则网格，并在此基础上建立TIN 模型。 2 一种一种构建构建构建不规则三角网的不规则三角网的不规则三角网的网格网格网格生长算法生长算法 2.1 离散点离散点网格网格网格化化 网格由许多单元格组成，通常将单元格看成一个对象。从处理效率上看，单元格值的情况越少，单元格之间的计算 速度越快。所以，从计算效率出发，针对离散数据确定如下 规则网格构建准则：规则网格包含所有离散点，每个离散点对应一个单元格，且一个单元格内的离散点数量小于2。当单元格内存在一个离散点时表示该单元格有值(用1表示)，称为有值单元格，当不存在离散点时表示该单元格无值(即为Null)，称为空值单元格，并将按照该准则建立的规则网格称为唯一网格，其唯一性体现在离散点与有值单元格的一一对应关系。原理如图1所示，图1(a)表示一个单元格只包含 1个或0个离散点，图1(b)是对有值单元格进行赋值的结果(其中，黑色表示有值单元格即为1；其余无值即为Null)。 (a)离散点与网格关系 (b)网格化结果 图1 离散点离散点网格网格网格化化 基金项目 基金项目：：“十一五”国家科技支撑计划基金资助项目(2006BAJ05 A13) 作者简介作者简介：：刘 刚(1986－)，男，硕士，主研方向：复杂网络，GIS 原理及其应用；李永树，教授、博士生导师；张水舰，博士 收稿日期收稿日期：：2011-01-08 E-mail ：liugang233666@https://www.wendangku.net/doc/df9647085.html,
三角网坐标平差
三角网坐标平差 时间:2009-12-27 来源:本站作者:节选 §12.1三角网坐标平差 第十二章概述 间接平差又称参数平差。水平控制网按间接平差时，通常选取待定点的坐标平差值作为未知数(按方向平差时，还增加测站定向角未知数)，平差后直接求得各待定点的坐标平差值，故这种以待定点坐标作为未知数的间接平差法也称为坐标平差法。参加平差的量可以是网中的直接观测量，例如方向、边长等；也可以是直接观测量的函数，例如角度等。由于三角网的水平角一般是采用方向观测法观测，并由相邻方向相减而得，故它们是相关观测值。此时，若不顾及函数间的相关性，平差结果将受到一定的曲解。因此，坐标平差法都按方向平差。 间接平差的函数模型是误差方程，它是表达观测量与未知数之间关系的方程式。一般工程测量平面控制网的观测对象主要是方向(或角度)和相邻点间的距离(即边长)因此坐标平差时主要列立各观测方向及观测边长的误差方程式，再按照间接平差法的原理和步骤，由误差方程和观测值的权组成未知数法方程去解算待定点坐标平差值，并进行精度评定。 本章主要研究（测）方向网、测边网以及测边测角网的严密坐标平差。 水平控制网按坐标平差法进行平差时，为降低法方程的阶数以便于解算，定向角未知数可采用一定的法则予以消掉。由于误差方程式的组成简单且有规律，便于由程序实现全部计算，因此，在近代测量平差实践中，控制网按间接平差法得到了广泛的应用。平面控制网按坐标平差时，网中每一观测值都应列立一个误差方程式。 为便于计算，通常总是将观测值改正数表示为对应待定点坐标近似值改正数的线性式。坐标平差的第一步是列组误差方程式。对于方向网而言,参与平差的观测值是未定向的方向，选定的未知数是待定点的纵、横坐标值。误差方程式就是方向观测值改正数表达为待定点纵横坐标值的函数式，可以通过坐标方位角来建立方向值与未知数之间的联系。 12.1.1方向误差方程式的建立和组成 在测站k上观测了等方向 其方向观测值为
不规则三角网(TIN)生成的算法
第五章 不规则三角网（TIN）生成的算法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找 距离此点最近的点 2，相连后作为初始基线 1-2；
（2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个 Delaunay 三角形；
（3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
1
5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至找不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包 图 5.1.2 凸闭包的计算(引自 Tsai，1993)
一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建 三角网，具体算法如下：
2
实验四：不规则三角网
本科学生野外实验报告 学号姓名 学院旅游与地理科学学院专业、班级 实验课程名称地理信息系统实习教程 教师及职称 开课学期2012 至2013 学年下学期填报时间2013 年 5 月29 日 云南师范大学教务处编印
1、实验现象与结果 （1）视线分析，打开ex15.mxd,激活Data frame1，在General标签栏中，在Units框内，用下拉式菜单将Map和Display从Unknow Units改为Meters，完成后按“确定”关闭，选用菜单Tool/Extension，加载3D Analyst扩展模块，选用菜单View/Toolbars/3D Analyst，加载 3D Analyst工具条，点击产生视线按钮，出现Line of Sight对话框：
（2）基于视点的视域分析 ①产生单个观察点的视域栅格，选用3D/Options，作初始设置，初始设置完成后，选用菜单3D Analyst/Sueface Analysis/Viewshed…，出现Viewshed参数设置对话框，按ok键确定后，软件产生栅格状视域分析结果图层Visibilel。
②改变观察点的高程，视域分析中，需预先设定部分参数，其中有观察点的高度。在前面分析的视域分析中，没有作任何特别的设置，软件默认为观察点的高度比所在位置的三维面高一个地图单位，其观察点绝对高程为90m的视域： ③两次视域分析结果的比较，前一次不作任何设置，观察点高程仅仅是比对应的三维表面层
Analyst/Convert/Features to 3D，出现“Convert features to 3D”参数设置对话框进行设置，再Viewshed参数设置对话框进行设置，最后就能得到基于路径的视域分析结果图;
CASS软件三角网法计算土方量
CASS软件三角网法计算土方量 数字地面模型（DTM）可以解决一些工程实际的问题，该模型能用三维场景表示出地貌的起伏状态，可以按用户要求进一步生成坡度图、等高线图、断面图等；三角网是DTM模型中的一种，利用该模型可以较方便的计算出土方量，在工程上得到了广泛的应用。 标签：CASS软件；DTM；土方量计算 1 土方量计算概述 土方量的计算是工程费用概算及施工方案选取的重要依据，所以工程施工前的设计阶段必须对施工区域的土石方量进行计算。土石方量计算是以设计高程作为底面高程，以施工前该区域的实际地形高程作为顶面高程。土石方量的计算方法有等高线法，方格网法，断面法和三角网法等。在实际工作时，无论采用哪一种方法，都需要利用测量仪器获得大量的地形数据，其采样的间隔越小，其计算出的土方量越准确。在这几种土方量计算方法中，三角网法由于很好的拟合实际地貌的几何特征，并且能克服地形起伏不大的地区产生冗余数据的问题，其计算精度高于等高线法，方格网法，断面法精度。 2 三角网法土方量计算 2.1 建立三角网 数字高程模型（DEM）的格网间隔（数据点密度）与其同比例尺地形图高程精度相适配，并形成有规则的格网系统，根据不同的高程精度，可分为不同类型产品。为完整反映地表形态，可配套提供离散高程点数据。三角网是数字高程模型中的一种，是在一定区域内规则三角网点的三维坐标数据的集合，这个数据集合可以代表该区域地形地貌的起伏状态。利用CASS（数字地形地籍绘图软件）可以较为容易的生成三角网，其建立方法分为两种：一种是根据“坐标数据文件”生成，另一种是根据“图面高程点”生成。无论采用哪一种方法，都必须是依据坐标数据文件，必须采用如下格式：“点号，编码，Y坐标，X坐标，高程”才能在CASS软中将高程点展绘出来。需要注意的是编码一位可以是空缺的，但是“逗号”不能省略，此文件格式必须是五个“逗号”，并其需要注意横坐标在前，纵坐标在后。 因实际地貌的多样性和复杂性，自动构成的三角网模型与实际地貌会有一定偏差，如果出现了三角网与实际地形不符合的情况，可以采用如下方法进行局部的修改：（1）删除三角形：如果区域边界生成了多余的三角形，应把其删除；（2）增加三角形：如果边界区域某范围没有生产三角网，则应通过内插点生产三角形，否则没有三角形的范围不参与土方量的计算；（3）过滤三角形：如果某些三角行的某个角度过小，可以采用该方法，将这些三角行重新组合成三角形；（4）删三角形顶点：采用该方法可以将有公共点的三角形统一删除，这样该区域范围不参
论文1-测方向三角网函数模型与测角网函数模型解算结果的比较分析《科技视界》
测方向三角网函数模型与测角网函数模型解算结果的比较分析 王振 （山东省地质矿产勘查开发局第五地质大队，山东泰安，271000） 摘 要：在传统的三角网测量中，如果观测值是角度，可以分为测方向三角网和测角三角网。本文通过一个算例，分别以方向观测值和角度观测值为平差时的观测值，采用测方向三角网函数模型与测角网函数模型，进行了相应的平差计算，并对两种计算结果进行了比较分析。 关键词：测方向三角网，测角网，函数模型，间接平差 0 引言 如图所示，图1为测方向的三角网，图2为测角的三角网。A 、B 、C 为已知坐标的三个控制点，加密待定点D ，起算数据列于表1。以下分两种方式来解求待定点D 的坐标，并给出精度。 方式一：采用测方向三角网函数模型 如图1，在四个测站上同精度测得10个方向，观测值列于表2，以D 点坐标为平差参数，求D 点坐标的平差值。 方式二：采用测角网函数模型 如图2，同精度测得6个角度，观测值列于表3，以D 点坐标为平差参数，求D 点坐标的平差值。 表1 起算数据 表2 方向观测值 图1 方向观测控制网 图2 测角控制网
表3 角度观测值 在实际的测角工作中，初始的直接观测值是利用经纬仪或全站仪所测得的方向值。对于方式一，是以这些方向值为观测数据，进行三角网的平差；对于方式二，是以同一测站观测方向值做差而求得水平角，然后以这些水平角为观测数据，进行三角网的平差。 采用方式一，保留了原始数据的一些特征和信息；采用方式二，由于各方向值之间做差，从而消除了或减弱了初始直接观测值的一些信息，势必使得利用这两种方式所求的最终结果之间产生一些差别，从而对最终结果的精度产生影响。 本文通过对两种情况的解算，对计算结果进行了比较分析。 1 理论内容 1.1 测方向三角网函数模型 如图3所示为方向观测的示意图， 图3 方向观测 由于每一个测站有一个定向角，它们是方向坐标平差中的未知参数，设其平差值为j Z ?，则得误差方程 jk jk j jk L Z v -+-=α?? 1.2 测角网函数模型 如图4所示为测角示意图，
不规则三角网的建立与应用
作为空间数据基础设施中的“4D”产品之一和地理信息系统的核心数据库，数字高程模型（DEM）已在测绘、遥感、农林规划、城市规划、土木水利工程、地学分析等各个领域都有了广泛的应用。数字高程模型的表示方法主要有规则格网模型、不规则三角网模型和等高线模型三种，而不规则三角网(TIN)是数字高程模型中最基本和最重要的一种模型，它能以不同层次的分辨率来描述地形表面，并可以灵活的处理特殊地形。因此，围绕基于TIN 的DEM 的构建，本文主要论述了基于TIN 结构的数字高程模型建模原理和方法，离散点的Delaunay 三角网生成算法，建立有约束条件的约束三角网，最后分析了建立的TIN模型在土方计算方面的应用。 在本论文论述的过程中，针对传统算法进行了对比和分析后，在逐点插入法的基础之上，提出了一些新的细部改进的实现方法。局部优化操作和改进的算法实现使得对大容量离散点的三角网构建速度更快，效率更高；对限制条件的嵌入满足由此计算出来的土方量更接近实际期望值。本论文中主要的研究成果和内容如下：1）在离散点的Delaunay 三角网生成方面，本文中在插入点算法的基础上，建立凸包和矩形包容盒，建立虚拟网格，对原始离散点进行一级格网自适应分块，并建立索引关系。在定位点所在三角形时引入快速点定位算法，简易的空外接圆及圆内测试公式，通过这些改进使得Delaunay 三角网的剖分更加高效。 2）在约束Delaunay 三角网理论基础之上，结合上面散点域的剖分方法，对已有的两步算法基础上改进，完成约束Delaunay 三角网的构建。在其过程中应用矢量点积等数学工具改善了计算中的凹凸点判断，继续采用上章的快速索引和最速定位方法，并且对约束线相切等特殊情形进行了处理，进一步完善了算法的稳健性。 3）对于在约束三角网构造基础上的TIN 模型的应用，文中对其在土方量计算方面精度的优越性进行了分析，在可视化表达方面最后结合广东省东莞市某高尔夫球场工程给出了例证。 关键词：不规则三角网（TIN）;逐点插入法;土方计算
不规则三角网(TIN)生成的算法
第五章 不规则三角网（TIN）生成的算法
在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基 本的建模方法。三角网被视为最基本的一种网络，它既可适应规则分布数 据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网 络，也可根据三角网直接建立连续或光滑表面模型。在第四章中同时也介 绍了 Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳 为两大类：即静态三角网和动态三角网。由于增量式动态构网方法在形成 Delaunay 三角网的同时具有很高的计算效率而被普遍采用。本章主要介绍 静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法； 同时，还将给出考虑地形特征线和其他约束线段的插入算法。而其他非 Delaunay 三角网算法如辐射扫描法 Radial Sweep Algorigthm（Mirante & Weingarten, 1982）等本文将不再介绍。
5.1 三角网生长法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找
1
距离此点最近的点 2，相连后作为初始基线 1-2； （2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个
Delaunay 三角形； （3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先找到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至找不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包
2
浅析工程测量三角网坐标平差的测绘数据处理
浅析工程测量三角网坐标平差的测绘数据处理 【摘要】通过三角网坐标平差进行测量得到的结果精度较高，但是必须要科学处理相关数据。本文主要分析了三角测量平差数据处理，并探讨了三角网坐标平差的测绘数据处理的有效开展。 【关键词】三角网；坐标；平差；测绘；数据；处理 近些年，三角网测量在各国建立地面控制点中得到了广泛应用。三角网测量的一般平差是通过条件方程式来完成，而它的建立基础是布置三角网。测量平差是依据最小二乘准则，由观测到的测量数据求定未知量最佳估值及其精度，容易形成数据误差。所以，必须谨慎处理相关数据。 1.三角测量平差数据处理概述 三角测量中很多观测都是多余的，这就使得三角网以不同路线计算各点坐标存在了可能。因为观测有些误差难以避免，按照各种路线得出的计算结果往往有出入。要最大限度的避免多余观测之间的矛盾，并在所有观测结果中求出三角测量各元素的值，以及鉴定三角网观测值和平差元素的精度，应该根据最小二乘法原理来计算三角网的平差。 1.1数据处理流程 数据处理要遵循一定的原则：在空间网坐标/基线约束下，在WGS一84椭球面上进行地面网平差。一般工程测量三角网坐标平差的测绘数据处理按照下列的步骤流程进行： （1）突出合理的平差总体方案，建立平差的函数模型和随机模型。 （2）进行高精度GPS网数据处理。 （3）进行三角网点与高精度GPS网公共点（重合点）的分析，确定用于平差的重合点。 （4）分析基本星表、时号改正系统的变化所引起的天文观测量的改变，使用精度高而又简单方便的归算天文观测量的数学模型和数据处理方法。 （5）垂线偏差和高程异常确定：为满足地面观测数据归算要求，须重新计算相应于新的椭球面的垂线偏差。高程异常可采用我国最新计算的CQG似大地水准面进行内插求取。 （6）平差在地心坐标系下进行，三角网的数据必须归算到相应的椭球面上；涉及的内容包括三角网点归算元素ξ、η、ζ的计算以及观测边、方向值、方位角
三角网构造原理
VB环境下不规则三角网的算法设计与实现 江剑霞1，刘少华1,2， （1北京建筑工程学院，北京100044；2江西省数字国土重点实验室江西抚州344000；）摘要：本文对不规则三角网生长算法实现的研究，利用了VB强大的可视化用户界面及其编程语言的灵活性及简单易懂特点，基于各行业对于DEM的需要，从而开发出一种利用VB6.0语言生成基于生长算法的不规则三角网，结合数据库强大的数据库存取，编辑，查询功能，共同实现离散点的管理和三角网的构成。 关键词：不规则三角网；Delaunay三角网；VB环境；算法 Algorithm designing and realizing of TIN In VB JIANG Jian-xia1,LIU Shao-hua1,2 (1BeiJing Institute of Civil Engineering And Architecture,BeiJing,100044;2Digital Land Key Lab of JiangXi Province,Fuzhou344000) Abstract:the paper discuss the algorithm of the TIN which takes advantage of VB’s powerfully visible interface of user and flexibility and knowing easily of compiling procedure.On the basis of demanding for DEM for all professions,the author uses the VB language to develop a kind of TIN based on the growth-algorithm,in combination with the powerful function of the data base’s data accessed,edited and inquired about,achieving the management of the dispersed points and the construction of TIN Key words:TIN,Delaunay,VB,algorithm 1引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM（Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。 基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学 基金项目:湖北省高等学校优秀中青年团队计划项目资助(T200602);;江西省数字国土重点实验室开发研究基金资助 (DLLJ200501);;长江大学发展基金资助(2004Z0115)