Delaunay三角网构建DEM整体优化算法

格式：pdf
大小：393.10 KB
文档页数：5

下载文档原格式

/ 5

Delaunay三角网生成算法的研究与实现(1).

Delaunay三角网生成算法的研究与实现(1)摘要 Delaunay三角网作为一种主要的数字地形模型表示法，经过二十多年来的研究，它的生成算法已趋于成熟。

本文在简单回顾和评价了分割—归并法、逐点插入法、三角网生长法等三类主流算法的基础上，介绍并实现了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。

关键字数字地层模型；三棱柱； Delaunay；三角网；生成算法0 引言计算机图形学是利用计算机研究图形的表示、生成、处理、显示的学科。

经过30多年的发展，科学可视化已成为计算机图形学中最活跃的分支之一，并得到了广泛的应用。

在地质领域,由于大量珍贵的地层钻探数据需要用有效的方式进行直观地表达，因而致使可视化技术成为地质研究和工程勘查领域必不可少的手段。

在建模中，2.5维的分析处理由DTM(数字地形模型)模型进行。

DTM主要由栅格与TIN（不规则三角网）两种数据格式来表示[1，2]，而以后者更为重要。

TIN的生成算法中，最终有三种为普遍接受和采用，它们是分割—归并法、逐点插人法和逐步生长法。

本文在简要分析了上述算法所有缺点的基础上，实现了一种合成算法。

1 Delaunay三角网生成算法回顾Tsaj根据实现过程，把生成Delaunay三角网的各种算法分为三类：分治算法；逐点插入法；三角网生长法。

Tsai为比较算法性能，给出了一张各种算法的时间复杂度对照表，如表1所示。

表中，N为数据点数。

0(f(N))表示算法的时间复杂度，它以算法中频度最大的语句频度f(N)来度量。

上述三类算法中，三角网生长法在80年代中期以后就很少用到，较常见的是分治算法和逐点插入法，而这两类算法又各有其长处和短处。

逐点插入法虽然实现过程相对简单，所需内存较小，但它的时间复杂度高。

所以从时间复杂度方面看，分治算法最好。

但由于算法中存在递归，它需要较大内存空间。

在普通的计算机平台上，运行速度慢和占用较大内存都是应该尽量避免的。

本次设计中，我们引入并实现了一种合成算法，将逐点插入法植入到了分治算法中，互相取长补短，从而达到了较好的时空性能，也很好地体现了两者的优势。

水深三角网的快速构建及优化算法_张立华

２００６年２月第２期总第３８５期
水运工程Ｐｏｒｔ＆ＷａｔｅｒｗａｙＥｎｇｉｎｅｅｒｉｎｇ
Ｆｅｂ．２００６Ｎｏ．２ＳｅｒｉａｌＮｏ．３８５
水深三角网的快速构建及优化算法＊
张立华１，２，殷晓冬１，吴理达１
（１．海军大连舰艇学院海洋测绘系，辽宁大连１１６０１８；２．武汉大学测绘遥感信息工程国家重点实验室，湖北武汉４３００７９）
（ａ）
（ｂ）
图４优化算法中的三角形重组
（ａ）
（ｂ）
优化算法的基本实现过程如图４：１）扫描所有三角形，如果三角形Ｔｉ的任意２个顶点和三角形Ｔｊ的２个顶点相同，则三角形Ｔｉ与三角形Ｔｊ相邻（ｉ≠ｊ，ｉ，ｊ为多边形的序号）。不妨假设Ｔ·ｉ ν１＝Ｔ·ｊ ν２，Ｔ·ｉ ν２＝Ｔ·ｊ ν１，其余情况依此类推。
摘要：Ｄｅｌａｕｎａｙ三角网目前被广泛用于等深线绘制，但存在将浅水区划入深水区的可能性，形成不合理的海底地形走
势，从而对舰船航行安全构成危险。讨论了快速构建水深三角网的基本策略，如网格划分、逐点插入法、Ｄｅｌａｕｎａｙ子三角网
的合并，提出了浅点相割算法。此算法通过比较相邻三角形顶点水深，对Ｄｅｌａｕｎａｙ三角网进行局部优化，构建合理的、符
Ｄｅｌａｕｎａｙ网是目前构建三角网是最为常见的形式。随着水深数据量的不断增加，需要快速构建合理的水深三角网，本文从网格划分、逐点插入法、Ｄｅｌａｕｎａｙ子三角网间的合并等方面进行了相应的分析。为了使等深线真正用于保证舰船航行安全，本文提出的浅点相割算法，改进了水深Ｄｅｌａｕｎａｙ三角网的构建，可以避免不合理的等深线出现。文中算法通过实际检验，是切实可行的。
Ａｂｓｔｒａｃｔ：ＮｏｗａｄａｙｓＤｅｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎｉｓｅｘｔｅｎｓｉｖｅｌｙｕｓｅｄｔｏｄｒａｗｄｅｐｔｈｃｏｎｔｏｕｒｓ，ｔｈｅｗｅａｋｐｏｉｎｔｏｆ

基于等高线的delaunay缝合算法分析与实现

II
To sum up, the research showed that the method presented in the thesis combined the advantages of
the Incremental Insertion Algorithm and Divide-and-conquer Algorithm. The method is easy to understand and its time complexity is close to linear. In conclusion, it’s a really practical algorithm.
Firstly，the experimental data was obtained through DXF-file. The 3D data on the contour lines was read and homogenized. Then the block-number was selected or input by the dialog interface. And the blocked data was stored in txt files block by block. Secondly, Delaunay Triangulation Networks were built according to the blocks, and the flat triangles of every network were converted after that. Thirdly, by searching and accessing the suturing edges, the suturing points were clockwise stored and divided into four parts according to four directions like top, right, bottom and left. In addition, the up and down blocks were sutured in the horizontal direction, after which the left and right blocks were sutured in the vertical direction. Finally, by optimizing the sutured triangulation network with the Local Optimal Procedure (LOP) algorithm, and converting the flat triangles, the Delaunay Triangulation model was established at last.

Delaunay三角网建立的改进算法

的时间复杂度差，但运行速度
０引言
２维任意域内点集的Ｄｌｎｙｉ角剖分具有最小ｅｕａａ角最大的良好性质，被公认为最优的三角剖分，科学在
比较慢。本文深入研究了算法的实现步骤，对其中的关键环节加以优化和改进，高了算法的执行效率，提使算
中图分类号：２ｌＰ２
文献标识码：Ｂ
文章编号：６２— ８７２０）ｌ０３ — ４１７５６（０７０一０８０
ＡｎＩｐｒｖｄＡｌｏｉｈｏｅｔｏｆＤｅａｎｙＴｒａｇｌｔｏｍｏｅｇｒｔｍｆｒＣｒａｉｎｏｌｕａｉｎｕａｉｎ
维普资讯
第３０卷第１期
２０年２月０７
测绘与空间地理信息
ＧＥＯＭＡＴＣＳ＆ＳＰＡＴＡＬｌｏＲＭＡｏＮＥＣＨＮＯＬＧＹＩＩＮＦＴｌＴＯ
Ｖｏ．０，．１１３Ｎｏ
Ｆｂ，２０ｅ．０７
响算法效率的关键环节，并采用数据点集分块管理、三角形快速定位、变点插入顺序等方法进行了算法优化，改
对三角形快速定位方法进行了改进。测试实验的结果说明，法改进后Ｄｌｎｙ算ｅｕａ三角网建立的效率提高了４～ａ６
倍。
关键词：ｅｕａ三角网：点插入法：角形快速定位Ｄｌｎｙａ逐三
１求出点集中）Ｙ和 — Ｙ的最大值和最小值，并
将对应的４点按逆时针方向组成一个链表，成初始个构

delaunay三角网生长准则及算法

Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形◆Delaunay 三角网的定义:由一系列相连的但不重叠的三角形的集合, 而且这些三角形的外接圆不包含这个面域的其他任何点。

◆Voronoi图的定义：Voronoi图把平面分成N 个区，每一个区包括一个点，该点所在的区域是距离该点最近的点的集合。

◆Delaunay三角网的特性：◆不存在四点共圆；◆每个三角形对应于一个Voronoi图顶点；◆每个三角形边对应于一个Voronoi图边；◆每个结点对应于一个Voronoi图区域；◆Delaunay图的边界是一个凸壳；◆三角网中三角形的最小角最大。

空外接圆准则最大最小角准则最短距离和准则在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角一点到基边的两端的距离和为最小Delaunay三角剖分的重要的准则张角最大准则面积比准则对角线准则一点到基边的张角为最大三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小两三角形组成的凸四边形的两条对角线之比。

这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化Delaunay三角剖分的重要的准则不规则三角网(TIN)的建立●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。

●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。

方法说明方法实例收缩生长算法先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网分割合并算法逐点插入算法扩张生长算法从一个三角形开始向外层层扩展，形成覆盖整个区域的三角网递归生长算法逐点插入算法分割合并算法12121212递归生长算法333TIN 建立过程中的几个问题:◆邵春丽.DELAUNAY 三角网的算法详述及其应用发展前景◆鲍蕊娜，等:基于凸壳技术的Delaunay 三角网生成算法研究◆于杰等：Delaunay 三角网构建方法比较研究周围点的提取点在三角形中的查找空外接圆判断准则线段求交问题。

DELAUNAY三角网的算法

二、Delaunay（德洛内）三角网 1、定义：一系列相连但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他人任何点。 2、性质：（1）、每个Delaunay三角形的外接圆不包含面内其他任何点，即Delaunay三角网的空外接圆性质。这是创建Delaunay三角网的一项判别标准。（2）、在由点集V中所能形成的三角网中， Delaunay三角网中三角形的最小角度是最大的。
DELAUNAY三角网的算法
一、引言 TIN（Triangulated Irregular Network,不规则三角网）
是由Peuker和他的同事于1978年设计的一个系统，它是根据区域的有限个点集将区域划分为相等的三角面网络，数字高程由连续的三角面组成，三角面的形状和大小取决于不规则分布的测点的密度和位置，能够避免地形平坦时的数据冗余，又能按地形特征点表示数字高程特征。TIN常用来拟合连续分布现象的覆盖表面。
3、优点：结构良好，数据结构简单，数据冗余度小，存储效率高，可适应各种分布密度的数据。
p1
p4
p2 p3
p6
p5
三、Voronoi图（泰森多边形或Dirichlet图）
由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。 N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。 Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。 Delaunay三角形的外接圆圆心是与三角形相关的 Voronoi多边形的一个顶点。 Voronoi三角形是Delaunay图的偶图。

3、根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。 4、循环执行上述第2步，直到所有散点插入完毕。上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。

浅较基于ArcGIS的两种DEM生成方法

浅较基于ArcGIS的两种DEM生成方法数字高程模型（DEM）是新一代的地形图，地貌和地物不再用直观的等高线和图例符号在纸上表达，而是通过储存在磁性介质上的大量密集的地面点的空间坐标和地形属性编码，以数字的形式描述。

DEM以数字的形式按一定的组织结构组织在一起，表示实体地形特征空间分布的模型，是地形形状大小起伏的数字描述。

由于生成DEM的数据获取方式不同、生成算法各异等原因，DEM的生成方法很多，最常用的生成方法就是对现有地形图进行数字化，以获取原数据，并用于构建不规则三角网从而建立DEM或直接通过内插的方法建立DEM。

本文将对这两种生成DEM的方法进行实验，依据高程吻合度等质量评价标准对这两种方法生成的DEM进行对比。

1 实验数据和研究方案根据数字化地形图数据分别以构TIN法和TOPO法生成DEM，并对其比较，找出其区别和优缺点。

其中通过构建不规则三角网生成DEM时对分别以无骨架点数据构TIN和增加骨架点数据构TIN两种方法生成的DEM进行对比，找到更高质量的构TIN方案；在TOPO法建立DEM中，通过对DEM生成参数的设置，建立更佳的DEM，对构TIN法生成的DEM与TOPO法建立的最佳DEM进行对比。

2 DEM建立方法2.1 构TIN法（以Delaunay三角网为例）不规则三角网表示数字高程模型既能减少规则格网方法带来的数据冗余，同时在计算效率方面优于纯粹基于等高线的方法。

单纯以等高线构建DEM会出现平顶，沟谷、山脊不明显等缺点，不能够很好地表现微地形特征。

为了克服这些缺点，需在等高线数据基础上增加骨架点数据来弥补。

骨架点就是分布于整个图内，弥补等高线不能反映出的具体特征地形的一系列特征点。

与没有骨架点的DEM晕渲图相比，平顶、沟谷、山脊不明显等缺点，已经较好地得到了改善。

包含骨架点数据生成的DEM比不包含骨架点数据生成的DEM在山顶、沟谷、山脊等方面优秀，包含骨架点生成TIN得到DEM的相同抽取点高程误差的均方差小于不包含骨架点生成TIN得到的DEM的抽取点高程误差的均方差。

浅谈DEM的制作方法

浅谈DEM的制作方法摘要：论文阐述了数字高程模型DEM内涵，简要介绍了DEM的制作方法，通过对乌海市海勃湾区某煤场地形图航片的数字处理，通过JX4-G TINDEM.exe 模块，理论联系实际的展现利用数字摄影测量的方法生成多种DEM和其它三维数字产品的全过程。

关键词：摄影测量；DEM；三维产品1 DEM的内涵数字地面模型（DTM）是表示地面特征的空间分布的数据阵列，最常用的是用一系列地面点的平面坐标X，Y以及该点的地面高程Z或属性组成的数据阵列。

若地面点按一定的网格排列，点的平面坐标X，Y有起始点开始推算，无需记录，地面形态只用地面高程表示这样的数据阵列被称为数字高程模型（DEM）。

三维分析大多是在数字高程模型（DEM）上进行的，一旦区域上生成所需密度和精度的DEM，内容丰富的各种三维分析是轻而易举的，其三维的可视化、真实场景、电子沙盘也迎刃而解。

DEM最常用的三种形式为：等值线DEM、TINDEM 、格网DEM。

1.1 等值线DEM高程等值线方法是地图学的基本方法，将地图上所有等高线数字化，即可形成高程等值线DEM。

等高线DEM的建立一般是直接采用数字化地图上的等高线。

1.2 不规则三角网TIN若将按地形特征采集的点按一定规则连接成覆盖整个区域且互不重叠的许多三角形，构成一个不规则三角网TIN表示的DEM，通常称为三角网DEM或TIN。

通常的TIN（Triangulated Irregular Network）结构是按Delaunay三角形规则生成，该三角形的特点是任一三角形外接圆内部包含其它点，这里并未包括外接圆上。

按这个规则生成的三角网，称为Delaunay三角网。

1.3 格网DEM利用一系列在X，Y方向上都是等间隔排列的地形点的高程Z表示地形，形成一个个矩形格网DEM。

格网的每一个交点都包含有此处相关的高程信息。

2 DEM的制作方法论文用摄影测量的方法制作DEM，这种方法制作DEM是指通过影像中的地物以及已经制作好的数据来进行生产。

三维空间Delaunay三角剖分算法的研究及应用

三维空间Delaunay三角剖分算法的研究及应用一、本文概述随着计算几何和计算机图形学的发展，三维空间Delaunay三角剖分算法已成为一种重要的空间数据处理和分析技术。

本文旨在全面深入地研究三维空间Delaunay三角剖分算法的原理、实现方法以及应用领域。

本文将对三维空间Delaunay三角剖分算法的基本概念和性质进行详细的阐述，包括其定义、性质、特点以及与其他三角剖分算法的比较。

接着，本文将重点探讨三维空间Delaunay三角剖分算法的实现方法，包括增量法、分治法和扫描转换法等，并分析它们的优缺点和适用范围。

本文还将对三维空间Delaunay三角剖分算法在各个领域的应用进行详细的介绍和分析。

这些领域包括计算机科学、地理信息系统、地质学、气象学、生物医学等。

通过具体的应用案例，本文将展示三维空间Delaunay三角剖分算法在实际问题中的应用价值和效果。

本文还将对三维空间Delaunay三角剖分算法的未来发展方向进行展望，探讨其在新技术和新领域中的应用前景和挑战。

本文旨在全面系统地研究三维空间Delaunay三角剖分算法的理论和实践，为其在实际问题中的应用提供有力的支持和指导。

二、三维空间Delaunay三角剖分算法的基本原理Delaunay三角剖分算法是一种广泛应用于二维空间的数据处理算法，它的核心目标是将一组离散的二维点集剖分为一系列互不重叠的三角形，且这些三角形满足Delaunay性质。

简单来说，Delaunay 性质要求任何一个三角形的外接圆内部不包含该三角形之外的任何数据点。

初始化：为每个点分配一个初始的三角形。

这通常是通过连接每个点与它的两个最近邻点来完成的，形成一个初始的三角形网格。

合并三角形：接下来，算法会尝试合并相邻的三角形，以形成更大的三角形。

在合并过程中，算法会检查新形成的三角形是否满足Delaunay性质。

如果满足，则合并成功；如果不满足，则放弃合并，并标记这两个三角形为“已处理”。

Delaunay三角网剖分的约束边嵌入改进算法_陈学工

2009，45（24）B图1平面直线图1引言地学领域中的大量离散数据不是独立的，相互之间存在着一定的约束关系，比如地表的山脊线、山谷线、断裂线等。

在构建Delaunay 三角网时，如果三角网中没有带约束数据，则生成的数字地面模型是不能正确地表达地表的复杂关系，也不能满足实际应用的需要，于是在无约束数据的三角网中嵌入约束线段就成为一个关键的问题，该文重点研究约束边嵌入三角网的问题。

文献[1]中提到的“轨迹生成”法，易于实现，但当交换边所在四边形为凹多边形时，“轨迹生成”法失效。

文献[2]提出“多对角线交换算法”，经研究[3]表明该结论是不正确的，文献[4-5]分别提出一种插点算法，此类算法需要大量插入点并修改三角剖分的结构。

根据约束边影响域所在多边形顶点的凸凹性，文献[3]提出一种基于凸凹判定的对角线交换算法，当约束边与三角形的边相切时交换对角线会出现错误，且执行效率较低，针对文献[3]出现的问题，在不改变原算法思想的前提下提出“分裂约束边”的思想完善原算法的健壮性，并引入快速点定位算法[6]以提高算法的执行效率。

2基本概念定义1平面直线图（Planar Straight Line Graph ，PSLG），它由顶点集p =（p 1，p 2，…，p n ）以及其中点组成的直线段（约束边）的集合L ={p i p j |p i ∈p ，p j ∈p ，p i ，p j 为直线段的两端点}组成，并且L 中任意两条直线段之间除端点外没有其他交点。

PSLG 扩展了传统的以内、外环定义平面图形的方式，可表示任意复杂的正则及非正则图形。

三角网则可以看作一个平面直线图。

定义2与待嵌入边E c 相交的三角形组成的多边形，称为E c 的影响域。

图1中多边形EFGHSIJ 是约束边E c 的影响域。

E c左边影响域记为QL=（S ，H ，G ，F ，E ），右边影响域记为QR=（S ，I ，J ，E）。

Delaunay 三角网剖分的约束边嵌入改进算法陈学工1，李源1，曹建1，肖克炎2CHEN Xue-gong 1，LI Yuan 1，CAO Jian 1，XIAO Ke-yan 21.中南大学信息科学与工程学院，长沙4100832.中国地质科学院矿产资源研究所，北京1000371.School of Information Science and Engineering ，Central South University ，Changsha 410083，China 2.Institute of Resources ，Chinese Academy of Geological Science ，Beijing 100037，China E-mail ：lyazjx@CHEN Xue-gong ，LI Yuan ，CAO Jian ，et al.Improved algorithm of inserting constrained edge into Delaunay triangulation.Computer Engineering and Applications ，2009，45（24）：235-237.Abstract ：This paper focuses on researching the problem of inserting constrained edge into D-Triangulation.It is a very effectivemethod of changing D-Triangulation into CD-Triangulation that constrained edge is inserted into D-Triangulation ，and only CD-Triangulation can present real terrain and relief.According to the shortcoming of the diagonal line exchange algorithm which is based on convexo-concave ，this paper proposes an idea of “split -restraint ”to improve the robustness of the algorithm and intro －duces the rapid point positioning algorithm to enhance the efficiency of the algorithm.Key words ：constrained edge ；Delaunay triangulation ；diagonal ；convexo-concave 摘要：重点研究约束边强行嵌入D-三角网的问题。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第２８卷第３期２００８年５月长安大学学报（自然科学版）Ｖ０１．２８Ｎｏ．３ＪｏｕｒｎａｌｏｆＣｈａｎｇ’ａｎＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｍａｙ２００８文章编号：１６７１—８８７９（２００８）０３—００４４—０５Ｄｅｌａｕｎａｙ三角网构建ＤＥＭ整体优化算法马智民１，罗斌１’２（１．长安大学地球科学与资源学院，陕西西安７１００５４；２．中国科学院地理科学与资源研究所，北京１００１０１）摘要：针对现有的公路选线系统ＤＥＭ（数字高程模型）的建立存在的效率低、速度慢、网形差和精度难以保证等问题，分析了同类算法的特点和缺陷，研究了影响约束数据域Ｄｅｌａｕｎａｙ三角剖分算法效率提高的因素，提出了基于约束数据域三角剖分的整体模型优化算法，讨论了基于该模型的ＤＥＭ建立的方法、步骤和过程，以及道路表面模型与ＤＥＭ拼合的方法和思路，并以公路定线实例对整体模型优化算法进行了验证。

结果表明：基于约束数据域三角剖分的整体模型优化算法能很好地将公路设计表面模型和数字地面模型拼合成整体模型，且具有构网速度快、网形优和算法精度高等特点，在公路选线系统ＤＥＭ模型建立方面具有明显的应用优势。

关键词：道路工程；公路定线；数字高程模型；Ｄｅｌａｕｎａｙ三角剖分；约束数据域中图分类号：Ｕ４１２．３文献标志码：ＡＥｎｔｉｒｅｏｐｔｉｍｉｚｅｄｔｒｉａｎｇｕｌａｔｉｏｎａｌｇｏｒｉｔｈｍｏｆＤｅｌａｕｎａｙｔｒｉａｎｇｌｅｎｅｔｗｏｒｋｆｏｒＤＥＭｃｏｎｓｔｒｕｃｔｉｏｎＭＡＺｈｉ—ｍｉｎｌ．ＬＵ０Ｂｉｎｌ，２（１．ＳｃｈｏｏｌｏｆＥａｒｔｈＳｃｉｅｎｃｅｓａｎｄＲｅｓｏｕｒｃｅｓ，Ｃｈａｎｇ’ａｎＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ７１００５４，Ｓｈａａｎｘｉ，Ｃｈｉｎａ；２．ＩｎｓｔｉｔｕｔｅｏｆＧｅｏｇｒａｐｈｙＳｃｉｅｎｃｅａｎｄＮａｔｕｒａｌＲｅｓｏｕｒｃｅｓ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ１００１０１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇａｔｔｈｅｐｏｏｒｅｆｆｉｃｉｅｎｃｙ，ｓｌｏｗｓｐｅｅｄ，ｐｏｏｒｓｈａｐｅｐｒｏｐｅｒｔｉｅｓｏｆｔｈｅｔｒｉａｎｇｕｌａｔｉｏｎａｎｄｔｈｅｌｏｗａｃｃｕｒａｃｙｉｎｅｘｉｓｔｉｎｇＤＥＭｃｏｎｓｔｒｕｃｔｉｏｎｍｅｔｈｏｄ０１０９ｉｅｓｆｏｒｒｏａｄｄｅｔｅｒｍｉｎｉｎｇｓｙｓｔｅｍｓ，ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｄｔｈｅｆａｃｔｏｒｓｗｈｉｃｈｉｎｆｌｕｅｎｃｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆＤｅｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎｏｆｃｏｎｓｔｒａｉｎｅｄｄａｔａｓｅｔａｆｔｅｒｔｈｅａｎａｌｙｓｉｓｏｆｅｘｔａｎｔａｌｇｏｒｉｔｈｍ，ｐｒｏｐｏｓｅｄａｎｅｎｔｉｒｅｏｐｔｉｍｉｚｅｄａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＤｅｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎｏｆｃｏｎｓｔｒａｉｎｅｄｄａｔａｓｅｔ．Ｔｈｅｍｅｔｈｏｄａｎｄｐｒｏｃｅｄｕｒｅａｒｅｄｉｓｃｕｓｓｅｄ，ａｓｗｅｌｌａｓｈｏｗｔｏｍｅｒｇｅｔｈｅｈｉｇｈｗａｙｄｅｓｉｇｎｅｄｓｕｒｆａｃｅｍｏｄｅｌｉｎｔｏｔｈｅＤＥＭ．Ｍｅａｎｗｈｉｌｅ，ｔｈｅｏｐｔｉｍｉｚｅｄａｌｇｏｒｉｔｈｍｗａｓａｐｐｌｉｅｄｉｎｔｈｅｈｉｇｈｗａｙｌｏｃａｔｉｎｇａｓａｃａｓｅｓｔｕｄｙ．Ｔｈｅｒｅｓｕｌｔｓｈｏｗｓｔｈａｔ：ｔｈｉｓｎｅｗａｌｇｏｒｉｔｈｍｃａｎｐｕｔｔｈｅｈｉｇｈｗａｙｄｅｓｉｇｎｓｕｒｆａｃｅｍｏｄｅｌｔｏｇｅｔｈｅｒｗｉｔｈｔｈｅｄｉｇｉｔａｌｔｅｒｒａｉｎｍｏｄｅｌ，ａｎｄｈａｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｃｏｎｓｔｒｕｃｔｉｎｇｎｅｔｑｕｉｃｋｌｙ，ｂｅｉｎｇｓｕｐｅｒｉｏｒｉｎｔｈｅｎｅｔｓｈａｐｅ，ｈａｖｉｎｇｈｉｇｈｐｒｅｃｉｓｅｉｎａｌｇｏｒｉｔｈｍｃｏｍｐｕｔａｔｉｏｎ，ｉｔｏｂｖｉｏｕｓｌｙｈａｓｔｈｅａｄｖａｎｔａｇｅｏｆｂｕｉｌｄｉｎｇＤＥＭｉｎｒｏａｄｌｏｃａｔｉｏｎａｎｄｄｅｓｉｇｎｓｙｓｔｅｍｓ．７ｆｉｇｓ，１０ｒｅｆｓ．Ｋｅｙｗｏｒｄｓ：ｒｏａｄｅｎｇｉｎｅｅｒｉｎｇ；ｈｉｇｈｗａｙｌｏｃａｔｉｎｇ；ＤＥＭ；Ｄｅｌａｕｎａｙｔｒｉａｎｇｕｌａｔｉｏｎ；ｃｏｎｓｔｒａｉｎｅｄｄａｔａｓｅｔ收稿日期：２００７－０５—２０基金项目：科技部中西部专项资助项目（２００２ＢＡ９０１Ａ４３）作者简介：马智民（１９５７一）。

男，陕西杨凌人，教授，博士．Ｅ－ｍａｉｌ：ｚｈｍｍａ＠ｃｈｄ．ｅｄｕ．ｃａ第３期马智民，等：Ｄｅｌａｕｎａｙ三角网构建ＤＥＭ整体优化算法４５Ｏ引言在数字高程模型（ＤＥＭ）的各种表示方法中，Ｄｅｌａｕｎａｙ三角网在地形拟合方面表现的最为出色［１。

３］，而顾及强制约束数据构建Ｄｅｌａｕｎａｙ三角网的技术在建立高质量ＤＥＭ中起着决定性的作用。

经过长期的研究，国内外已经出现了很多算法［４１引，通过对比分析可以发现，这些算法有的只是对构网过程进行研究，从而对带约束数据域的三角剖分就不适用了；有的算法虽然考虑了带约束数据域的情况，但不能基于一个算法同时处理多种类型的约束数据情况；除此之外，现存的算法在构网效率方面都较少考虑优化问题，一般只能处理小数据量。

为此，本文将构网与嵌入约束数据作为一个整体进行研究，在逐点插入算法的基础上，提出一种改进的基于两步法的边交换迭代算法，实现约束线段的嵌入，并对该算法进行推广，使得能解决约束区域的嵌入。

１逐点插入算法逐点插入算法的思想是先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入。

运用Ｄｅｌａｕｎａｙ三角网的空外接圆性质，对由两个有公共边的三角形组成的四边形进行判断，如果其中一个三角形的外接圆中含有第４个顶点，则交换由两个三角形所构成的四边形的对角线。

这一调整过程称为局部优化过程（ＬＯＰ）。

逐点插入算法的基本步骤是：①定义一个包含所有数据点的初始包容盒；②对初始包容盒进行初始三角剖分，然后对以下③、④步迭代，直至处理所有数据点；③插入新数据点Ｐ，在三角网中找出包含Ｐ的三角形ｔ，把Ｐ与ｔ的３个顶点相连，生成新的三角形；④以ＬＯＰ算法优化三角网；⑤最后处理外围多余三角形。

２基于逐点插入算法的约束数据域三角剖分算法２．１快速定位点所在的三角形逐点插入算法中一个重要环节就是确定包含新插入点的三角形。

一般将点在三角形中的查找算法称为三角形的定位问题。

解决这一问题的最直接的办法就是利用计算几何中点在多边形（此处多边形为三角形）中的测试方法。

由于每插入一点要对整个三角网扫描一次，显然这种方法是比较费时的。

尽管可以通过建立索引的方法来减少定位时间，但效率仍然较低。

在ＴＩＮ（泰森不规则三角网）中，如果建立了三角形之间的拓扑关系，利用三角形的拓扑关系和三角形面积坐标，则很容易判断包含插入点的三角形。

如图１所示，设△Ａ。

ＡｚＡ。

的坐标为Ａ。

（ｚ。

，Ｙｔ）、Ａ２（ｚ２，ｙ２）、Ａ３（ｚ３，ｙ３），任给一点Ｐ（ｘ，ｙ），则在△Ａ。

Ａ。

内的面积坐标Ｓ。

、Ｓ２、Ｓ。

定义为：Ｓ１一Ｖ－／ｖ，Ｓ２＝Ｖ２／ｖ，Ｓ３一Ｖ。

／Ｖ。

其中：Ｖ为△Ａ，Ａ２Ａｓ的面积；Ｋ、％、玑分别为△Ａ。

Ａ。

Ｐ、△Ａ。

Ａ。

Ｐ、△Ａ。

Ａ。

Ｐ的面积。

在实际计算中，并不计算三角形面积坐标，而仅关心其正负号。

故当三角形顶点Ｐ按逆时针方向排列时，点Ｐ的面积坐标（Ｓ。

，Ｓ：，Ｓ。

）可简化为Ｓ１一（ｙ—Ｙ２）（ｚ３一ｚ２）一（３，３一ｙ２）（ｚ—ｚｚ）Ｓ２一（ｊ，一ｙ３）（ｚｌ—ｚ３）～（ｙ１一Ｙ３）（ｚ—ｚ３）Ｓ３一（ｙ—Ｙ１）（ｚ２一ｚ１）一（弛一ｙ１）（ｚ—ｚ１）则Ｐ与三角形的位置关系可以用Ｐ的面积坐标（Ｓ。

、Ｓ。

）的正负关系来判断：Ｓ１＞０且Ｓ２＞０且Ｓ３＞０一Ｐ在三角形中；Ｓ１＜０或Ｓ２＜０或Ｓ３＜０一Ｐ在三角形外；Ｓ，一０或Ｓ２—０或Ｓ。

＝０一Ｐ在三角形某条边上。

圈１三角形面积坐标当点Ｐ在三角形中时，必有其所有面积坐标分量大于０；而若点Ｐ不在三角形中，则至少有一个面积坐标分量小于０（图２）；点Ｐ在△ＡＢＣ之外，且在ＢＣ边的外侧，这时点Ｐ的面积坐标Ｓ－＜０，Ｓ２＞０，Ｓ。

＞０。

事实上，正是小于０的面积坐标分量指明了定位时的查找方向。

在ＴＩＮ中，若建立了三角形的拓扑关系，利用面积坐标这一特性，可很快查找到包含插入点的三角形（图２）。

对△ＡＢＣ、△ＣＢＤ、／ｘＢＥＤ、／ＸＤＥＧ、／ＸＥＦＧ、／ＸＦＨＧ依次编号１、２、３、４、５、６。

首先计算点Ｐ在三角形１中的面积坐标，其符号为（上标为三角形编号）：Ｓ｝＜０，Ｓ；＞０，Ｓｊ＞０。

取小于０的面积坐标对应边（图２中为ＢＣ边）的邻接三角形２，计算面积坐标有：Ｓ；＜０，Ｓ；＞０，Ｓｉ＞０。

４６长安大学学报（自然科学版）２００８血图２快速定位点所在的三角形取小于０的面积坐标对应边（ＢＤ边）的邻接三角形３，重复以上过程，直到计算出点Ｐ在三角形６中的面积坐标：Ｓ２＜０，Ｓ２＞０，Ｓ；＞０。

即点Ｐ的３个面积坐标分量都大于０，点Ｐ在三角形６（△ＦＨＧ）中。

２．２约束线段的嵌入三角部分算法的实质是首先在逐点插入算法的基础上对约束数据集建立非约束Ｄｅｌａｕｎａｙ三角网，包括将约束线段的端点作为离散点，按照逐点插入算法插入初始三角网，形成包含原始离散点和约束线段端点的三角网。

然后从约束线段的起点出发，按一定的规则逐步交换与约束线段相交的边，最终使约束线段的起点和终点相连，从而将约束线段嵌入。

同时，对除约束线段以外的其他新产生的边的左右三角形进行空外接圆检测。

由此可以发现，基于两步法的边交换迭代算法的核心问题除了逐点插入算法之外，另一个就是按一定的规则交换与约束线段相交的边的问题。

交换的原则和方法是：如果共用相交边的两个三角形组成的四边形是一个严格凸四边形，则交换四边形对角线，从而将与约束线段相交的边交换成四边形的另一对角线，用新生成的两个三角形替换原三角形。

影响算法效率的因素除了逐点插入算法之外，另一因素就是快速查找与约束线段相交的边。

对于相交边的查找，传统方法一般是对所有的边进行扫描，逐条判断是否与约束线段相交，这样的判断过程效率相对较低。

作者对快速定位点所在三角形算法进行推广，利用三角形的拓扑关系和三角形面积坐标对相交边进行判断。

如图３所示，对△Ａ，Ａ。

Ａ。

、△Ａ３Ａ２Ａ４、△Ａ２Ａ５Ａ４、△Ａ４Ａ５Ａ６、△Ａ５Ａ７Ａ６依次编号为Ｉ、Ⅱ、Ⅲ、Ⅳ、Ｖ、Ⅵ。

首先查找到约束线段经过的第一个三角形，即在约束线段上取离Ａ，点很近的点Ｐ，用Ｐ取代Ａ。

来判断Ａ，所在的三角形，然后快速定位点所在的三角形。

此时有两种情况：点在某个三角形内，记录所在的三角形，即为约束线段经过的第一个三角形；三角网中的一条边与约束线段部分重合或者完全重合，对于完全重合的情况，表明图３快速查找相交边不存在与约束线段相交的边，对于部分重合的情况，将约束线段的起点用重合边的另一端点替代重新处理。