不规则三角网的算法设计与实现

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三角形有三个相邻点连接而成，这三个相邻顶点对应的Voronoi多边形有一个公共的顶点，此顶点是Delaunay 三角形外接圆的圆心（如图1）。

根据构建三角网的步骤，可将三角网生成算法分为三类：（1）分而治之算法（由Shmaos

和Hoey提出），其基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用局部优化（LOP，即Local Optimization Procedure）算法保证其成为Delaunay三角网[3]，它的优点是时间效率高，但需要大量递归运算，因此占用内存空间较多，如果计算机没有足够的内存，这一方法就无法使用[2]；（2）数据点渐次插入算法（由Lawson提出），其思路很简单，先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法保证其成为Delaunay三角网[3]。此算法虽然容易实现，但效率极低；（3）三角网生长算法，在这三种算法中，三角网生长算法在80年代以后的文献中已很少见，较多的是前两种算法[3]，三角网生长算法目前较少人研究，笔者在这里讨论的就是这一算法，该算法是由Michael J.McCullagh,Charles G.Ross提出的，本文对原有的三角网生长算法作了进一步优化。

2.1 三角网生长算法步骤：（过程如图2）

（1）在所采集的离散点中任意找一点，然后查找距此点最近的点，连接后作为初始基线。

（2）在初始基线右侧运用Delaunay法则搜寻第三点，具体的做法是：在初始基线右侧的离散点中查找距此基线距离最短的点，做为第三点。

（3）生成Delaunay三角形，再以三角形的两条新边（从基线起始点到第三点以及第三点到基线终止点）作为新的基线。

（4）重复步骤（2），（3）直至所有的基线处理完毕。

也有人称此算法为“炸弹法”。

图1 delaunay三角形与Voronoi多边形偶图图2 三角网生长算法过程

2.1 在VB环境中的数据结构

为了对离散数据进行有效管理，作者在构建TIN时采用的数据结构为点结构，边（或线）结构，三角形（或面）结构。数据结构定义如下（图3是对应于图4的不规则三角网的表示方法[6]）：

(1)类模块

a.三角形数据结构

Triangle(Triangle.cls)

Public pnt1 As New POINT …三顶点

Public pnt2 As New POINT

Public pnt3 As New POINT

Public NO As Long …三角形编号

Public triNO1, triNO2, triNO3 As Long …三角形的相邻三角形号

Public EdgeNO1, EdgeNO2, EdgeNO3As Long …三角形的三条边号b.点的数据结构

Point(Point.cls)

Public x As Double

Public y As Double

Public z As Double

Public pntNO As Long …顶点编号

c.边的数据结构

Edge(Edge.cls)

Public eS As Point …边的起点

Public eE As Point …边的终点

Public LTriNO As Long …边的左三角形编号

Public RTriNO As Long …边的左三角形编号

(2) 模块

a. 三角形数组和点数组，三角形记数和点记数

Modulel(Modulel.bas)

Public triArray As New Collection …三角形集合

Public pntArray As New Collection …点的集合

Public edgeArray As New Collection …边的集合

Public nCount As Long …点个数

Public eCount As Long …边个数

Public triCount As Long …三角形个数

b. 存放窗体函数中的调用函数

mathCal(mathCal.bas)

Function TwoPntDistance(ByVal p1 As POINT, ByVal p2 As POINT) As Double …计算两点之间的距离

Function MinDistancePnt(ByVal p As POINT) As POINT …找与已知点最短距离的点

Fun ction MaxAnglePnt(ByVal e as Edge) As POINT …找距与已知的基线两端点组成夹角最大的点

图3 TIN的数据结构图 4 TIN的平面图形

3 VB环境中此算法思想以及实现过程

本文选用的方法是一种改进的生长算法,本算法和原始的生长算法比较,具有速度快等优点,主要是在Edge边数据结构中加入了边的使用次数,这样就没有必要对每个新生成的三角形的两条新边都向外扩展生长,有效地减少了扩展的边个数,从而提高了构网速度,本算法的详细如下。

(1) 在离散数据点集V中任取一点A ,以点A为基点寻找与它最近的一点B。连接AB ,就得到了三角形的一条基边,把该边作为扩展基边,转(2) 。

(2) 在扩展基边(是有向的)的右边点集中去找与该边两端点连成直线组成的夹角为最大的P

点,就组成了第一个三角形,将所有新生成的边与三角形信息用相应的链表进行存储起来,边

每使用一次,其数据结构中的UseTimes就加1,转(3) 。

(3) 在边链表中取出头位置的边,以该边为扩展基边向外进行扩展。如果该边的使用次数为2

或是右边没有点,该边不进行扩展;否则,转( 2)进行扩展,同时存储新生成的边和三角形。转(4)。

(4) 对边链表中下一位置的边进行扩展,实现过程同步骤(3) ,转(5)。

(5) 重复步骤( 4) ,直至边链表中的所有边都进行了扩展,就结束构网。

为了对算法的稳定性及可行性进行检验，笔者在VB中实现了上述算法，并用一些实验数据点验证了上述算法，图5是原始的数据点，图6是用该算法实现TIN。应用以上算法原理,基于Visual Basic 6.0 编译环境及数据库相结合,高效地实现了海量数据的Delaunay 三角网构建,实验表明,此算法的执行效率较高,对计算机硬件配置的要求较低。

图5 原始数据点图6 原始数据点生成TIN

4 数据的存储—数据库管理

由于我们构网所使用的点是我们事先所采样测量得到的点，且对于一个实际的项目应用来说，数据容量大，而如果是直接人为在窗体的坐标轴中输入数据的话，很难找准所给的采样点位置，因此就要将数据存储在数据库中，进行统一存储管理。本文中，作者是将数据库与VB连接起来，那么在VB中程序运行时可直接调用数据库中的数据。在现实的工程项目中，修路时要将某处的山地挖为平地，旅游园林公园等单位要在某些平坦的地方填方建造山林，采矿单位在地下挖方开采就形成了低洼或山体的峡谷等，形成了地形的复杂多变，那么就要在变化的区域进行点的重新测量采样，在构网时，有的地方要增加点，有的地方要删除点，有时我们还需要查询和编辑修改某个点的说明信息。那么这些都要依靠数据库的管理。

当然，也可以将数据存储在文本文件中进行读取，关于从文件中读取数据，相信大家在平时的学习中都有所接触，这里不再赘述。本文空间数据的操作包括图形的显示，放大，缩小，漫游，编辑，拓扑建立，查询和分析。

5 改进和提高

数据放在数据库（内存）里，再从内存中读取数据，这比直接从硬盘上读取数据快的多，但是，若数据量很大，Windows就要频繁地在内存和硬盘之间交换数据，反而影响速度，这种方法对硬件的依赖很大，并未从根本上解决问题[4,7]。为了提高构网速度，要采用格网索引，即在寻找第三点时，减少搜寻时间。同时对于生成的三角网的显示和缩放具有优势。在这里的改进方式有文件格网索引和数据库格网索引。对格网索引有兴趣的话可参阅[4,7]。

6．结束语

实现上述算法具有很强的现实意义。TIN的直接应用价值就是生成DEM，为DEM的生成在许多领域中打下基础。在土木工程中，如工程项目的填挖方计算，线路勘测设计，水利建设工程等的应用；TIN在GIS中得到了普遍使用，特别是在三维可视化方面受到格外关注，基于DEM的水文分析与GIS结合，DEM库，矢量库，影像库的三维一体化，DEM与数字地球等的应用。还有在摄影测量与遥感方面，气候分析和环境研究中的应用以及在地质和采矿工程，林业，地形学方面都有很强的应用。

本文对不规则三角网生长算法实现的研究，利用了VB6.0强大的可视化用户界面及其编程语言的灵活性及简单易懂特点，基于各行业对于DEM的需要，从而开发出一种利用VB语言生成基于生长算法的不规则三角网，结合数据库强大的数据库存取，编辑，查询功能，共同实现离散点的管理和三角网的构成。此算法思想的实现和数据的存储结构具有可行性，稳定性，高效性，相信这一研究会有很大的现实作用及意义。

不规则三角网的算法设计与实现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三角形有三个相邻点连接而成，这三个相邻顶点对应的

Delaunay三角形构网的分治扫描线算法

第36卷　第3期测　绘　学　报 Vol.36,No.3 　2007年8月 ACTA GEODAETICA et CARTO GRAPHICA SINICA Aug ,2007 文章编号:100121595(2007)0320358205中图分类号:P208 文献标识码:A Delaunay 三角形构网的分治扫描线算法 芮一康,王结臣 (南京大学地理信息科学系,江苏南京210093) A N e w Study of Compound Algorithm B ased on Sw eepline and Divide 2and 2conquer Algorithms for Constructing Delaunay T riangulation RU I Y i 2kang ,WAN G Jie 2chen (Depart ment of Geographic Inf ormation Science ,N anji ng U niversity ,N anji ng 210093,Chi na ) Abstract :As one of the most important DTM model ,Delaunay triangulation is widely applied in manifold fields.A wide variety of algorithms have been proposed to construct Delaunay triangulation ,such as divide 2and 2conquer ,in 2cremental insertion ,trangulation growth ,and so on.The compound algorithm is also researched to construct Delau 2nay triangulation ,and prevalently it is mainly based on divide 2and 2conquer and incremental insertion algorithms.This paper simply reviews and assesses sweepline and divide 2and 2conquer algorithms ,based on which a new com 2pound algorithm is provided after studying the sweepline algorithm seriously.To start with ,this new compound al 2gorithm divides a set of points into several grid tiles with different dividing methods by divide 2and 2conquer algo 2rithm ,and then constructs subnet in each grid tile by sweepline algorithm.Finally these subnets are recursively merged into a whole Delaunay triangulation with a simplified efficient LOP algorithm.For topological structure is im 2portant to temporal and spatial efficiency of this algorithm ,we only store data about vertex and triangle ,thus edge is impliedly expressed by two adjacent triangles.In order to fit two subnets merging better ,we optimize some data structure of sweepline algorithm.For instance ,frontline and baseline of triangulation are combined to one line ,and four pointers point to where maximum and minimum of x axis and y axis are in this outline.The test shows that this new compound algorithm has better efficiency ,stability and robustness than divide 2and 2conquer and sweepline algo 2rithms.Especially if we find the right dividing method reply to different circumstance ,its superiority is remarkable.K ey w ords :Delaunay triangulation ;compound algorithm ;sweepline algorithm ;divide 2and 2conquer algorithm 摘　要:Delaunay 三角网作为一种主要的DTM 表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay 三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。 收稿日期:2006206221;修回日期:2007202206 基金项目:国家自然科学基金(40401046) 作者简介:芮一康(19832),男,江苏溧阳人,研究生,主要从事地理信息系统理论与应用研究。 关键词:Delaunay 三角网;合成算法;扫描线算法;分治算法 1　引　言 2维平面域内任意离散点集的不规则三角网(TIN 2Triangular Irregular Network )的构建是GIS 数据表达、管理、集成和可视化的一项重要内 容,也是地学分析、计算机视觉、表面目标重构、有限元分析、道路CAD 等领域的一项重要的应用技 术。在所有生成TIN 的方法中,Delaunay 三角网 最优,它尽可能避免了病态三角形的出现,常常被用来生成TIN 。Delaunay 三角网是Voronoi 图的直线对偶图,即是连接所有相邻的Voronoi 多边形的生长中心所形成的三角网。它有以下两条重要性质[1]:空外接圆性质,即由点集所形成的三角网中,每个三角形的外接圆均不包含点集中的

不规则三角网(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 的最大允许大小视连续可用内存资源而定。对

一种基于TDOA与三角形加权质心定位的混合算法

邮局订阅号：82-946120元/年技术创新 软件时空 《PLC 技术应用200例》 您的论文得到两院院士关注 一种基于TDOA 与三角形加权质心定位的混合算法 A Hybrid Algorithm Based On TDOA And Triangle Weighted Centroid Localization (1.兰州大学;2.总参谋部通信训练基地) 傅涛 1,2 杨凌 1 李晓燕 1 闫胜武 1 FU Tao YANG Ling LI Xiao-yan YAN Sheng-wu 摘要:提出一种基于TDOA 与三角形加权质心定位的混合算法,该算法仅采用三个信标节点,充分利用节点的数据处理单元和通信单元,通过三角形加权质心定位算法得到一个定位信息,同时待定节点充分利用接收信号进行相关运算,求时差得到另一个定位信息。对两组定位信息比较、取均值,得到相对稳定的定位信息,实验证明该算法不仅减小了定位误差,提高了定位精度,而且解决了TDOA 的模糊定位问题。 关键词:TDOA;信标节点;三角形加权质心定位;混合定位 中图分类号:TP393 文献标识码:A Abstract:A hybrid algorithm based on TDOA and triangle weighted centroid localization was proposed.This algorithm only used three beacon nodes,make full use of the data processing unit and node communication unit,We can get a location information through the triangle weighted centroid localization algorithm,and at the same time,an Unknown node make full use of accept signal related calculation,for time to get another location information.For both groups positioning information comparison,Calculate average and get a relatively stable location information,the experiment shows that this algorithm not only improve location accuracy,reducing the positioning error,and solve the problem of the fuzzy TDOA localization. Key words:TDOA;Beacon nodes;Triangle weighted centroid localization;Hybrid localization 文章编号:1008-0570(2012)10-0395-02 1引言 在无线传感器网络(WSN)中,没有位置信息的监测消息是毫无意义的,因而节点定位技术成为无线传感器网络中的一项关键支撑技术。依据定位过程中是否需要测量实际节点间的距离,可将WSN 定位算法分为基于测距定位算法(Range-Based)和基于非测距定位算法(Range-Free)。前者包括:到达时间法 (TOA)、 到达时间差法(TDOA)、到达角度法(AOA)、信号强度法(RSSI)等。后者包括:质心算法、DV-HOP 算法、Amorphous 算法和APIT 算法等。事实上,每种定位算法都有其适用范围和局限性,因而本文提出一种基于TDOA 与三角形加权质心定位的混合算法。 2TDOA 双曲线定位算法 WSN 中传统的TDOA 测距技术是利用两种不同信号(一般是射频信号和超声波)到达同一节点所产生的时间差来确定节点间的距离,不仅增加了硬件成本和体积,而且应用规模受限,不符合本文要求,而移动通信系统中的TDOA 作为一种双曲线定位技术,可以很好的移植到WSN 当中,在不增加节点硬件成本的情况下完成节点定位功能。 2.1TDOA 定位算法原理如图1所示,假设A(x A ,y A )、B(x B ,y B )、C(x C ,y C )是三个信标节点,O(x,y)点是待定节点,T ij 表示信号从i 点到待定节点所用时间与信号从j 点到待定节点所用时间差,v 表示信号传播速度,d ij 表示待定节点到信标节点i 和j 点的距离差,解以下双曲线方程组即可得出未知节点的坐标,但此种方法存在模糊定位问题,可能存在双解两交点的情况,需要优化。 2.2TDOA 互相关方法数学模型 TDOA 算法关键在于得到两个信标节点到待定节点的时间差T 。直接计算TOA 需要节点达到严格同步,会大幅度增加节点的成本和能量消耗,实现起来困难,所以本文采用互相关技术求解时间差T,从而达到不增加节点硬件成本的效果。 如图1所示,当待定节点发起请求定位信号时,信标节点A 和B 发射的连续波信号为s(t),经传输后受到噪声干扰,待定节点O 接收到信号分别为x 1(t)、x 2(t): 由(2)式化简可得(3)式: 式中:T 是传输时延,T=d 1-d 2;A 为幅度比,A=A 1/A 2,则待定节点接收到信号的互相关函数为: 根据自相关函数的性质,,可以用互相关函数达到极大值来估计时延差T 。当取极大值时,τ就是我们需要测算的到达时间差T 的值,将T 代入公式,得解。 3基于RSSI 的定位算法 3.1基于RSSI 的三角形质心定位算法 傅涛:讲师硕士研究生 395--

三角网算法

三角网算法 (2010-11-15 10:54:01) 原作：Paul Bourke / 1989.1 翻译：robter_x 原文出处： https://www.docsj.com/doc/6d13491326.html,.au/~pbourke/terrain/triangulate/ 这是一个适用于地形模型的三角网算法。 摘要（略） 介绍 有很多技术能够应用于表面插值，也就是说，已知一些采样点高度，求与这些采样点接近的某点的高度。一些常用的方法是邻接插值，表面补丁，二次曲面，多边形插值，样条插值和下面将要描述的丹尼三角网（Delauney Triangulation）。一些插值方法经常应用于经验数据的显示，例如，地形模型中的原始数据来源于调查，气象中心的气象分析数据，或有限元分析筛选出的数据等。 这篇文章讨论的技术不仅适用于地形模型，而且适用于其它方面，这个技术具有下列特点 有一些地方的采样点密度高，而另一些地方的采样点密度低。例如，在地形模型中，一般水边界的内部的采样点呈低密度分布，而在一些较复杂的地方，采样点呈高密度分布。 由于地形表面的不连续，导致采样平面上的采样点较密集。这些可能是自然情况，如，悬岩和河岸，也可能是人工制造的不连续，如围墙。很多平滑方法不能很好的处理这种情况，特别是那些基于多边形的函数将导致表面尖突，摆动和不稳定。 采样点经常沿着等值线分布，这是由于采样点的来源可能是等值线图或者地质调查组的实际勘探。这是导致采样点密度不一致的另一个原因。沿着采样点曲线有较高的采样点密度，而与采样点曲线垂直的路径，除非遇到另一条采样点曲线，否则，没有采样点。 经常需有处理大量的采样点。对一个适用的技术来说，随着采样点数量的增加，处理采样所需的时间应该适度的增加。典型的采样点数量一般是100～100000，对于一个自动化的取样方法来说，通常会有这么大数量的采样点。 获得的采样点一般是逐步增多的。最初获得的采样点被分析，对于感兴趣的地方可能会增加采样密度。很显然，在分析结果上增加一些新的采样点来进一步分析比对所有的采样点重新分析要有利。

三角剖分

Delaunay三角剖分算法 默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅 转载：https://www.docsj.com/doc/6d13491326.html,/renliqq/archive/2008/02/06/1065399.html 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下： 1.1.三角剖分定义 【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。 1.2. Delaunay三角剖分的定义 在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起： 【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。 【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。 1.3.Delaunay三角剖分的准则 要满足Delaunay三角剖分的定义，必须符合两个重要的准则：

delaunay算法简介

三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。 然后有两个问题要解决：

1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路

第三章 不规则三角网

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

word版本hslogic_Delaunay三角剖分算法应用

本课题的研究方法 三角网格化主要有两种准则:一种称为Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。 Delaunay的重要性质 空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。λ 最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。λ唯一性：不论从区域何处开始构网，最终都将得到一致的结果。λ 由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。 3.3 详细算法描述 算法基于上述的传统构建算法，但仅有两步： 第一步： （1）在离散点集中寻找一纵坐标最小的点A。 （2）以点A为起点，寻找两个点B、D，使得向量AB与横坐标轴夹角最小，向量AD与横坐标轴夹角最大。若点A、B、D共线，将原B点标记为A，寻找点D，使得向量AD与直线AB夹角最大；寻找点C使得向量BC与线段AB夹角最小。否则，若A、B、D不共线，则寻找点C使得向量BC与线段AB夹角最小。这样，所有点都在逆时针旋转的折线DABC的左侧。 （3）上面一步生成的点C、D如果为同一点，则△ABC（或△ABD）即为包含所有不规则点的Delaunay三角形，生成凸包的过程结束跳过一下各步；否

delaunay算法简介.(优选.)

最新文件---- 仅供参考------已改成word文本------ 方便更改 三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。

然后有两个问题要解决： 1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”；

delaunay三角网生长准则及算法

Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形 ◆Delaunay 三角网的定义: 由一系列相连的但不重叠的三角形的集合, 而且这些 三角形的外接圆不包含这个面域的其他任何点。 ◆Voronoi图的定义： Voronoi图把平面分成N 个区，每一个区包括一个点， 该点所在的区域是距离该点最近的点的集合。 ◆Delaunay三角网的特性： ◆不存在四点共圆； ◆每个三角形对应于一个Voronoi图顶点； ◆每个三角形边对应于一个Voronoi图边； ◆每个结点对应于一个Voronoi图区域； ◆Delaunay图的边界是一个凸壳； ◆三角网中三角形的最小角最大。 空外接圆准则最大最小角准则最短距离和准则 在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成 的凸四边形中，这两三角形 中的最小内角一定大于交换 凸四边形对角线后所形成的 两三角形的最小内角 一点到基边的两端的距离 和为最小 Delaunay三角剖分的重要的准则

张角最大准则面积比准则对角线准则 一点到基边的张角为最大三角形内切圆面积与三角形 面积或三角形面积与周长平 方之比最小 两三角形组成的凸四边形 的两条对角线之比。这一 准则的比值限定值，须给 定，即当计算值超过限定 值才进行优化 Delaunay三角剖分的重要的准则 不规则三角网(TIN)的建立 ●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。 ●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。 方法说明方法实例 收缩生长算法先形成整个数据域的数据边界（凸壳）， 并以此作为源头，逐步缩小以形成整个三 角网 分割合并算法 逐点插入算法 扩张生长算法从一个三角形开始向外层层扩展，形成覆 盖整个区域的三角网 递归生长算法

平面点线集三角剖分的扫描算法

第24卷　第2期2004年2月北京理工大学学报 T r ansactions of Beijing Instit ute o f T echnolog y V ol.24　N o.2F eb.2004 文章编号:1001-0645(2004)02-0129-04 平面点线集三角剖分的扫描算法 周培德 (北京理工大学信息科学技术学院计算机科学工程系,北京　100081) 摘　要:提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O (N lb N ),其中N 是点线集中点的数目与线段端点数之和. 关键词:散乱点线集;三角剖分;平面扫描;算法;时间复杂性中图分类号:T P 301.6 文献标识码:A Sweeping Algorithm for Triangulation of Plane Point -Line Set ZHOU Pei-de (Depar tment of Co mputer Science and Engineer ing ,School o f Infor matio n Science and T echno lo gy ,Beijing Instit ut e of T echno lo gy ,Beijing 100081,China) Abstract :Sw eeping alg orithm is presented fo r the tr iangulation of plane point -line set .T he algor ithm m akes use of the idea of plane sw eeping .When the sw eep -line reaches it ,the event -po int w ill be dealt w ith,viz.,the event-point is connected w ith so me points sw ept and thus the sw ept regions are triang ulated.When the sw eep-line r eaches the leftmost event-point,the point w ill be dealt w ith ,and the triang ulation of the plane point -line set is accom plished .It is prov ed in detail that the time co mplex ities o f the alg orithm is O (N lb N ),w here N is the sum of the num ber of points and the num ber of line-seg ment endpoints w ithin the point-line set. Key words :debunching point-line set;triang ulation;plane sw eep;alg orithm;tim e co mplex ity 收稿日期:20030321 作者简介:周培德(1941-),男,教授. 平面点集三角剖分问题是计算几何中的一个重要问题,它是从许多实际问题中提出来的,至今,人们已研究了求解该问题的许多算法,其中以Delaunay 算法最为著名.将平面点集中的某些点组成点对并满足某些特殊关系,比如它们为平面线段的两个端点,而另外一些点仍为孤立点,这样便构成点线集.平面点集三角剖分问题可以转换为平面点线集的三角剖分问题,并且它们具有相同的时间复杂性下界.平面点线集三角剖分问题要求三角形的三条边或为点线集中的线段,或为点线集中不同线段端点的连线,或为点线集中点与线段端点的连线, 或为点线集中点与点的连线.三角形的顶点为点线集中的点或线段端点.另外还要求连线与连线,连线与点线集中线段均不相交.给定的平面点线集中线段互不相交(线段端点处相交除外).不难看出,平面散乱点线集三角剖分问题是平面点集三角剖分问题的一个特殊情况.按照常规,求解平面点集三角剖分的算法(比如Delaunay 三角剖分算法)可以用于平面散乱点线集的三角剖分.但在平面点集三角剖分的算法中如何保证点线集中的线段必是三角形的一条边,以及连线与点线集中线段不相交.只要解决这个问题就可以实现点线集的三角剖分.目前解决这

基于不规则三角网的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.docsj.com/doc/6d13491326.html,