（计算机科学与技术专业论文）带断层线的等值线生成方法研究.pdf

摘要 等值线图在石油勘探开发、采矿、地质等领域有广泛应用，但由 于这些领域经常遇到断层，使得断层附近的等值线追踪结果不能正确 反应真实的地质构造。因此本文主要研究了基于三角网的等值线生成 方法，并提出了一种分区算法来实现带断层线的等值线追踪。 在基于三角网的等值线生成算法方面，本文改进了原有的等值线 生成算法。该算法首先在建立三角网的同时保存边界边到凸壳边表， 然后求出所有存在等值点的三角形，将其保存在三角形数组中，最后 根据一定的规则进行等值线的追踪。通过凸壳边表可以快速地找到开 曲等值线的线头，通过判断三角形数组是否为空，可以快速确定是否 存在闭合等值线，从而提高了效率。 目前约束d e l a u n a y 三角网生成算法多数是采用对角线交换的方 法来解决三角形与约束线的相交。考虑到断层线的特殊性，如果采用 该方法，生成的等值线延伸不到断层线，从而不能真实的反应地质构 造。为了解决该问题，本文对已有的约束三角网生成方法进行了改进， 即将断层线与三角形的交点看作插入点，再次进行三角剖分。这样处 理后再通过本文提出的分区算法估算插入点和断层线端点的高程值， 就能得到延伸到断层线的等值线，从而提高了精度，更好的反应了真 实的地质构造。 在带断层线的等值线追踪算法方面，为了得到断层线上点的精确 高程值，同时考虑到断层的复杂性，本文提出了一种基于三角网拓扑 结构的分区方法来解决该问题。算法首先把与断层线重合的三角形的 边标志为边界边，其次根据组成区域边界的边类型，搜索出所有合理 区域和各个区域内部的点，然后搜索与断层线上点在同一个区域的 点，通过这些点来插值断层线上点的高程值，最后得到带断层落差的 等值线。该算法可以处理各种断层线，并且分区的同时实时保存了每 个区域的内部点，避免了判断点在区域多边形的内外，优化了分区。 关键词d e l a u n a y 三角化，凸壳，断层线，等值线 a b s t r a c t t h ei s o l i n em a pi si n c r e a s i n g l yu s e di no i le x p l o r a t i o n ，m i n i n ga n d g e o l o g ya p p l i c a t i o n b e c a u s eo ff a u l t s ，t h er e s u l to fi s o l i n et r a c i n gc a n n o tr e f l e c t g e o l o g i c s t r u c t u r ec o r r e c t l yi nt h e s ef i e l d s t h i s p a p e r p r i n c i p a l l yd i s c u s s e dt h eg e n e r a t i o np r o c e s so fi s o l i n ew h i c hi sb a s e do n t h et r i a n g u l a t i o nm o d e la n dp u tf o r w a r da na l g o r i t h mo fi s o l i n et r a c i n g w i t hf a u l tl i n e s a tt h ea s p e c to ft h ei s o l i n et r a c i n gb a s e do nt h et r i a n g u l a t i o nm o d e l ， t h i sp a p e ri m p r o v e dt h eo r i g i n a la l g o r i t h m i nt h ef i r s tp l a c ei tp r e s e r v e d b o u n d a r ye d g e st ot h et a b l eo fc o n v e xh u l lw h e nb u i l d i n gt r i a n g u l a t i o n i nt h es e c o n dp l a c ei tp r e s e r v e dt r i a n g l e st ot r i a n g l e a r r a yw h i c hh a v e e q u i v a l e n tp o i n t s w ec a nq u i c k l ys e a r c ht h es t a r tp o i n to ft h eo p e nc u r v e a n d j u d g ec l o s e dc h iv ef r o mt r i a n g l ea r r a y , s oi ti m p r o v e st h ee f f i c i e n c y a tp r e s e n tt h ea l g o r i t h mo ft r i a n g u l a t i o nw i t hc o n s t r a i n e dl i n e s u s u a l l yr e s o l v e st h ei n t e r s e c t i o no ft r i a n g l e sa n dc o n s t r a i n e dl i n e s a c c o r d i n gt ot h ed i a g o n a ll i n ee x c h a n g ea l g o r i t h m i fw eu s et h i sm e t h o d ， t h ei s o l i n ec a nn o te x t e n df a u l tl i n e s t or e s o l v et h i sp r o b l e m t h i sp a p e r i m p r o v e dt h ei n i t i a la l g o r i t h m f i r s ti tr e g a r d e dt h ei n t e r s e c t i o np o i n t sn o t i n c l u d i n gt h ee n d p o i n t so ff a u l tl i n e so ft r i a n g l e sa n df a u l tl i n e sa s i n s e r t i o np o i n t s t h e ni td i dt r i a n g u l a t i o na g a i nw i t hi n s e r t i o np o i n t s t h r o u g ha b o v ep r o c e s s ，i s o l i n ec a nr e a c hf a u l tl i n e sa n dr e f l e c ta c t u a l g e o l o g i cs t r u c t u r e a tt h ea s p e c to ft h ea l g o r i t h mo f t r a c i n gi s o l i n ew i t hf a u l tl i n e s ，t h i s p a p e rr e a l i z e dap a r t i t i o na l g o r i t h mb a s e do i l t o p o l o g ys t r u c t u r eo f t r i a n g u l a t i o nt oe s t i m a t ee l e v a t i o nv a l u e so fb o t hs i d eo fp o i n t so nf a u l t l i n e s c o n s i d e r i n gt h ec o m p l e x i t yo ff a u l tl i n e s f i r s t l y , t h ea l g o r i t h m r e g a r d e de d g e sc o i n c i d e dw i t hf a u l tl i n e sa sb o u n d a r ye d g e s s e c o n d l yi t s e a r c h e da l lr e a s o n a b l er e g i o n s , i n t e r n a lp o i n t sa n di n t e r p o l a t e dp o i n t so f f a u l tl i n e sb yj u d g i n gt h ee d g et y p e c o n s i s t i n go fr e g i o nb o u n d a r y l a s t l y w ec a ng e ti s o l i n ew i t hf a u l t1 i n e s t h ea l g o r i t h mc a nd e a lw i t ha l lk i n d s i i o ff a u l tl i n e sa n do p t i m i z ep a r t i t i o nb yp r e s e r v i n gi n n e rp o i n t so fe v e r y r e g i o n k e yw o r d s d e l a u n a yt r i a n g u l a t i o n ，c o n v e xh u l l ，f a u l tl i n e s ，c o n t o u r i i i 硕士学位论文第一章绪论 第一章绪论 对地形表面进行数字建模，建模的结果就是数字地形模型【啦】( d t m ，d i g i t a l t e r r a i nm o d e l ) 。基于高程的数字地形模型称为数字高程模型( d e m ，d i g j i t a l e l e v a t i o nm o d e l ) 。数字高程模型广泛应用于地学的相关领域，它的主要功能是 从数字高程模型生成等值线图。等值线图是连接空间分布的具有相同高程值的 点，并将这些点投影n - 维平面上得到的图形。它不仅可以表示空间连续分布现 象，并且能精确表示空间的垂直变化和水平方向差异。但由于地质中经常遇到断 层，使生成的等值线不连续，因而增加了等值线绘制的难度。近年来，不连续等 值线的绘制成了研究的热点。 1 1 研究内容和研究意义 本文的研究课题是带断层线的等值线生成算法，研究内容主要包括以下三个 方面： ( 1 ) 三角网生成等值线算法： ( 2 ) 约束三角网生成方法和分区算法； ( 3 ) 带断层线的等值线生成算法及其光滑算法。 等值线图是最广泛使用的地质图件，是地质和石油勘探开发中不可或缺的基 本图件。但由于地壳的频繁运动使得地质中经常出现断层，故仅仅绘制连续的等 值线已不能满足要求，于是人们开始研究不连续等值线的生成。自地质绘图技术 和分区、插值算法提出后，非连续界面( 如断层) 等值线绘制有了一定的进展。 近年来很多学者对非连续界面的等值线生成进行了研究，并提出了各自的方法， 但这些方法都不能很好的解决该问题。因此研究非连续的等值线具有重要的意 义。 1 2 国内外研究现状与水平 因等值线可以表示地面的起伏变化和变化方向，故等值线图可精确地表示地 形的变化。目前，等值线图在地学中有着广泛的应用，但地质、采矿中常遇到断 层，且由于断层的影响使得断层两侧的数据呈现不连续性，使得断层附近的等值 线不能正确反映真实的地质构造。因此人们开始研究非连续界面等值线的生成技 l 硕士学位论文 第一章绪论 术，虽然现在国外一些公司( 如z y c o r 公司) 的等值线绘图软件已经具备了绘制 带正断层的地质等值线图的功能，但这些软件要求操作人员有相关的专业知识才 能操作，同时，这些软件价格十分昂贵。这两个原因大大限制了这些软件的使用 范围。因此绘制带断层线的等值线图成了国内外研究的热点。 1 2 1 数字高程模型 数字高程模型是一种地面模型，它用一组有序的数值表示地面的高程，是数 字地形模型的一个分支。因数字高程模型描述的是地面的高程信息，因此在地质 及自然科学领域有广泛的应用。数字高程模型主要用规则格网( g r i d ) 和不规则 三角网( t r i a n g u l a t e di r r e g u l a rn e t w o r k ，t i n ) 来表现。其中不规则三角网是d e m 最重要的一种表现形式。 如果采集到的离散数据点本身是规则的，或者是将离散数据点通过内插的方 法生成了规则数据点，则数字高程模型可以用规则格网法来表示。用规则格网来 表示，不仅结构简单而且便于管理，且占用的内存也相对较少。但如果采集到的 数据点是通过离散点内插得到的规则网格点，则不能很精确地表示地形特征。如 果地形很平坦，用规则格网表示时还会存在大量的数据冗余，因此如果采样点是 离散数据集，一般用不规则三角网来表示。 不规则三角网是通过连接采集到的离散数据点生成不互相重叠的三角面来 模拟地形表面。因采集的离散数据会随着地形的复杂情况而变化，当地形复杂时， 采集到的数据点就相对密集，当地形平坦时，采集到的数据点就相对稀疏，又因 为采集到的所有数据点均参与三角网的形成，因此不规则三角网可以更精确的表 示地表形态f 3 4 】和地形内部特征( 如地形中存在断裂线、构造线等) ，同时也避免 了数据冗余。由于t i n 的上述优点，使得t i n 成为表示数字高程模型最广泛使 用的一种方法。 目前，国内外出现了很多成熟的方法来构建不规则三角网，其中最常用的方 法是用d e l a u n a y 三角剖分来构建t i n 。这是因为d e l a u n a y 三角剖分具有空外接 圆性质和最大最小角性质，从而可以保证生成的三角形大部分是等边三角形，减 少数据精度问题。 d e l a u n a y 三角网的生成算法有直接d e l a u n a y 三角剖分和间接d e l a u n a y 三角 剖分两种【1 】。间接d e l a u n a y 三角剖分算法因过程复杂，现在很少使用该方法。 直接d e l a u n a y 三角剖分算法有分治算法、逐点插入算法和三角网生长算法三种 类型【5 l 。近年来，国内外很多学者深入研究三角网的生成方法并提出了不同于经 典算法的快速插入算法【6 ，7 1 、合并算法【8 】和凸壳算法【9 】。 2 硕士学位论文 第一章绪论 实际应用中经常遇到带约束条件的d d a u n a y 三角剖分，如d e m 生成过程中 的地形特征线( 山脊线、山谷线、断裂线等) 的约束。目前带约束条件的d e l a u n a y 三角剖分方法【l 叫3 】主要有约束图法、分割合并算法、加密点算法、s h e l l 三角 化算法、两步法和约束线段的迭代算法。 1 2 2 等值线的生成和光滑 由离散点绘制等值线主要有三类方法：第一类方法是首先将离散点插值为规 则格网点，然后线性内插出格网边上的等值点，最后按一定规则追踪出一条等值 线的所有等值点，对所有高程值做上述处理后，便得到一幅等值线副1 4 】；第二 类方法也是首先将离散点内插为规则的格网点，然后通过一定的数学方法( 如双 三次拟合) 得到一张曲面，将规则网格点的平面坐标带入曲面方程从而得到网格 点的高程值，最后按一定规则追踪出一条等值线的所有等值点，对所有高程值做 上述处理后，便得到一幅等值线刚1 5 】；第三类方法是首先由不规则分布的数据 点生成不规则三角网，然后线性内插出三角形边上的等值点，最后按一定规则追 踪出一条等值线的所有等值点，对所有高程值做上述处理后，便得到一幅等值线 图【1 6 】。 带断层线的等值线生成原理与一般等值线生成原理基本上是相同的，不同点 是当等值线追踪到断层线时应停止，而不是穿过断层线。 用上述方法生成的等值线由一系列折线段组成，不能满足实际需要，因此需 要对其进行光滑处理。目前光滑曲线的方法主要有插值法和拟合法两种f 1 7 】。插 值法中线性插值法是最简单的方法【l 引，线性插值法的思想是：对平面上的有序 点列，依次顺序取三个点，在三点之间迭代插补点，插补的同时去掉一批尖角点， 对所有的点处理完毕后将最后一次插补的点连接起来就可以得到一条光滑曲线。 该方法虽然思想简单但最终生成的光滑曲线与由原始数据生成的曲线的位置差 距较大，所以如果对曲线的精确度要求比较严格，则不适合用该方法进行光滑。 后来，人们提出了分段三次多项式插值方法来生成光滑曲线，该方法能克服线性 插值导致生成的曲线不精确的缺点。该方法的基本思想是：首先顺序读取离散数 据；然后在相邻的两个离散点数据之间建立三次多项式方程，保证得到的曲线具 有连续的一阶导数；最后绘制光滑的曲线。该方法的优点是，生成的光滑曲线均 通过原始的离散点，能较精确地绘制出原有曲线，缺点是当点稀疏时，可能造成 相邻的两条曲线相交。在实际应用中，如果曲线的光滑算法满足以下两个条件 纠：( 1 ) 可以形成光滑的曲线；( 2 ) 可以形成分段的线性函数。那么，就可以 在保证曲线光滑的前提下使光滑的曲线尽可能不相交。经过许多学者的大量研究 发现张力样条函数f 2 0 , 2 1 1 满足上面的曲线光滑的两个条件。 3 硕士学位论文第一章绪论 1 2 3 断层处理技术 目前，常用的断层处理技术主要有两类：一类是在数据网格化过程中处理断 层；一类是在图形生成过程中处理断层。网格化过程中处理断层的方法主要有四 种【2 2 之4 】：( 1 ) 分块法；( 2 ) 断面法；( 3 ) 层位复原法；( 4 ) 断层轨迹法。 l 、分块法 分块法的思想是首先根据断层形状，把整个数据区域划分成若干断块，然后 对每个断块的数据用克里金插值或距离反比插值进行网格化处理，最后所有的网 格数据整合在一起便得到整个数据区域的网格数据体。由于分块法根据断层形状 划分区域，从而保证了划分的断块不互相重叠，但如果断层很多而且复杂时，用 该方法进行断块划分，速度很慢，所以该方法仅适用于划分的断块上数据点较多 的情况。 2 、断面法 断面法的思想是首先建立断层面的网格和被断层面分开的两侧地层面的网 格，然后把低于断层面的地层面网格数据与断层面网格数据作比较，取两者中的 较小值作为下层地层面网格数据，把高于断层面的地层面网格数据与断层面网格 数据作比较，取两者中的较大值作为上层地层面网格数据，最后把所有的网格体 数据结合起来。该方法仅能处理倾斜断层，且当存在多条断层时，处理难度很大。 3 、层位复原法 层位复原法的思想是首先对因断层而产生的地面的垂直位移进行网格化，消 除因断层存在而受到影响的地面数据，然后对这些数据进行网格化，得到产生断 层前的地层面，最后将该地层面网格数据和垂直位移网格数据叠加。该方法要获 得较多断层的信息，因此仅能处理单线断层。 4 、断层轨迹法 断层轨迹法的思想是首先通过断层两边的数据估计出断层上的点或邻近点 的高程值，然后将这些数据也作为原始数据网格化。用这种方法网格化数据，可 以处理任意复杂的断层线。 图形生成中断层处理技术主要有两种：一种是生成规则格网后嵌入断层线， 然后采用外推法，插值得到断层线上点的高程值；另一种是生成三角网后嵌入断 层线，然后利用分区的方法估计出断层线上点的高程值。当存在大量断层线时， 三角网模型能更好的顾及这些断层线的特征从而使生成的构造图正确，而格网模 4 硕士学位论文第一章绪论 型虽易于处理，但当数据点分布不均匀时，很可能使生成的等值线和数据点的位 置有明显矛盾。因此，采用在三角网生成过程中嵌入断层线是常用的方法，即生 成带约束条件的三角网，然后通过分区估计断层线上点的高程值。 1 3 研究思路和关键问题 不带约束条件的三角网生成等值线主要包括两个步骤：( 1 ) 建立d e l a u n a y 三角网；( 2 ) 等值线追踪。进行等值线追踪的关键是快速找到开曲等值线的线头 和判断是否存在闭合等值线，因此本文在不带约束条件的三角网生成等值线方面 主要做以下两个方面的研究： ( 1 ) 快速凸壳法建立d e l a u n a y 三角网的算法； ( 2 ) 三角网生成等值线的算法。 生成带约束条件( 断层线) 的等值线主要包括三个步骤：( 1 ) 生成带约束条 件( 断层线) 的三角网；( 2 ) 通过分区插值断层线端点和特殊点的高程值；( 3 ) 实现带断层线的等值线追踪。 生成带约束条件的三角网的关键是避免约束线与三角形的边相交，目前常采 用对角线交换算法，但该方法将使生成的等值线在约束线附近精度不高。因此本 文在约束三角网生成方面主要研究了一种提高等值线精度的约束线嵌入方法。 由于断层线上的点没有高程值，故生成带断层线的等值线的关键点是通过分 区方法估计出断层线的端点和特殊点的高程值。由于断层线的复杂性，目前常用 的分区算法运算量大、时间复杂度高，故不适合用这些方法来估计断层线上点的 高程值，经分析研究得到结合三角网的拓扑结构进行分区，可以处理各种情况的 断层线并能降低时间复杂度。因此，在分区和插值方面做以下两个方面的研究： ( 1 ) 结合三角网的拓扑结构实现一种分区方法； ( 2 ) 利用距离反比方法插值断层线上点的高程值。 用上述方法插值后，进行带断层线的等值线追踪，当等值线追踪到断层线时 立即结束，从而使生成的等值线真实的反应地质构造。但生成的等值线有折线段 构成所以不光滑，因此需要对等值线进行光滑处理。本文在带断层线的等值线生 成和处理方面做以下两个方面的研究： ( 1 ) 带断层线的等值线追踪方法： ( 2 ) 等值线光滑算法。 5 硕士学位论文 第一章绪论 1 4 论文的组织 本文共分五章，分别为绪论、数字高程模型、等值线生成算法研究、带断层 线的等值线生成方法、总结和展望。 第一章为绪论，主要概述了本文的研究内容和研究意义，并分别介绍了不规 则三角网建立、等值线生成原理及断层处理技术的研究现状和水平，描述了研究 思路和关键问题。 第二章主要介绍了相关的背景知识，包括数字高程模型的发展和应用、数字 高程模型的表示方法，经典的d e l a u n a y 三角网建立方法和常用的带约束条件的 d e l a u n a y 三角网建立方法。 第三章主要介绍了基于三角网的等值线追踪原理和算法，并针对等值线生成 算法的缺点实现了一种改进算法。 第四章主要研究了如何通过分区估计断层线上端点和特殊点的高程值，并结 合三角网的拓扑结构提出了一种分区算法，从而实现了带断层线的等值线生成方 法，然后介绍了张力样条函数光滑算法并实现了该算法。 第五章总结了全文所做的工作，并指出了进一步的研究工作。 6 硕士学位论文第二章数字高程模型 第二章数字高程模型 2 1 数字高程模型的发展和应用 数字地面模型【1 1 ( d i g i t a lt e r r a i nm o d e l s ，d t m ) 是有序数字阵列： k ( 汪1 , 2 ，刀) ，其中向量k = ( k 。，形：，圪) 中的各个分量描述了如地形、环境 等多种信息。如果只考虑d t m 中地表多种信息的地形分量，则称其为数字高程 模型d e m 。 数字高程模型在数学上用三维向量的有限序列来表示，用函数描述为： 杉= ( x ，z ，z ，) o = 1 , 2 9 o9 力) ，其中x ，、是平面点的坐标，z ，是与点( x ，z ) 相 对应的高程值。 从d e m 诞生到至今，对它的研究经历了四个时期【2 5 】：2 0 世纪5 0 年代末期 形成d e m 概念；6 0 、7 0 年代对d e m 的内插问题进行了大量的研究；7 0 年代中 后期大量研究了采样方法，如渐进采样和混合采样等等；8 0 年代以来，对d e m 的研究已经涉及到d e m 的各个环节，包括d e m 表示地形的精度、d e m 的数据 压缩、d e m 的应用以及不规则三角网的建立和应用等等。 地表通常表现为一种连续变化的曲面，由于d e m 可以表示地面的连续起伏 变化，现在已广泛应用于各个领域。具体来说，d e m 主要应用在以下四个方面： ( 1 ) d e m 可用于绘制地貌分析图，如等高线、坡度图、立体透视图和立体 景观图等； ( 2 ) 在环境与城市规划中d e m 可用于分析土地的现状、进行地表分析与 比较等； ( 3 ) 采集到的d e m 数据是地表三维模拟的关键数据； ( 4 ) 把采集到的数据中的高程数据转换成其他数据，从而可以生成非地形 性质的三维表面模型。 2 2 数字高程模型的表示方法 地表高程的变化可以用多种方法表达，常用的两种方法为：( 1 ) 数学方法； ( 2 ) 图形方法。 7 硕士学位论文第二章数字高程模型 1 、数学方法 表示地表高程变换的数学方法主要有两种：一是整体拟合地表高程；一是局 部拟合地表高程。整体拟合即将区域中采集到的所有点，通过傅里叶级数的方法 拟合地表高程曲面。局部拟合首先划分地表表面为面积大致相等的不规则区域或 任意的规则区域，然后对每个区域的点用傅里叶级数的方法拟合高程曲面。 2 、图形方法 用图形的方法来表示地表高程，主要有线模式和点模式两种。线模式中最常 用的一种形式是等高线，除等高线外，山脊线、海岸线等地形特征线也是较常用 的线模式。点模式即用采样到的离散数据点建立数字高程模型。采集的数据可以 是规则的也可以是不规则的，还可以是直接从等高线上采集的数据，或是有选择 性的采集数据，如采集地形中某些特征线上的点数据。 在地理信息系统中，表示d e m 的方法主要有三种【2 6 】：( 1 ) 规则格网模型； ( 2 ) 不规则三角网模型；( 3 ) 等高线模型。三种模型之间可以相互转换，即由 一种模型通过某种方法转换成另一种模型，以满足某些特殊应用。 2 2 1 规则格网模型 规则格网模型即将平面的有限区域划分成规则的格网单元，格网单元可以是 矩形也可以是正方形，但一定要保证是规则的。划分的每个格网单元都对应一个 数。如图2 1 所示，该平面区域被分成3 5 个规则的正方形格网，每个格网对应 一个高程值。 1 0 05 03 06 6 5 2 7 0 8 2 5 39 l8 06 27 44 57 0 8 06 35 57 l6 29 38 l 8 67 06 97 45 84 71 0 3 5 04 48 44 95 02 53 5 图2 - 1 规则格网模型 规则格网存储一般用二维数组实现。用规则格网表示的高程矩阵，具有很多 优点，如用计算机很容易处理、占用内存空间相对较少等。鉴于以上优点，规则 格网模型是表示数字高程模型经常使用的模型之一。 8 硕士学位论文 第二章数字高程模型 用规则格网模型来表示地形也存在一些缺点，如：当采集到的离散数据点分 布不均匀时，规则格网模型不能很好地表示地形的内部特征细节；当采集到的离 散数据点过大时，又会给数据管理带来不便，还需要对数据进行压缩存储。 2 2 2 不规则三角网模型 不规则三角网是另一种表示数字高程模型的方法，对于数字高程模型中的其 它模型，它有着独特的优点。不规则三角网将有限离散点集划分为连续的三角网， 每个三角形的顶点对应一个高程值。如图2 2 所示，离散点集中点的位置和密度 直接影响三角形的大小。 与规则格网相比，不规则三角网在表示数字高程模型方面有以下优点 2 7 1 ： ( 1 ) 生成不规则三角网时，采集的数据随地表的具体形态而变，故不会产 生数据冗余； ( 2 ) 不规则三角网中参与三角网连接的点都是原始采样点，因此能较好的 顾及地面的特征，从而准确表示地形的结构特征和内部的一些细节； ( 3 ) 不规则三角网可以用不同层次的分辨率来描述地形表面，因采集的数 据点随地形变化而变化，故生成t i n 的三角形的密度随地形变化而变化，所以 模拟的地形与实际的地形特征恰好一致。 图2 2 不规则三角网模型 鉴于以上优点，不规则三角网成为一种非常重要的数据模型，并在地理信息 系统的空间分析中广泛应用。 不规则三角网的存储相对规则格网来讲要复杂的多，因为它要存储点的平面 坐标和该点对应的高程值，还要存储边和三角形的拓扑关系等等。不规则三角网 拓扑结构的存储方式有很多种。如图2 3 所示为其中一种存储方式，点文件中存 储点的x ，】，和z 坐标值，三角形文件中存储三个顶点的序号和每个边相邻的三 角形。 9 硕士学位论文 第二章数字高程模型 xyz x 】， z x】，z xj ，z xyz xyz xyz xyz 6 2 5 3 顶点邻接三角形 点文件 三角形文件 图2 - 3 三角网的一种存储方式示意图 2 2 3 等高线模型 由一系列的等高线和与他们相对应的高程值构成的模型称为等高线模型。在 该模型中每一条等高线都有一个高程值，如图2 4 所示。 图2 - 4 等高线模型 如上图所示，等高线可以看作是一个简单的多边形，但该多边形上的点具有 高程值。由于等高线模型中除了等高线上的点外，还有其他的点，故要用等高线 上的点来插值等高线外的点。由上图可以看出，等高线外的点肯定落在两条或多 条等高线之间或等高线与边界边( 边界边的高程值看作零) 之间，故估计这些点 的高程值时，可以用包围这些点的等高线的高程值来插值。存储等高线通常用二 维数组，直接保存等高线上有序的坐标点。但当等高线复杂时，一般用图来存储。 图不仅保存了等高线本身的信息，还保存了不同等高线之间的拓扑结构。 然而，等高线模型一般不用来表示数字高程模型。因等高线稀疏时，即使采 集了所有等高线上的点也不能很好的用这些点来模拟地表。因此，只有将等高线 模型通过局部插值的方法转换成规则格网的数据，才适合进行地表的模拟。 1 0 硕士学位论文第二章数字高程模型 2 3 不规则三角网t i n 的建立 通常用点、边和三角形来描述t i n 。点即采集得到的离散数据。边即两个三 角形的共用边，它也可以包含特征线、断裂线等约束线。三角形由最近的三个点 组成，是用来描述地表形态的基本单元，不能交叉和重叠。 2 3 1 不规则三角网的类型 原始数据点之间可以相互独立，也可以存在某种约束条件。如果数据点之间 完全离散，彼此相互独立，则称这些数据为无约束数据域，如图2 5 ( a ) 所示。 如果采集到的原始数据点中某些数据之间存在约束关系( 比如，采集到的地形数 据中，还包括山脊线、断裂线等) ，则称这些数据为约束数据域。约束关系可以 分为边界约束和内部约束两种。边界约束是指用某一个多边形将所有的离散数据 点包围，该多边形就称为边界约束多边形，如图2 - 6 ( a ) 所示；内部约束是指原 始采集到的数据点中部分数据点之间存在的限制条件，如图2 7 ( a ) 所示。 ( a ) 无约束数据域( b ) 无约束不规则三角网 图2 5 无约束数据域和无约束不规则三角网 ( a ) 边界约束数据域( b ) 边界约束不规则三角网 图2 - 6 边界约束数据域和边界约束不规财三角网 硕士学位论文 第二章数字高程模型 ( a ) 内部约束数据域( b ) 内部约束不规则三角网 图2 7 内部约束数据域和内部约束不规则三角网 建立三角网的原始数据主要包括无约束数据和约束数据两种类型。由无约束 数据建立的不规则三角网，称为无约束三角网，如图2 5 ( b ) 所示；由约束数据 建立的不规则三角网，称为约束三角网，如图2 - 6 ( b ) 和图2 7 ( b ) 所示。约 束t i n 可以更好的顾及地形内部结构特征和细节，因此是广泛使用的一种建模 方法。 2 3 2 不规则三角网的三角剖分 有限点集s 的三角剖分是用不相交的直线段将点集s 连接成不互相重叠的三 角形，且每个三角形都位于点集s 凸壳的内部。正确的三角剖分应满足如下规则 【2 8 】： ( 1 ) 三角形顶点包含了有限点集中的所有点； ( 2 ) 三角形的边不相交； ( 3 ) 所有三角形的集合是有限点集的凸壳。 t i n 三角剖分就是按照三角剖分准则，将采样到的原始数据点用互不相交的 直线段连接形成三角网，然后通过某种结构存储。到目前为止，有很多经典的三 角化算法和许多不同于经典算法的新算法。由于采样到的原始数据分为不规则分 布的数据、规则分布的数据和等高线数据三种，所以对应这三种数据均有相应的 三角剖分方法。对于不规则分布的数据建立三角网主要有数学地形算法、分治算 法、逐点插入算法和三角网生长算法；对于规则分布数据建立三角网主要有循环 迭代算法；对于等高线数据建立三角网主要有特征线算法和探测优化算法【2 9 】。 虽然t i n 能通过将不规则分布的数据点连接成连续但不重叠的三角面来逼 近地形表面，但如果连接的三角形很狭长，则不能精确的表示地形，所以并不是 任意一个三角剖分都是理想的三角剖分。理想的三角剖分应使生成的三角形应尽 可能等角。在所有不规则三角网生成算法中，d e l a u n a y 三角剖分可以很好的满足 1 2 硕士学位论文 第二章数字高程模型 上述性质，同时适用各种数据、唯一性好，可以很好的保持原始数据的精度，因 此广泛用于t i n 的生成。 2 3 3d e l a u n a y 三角网基本概念和性质 v o r o n o i 图又叫泰森多边形，是通过垂直切分一个中心点和它周围点之间的 连线来定义的。v o r o n o i 图的对偶图是d e l a u n a y 三角网，所以人们首先研究 v o r o n o i 图，根据他们之间的对偶关系来研究d e l a u n a y 三角网。如图2 8 表示点 p 的v o r o n o i 多边形。 图2 - 8 点尸的v o r o n o i 多边形 对点集中的每一个点应用上述方法来处理，将得到多个多边形，且这些多边 形彼此连接，称这些相邻的多边形为v o r o n o i 图。图2 - 9 实线是一组由离散点集 组成的v o r o n o i 图。连接v o r o n o i 图中所有相邻的v o r o n o i 多边形的垂直平分线 形成的三角网被称作d e l a u n a y 三角网【2 6 】，如图2 - 9 中虚线所示。 图2 - 9v o r o n o i 图及其对偶图 d e l a u n a y 三角网具有两个非常重要的性质： ( 1 ) 空外接圆性质 点集矿所形成的d e l a u n a y 三角网中，如果每个三角形的外接圆不包含点集 矿中除自身的三个点外的其它点，则d e l a u n a y 三角网满足空外接圆性质。如图 2 1 0 所示，三角形a b c 的外接圆不包含点集中的其它点，满足空外接圆性质。 1 3 硕士学位论文第二章数字高程模型 图2 - 1 0 满足笙外接圆的d e l a u n a y 三角剖分 ( 2 ) 最大最小角性质 用常用方法生成三角网，取三角网中每个三角形的最小角，对这些最小角升 序排列，则d e l a u n a y 三角网中三角形的最小角的数值最大，称为最大最小角准则。 设有两个共边的三角形，q 是由此两个三角形所组成的四边形。当交换q 中的对 角线不会增加两个三角形中6 个内角中的最小角时，称该共边满足最大最小角性 质。如图2 1 1 所示，在四边形a b c d 中，当以边b d 为对角线时，a a b d 和a b c d 中最小角为z c b d 。当以边a c 为对角线时，a a b c 和a a d c 中最小角为z a c d ， 因z a c d 大于z c b d ，所以只有交换对角线，才能满足最大最小角性质。 c db c ( a )( b ) 图2 - 1 1 最大最小角性质示意图 由于这两个性质，使d e l a u n a y 三角网具有很多的优点，所以d e l a u n a y 三角 网不仅应用于地学，而且活跃于与2 5 维分析有关的所有领域【3 0 l 。 2 3 4d e l a u n a y 三角网的建立 由d e l a u n a y 三角网的实现过程得到d e l a u n a y 三角网的三种生成算法：三角 网生长法、逐点插入法和分治法。 b r a s s e l 和r e i f 3 1 】于1 9 9 7 年提出了用三角网生长方法建立d e l a u n a y 三角网。 该算法的主要思路是：首先寻找离散点集中相距最短的两点，将此两点连接成一 条d e l a u n a y 边；然后根据d e l a u n a y 三角网的两个性质( 空外接圆和最大最小角 1 4 硕士学位论文第二章数字高程模型 原则) 找到第三个点，使其构成d e l a u n a y 三角形，按同样的方法处理新生成的 边，直到所有的边均找不到第三点，使其与该边构成d e l a u n a y 三角形。三角网 生长法的主要步骤是： ( 1 ) 取点集中的任意一点，遍历点集找到与该点相距最近的点，连接这两 点生成一条边，作为d e l a u n a y 三角形的第一条边，将该边作为基边； ( 2 ) 按d e l a u n a y 三角网的空外接圆性质和最大最小角性质找到第三点，使 其能与基边构成d e l a u n a y 三角形； ( 3 ) 将第三点分别与基边的两个端点相连，生成两条新边，将这两条新边 也作为基边； ( 4 ) 迭代步骤( 2 ) 和步骤( 3 ) 直到所有的基边都处理完毕。 实现三角网生长法的关键是搜寻出“第三点”，但搜寻“第三点 的算法改 进十分有限，所以，现在三角网生长法已很少使用。 l a w s o n 首先提出了逐点插入法建立d e l a u n a y 三角网【3 2 】。l e e 、s c h a c h t e r 和 s l o a n 先后对逐点插入法进行了发展和完善 3 3 】。逐点插入法建立d e l a u n a y 三角网 的思想是：首先生成一个初始三角网，该三角网包含所有已知的数据点；然后按 顺序将没有处理过的数据点插入到已经生成的初始三角网中，生成新的三角网； 最后用l a w s o n 的局部优化( l o c a lo p t i m i z a t i o np r o c e d u r e ，l o p ) 算法优化新生 成的三角网，使其成为d e l a u n a y 三角网。逐点插入算法的主要步骤为： ( 1 ) 建立一个初始多边形，该多边形包含所有离散点数据； ( 2 ) 通过初始多边形建立初始三角网，然后迭代步骤( 3 ) 和步骤( 4 ) ，直 到所有数据点都处理完毕为止； ( 3 ) 插入一个未处理过的数据点，搜索该点所在的三角形，然后连接该点 和该三角形的三个顶点，生成三个新的三角形； ( 4 ) 用l o p 算法优化新生成的三角网，使其成为d e l a u n a y 三角网。 实现逐点插入法的关键是如何快速定位插入点的位置，目前出现了很多快速 定位算法，其中比较完善的是快速三角形定位算法，它通过网格点三角形的策 略来定位点所在的三角形。 l e e 和s c h a c h t e r l 3 4 提出了用分治算法生成d e l a u n a y 三角网，分治算法又称 分割归并算法。该算法的思想是：首先划分离散点集为两个子集，使这两个子 集中点的数量近似相等，并且两个子集不能互相重叠；然后对两个子集分别生成 15 硕士学位论文第二章数字高程模型 d e l a u n a y 三角网；最后合并两个子d e l a u n a y 三角网并生成最后的三角网，用l o p 算法对最后的三角网进行优化，使之成为d e l a u n a y 三角网。l e e 和s c h a c h t e r 的 分治算法的基本步骤是： ( 1 ) 对点集y 进行排序，排序的方式为先按横坐标升序排序，如果横坐标 相同，则按纵坐标升序排序，然后递归地执行以下步骤； ( 2 ) 划分点集为两个近似相等且不互相重叠的子集； ( 3 ) 分别对两个子集中的数据点生成三角网： ( 4 ) 用局部优化算法( l o p ) 优化生成的两个子三角网，使之成为d e l a u n a y 三角网： ( 5 ) 找出连接两个子三角网的凸壳的底线和顶线； ( 6 ) 由底线至顶线合并两个三角网。 分治算法虽然效率很高，但分治算法实现过程中要划分子网，合并子网，故 前期和后期处理繁琐。近年来，经过许多学者的不断研究出现了很多与三种经典 算法思路不同的d e l a u n a y 三角剖分算法，如贪心算法【3 5 1 、扫描线算法【3 6 1 和凸壳 算法f 3 刀。 2 4 约束三角网 实际采集到的离散数据中，部分数据之间可能存在某种制约关系，比如地表 中可能存在山脊线、断裂线、河流等。如果忽略这些制约条件，仅仅生成无约束 数据域的三角网，则生成的数字高程模型不能正确的反应复杂的地表。因此需要 将这些约束条件强行嵌入，使生成的三角网更精确地模拟地表。在二维情况下， 约束关系主要分两种情况1 3 8 - 4 0 ：一种情况是离散数据中包含由有向折线组成的约 束线段；另一种情况是离散数据中包含约束多边形。约束d e l a u n a y 三角剖分 ( c o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n ，简称c d t ) 是指在离散点数据中带有约束 线段或约束多边形的情况。 2 4 1 基本概念 定义2 - 1 平面直线图( p l a n a rs t r a i g h tl i n eg r a p h ，p s l g ) ，由离散点的集合 p = ( p 。，p ：，p 。) 以及由离散点组成的直线段( 约束边) 的集合 l = p ，p ，fp ，p ，p ) ( p ，p ，为直线段的两个端点) 组成，并且三中任意两条直 线段不相交，但端点可以落在其他直线段上。根据上述定义带约束条件的三角网 1 6 硕士学位论文 第二章数字高程模型 可以看作一个平面直线图。 定义2 - 2 可见点：p = p l ，p 2 ，p 。 cp ，t 是p 的三角剖分，插入一个新 点，记作足，设点足位于r 外，对于任意的p ，p ，如果p ；专p 不与r 中任 意一个三角形