基于不规则三角网的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的应用研究.

离此点最近的点B 作为三角形的第二个顶点,相连后以AB 的连线作为基线.然后再从附近的点中选取第三个顶点C .选取时主要有以下几种准则:

1)空圆准则[1]

:在TI N 中,过每个三角形的外接圆均不包含点集中的其余任何点(图2a).

2)最短距离和准则[3]

:在TI N 的每个三角形中,一点到基边两端的距离和最小(图2b).

3)最大最小角准则[1]

:在TIN 的两个相邻三角形形成的凸四边形中,这两个三角形中的最小内角一定大于交换凸四边形对角线后形成的两三角形的最小内角(图2c).

4)张角最大准则[3]

:在每个三角形中,第3点到两基边的张角为最大(图

2d).

图2 T IN 的三角化准则

当起始三角形构建后,以起始三角形的三边作为基边依次向外扩展,直至将点集内所有的离散点都构成三角网为止.

需要注意的是,虽然目前计算机的存储能力和计算速度在不断地提高和加快,但在搜索最佳点构建不规则三角网时,如果对所给的每个点都按某种准则进行搜索,就会减慢搜索的速度,从而影响构网的效率.对于小数据量,效果不明显;而对于大数据量进行构网则会显得非常耗时.因此,在构网时,我们应事先把数据点集按某种规律进行分块存储,这样可以大幅度地提高搜索的速度,从而减少构网的时间.具体方法如下:

在初次调入原始数据时,先计算出原始点集中X ,Y 的最大值和最小值:X max 、Y max 、X min 、Y min ,则所有的点均落在(X min 、Y min )、(X min 、Y max )、(X max 、Y min )、(X max 、Y max )4点构成的矩形区域内;然后将此矩形划分成适当数量的正方形格网;最后计算各点落入的网格并统计每一网格存储有哪些点,记录下来.当搜索第3点时,我们首先确定底边之中点P 所在的网格,搜索此网格内所有点,直到找到一个距P 最近的点.为了确保找到的点是最近的点,还需要补充此网格周围的8个网格.若在P 点所属网格内没有点,则需对该网格周围8个网格分别做与上面情况同样的处理.

2 特殊地貌和地物的处理

由于实际地貌、地物的复杂性,因此,在TI N 生成的过程中,还应考虑对特殊地貌和地物的处理,即将地形特征点作为模型的顶点,地形特征边和地物作为模型的限制边参与建模,使得所生成的不规则三角网的顶点包含地形特征点,边包含地形特征线和地物.把地性线、地物和断裂线等作为约束条件构

建不规则三角网,可有效消除TIN 中的 平三角形

和不合理的三角化现象,从而保证所生成DTM 的正

确性[2]

.

2.1地性线的处理

由于不规则三角网结构的DTM 是以三角形为基本单元表达实际地形,所以,山脊线、山谷线等地性线就不应该通过TIN 中的任一三角形的内部,否则三角形就会 进入 或 悬空 于地面,与实际地形不符,产生的数字地形模型有误[4]

.因此,在原始数据的采集过程中,必须用特征码记录地性线的编码信息.当构造TI N 时,应使地性线作为约束线段(强制线段)来处理,即作为三角网的一条边,以此作为基线向外扩展三角形(图3).这样,就保证了实际地形和DTM 相符,从而提高DTM 的精度.其处理的具体步骤如下:

a)调整前三角网 b)调整后三角网图3 含有地性线的不规则三角网

1)利用原始数据点集建立初级的不规则三角网;

2)在初级三角网中插入一约束线(地性线);3)确定边界与约束线段相交的三角形,如果两个这样的三角形有公共边,则将此公共边删除,最后形成带约束线段的影响多边形(影响区域);

4)将影响多边形其它顶点与约束线段的起始点相连;

5)应用带约束条件的局部最优方法(LOP Lo cal Optimization Procedure)交换凸四边形的对角线,以更新影响多边形内的三角形,使约束边成为三角网中的一边;

91第2期 赖鸿斌,等:基于不规则三角网的DTM 若干问题的探讨

6)重复上面4步,直至所有约束线段都加入到三角网中.

2.2地物的处理

由于房屋、河流、池塘等地物的内部标高基本上是一致的,所以,在建立DTM 时,应该将它们作为闭合区域来处理.具体的处理方法是:首先按处理地性线类似的方法调整三角网;然后,利用 射线法 或 垂线法 判定三角网中各三角形的重心是否落在该区域内.若是(即 射线 或 垂线 与地物边界的交点个数为奇数2n +1个),则消去该三角形;若不是(即 射线 或 垂线 与地物边界的交点个数为偶数2n 个),则保留该三角形.经测试后,除去所有重心落在地物区域内部的三角形,从而形成 空白区域 .最后,在扩展三角形时,应以地物的边线作为一条基边向外扩展.

3 不规则三角网与规则格网的混合模

型

TI N 模型的主要优点就是可以根据地形的起伏变化而改变采样点的密度,并决定采样点的位置.这样既能避免地形起伏不大地区产生冗余数据问题,从而节省存储空间,同时,TI N 还能根据地性线、地物等来生成符合实际地形情况的DTM.但是,正是

这些优点导致了其数据存储与操作的复杂性[1]

,不便于规范化管理.因此,在实际应用中,应将不规则三角网与规则格网结合起来形成混合模型,用来表示

DTM.

图4 TIN 和规则格网的混合模型

在混合表面建模中,大部分的软件是首先根据

系统格网采样建立初级的正方形和三角形,初级网构建后,如果数据中还包含地性线,则规则格网进一步分解成局部不规则三角网(图4).

4 TIN 数据结构

TI N 的数据存储方式比格网DTM 复杂,它不仅要存储每个点的高程,还要存储其平面坐标、节点连接的拓扑关系、三角形及邻接三角形等关系.

目前,国内外已有很多学者对TI N 拓扑结构的

存储方式作了深入的研究并给出了其数据的存储结构.表1是对应于图5的不规则三角网的一种表示方法,包括点数据结构、边数据结构和三角形数据结构,其各自的数据结构用C 语言定义如下:

表1 TIN 的数据结构

点边结点

点号坐标三角形相邻三角形三角形结点1x 1,y 1,z 1A B ,E A 1,2,62x 2,y 2,z 2B C ,A B 2,3,63x 3,y 3,z 3C F ,D ,B C 3,4,64x 4,y 4,z 4D H ,E ,C D 4,5,65x 5,y 5,z 5E D ,A E 5,6,16x 6,y 6,z 6F C ,G F 3,7,47x 7,y 7,z 7G F ,H G 7,8,48

x 8,y 8,z 8

H

D ,G

H

8,5,4

图5 TIN 的平面图形

点数据结构

Struct Point

{float x,y,z; 三维坐标}*Ppoint 边数据结构Struct Line

{int firstIndex,lastInde x ; 起点坐标int Tri1,Tri2; 左右三角形号}*Pline 三角形数据结构

Struct Triangle

{int iPoint1,iPoint2,iPoint3; 三角形三个点号int Tri1,Tri2,Tri3; 左右三角形号}*Ptriangle

5 实际应用

用不规则三角网生成的DTM 在工程中应用十分广泛,例如在铁路、公路的勘察和设计工作中,可利用DTM 生成等高线,绘制断面图、坡面图,以及立体透视图,并计算测区的面积、土方量等.下面实例就是利用野外测量的原始数据生成不规则三角网,从而绘制该测区的等高线.

表2是利用Leica 全站仪配合电子手簿在某高速公路测区采集的部分原始资料.由于受各种因素的影响,必须对所采集的原始数据进行一些适当的

92 重庆交通学院学报 第23卷

表2 某高速公路段采集数据

编号

X Y Z 1589 820567 88050 1002547 880551 08049 6003561 120551 08048 6004505 490574 69053 3005513 170561 73051 300 40553 027536 81744 19841539 855528 03142 52542528 879516 10141 96643500 000500 00050 000

(比例尺1 1000 等高距1m)图6 生成的不规则三角网和等高线

处理才能够满足实际应用的需要.当数据处理后进行构网时,应考虑对地性线、地物等的处理,最后,利用基于不规则三角网的DTM 生成等高线.在等高线的生成中,一般先追踪生成折线等高线,然后,以一定的拟合方式(例如张力样条拟合、三次B 样条拟合、SPLINE 拟合等)生成曲线等高线.图6是利用三次B 样条拟合方式生成比例尺为1 1000、等高距为1m 的测区等高线.

6 结束语

利用基于不规则三角网的D TM 生成等高线、断面图,以及计算土方填、挖量等,从根本上改变了传统的作业方式,大大提高工作效率.近几年来,随着计算机软件、硬件、网络及测绘手段的不断改进,DTM 必将具有越来越广泛的应用.参考文献:

[1] 李志林,朱 庆.数字高程模型[M].武汉:武汉大学出

版社,2000.[2] 杨德麟.数字高程模型[J].测绘通报,1998,(3):37 38.[3] 刘学军,符锌砂.三角网数字地面模型的理论、方法现

状及发展[J].长沙交通学院学报,2001,(2):24 30.[4] 谢祥根,符锌砂.考虑地形特征的三角网数模建立方法

[J].中国公路学报,2000,(1):10 13.

Discussion of several problems in DTM based on TIN

LAI Hong bin, LI Yong shu

(Department of Surveying Engineering,South west Jiaoton g Universi ty,Chengdu 610031,China)

Abstract :A method of estabisihing digital terrain models(DTM)with TIN is introduced,and problems during modeling are discussed in the paper.Furthermore,application problems about the hybrid model,as well as the data structure of TIN,are analyzed.In the end,the method of applying DTM based on TIN in engineering is illustrated.

Key words :TIN;DTM ;data structrue

责任编辑:袁本奎

93第2期 赖鸿斌,等:基于不规则三角网的DTM 若干问题的探讨

不规则三角网的算法设计与实现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、现场联机全站仪现场测量、记录、平差； 2、对已经有整理好的内业资料情况，提供数据导入功能，导入测量记录完成平差计算。 一、现场联机全站仪测量、记录、平差操作流程： 1、点击主界面导线平差，进入导线平差界面，点击底部按钮创建导线 2、输入导线的起终点闭合数据。起点后视点位起点测站的后视点，终点前视为终点测站的前视点。 3、添加测站，写入测站名称、后视名称、前视名称。 4、点击测站条目弹出测回列表对话框，点击添加测回按钮进入测量界面。 5、输入仪器高、前后视棱镜高。 6、连接全站仪后点击测量完成正镜后视、正镜前视、倒镜前视、倒镜后视测量，软件获取全站仪数据并记录（或者手工输入数据），点击确定按钮完成本测回测量。 7、逐个完成测站和对应的测回测量。 8、在导线测量界面点击右上角三个点导出测量记录和导线平差计算表。

二、导入已有的导线观测数据： 1、导入工地通路测导线观测文件 点击导线平差界面右上角三个点，点击导入工地通观测文件，弹出导入对话框，在手机存储目录中找到数据文件，点击完成导入。 2、导入附合导线进行平差计算并完成成果表

点击导线平差界面右上角三个点，点击附合导线平差计算按钮，弹出导入对话框，对话框中提示要导入的文件格式的内容，本文件在Excel编辑上按照要求编辑后，选择单元格右键复制，黏贴到一个TXT文件中，将这个TXT文件发送到手机上，在手机存储目录中找到数据文件，点击完成导入，软件同时完成附合导线简易平差计算，并生成计算表。 3、导入三角高程数据计算并完成成果表 点击导线平差界面右上角三个点，点击三角高程计算按钮，弹出导入对话框，对话框中提示要导入的文件格式的内容，本文件在Excel编辑上按照要求编辑后，选择单元格右键复制，黏贴到一个TXT文件中，将这个TXT文件发送到手机上，在手机存储目录中找到数据文件，点击完成导入，软件同时完成三角高程平差计算，并生成计算表。 4、导入支导线数据进行计算并完成成果表 点击导线平差界面右上角三个点，点击支导线计算按钮，弹出导入对话框，对话框中提示要导入的文件格式的内容，本文件在Excel编辑上按照要求编辑后，选择单元格右键复制，黏贴到一个TXT文件中，将这个TXT文件发送到手机上，在手机存储目录中找到数据文件，点击完成导入，软件同时完成支导线计算，并生成计算表。 说明： 1、当遇到闭合导线时，实际上闭合导线计算和附合导线计算原理是一致的，闭合点只需要 填写为原来的起算点。 2、遇到闭合三角高程时，只需要将附合点填写为闭合点。 3、观测时设置为水平角为左角，竖直角为天顶零。 ============================================== 工地通路测工作环境为android4.0以上智能手机和设备，主要用于公路、铁路、市政、地铁工程施工测量。包括路线坐标高程计算和放样，坐标里程反算，桥涵、路基挖填方及断面、隧道断面、隧道仰坡、锥坡测量，坐标里程批量正反算，面积测量、控制测量、指南针，利用GPS计算坐标、里程、偏距，地图导航，测量记录，通讯对讲，科学计算器、缓和曲线参数计算、角度单位转换、坐标正反算等功能；支持超高、加宽、路基边坡渐变、隧道断面渐变；软件可生成路线平面图、路基土石方断面图、隧道断面检测图。 软件可与各品牌全站仪、RTK通讯测量，包括徕卡、尼康、宾得、三鼎、索佳、南方、拓普康、中纬、天宝、科维、科力达、中翰、徕纳得等品牌，同时完成计算、绘图、记录，实现测量信息化。

边角三角网平差程序的设计书

边角三角网平差程序设计书 一、课程设计的目的 学生在学习完误差理论与测量平差基础、测量平差程序设计基础等课程的基础上，设计一个完整的测量数据处理程序，培养学生综合应用量数据处理与计算机应用能力，培养学生主动学习，创新设计能力。 二、课程设计的任务和内容 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 的最大允许大小视连续可用内存资源而定。对

三角网条件平差计算

§3-4 三角网条件平差计算 2学时 三角网测量的目的，是通过观测三角形的各角度或边长，计算三角网中各未知点的坐标、边的长度及方位角等。三角网按条件平差计算时，首要的问题是列出条件方程。因此了解三角网的构成，总结其条件方程的种类及各种条件方程的组成规律是十分重要的。 三角网的种类比较多，网的布设形式也比较复杂。根据观测内容的不同，有测角网、测边网、边角同测网等；根据网中起始数据的多少，有自由三角网和非自由三角网。自由三角网是指仅具有必要起算数据的三角网，网中没有多余的已知数据。如果测角三角网中，只有两个已知点（或者已知一个已知点的坐标、一条已知边的长度和一个已知的方位角），根据数学理论，以这两个已知点为起算数据，再结合必要的角度测量值，就能够解算出网中所有未知点的坐标。如果三角网中除了必要的起算数据外还有其它的已知数据，或者说已知数据有冗余，就会增加对网形的约束，从而增强其可靠性，这种三角网称之为非自由三角网。无论多么复杂的三角网，都是由单三角形、大地四边形和中点多边形组合而成的。 在本节，我们先讨论三角网条件平差中条件方程个数的确定问题，然后主要讨论测角三角网的条件方程的形式问题。 一、网中条件方程的个数 三角网平差的目的，是要确定三角点在平面坐标系中的坐标最或然值。如图3-9所示，根据前面学到的测量基础知识，我们知道，必须事先知道三角网中的四个数据，如两个三角点的4个坐标值，或者一个三角点的2个坐标值、一条边的长度和一个方位角，这4个已知数据我们称之为三角网的必要起算数据。有了必要起算数据，就可以确定三角网在平面坐标系中的位置、网的大小及其方位，就可以计算三角网中未知点的坐标。 要对三角网进行平差计算，还必须先知道网中的总观测数n、判定必要观测数t，从而确定了多余观测数： r = n - t 由条件平差原理知，多余观测数与条件方程数是相等的，有了多余观测数，也就确定出了条件方程的个数。因此，问题的关键是判定必要观测数t。

导线平差计算

导线平差计算 1 简介 闭合导线和附合导线是长输管道站场和穿跨越测量常用的控制手段，其优点是可以同时完成平面和高程控制测量。导线平差原理请查阅相关文献。不同平差软件的平差方法步骤基本相同，本文件基于南方平差易软件平台介绍导线（闭合导线、附合导线是最简单的导线控制网）平差的操作方法。 2 规范性引用文件 下列文件中的条款通过本标准的引用而成为本标准的条款。 《长距离输油输气管道测量规范》（SY/T 0055-2003） 《工程测量规范》（GB 50026-2007） 3 操作步骤 （1）录入数据 录入数据是将导线测量数据录入平差软件。可以采用手工或文件方式录入（建议采用后者，选菜单“文件/打开”）。其数据格式如下： [NET] 控制网信息 [PARA] 控制网参数 [STATION]坐标和高程信息（11表示高程已知，如果无坐标则无法在平差易中看到和输出地图）[OBSER] 观测的转角、平距、高差等信息 下图为导入数据窗口： 图3-1 导入数据窗口 （2）坐标推算（F3）

选菜单“平差/推算坐标”，根据已知条件（测站点信息和观测信息）推算出待测点的近似坐标。为构建动态网图和导线平差作基础。 （3）概算 选菜单“平差/选择概算”→配置概算参数→输出概算结果。下图为“选择概算”的配置参数窗口： 图3-2 配置概算参数 （4）调整观测数据 将概算结果调整到输入的观测数据中，重新导入。 （5）计算方案的选择 对于同时包含了平面数据和高程数据的导线, 一般处理过程应为：先进行平面处理, 然后在高程处理时软件会使用已经较为准确的平面数据（如距离等）来处理高程数据。对精度要求很高的平面高程混合平差，您也可以在平面和高程处理间多次切换，迭代出精确的结果（但建议平面和高程分开了平差）。 针对导线平差，需要设置中误差及仪器参数、高程平差参数、限差及等级内容。 选菜单“平差/平差方案”即可进行参数的设置，如下图：

第三章 不规则三角网

第三章不规则三角网 教学目的与要求 通过本章的学习，让大家了解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 操作步骤：

三角高程测量

§4-6 三角高程测量 一、三角高程测量原理及公式 在山区或地形起伏较大的地区测定地面点高程时，采用水准测量进行高程测量一般难以进行，故实际工作中常采用三角高程测量的方法施测。 传统的经纬仪三角高程测量的原理如图4－12所示，设A点高程及AB两点间的距离已知，求B点高程。方法是，先在A点架设经纬仪，量取仪器高i；在B点竖立觇标（标杆）， 并量取觇标高L，用经纬仪横丝瞄准其顶端，测定竖直角δ，则AB两点间的高差计算公式为： 故（4-11） 式中为A、B两点间的水平距离。 图4-12 三角高程测量原理 当A、B两点距离大于300m时，应考虑地球曲率和大气折光对高差的影响，所加的改正 数简称为两差改正： 设c为地球曲率改正，R为地球半径，则c的近似计算公式为： 设g为大气折光改正，则g的近似计算公式为： 因此两差改正为：，恒为正值。 采用光电三角高程测量方式，要比传统的三角高程测量精度高，因此目前生产中的三角高程测量多采用光电法。

采用光电测距仪测定两点的斜距S，则B点的高程计算公式为： （4-12) 为了消除一些外界误差对三角高程测量的影响，通常在两点间进行对向观测，即测定hAB 和hBA，最后取其平均值，由于hAB和hBA反号，因此可以抵销。 实际工作中，光电三角高程测量视距长度不应超过1km，垂直角不得超过15°。理论分析和实验结果都已证实，在地面坡度不超过8度，距离在1.5km以内，采取一定的措施，电磁波测距三角高程可以替代三、四等水准测量。当已知地面两点间的水平距离或采用光电三角高程测量方法时，垂直角的观测精度是影响三角高程测量的精度主要因素。 二、光电三角高程测量方法 光电三角高程测量需要依据规范要求进行，如《公路勘测规范》中光电三角高程测量具体要求见表4-6。 表4-6 光电三角高程测量技术要求 往返各 注：表4-6中为光电测距边长度。 对于单点的光电高程测量，为了提高观测精度和可靠性，一般在两个以上的已知高程点上设站对待测点进行观测，最后取高程的平均值作为所求点的高程。这种方法测量上称为独立交会光电高程测量。 光电三角高程测量也可采用路线测量方式，其布设形式同水准测量路线完全一样。 1．垂直角观测 垂直角观测应选择有利的观测时间进行，在日出后和日落前两小时内不宜观测。晴天观测时应给仪器打伞遮阳。垂直角观测方法有中丝法和三丝法。其中丝观测法记录和计算见表4-7。表4-7 中丝法垂直角观测表 点名泰山等级四等 天气晴观测吴明 成像清晰稳定仪器Laica 702 全站仪记录李平 仪器至标石面高1.553m 1.554 平均值1.554m 日期2006.3.1

三角高程测量误差分析报告(精)

三角高程测量 1 三角高程测量的基本原理 三角高程测量是通过观测两点间的水平距离和天顶距（或高度角）求定两点间的高差的方法。它观测方法简单，不受地形条件限制，是测定大地控制点高程的基本方法。目前，由于水准测量方法的发展，它已经退居次要位置，但在山区和丘陵地带依然被广泛采用。 在三角高程测量中，我们需要使用全站仪或者经纬仪测量出两点之间的距离(水平距离或者斜距和高度角，以及测量时的仪器高和棱镜高，然后根据三角高程测量的公式推算出待测点的高程。三角高程测量 由图中各个观测量的表示方法，AB两点间高差的公式为： H=S0tanα+i1-i2① 但是，在实际的三角高程测量中，地球曲率、大气折光等因素对测量结果精度的影响非常大，必须纳入考虑分析的范围。因而，出现了各种不同的三角高程测量方法，主要分为：单向观测法，对向观测法，以及中间观测法。 1.1 单向观测法 单向观测法是最基本最简单的三角高程测量方法，它直接在已知点对待测点进行观测，然后在①式的基础上加上大气折光和地球曲率的改正，就得到待测点的高程。这种方法操作简单，但是大气折光和地球曲率的改正不便计算，因而精度相对较低。 1.2 对向观测法 对向观测法是目前使用比较多的一种方法。对向观测法同样要在A点设站进行观测，不同的是在此同时，还在B点设站，在A架设棱镜进行对向观测。从而 就可以得到两个观测量：直觇：

h AB= S往tanα往+i往-v往+c往+r往② 反觇： h BA= S返tanα返+i返-v返+c返+r返③ S——A、B间的水平距离； α——观测时的高度角； i——仪器高； v——棱镜高； c——地球曲率改正； r——大气折光改正。 然后对两次观测所得高差的结果取平均值，就可以得到A、B两点之间的高差值。由于是在同时进行的对向观测，而观测时的路径也是一样的，因而，可以认为在观测过程中，地球曲率和大气折光对往返两次观测的影响相同。所以在对向观测法中可以将它们消除掉。 h=0.5(hAB- hBA =0.5[( S往tanα往+i往-v往+c往+r往-( S返tanα返+i返-v返+c返+r返] =0.5(S 往tanα往-S返tanα返+i往-i返+v返-v往④ 与单向观测法相比，对向观测法不用考虑地球曲率和大气折光的影响，具有明显的优势，而且所测得的高差也比单向观测法精确。 1.3 中间观测法 中间观测法是模拟水准测量而来的一种方法，它像水准测量一样，在两个待测点之间架设仪器，分别照准待测点上的棱镜，再根据三角高程测量的基本原理，类似于水准测量进行两待测点之间的高差计算。此种方法要求将全站仪尽量架设在两个待测点的中间位置，使前后视距大致相等，在偶数站上施测控制点，从而有效地消除大气折光误差和前后棱镜不等高的零点差，这样就可以像水准测量一样将地球曲率的影响降到最低。而且这种方法可以不需要测量仪器高，这样在观测时可以相对简单些，而且减少了一个误差的来源，提高观测的精度。全站仪中间观测法三角高程测量可代替三、四等水准测量。在测量过程中，应选择硬地面作转点，用对中脚架支撑对中杆棱镜，棱镜上安装觇牌，保持两棱镜等高，并轮流作为前镜和后镜，同时将测段设成偶数站，以消除两棱镜不等高而产生的残余误差影响。

三角网坐标平差

三角网坐标平差 时间:2009-12-27 来源:本站作者:节选 §12.1三角网坐标平差 第十二章概述 间接平差又称参数平差。水平控制网按间接平差时，通常选取待定点的坐标平差值作为未知数(按方向平差时，还增加测站定向角未知数)，平差后直接求得各待定点的坐标平差值，故这种以待定点坐标作为未知数的间接平差法也称为坐标平差法。参加平差的量可以是网中的直接观测量，例如方向、边长等；也可以是直接观测量的函数，例如角度等。由于三角网的水平角一般是采用方向观测法观测，并由相邻方向相减而得，故它们是相关观测值。此时，若不顾及函数间的相关性，平差结果将受到一定的曲解。因此，坐标平差法都按方向平差。 间接平差的函数模型是误差方程，它是表达观测量与未知数之间关系的方程式。一般工程测量平面控制网的观测对象主要是方向(或角度)和相邻点间的距离(即边长)因此坐标平差时主要列立各观测方向及观测边长的误差方程式，再按照间接平差法的原理和步骤，由误差方程和观测值的权组成未知数法方程去解算待定点坐标平差值，并进行精度评定。 本章主要研究（测）方向网、测边网以及测边测角网的严密坐标平差。 水平控制网按坐标平差法进行平差时，为降低法方程的阶数以便于解算，定向角未知数可采用一定的法则予以消掉。由于误差方程式的组成简单且有规律，便于由程序实现全部计算，因此，在近代测量平差实践中，控制网按间接平差法得到了广泛的应用。平面控制网按坐标平差时，网中每一观测值都应列立一个误差方程式。 为便于计算，通常总是将观测值改正数表示为对应待定点坐标近似值改正数的线性式。坐标平差的第一步是列组误差方程式。对于方向网而言,参与平差的观测值是未定向的方向，选定的未知数是待定点的纵、横坐标值。误差方程式就是方向观测值改正数表达为待定点纵横坐标值的函数式，可以通过坐标方位角来建立方向值与未知数之间的联系。 12.1.1方向误差方程式的建立和组成 在测站k上观测了等方向 其方向观测值为

测量平差 条件方程t的判定知识分享

测量平差条件方程t的判定

§3-4 三角网条件平差计算 2学时 三角网测量的目的，是通过观测三角形的各角度或边长，计算三角网中各未知点的坐标、边的长度及方位角等。三角网按条件平差计算时，首要的问题是列出条件方程。因此了解三角网的构成，总结其条件方程的种类及各种条件方程的组成规律是十分重要的。 三角网的种类比较多，网的布设形式也比较复杂。根据观测内容的不同，有测角网、测边网、边角同测网等；根据网中起始数据的多少，有自由三角网和非自由三角网。自由三角网是指仅具有必要起算数据的三角网，网中没有多余的已知数据。如果测角三角网中，只有两个已知点（或者已知一个已知点的坐标、一条已知边的长度和一个已知的方位角），根据数学理论，以这两个已知点为起算数据，再结合必要的角度测量值，就能够解算出网中所有未知点的坐标。如果三角网中除了必要的起算数据外还有其它的已知数据，或者说已知数据有冗余，就会增加对网形的约束，从而增强其可靠性，这种三角网称之为非自由三角网。无论多么复杂的三角网，都是由单三角形、大地四边形和中点多边形组合而成的。 在本节，我们先讨论三角网条件平差中条件方程个数的确定问题，然后主要讨论测角三角网的条件方程的形式问题。 一、网中条件方程的个数

三角网平差的目的，是要确定三角点在平面坐标系中的坐标最或然值。如 图3-9所示，根据前面学到的测量基础知识，我们知道，必须事先知道三角网 中的四个数据，如两个三角点的4个坐标值，或者一个三角点的2个坐标值、 一条边的长度和一个方位角，这4个已知数据我们称之为三角网的必要起算数据。有了必要起算数据，就可以确定三角网在平面坐标系中的位置、网的大小 及其方位，就可以计算三角网中未知点的坐标。 要对三角网进行平差计算，还必须先知道网中的总观测数n、判定必要观 测数t，从而确定了多余观测数： r = n - t 由条件平差原理知，多余观测数与条件方程数是相等的，有了多余观测 数，也就确定出了条件方程的个数。因此，问题的关键是判定必要观测数t。 1.网中有2个或2个以上已知点的情况 三角网中有2个或2 个以上已知三角点，就一定具备了4个必要起算数 据。无论是测角网、测边网还是边角同测网，如果有2个已知点相邻，要确定 一个未知点的坐标，需要观测两个观测值（2个角，或者1条边和1个角，或者2条边）。也就是说，确定1个未知点要有2个必要观测值；那么如果网中有p 个未知点，必要观测数应等于未知点个数的两倍。 t = 2 ·p(3-4-1) (1) 测角网 图3-9所示，三角网中有2个已知点，待定点个数为p = 6。如果三角网中观测量全部是角度时。 总观测值个数：n = 23 必要观测数：t = 2 · p =12

基于不规则三角网的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的应用研究.

三角高程网高程平差结果

三角高程网高程平差结果 -------------------------------------------------------------------- APPROXIMATE HEIGHT -------------------------------------------------------------------- No. Name Height(m) -------------------------------------------------------------------- 1 S0 219.959200 2 N2 212.532800 3 N1 157.143292 4 S246 181.979042 5 N0 207.851742 6 S2 242.626692 7 N3 151.135300 -------------------------------------------------------------------- KNOWN HEIGHT -------------------------------------------------------------------- No. Name Height(m) -------------------------------------------------------------------- 1 S0 219.95920 2 N2 212.53280 -------------------------------------------------------------------- MEASURING DATA OF HEIGHT DIFFERENCE -------------------------------------------------------------------- No. From To Observe(m) Distance(km) Weight -------------------------------------------------------------------- 1 N1 S246 24.84150 0.6120 1.634 2 N1 S0 62.81591 0.8580 1.166 3 N1 N0 50.70845 0.5250 1.905 4 N0 S2 34.7749 5 0.6900 1.449 5 N0 N2 4.67680 0.1830 5.464 7 N0 S246 -25.87270 0.8380 1.193 8 N0 S0 12.09575 0.7320 1.366 9 N2 S0 7.42785 0.7420 1.348 10 N2 S2 30.10300 0.6560 1.524 11 N2 N3 -61.39750 0.3340 2.994 13 S2 N3 -91.50100 0.5710 1.751 16 S2 S0 -22.67050 0.1810 5.525 20 S0 S246 -37.96760 0.5190 1.927 -------------------------------------------------------------------- ADJUSTED HEIGHT -------------------------------------------------------------------- No. Name Height(m) Mh(mm) -------------------------------------------------------------------- 1 S0 219.959200

基于不规则三角网构建的网格生长算法

基于基于不规则三角网不规则三角网不规则三角网构建构建构建的的网格生长算法 刘 刚，李永树李永树，，张水舰 (西南交通大学地理信息工程中心，成都 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.sodocs.net/doc/513237427.html,