典型山区供水管网离散优化布置分析——以贵州纳雍金蟾供水工程为例 90页

'·三峡大学全日制专业学位硕士学位论文1绪论1.1研究背景与意义按照水质、水量、用水方便程度等指标衡量，目前全国尚有3亿多山区农村人口（中西部地区占80%）饮水未达到安全标准[1]。长久以来，由于山区地形条件复杂，交通不便，经济不发达等原因，导致我国大部分山区农村饮水安全问题特别突出。贵州省毕节市纳雍县水资源总量8.1亿m3，由于受地形地质条件影响，水资源开发利用率很低。农村的用水都是靠山体内蓄存流放出来的地下水，农村缺水面大、难度高。其中纳雍县羊场乡、姑开乡、锅圈岩乡和维新镇都是以农业为主的乡镇，在灌区范围内有耕地137872亩，人口109442人，大牲畜22915头。受地形地势和水文地质条件限制，水低田高，取水十分困难。四乡镇蓄水、引水、提水工程比较少，农田灌溉困难。部分耕地靠山塘供水，用水时段受到很大的限制。靠近河流的耕地由于距河高差较大，依靠电力提灌，成本非常高。耕地由于受用水影响，农作物产量非常低，农业经济发展慢，当地人民生活水平低，每逢大旱年，致使河流断流，大量农作物干死，粮食颗粒无收。四乡镇的居民主要分布在河流分水岭地带、切割较深的台地上，无饮水水源保证和存在饮水水质安全隐患，急需新建灌溉引水水源。输配水管网是山区农村饮水安全工程中供水系统的重要组成部分，在整个供水系统中管网部分的投资最高，一般要占到工程总投资的60%～80%[2]。供水管网的优化布置能减少埋管工程的总投资，也能缩短输水距离、降低输水能耗和减少输水成本。然而，山区供水工程设计中管网布置一直根据经验确定，缺乏科学的理论与方法。供水管网优化布置的首要工作就是求出控制点间的最短曲线线程，即该曲面地形的测地线。由于山区地形复杂而难以用数学函数来表征，导致测地线方程不能得到解析解，管网优化便陷入困境。因此，复杂地形条件下的最短线路问题一直没有得到很好的解决。另外，山区供水管网工程一般布置成树状结构，然而，最小树方法虽然能对平面管网进行最优化处理，但在山区极其复杂的情况下，需考虑过陡的山头或悬崖等地形构造特征，平面最小树方法不再适合这种复杂地形的管网优化布置。本课题将以贵州省毕节市纳雍县灌溉区管网布置为研究对象，采用离散化地形表征技术，生成山区复杂地形条件下的两点最短线程模型，开发复杂地形中的最小树形图生成方法，构建管网优化的Steiner最小树形图模型，以解决复杂地形的部分·· ·1万方数据·· ·三峡大学全日制专业学位硕士学位论文输配水节点已确定需增设节点的管线优化问题，完成整个管网布置工程设计工作。本课题为典型山区供水管网浅埋管优化布置提供理论技术依据，有重要的工程意义和科学价值。1.1国内外研究现状管网优化发展至今，已经成为一个比较成熟的理论。各种优化设计理论方法层出不穷。国外从60年代就开始研究线性规划、非线性规划、动态规划等管网优化设计的方法，在这一领域取得了一些成果[3]。随着计算机技术的进步，我国从20世纪80年代开始研究供水管网的系统优化设计问题，供水管网优化研究得到进一步的发展。管网优化的主要内容分为管径优化、工作方式优化和管网布置优化三方面。本文主要研究管网布置的优化方法。布置优化是管网优化的重要内容，对减少运行费和节省管网投资具有十分重要的作用。但由于管网优化布置需要综合考虑地形、作物种植等多方面因素，同时还需要借助设计人员经验，难度大，为此需要从数字地面模型、最短路径以及最小树等方面进行研究。1.2.1数字地面模型研究现状数字地面模型的概念是在1958年由美国麻省里工学院的Milier教授提出，并成功地运用到公路的勘测设计中[4]。在近60年的发展中，DTMs的理论和应用不断地得到发展与完善。特别是在现今的信息社会中，DTMs对社会各行业如城市规划、农业、水利等的重要性日益明显，同时DTMs也是数字地球海量数据库的主要组成部分，是数字地球的数学基础，是三维虚拟现实的基本框架。数字地面模型属于计算机图形学的一个分支，是以数字的形式按一定的结构组织在一起、从离散数据结构出发构造相互连接的网络结构，表示实际地形特征的空间分布，从而建立起相关区域内平面坐标与高程间的映射关系。它是对地形表面在地形采样数据基础上的表面重构。如果采样数据为高程，则为数字高程模型(DigitalElevationModle，DEM)[5]。在数字地面模型的研究早期，由于不规则三角网数据结构复杂，计算机自动生成算法不成熟，数字地面模型多采用规则格网。近年来经过众多学者的不断研究，不规则三角网逐渐成熟，尤其是顾及地物限制的边界一致的三角网格理论和算法有所突破，加上计算机软硬件对三角片的显示支持，三角网数字地面模型的显示速度得到大幅度提高。不规则三角网格模型正在成为数字地面模型的主流。在目前所有的三角化算法中，由于Delaunay三角网具有空外接圆和最小角最大性质，决定了Delaunay三角网具有极大的应用价值，它形成的三角形具有整体最优特性，因而成·· ·2万方数据·· ·三峡大学全日制专业学位硕士学位论文为一种最流行的三角剖分方法。作为数字高程模型（DEM）的一种主要表达方式，Delaunay三角剖分的概念最初是由俄国数学家Delaunay为了解决离散数据的剖分问题，在二十世纪四十年代提出来的，并提出了相应三角剖分算法。但是三角剖分技术的快速发展和广泛应用是在80年代以后，伴随着计算机技术的迅猛发展，大规模计算和图像显示问题得到了有效的解决，同时来自计算机图像学技术的需求，三角剖分技术在最近几十年里有了长足的发展，并且被广泛的应用到社会的多个领域。三角剖分问题的实质就是要研究平面上离散数据点之间的相互邻接关系，并且将这种邻接关系以三角网的形式表现出来，所以三角剖分方法按照邻接关系的标准不同，可以被分为许多不同的三角剖分方法。在所有邻接关系表示标准中，Voronio图的标准是应用最为广泛的，Voronio图的对偶图就是一个Delaunay三角网。以Voronio图的相关理论作为理论基础，最初是R.Sibson与P.J.Green等人给出了很多三角剖分算法的纯数学理论研究[6]，这些研究使得三角剖分理论更加的严密。之后又经过A.Bowyer和D.F.Waston提出了一系列不同三角剖分算法，使得三角剖分领域的研究有了突破性的进展[7]-[8]。之后，由于三角剖分在越来越多领域得到广泛的应用，又有更多的三角剖分算法相继被提了出来，这些算法的主要研究重点是在实际应用中如何提高三角剖分算法的效率问题，已经如何解决三维空间复杂实体的三角剖分问题。这期间，很多比较经典的算法被提了出来，如局部变换法，单元生长法，四叉树或者八叉树法等，这些三角剖分算法各有各的优缺点，在实际应用中的话也如果仅仅使用同一个优化标准的话也不能满足不同需求，因此各个领域的研究人员根据各自领域的需求围绕原有算法中存在的一些问题提出了大量的改进算法，以满足特点领域的实际应用问题。宁慧[9]根据DEM数据及视觉中心相关地形简化的特点，提出了一种基于网络划分的实时简化算法。该方法首先将DEM栅格数据分成以视点为中心的数据块，利用视觉相关的误差简化算法实现了DEM数据的快速动态分层与地形平滑，其次利用三角形剖分方法最终消除了裂缝，对实际数据的实验结果验证了算法的有效性。KennethP.Bowman[10]就球面上求解Helmhohz方程的问题提出了一个多重网格有限差分法。该解算方法适用于球面上的一般椭圆型方程，对不宜做均匀网格距求解的一些问题也是有用的。但离散误差较大。刘堃[11]结合等值线的特性介绍了基于规则网格的等值线生成算法，为规则网格的优化提供依据。高艳等[12]选取项目区内的115个离散样本数据，通过选用不同的内插方法以及改变规则网格的大小对DEM精度进行分析，并确定所选用的规则网格大小。半规则网格在视差估计上也有较广泛的应用[13]。但3·· ·万方数据·· ·三峡大学全日制专业学位硕士学位论文规则网格不能准确表示地形的结构和细部，需要采用附加地形特征数据,如地形特征点、山脊线、谷底线、断裂线等，以描述地形结构。其另一个缺点是数据量过大，要进行压缩存储，给数据管理带来了不便。等高线模型的应用也较为广泛，它被广泛应用在各种地图和地理信息系统中，是二维手段表示三维物体的常用方法，可以直接利用Delaunay三角形对等高线上的点进行三维地形造型。但由于等高线自身的特点使得到的地表模型具有明显的等高线的台阶痕迹，所以通常不直接采用该方法构造地表模型，而是将等高线数据转换为网格数据，即数字高程模型(DigitalElevationModel,DEM)。不规则三角网模型（即TIN）能够根据地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置,因而它能够避免地形平坦时的数据冗余,又能按地形特征点如山脊线、山谷线、地形变化线等表示数字高程特征，是一种比较理想的地表模型。刘学军[14]等指出，与Grid结构相比，TIN能以更加灵活的方式在不同层次和空间上表达更复杂的地形表面，当地形数据中含有特征线如山脊线、山谷线、断裂线等时，TIN比Grid更能方便地表示之。陈甜甜等[15]针对逆向工程中的三角网格重构问题，提出了一种保持尖锐特征的版规则三角网格模型细分曲面重构算法，充分利用了细分曲面的多分辨特性。在三角网格的优化方面，蒲浩[16]运用数字地面模型，在生成初始三角形后，采用队列及平衡二叉树等数据结构进行三角网的扩展，通过点集分块改进点的搜索方法，减少了搜索时间，并用LOP算法优化网形。这种算法生成的带状数字地面模型已成功地应用于铁路和公路的勘测设计中。本文选取Delaunay不规则三角网模型对山区地面进行离散化表达，为管网优化提供精确地地形要素。1.1最短路径问题研究现状在保证供水质量的前提下，管网优化的关键在于寻求一条最短供水管线线路，也就是传统的最短路径问题。最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。1959年Dijkstra对最短路径提出有效算法以来，为提高算法效率，许多研究者由基本问题提出许多子问题。图论与计算机数据结构及算法的有效结合，产生了众多新算法。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。早期的最短路径算法是根据Bellman原理[17]，将最短子路径相加求节点对间的最短路径。标号算法作为研究最为成熟、应用最为广泛的最短路径算法集，其本质是应用Bellman原理求解，它采用顺推的方法，对图的每一边检测一次，没有重复·· ·4万方数据·· ·三峡大学全日制专业学位硕士学位论文的回溯搜索，因此标号法是一种最佳算法。目前，绝大多数最短路径算法都是在标号算法基础上，通过采用不同的数据结构、节点选取策略以及生成树更新技术而开发出不同实现形式。根据从集合中选取当前扫描节点的不同，搜索策略分为广度优先搜索、深度优先搜索和启发式搜索3种。广度优先和深度优先搜索不考虑路段的权重，在地理网络路径搜索中意义不大，但在社会关系网络研究中应用广泛；而启发式搜索策略考虑路段权重，它能减少搜索空间，在地理网络路径分析中应用很广。李帮义、姚恩瑜[18]提出利用遗传算法求最短路径，可得到问题的满意解；周培德[19]在《计算几何》中对平面中最短路径问题进行了讨论，将其归为“计算几何中运动规划的基本问题”。平面内带障碍物的最短路描述为:给定平面内两点s0和t0及多边形障碍物集合n:{w1，w2，⋯，wk}，求从s0到t0的避开所有多边形障碍物的最短路径。目前在GIS应用领域，对最短路径搜索问题的研究和应用较多，其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题。所采用的算法主要是来源于图论领域中的称为Dijkstra的算法，该算法运行的结果是某一顶点到其它所有顶点的最短路径。刘敏[20]根据Dijkstra算法的基本思想，选择合适的数据结构表示图，实现求解最短路径的Dijkstra算法。鲍培明[21]通过Dijkstra算法在动态权值系统中的应用体现Dijkstra算法在城市交通信息系统中重要性。传统Dijkstra算法在通用性和完备性的意义上无疑是非常优秀的，但基于GIS空间分布特征和GIS中最短路径查找的具体情况，其在算法本身的改进及效率的进一步提高是完全有必要的。李赉年[22]在Dijkstra算法的基础上，通过减少加法与比较运算次数来提高计算效率；KubyM[23]和ErkutE[24]在Dijkstra算法的基础上通过极大极小法提出了相异路径求解方法，解决了最短路径的P扩散问题；Ahmed和Mustaq[25]设计一种连续Dijkstra算法，来计算实际地面上两点间的最短下坡距离(shortestdescendingpath，SDP)；JozefowiezN[26]研究了航空线路在意外事件发生后的重规划问题，在航空公司费用和乘客满意度之间达到最优平衡；FaramrozeG[27]开发了一种新的动态规划方法来解决固定费用的最短路径问题；Lozano等[28]构建配套约束的最短路径模型，用以解决机组调度和乘务员排班问题；张水舰等[29]分析了网络弧和节点的动态随机特性及其相互关系，定义了动态随机最短路径，给出了动态随机最短路径优化数学模型，提出了一种动态随机最短路径遗传算法。花玲玲[30]结合GIS公路交通的空间分布特征和查找最短路径的具体情况，分析了传统最短路径算法在这种特定应用中的不足和改进的思路，编程实现了一个充分利用了GIS中空间分布特征的改进算法。5·· ·万方数据·· ·三峡大学全日制专业学位硕士学位论文1.1最小树问题研究现状最小树问题，是一个熟知的有着广泛应用意义的图论问题。在交通、通讯、管道、渠道等系统中，许多最优连接问题都归结为求一个无向连通图的最小支撑树，目前已有许多算法[31]。Kruskal算法就是利用MST[32]性质构造最小生成树的算法。杨小影[33]针对Kruskal算法思想及其在网络技术中的应用，对该算法进行分析并改进，并给出该算法的VB实现。王伟等[21]对Kruskal算法进行研究，降低了该算法的时间复杂度，在理论上，介绍了该算法的求解时间。PrimeDijkstra算法是求最短路径的最基本和使用最广泛的算法。章永龙[34]、王志和[35]等分别对节点邻居进行处理和采用配对堆结构实现对该算法的优化处理。虽然这两种方法计算所得的结果均比较接近最优解，但它们仅仅适用于平面上最小树优化。而实际情况往往需要求出多个最小树，以便进一步考虑其它优劣指标和约束条件，从中选出既优越又便于实施的方案来。多种最优方案的再选择在实际应用上的重要性，促使我们从数学上提出求全部最小树问题。与此有关的求全部支撑树间题，在电路分析方面极受重视，曾出现过一系列重要的工作。特别是oummins[36]提出树图的概念，并证明了树图的Hamilton性。随后Kamae[37]又给出树图和性的构造性证明，并提供求全部支撑树的深探型算法(不同于Mayeda—seshu的广探型算法)[38]。不久后shank[39]给出了树图H-性的一个极短的证明。至于如何求全部最小树，迄今未见文献中讨论。林诒勋[40]仿照树图的定义，证明最小树图的Hamilton性，建立求全部最小树的算法，并得到最小树图的Hamilton圈。权矩阵法[41]是通过权矩阵计算来实现Dijkstra算法的一种方法，该算法在复杂度上比Dijkstra算法更高一些，特别是在大型网络中求最小树时有太多的冗余运算。孙小军[42]针对权矩阵法在大型网络应用中的不足，在提高算法效率方面对其进行改进，降低了其计算复杂度。破圈法是一种相对简单的计算最小树的方法，该方法对于数学知识不多的实际工作者来说，更容易接受，同时计算复杂度也较低。但此方法仅限于图纸上工程的计算[43]。蚂蚁算法[44]对于一些度限制极其苛刻且网络图呈稀疏状态的问题方面表现出了相当好的性能，它能克服其它一些方法甚至找不出可行解来的弊病。模拟退火算法[45]是基于蒙特卡罗迭代方法的一种随机搜索算法。它用于求解组合优化问题的出发点是基于物理学中晶体物质的退火过程与一般组合优化问题之间的相似性。该方法在某些参数设定下速度较快，但得到的解并不一定是最优解[46]。在最小树问题的研究中，最经典的还是steiner最小树问题。steiner最小树问题是经典的组合问题，最早可以溯源到17世纪初。以瑞士数学家steiner的名字命名。6·· ·万方数据·· ·三峡大学全日制专业学位硕士学位论文经典Steiner树问题大体包括欧氏的、绝对值距离的、图的等几个重要方面。欧氏Steiner最小树是指对给定欧氏平面上的原点集P(也称正则点集)，找出连接P的最短网络。严蔚敏[47]在数据结构一书中给出了有关欧氏Steine最小树的理论。金慧敏[46]分别采用模拟退火法和蚂蚁算法对欧氏Steiner最小树问题作了智能性优化，并通过实验得出两种优化方法都有各自的优点（模拟退火法的速度较快，蚂蚁算法的结果更接近于最优解）。绝对值距离的Steiner最小树问题由Hanan[48]首次提出，1977年，Garey，Graham以及Johnson等人证明了欧氏的和绝对值的Steiner最小树问题属于NP难题[49]。因此，GareyM[50]用求点集P的最小生成树来代替求取近似解。图的Steiner树(GraphicalSteinerMinimumTree，简记GSMT)问题由Hakimi和Levin于1971年首次提出[51]。GSMT问题亦为NP难题，无法在多项式时间内得到最优解[52]。图的Steiner树问题的精确算法如Hakimi[53]的时间的算法，它枚举所有可能的Steiner点并计算相应的树长。Hakimi算法适于|P|接近于|V|的情况，而动态规划算法则适用于|P|较小时的情形。1.1研究内容、技术路线及创新点1.2.1研究内容本课题研究内容主要分为以下几部分：第一章，绪论。主要介绍本课题研究的背景和意义，国内外关于数字地面模型、最短路径及最小树问题的研究现状以及其研究内容、研究方法、技术路线等。第二章，山区供水管网优化布置方法。从山区管网优化布置的角度，分析山区复杂地形离散化、最短路径以及管网布置最小树等的求解方法，为供水管网优化布置提供理论依据。第三章，供水工程复杂地形离散化表达。主要利用施工测量的地形点坐标，构建三角网来拟合复杂的地表曲面，克服复杂地形无表征函数和不可展开性而使最短路径无法获得解析解的问题，实现复杂地形的格网显示，为最短路径的数值解法建立基础模型。第四章，三角网显示下点对间最短线程计算。为计算格网显示的地面两点间的近似最短线路，将网格模型转化成边权有向网络，计算带权网络上两点间的最短线路，并迭代细分最短线路邻域内的边以构造新的带权网络求解。在细分顶点的基础上，对邻域进行扩展以提高最短线路邻域内的边的细分效率。第五章，管网布置的最小树形图生成与优化。给定空间的配水点的点集，要求在关于拓扑网络边的约束条件下选择边的子集形成使管网极小化的网络，即复杂地7·· ·万方数据·· ·三峡大学全日制专业学位硕士学位论文形中的最小树问题。本课题结合山区地形因素，通过引入最小入弧圈概念，来构建山区地形中带约束的最小树生成方法。由于某些地形(悬崖峭壁)不适合进行管网布置，即在其他适合管网布置的地形处增加某些被称为Steiner点的附加点，形成新的管网。这时可能舍弃适合地形不用而绕行会使总的管线更短。第六章，研究结论与展望。通过方法与模型的结合，得到典型山区供水管网布置的优化方法，阐述本文的创新点，并提出相关方面的更深层次值得探讨的问题。1.1技术路线本文将以贵州省毕节市纳雍县灌溉区管网布置为研究对象，利用施工测量的地形点坐标，采用离散化地形表征技术，构建三角网来拟合复杂的地表曲面；将网格模型转化成边权网络，生成山区复杂地形条件下的两点最短线程模型；在给定供水端点的条件下求解复杂地形中的最小树形图，构建管网优化的Steiner最小树形图模型，以解决复杂地形的部分输配水节点的管线优化问题。技术路线如图1所示：典型山区供水管网离散优化布置研究工程概况分析地形离散化管网优化最短线程计算地形点数据处理确定管网布线方式采用Delaunay三角网格划分方法对复杂地形进行离散化处理选择布线已知点采用边权无向网络求解最短线程管网优化布置的最小树计算采用分离法计算带约 束的管网最小树优化结果加入Steiner点，计算 管网的Steiner最小树图1.1论文研究的技术路线1.2课题创新点创新点：1)构建山区复杂地形的格网显示模型，开发基于最短管线线程的三角网格划分方法。·· ·8万方数据·· ·三峡大学全日制专业学位硕士学位论文2)将山区复杂地形离散化显示后，加入离散点间的距离权值，形成边权网络，求解最短管线线程，提出GIS数据与图论网络之间的转化方法。3)提出复杂地形条件下Steiner最小树的构建方法，解决Steiner树选点困难等问题。1.1论文研究方法⑴文献研究法。通过大量的文献检索，对以往的研究成果进行综述与回顾，从而对相关研究概念甲乙界定。根据研究的需要对现有的研究成果加以总结、归纳与整合，在此基础上提出本研究的框架。⑵模型建立法。主要运用数字地面模型对供水区域地形进行离散化表达；采用图论相关知识对管网布置的优化工作进行分析，结合图论中的最短路径方法，最终确定供水管网管线最短的优化方案，减少供水管网布置工程的用钢量，降低工程成本。⑶案例分析法。本文以贵州纳雍金蟾供水工程为实际工程案例，分析其地形地质条件，采用相适应的数字地面模型和图论优化方法，最终得到适合本工程的供水管网布置的优化方案。·· ·9万方数据·· ·三峡大学全日制专业学位硕士学位论文2山区供水管网优化布置方法1.1Delaunay三角网格划分算法概述在计算机应用普遍的当下，数字地面模型的发展也日趋完善，在众多的数字地面模型类型中，离散点三角网数字地面模型是选线设计的最佳选择。这种数字地面模型以原始的地形点为顶点建立不规则的三角网，其建网过程是采用线性内插方法，这种方法具有内插精度高，内插简便，便于考虑地性线的影响等优点。这些优点使得在建模过程中不仅能减少规则建网造成的数据冗余，同时在计算复杂度方面又比基于等高线的建网方法有优势，尤其是在地形坡度较为复杂的情况下。因此，不规则三角网模型是GIS中非常重要的一种用于空间计算的数据模型。目前三角网格优化算法已经很多，且发展日趋成熟。随着技术发展的纯熟，老算法将不断地得到完善，同时也会出现更好的新的算法。所以对所有算法进行分类是不容易的，一般而言，地形数据通常呈规则分布、不规则分布以及等高线数据三种类型，对于不规则地形点数据，Delaunay三角网格划分方法无疑是最合适的选择。1.2.1Delaunay三角网格划分定义Delaunay三角划分是一种特殊的三角划分，它是在一般三角划分的基础上增加对Delaunay边的定义，以此定义Delaunay三角网。1）三角网格划分：假设V是实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段,E为边e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：⑴除了端点，平面图中的边不包含点集中的任何点；⑵没有相交边；⑶平面图中所有的面都是三角面，且所有三角面的合集就是点集V的凸包。2）Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足存在一个圆经过a,b两点，圆内不含点集V中任何的点，这一特性又称空圆特性，则称之为Delaunay边。3）Delaunay三角划分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角划分。由于Delaunay三角网格划分具有最大角最小化和空圆特性等优点，在数字地面模型中应用普遍。·· ·10万方数据·· ·三峡大学全日制专业学位硕士学位论文1.1Delaunay三角网格划分方法通常情况下，我们将Delaunay的各种算法分为三类：分割—归并算法、逐点插入法以及三角网生长法。1)分割—归并算法该算法是由Lee和Schachter[54]提出的，它的基本思想就是“分离—合并”，即将数据点集划分成两个相互独立的子集，各自生成Delaunay三角网后再合并。考虑到可能有约束条件，Lawson[55]尝试把初始点集划分成小区域的竖条，这些竖条均垂直于X轴，同时问题的约束条件又将其划分为更小的区域，再各自生成Delaunay三角网，最后根据约束条件合并。徐青[56]等提出了基于自适应分块的TIN三角网划分方法，这种算法与Lawson算法的不同在于如何划分源数据上。其优点是能够运用于地形的表达上，山区地形一般较复杂，源数据点的分布也极不均匀。通常情况下，平原等相对平坦的地区点击分布较稀疏，而山地、沟谷等地的点集分布比较密集，若按照Lawson的思想划分成同样的大小的子集，则根据点的密集度计算时间相差就会非常大。TIN三角网格划分方法就是根据实际地形，动态设置子集的大小，灵活变化子集的阈值，控制子集点数的下限值。2)逐点插入法逐点插入法的基本步骤是首先构建一个初始三角网，把不在初始三角网内的数据点根据要求插入到初始三角网内，直到所有点都入网即结束，然后再运用LOP算法优化三角网。LOP算法其实就是一个对角线交换的过程，即对三角网中共边的两个三角形作空外接圆检测，若不满足空外接圆法则，则交换四边形内公共边形成的对角线形成两个新的三角形，新形成的两个三角形一定满足空外接圆准则，如图2.1所示:图2.1LOP优化3)三角网生长法该算法是由Brassel和Reif[57]于1979年提出的。三角网生长算法的的基本思路是首先在点集中距离最短的两点，相互连结形成Delaunay边，然后根据Delaunay边三角网的判别法则寻找包含此边的Delaunay三角形的第三个顶点，对新生成的边再次判别寻找下一个点，直至所有点入网。三角网生长法的实现方法有很多，这些方法的主要不同都是如何寻找第三点。·· ·11万方数据·· ·三峡大学全日制专业学位硕士学位论文McCullagh和Ross[58]通过把点进行排序和点集分块，以此改进点搜索方法，减少了搜索时间。凌海滨[59]等对三角网增长算法作出改进，他们提出了封闭点（如图3.2）的概念，即在三角网的生成过程中将封闭点动态地剔除，减少需查找的点集的数量，从而加快三角形生成的速度。P图2.2封闭点P1.1基于最短路径的三角网格划分空间数据点的三角划分算法是数字地面模型建立的核心。在管线布置过程中，三角划分算法应能满足线路设计对它的要求，即对地形域数据点适应能力强、占用系统资源少、运行效率高、三角形结构良好等特点。综合分析以上三种算法，本文采用了逐点插入算法。1.2算法步骤zkq20150910逐点插入算法的基本步骤可归纳为:1）建立初始三角网：如图2.3所示，求出给定点集的包容盒，将包容盒沿对角线剖分为两个初始三角形，然后按以下步骤迭代，直到所有的数据点入网。（Xmax，Ymin）A1A2（Xmin，Ymin）（Xmin，Ymax）图2.3点集的包容盒2)定位三角形：从点集中取出一点，在已建立的三角网中找到包含该点的三角形，如图2.4(a)。·· ·12万方数据·· ·三峡大学全日制专业学位硕士学位论文图2.4逐点插入过程3)确定影响域：从包含该点的三角形开始，根据空外接圆法则，找出外接圆内包含当前插入点的三角形集，三角形集的外边界即为影响域，如图2.4。空外接圆检测方法根据公式2.1计算:图2.5空外接圆特性测试InCircle(d,a,b,c)=aaa+axyxybbb+bzkq20150910xyxyccc+cxyxyddd+dxyxy1111（2.1）当计算结果小于0，则表示d点在∆abc外接圆的内测；等于0时，在外接圆上；大于0时，在外接圆外侧。4)影响域内的三角网重构：将影响域内的三角形删除，对影响域内的点集进行三角网重构。重构方法是将以插入点作为公共顶点，将影响域的各边界点与当前插入点顺次连接(如图2.4(c))，得到的三角网即为D-三角网。5)当所有点插入完毕，删除边界上的冗余三角形，完成地形离散化。1.1最短路径概念与算法1.2.1最短路径相关概念1)路径路径是指在一个图G(N,M)中存在从节点V到节点V的点边交替出现序列0n(v,e,v,e,v,e,+)中，如果其中每条边只出现一次，则称之为简单路径，如011223nn1果同一个节点只出现一次，则称其为基本路径。赋权图的任意两点间的最短距离可用一个矩阵表示。设n阶有向或无向连通赋权图G(V,E)，其中顶点集，边集。设两·· ·13万方数据·· ·三峡大学全日制专业学位硕士学位论文顶点，间的最短距离为，其中则图G的最短距离矩阵的元素定义为=。2)最短路径最短路径问题是图论中的一个常用的问题，目的是寻找连通图中两节点之间的最短路径。其具体的形式包括：①起点最短路径问题：起始节点是已知的，求最短路径的问题。②终点最短路径问题：与问题①相反，即终止节点已知，求最短路径的问题。③起点终点最短路径问题：已知起点和终点，求两结点之间的最短路径。④全局最短路径问题：求图中所有存在的最短路径。3)网络一个具体的网络可以抽象为一个由节点集和边集组成的图G(V,E)。N=V为节点数，M=E为边数，集合E中的每一条边都与集合V中的一每一对节点都是一一对应的。由于网络中边的有向性，网络又可分为有向网络（directednetwork）和无向网络（undirectednetwork）。有向网络指的是任意节点对(i,j)和(j,i)对应边是不同的，而无向网络的节点对(i,j)和(j,i)表示相同的边。如果对无向网络的每条边赋予一个权值，那么网络就变zkq20150910成了无向有权网络。如图2.6就是个无向有权网络。图2.6无向有权网络4)邻接矩阵与关联矩阵⑴图的邻接矩阵：设图G(V,E)是一个有向图，其中V包含n个节点，如果各个节点之间存在从到的边，其中1