空间几何关系分析ppt课件.ppt

《空间几何关系分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《空间几何关系分析ppt课件.ppt（136页珍藏版）》请在三一办公上搜索。

1、第5章 空间几何关系分析,5.1 邻近度分析,邻近度（Proximity）是定性描述空间目标距离关系的重要物理量之一，表示地理空间中两个目标地物距离相近的程度。,5.1.1 缓冲区分析,缓冲区 是指为了识别某一地理实体或空间物体对其周围地物的影响度而在其周围建立的具有一定宽度的带状区域。缓冲区分析 则是对一组或一类地物按缓冲的距离条件，建立缓冲区多边形，然后将这一图层与需要进行缓冲区分析的图层进行叠加分析，得到所需结果的一种空间分析方法。 缓冲区分析适用于点、线或面对象，如点状的居民点、线状的河流和面状的作物区等。,基本原理,5.1.1 缓冲区分析,道路中心线,基本原理,5.1.1 缓冲区分析

2、,从数学的角度看，缓冲区分析的基本思想是给定一个空间对象或集合，确定其邻域，邻域的大小由邻域半径R决定，因此对象Oi的缓冲区定义为：Bi = x | d (x, Oi) R，即半径为R的对象Oi的缓冲区，Bi为距Oi的距离小于等于R的全部点的集合，d一般指最小欧氏距离，但也可以为其他定义的距离，如网络距离，即空间物体间的路径距离。对于对象集合 O = Oi | i=1, 2, , n，其半径为R的缓冲区是各个对象缓冲区的并集，即 ：,基本原理,5.1.1 缓冲区分析,邻域半径R即缓冲距离（宽度），是缓冲区分析的主要数量指标，可以是常数或变量。 空间对象还可以生成多个缓冲带。,基本原理,5.1.

3、1 缓冲区分析,根据研究对象影响力的特点，缓冲区可以分为均质与非均质两种。,基本原理,5.1.1 缓冲区分析,矢量数据缓冲区的建立方法,缓冲区建立方法, 点要素的缓冲区,5.1.1 缓冲区分析,矢量数据缓冲区的建立方法, 线要素的缓冲区,缓冲区建立方法,5.1.1 缓冲区分析,矢量数据缓冲区的建立方法, 面要素的缓冲区,缓冲区建立方法,5.1.1 缓冲区分析,栅格数据缓冲区的建立方法,缓冲区建立方法,栅格数据的缓冲区分析通常称为推移或扩散（Spread），推移或扩散实际上是模拟主体对邻近对象的作用过程，物体在主体的作用下沿着一定的阻力表面移动或扩散，距离主体越远所受到的作用力越弱。,5.1.1

4、 缓冲区分析,缓冲区建立方法,5.1.1 缓冲区分析,动态缓冲区,缓冲区建立方法,现实世界中很多空间对象或过程对于周围的影响并不是随着距离的变化而固定不变的，需要建立动态缓冲区，根据空间物体对周围空间影响度的变化性质，可以采用不同的分析模型。, 当缓冲区内各处随着距离变化，其影响度变化速度相等时，采用线性模型； 当距离空间物体近的地方比距离空间物体远的地方影响度变化快时，采用二次模型； 当距离空间物体近的地方比距离空间物体远的地方影响度变化更快时，采用指数模型。,5.1.1 缓冲区分析,缓冲区实现有两种基本算法：矢量方法和栅格方法。,缓冲区实现的基本算法,5.1.1 缓冲区分析,角分线法,缓冲

5、区实现的基本算法,角分线法简单易行，但算法存在不足： 难以最大限度地保证缓冲区左右边线的等宽性；校正过程复杂；算法模型欠结构化。,5.1.1 缓冲区分析,缓冲区实现的基本算法,凸角圆弧法,凸角圆弧法对于凸部的圆弧处理使其能最大限度地保证左右平行曲线的等宽性，避免了角分线法所带来的异常情况。,凸角圆弧法原理,5.1.1 缓冲区分析,凸角圆弧法的算法实施步骤为,缓冲区实现的基本算法, 直线性判断为简化计算过程，凸角圆弧法的第一步是进行相邻三点的直线性判断。当相邻三点处于近似共线状态时，用直线代替。常用的直线性判断方法是点到直线距离法，即直接利用解析几何中的距离公式 其中，Ax+By+C = 0为过

6、首末点的直线方程，x、y为相邻三点中相对中间点的坐标，d为该中间点到直线Ax+By+C = 0的距离，当d小于某一给定值时，相邻三点可视为直线，简化计算过程。,5.1.1 缓冲区分析,缓冲区实现的基本算法,凸角圆弧法的算法实施步骤为, 折点凸凹性的判断凸角圆弧法的关键在于对凸凹部分的不同处理，因此折线顶点处的凸凹特性的判断是非常重要的步骤，它能确定何处需要用圆弧连接而何处需要用直线求交。这个问题可转化为两个矢量的叉积：把相邻两个线段看成两个矢量，其方向取为坐标点序方向。若前一个矢量以最小的角度扫向第二个矢量时呈逆时针，则为凸顶点，反之，为凹顶点。, 凸顶点圆弧的嵌入设圆弧的始边与终边分别为 、

7、 ，其坐标形式分别为： ， ，为弦弧逼近误差（如图所示）。其中， ， ， ， 。,5.1.1 缓冲区分析,凸角圆弧法的算法实施步骤为,缓冲区实现的基本算法, 边线关系的判别和处理当轴线的弯曲空间不能容许左右平行曲线无压盖地通过时，就产生边线自相交问题，形成若干个自相交多边形，如图所示。自相交多边形分为两种情况：岛屿多边形与重叠区多边形。,边线多边形的形成,5.1.1 缓冲区分析,缓冲区实现的基本算法,岛屿多边形&重叠区多边形及其自动识别：矢量数据格式表示的曲线具有方向性，取曲线坐标串的方向为曲线前进的方向。当中心轴线被取定方向后，其两侧的平行曲线也就自然地获得了左右属性，称左边线和右边线。对于

8、左边线，岛屿多边形呈逆时针方向；对于右边线，岛屿多边形呈顺时针方向。对于重叠区多边形左边线呈顺时针方向；右边线呈逆时针方向,5.1.1 缓冲区分析,缓冲区实现的基本算法,凸角圆弧法的算法实施步骤为, 缓冲区边界的最终形成将重叠区进行合并绘制出最外围边线，同时绘出岛屿轮廓，就形成了最终的缓冲区边界。要注意的是，利用缓冲区进行检索的时候，按最外围边线所形成的圆头或方头缓冲区检索之后，要扣除按所有岛屿进行检索的结果。,5.1.1 缓冲区分析,数学运算法,矢量栅格转换法,矢量栅格混合法,对缓冲区内的栅格赋上一个与其影响度惟一对应的值，如果发生重叠的区域具有相同的影响度，则取任一值；如果发生重叠的区域具

9、有不同影响度等级，则影响度小的服从于影响度大的。,缓冲区实现的基本算法,5.1.1 缓冲区分析,缓冲区作为一个独立的数据层可以参与叠加分析，常应用到道路、河流、居民点、工厂（污染源）等生产生活设施的空间分析，为不同工作需要（如道路修整、河道改建、居民区拆迁、污染范围确定等）提供科学依据。结合不同的专业模型，缓冲区分析能够在景观生态、规划、军事应用等领域发挥更大的作用。例如，利用缓冲区分析和相邻缓冲区的景观结构总体变异系数方法对自然保护区进行自然景观和人为影响景观的分割研究。在虚拟军事演练系统中，缓冲区分析方法是对雷达群的合成探测范围和干扰效果进行研究的一种非常有效的手段。,缓冲区分析应用,为了

10、能根据离散分布的气象站降雨量数据来计算某地平均的降雨量，荷兰气候学家A.H.Thiessen提出了一种新的计算方法，即将所有相邻气象站连成三角形，作三角形各边的垂直平分线，每个气象站周围的若干垂直平分线便围成一个多边形，用这个多边形内所包含的惟一一个气象站的降雨强度来表示这个多边形区域内的降雨强度，该多边形称为泰森多边形（Thiessen Polygons或Thiessen Tesselations，又称Voronoi或Dirichlet多边形）。,5.1.2 泰森多边形分析,泰森多边形及其特性,其几何定义为：设平面上的一个离散点集P = P1, P2, , Pn ，其中任意两个点都不共位，即

11、Pi Pj（i j, i1, 2, , n, j1, 2, , n），且任意四点不共圆，则任意离散点Pi 的泰森多边形的定义为在泰森多边形 Ti 中，任意一个内点到该泰森多边形的发生点 Pi 的距离都小于该点到其他任何发生点 Pj 的距离。这些发生点 Pi（i1, 2, , n）也称为泰森多边形的控制点或质心（Centroid）。,5.1.2 泰森多边形分析,泰森多边形及其特性,泰森多边形因其生成过程的特殊性，具有以下一些特性：,5.1.2 泰森多边形分析,泰森多边形及其特性,Delaunay三角网是由与相邻泰森多边形共享一条边的相关点连接而成的三角网，它与泰森多边形是对偶关系。,5.1.2

12、泰森多边形分析,Delaunay三角网的构建,5.1.2 泰森多边形分析,Delaunay三角网具有以下特征：Delaunay三角网是惟一的；三角网的外边界构成了给定点集的凸多边形“外壳”；没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网（如图）。如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化” 的三角网。,Delaunay三角网的构建,凸包插值算法凸包插值算法是Tsai在1993年提出的在n维欧拉空间中构造Delaunay三角网的一种通用算法

13、，包括三个主要步骤：,5.1.2 泰森多边形分析,Delaunay三角网的构建,泰森多边形建立过程：建立Delaunay三角网，对离散点和形成的三角形进行编号，并记录每个三角形是由哪三个离散点构成的；找出与每个离散点相邻的所有三角形的编号，并记录下来； 将与每个离散点相邻的所有三角形按顺时针或逆时针方向进行排序；计算出每个三角形的外接圆圆心，并记录下来；连接相邻三角形的外接圆圆心，即可得到泰森多边形。对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。,5.1.2 泰森多边形分析,泰森多边形的建立,泰森多边形的栅格算法实现过程 一种栅格算法是先将图形栅格化为数字图像

14、，然后对该数字图像进行欧氏距离变换，得到灰度图像，而泰森多边形的边一定处于该灰度图像的脊线上；再通过相应的图像运算，提取灰度图像的这些脊线，就得到最终的泰森多边形。另外还可采用以发生点为中心点，同时向周围相邻八方向做栅格扩张运算（一种距离变换），两个相邻发生点扩张运算的交线即为泰森多边形的邻接边，三个相邻发生点扩张运算的交点即为泰森多边形的顶点。,泰森多边形的建立,用栅格方法得到的泰森多边形,5.1.2 泰森多边形分析,5.2 叠加分析,5.2.1 叠加分析概述,叠加分析是指将同一地区、同一比例尺、同一数学基础，不同信息表达的两组或多组专题要素的图形或数据文件进行叠加，根据各类要素与多边形边界

15、的交点或多边形属性建立具有多重属性组合的新图层，并对那些在结构和属性上既相互重叠，又相互联系的多种现象要素进行综合分析和评价；或者对反映不同时期同一地理现象的多边形图形进行多时相系列分析，从而深入揭示各种现象要素的内在联系及其发展规律的一种空间分析方法。,5.2.1 叠加分析概述,地理空间数据的处理与分析目的是获得空间潜在信息，叠加分析是非常有效的提取隐含信息的工具之一。例如，将全国水文监测站分布图与政区图叠加，得到一个新的图层，既保留了水文监测站的点状图形及属性，同时附加了行政分区的属性信息，据此可以查询水文站点属于哪个省区，或者查询某省区内共有多少个水文站点；又如将某区域的土地利用类型图与

16、土壤pH值状态图、地下水埋深图、植被覆盖图等专题地图叠加，生成新的图层后按照湿地的定义形成属性判别标准，从而判断该区域是否为湿地。,将一个点层作为输入图层叠加到一个多边形图层上，即通过计算点与多边形线段的相对位置，来判断这个点是否在多边形内，从而确定是否进行属性信息的叠加。,5.2.2 空间要素图形叠加,点与多边形的叠加,点与多边形叠加分析,将一个线图层作为输入图层叠加到一个多边形图层上，要进行线段与多边形的空间关系判别，主要是比较线上坐标与多边形的坐标，判断线段是否落在多边形内。,5.2.2 空间要素图形叠加,线与多边形的叠加,线与多边形叠加分析,5.2.2 空间要素图形叠加,多边形与多边形

17、的叠合是指将两个不同图层的多边形要素相叠合，产生输出层的新多边形要素，用以解决地理变量的多准则分析、区域多重属性的模拟分析、地理特征的动态变化分析，以及图幅要素更新、相邻图幅拼接、区域信息提取等。,多边形与多边形的叠加,层1属性：地貌层2属性：土壤结果层属性：地貌、土壤,5.2.2 空间要素图形叠加,多边形与多边形的叠加,根据叠加结果要保留不同的空间特征，常用的GIS软件通常提供了三种类型的多边形叠加分析操作，即并、叠和、交。,矢量数据属性叠加处理更多地使用逻辑叠加运算，即布尔逻辑运算中的包含、交、并、差等。,5.2.3 空间要素属性叠加,矢量数据叠加分析,栅格数据中对于同一区域、同一比例尺、

18、同一数学基础的不同信息表达的要素来说，其栅格编号不会发生变化，即对于任意栅格单元用作标识的行列号I0、J0是不变的，进行叠加的时候只是增加了属性表的长度，下表表示进行多重叠加后的栅格多边形的数据结构：,栅格数据叠加分析,5.2.3 空间要素属性叠加,栅格数据来源复杂，叠加分析操作的前提是要将其转换为统一的栅格数据格式，如BMP、GRID等，且各个叠加层必须具有统一的地理空间，即具有统一的空间参考（包括地图投影、椭球体、基准面等），统一的比例尺以及具有统一的分辨率（即像元大小）。 栅格数据的叠加分析操作主要通过栅格之间的各种运算来实现。可以对单层数据进行各种数学运算如加、减、乘、除、指数、对数等

19、，也可通过数学关系式建立多个数据层之间的关系模型。,5.2.3 空间要素属性叠加,栅格数据叠加分析,基于不同的运算方式和叠加形式：,5.2.3 空间要素属性叠加,栅格数据叠加分析,栅格叠加变换类型：,局部变换每一个像元经过局部变换后的输出值与这个像元本身有关系，而不考虑围绕该像元的其他像元值。,5.2.3 空间要素属性叠加,栅格数据叠加分析,邻域变换如果要计算某一像元的值，就将该像元看作一个中心点，一定范围内围绕它的格网可以看作它的辐射范围，这个中心点的值取决于采用何种计算方法将周围格网的值赋给中心点，其中的辐射范围可自定义。,5.2.3 空间要素属性叠加,栅格数据叠加分析,分带变换将同一区域

20、内具有相同像元值的格网看作一个整体进行分析运算，称为分带变换。,5.2.3 空间要素属性叠加,栅格数据叠加分析,全局变换全局变换是基于区域内全部栅格的运算，一般指在同一网格内进行像元与像元之间距离的量测。,5.2.3 空间要素属性叠加,栅格数据叠加分析,在距离量测中像元间距离考虑全部的源数据，且要求像元间距离最短，但没有考虑其他因素如运费等。成本距离量测运算比空间距离量测运算要复杂得多，需要另一个格网来定义经过每个像元的成本或阻抗。,5.2.3 空间要素属性叠加,栅格数据叠加分析,栅格逻辑叠加栅格数据中的像元值有时无法用数值型字符来表示，不同专题要素用统一的量化系统表示也比较困难，故使用逻辑叠

21、加更容易实现各个栅格层之间的运算。图层之间的布尔逻辑运算包括：与（AND）、或（OR）、非（NOT）、异或（OR）等。,布尔逻辑运算示例,5.2.3 空间要素属性叠加,栅格数据叠加分析,假设某市政府要在辖区范围内选择理想地点建立一个垃圾场，有关垃圾场的选址条件如下所述：区域地表物质应具有低渗透率，以阻止可溶性物质快速渗入地下水中；区域与现有市政区域范围保持一定距离；区域不属于环境敏感区；区域应属于农业区，而非市政区或工业区；区域的地表平均坡度平稳，并小于某个极限值；区域不发生洪水。,5.2.3 空间要素属性叠加,栅格数据叠加分析,二值逻辑叠加模型：根据垃圾场选址条件组织有关图件资料，包括表土渗

22、透性图、城区范围图、生态敏感度分布图、城乡区划图、地表坡度图和洪泛区分布图等。建立垃圾场选址的模型。该模型将以上图层结合起来进行布尔逻辑运算，结果生成二值图，其中值为1的地点表示满足上述垃圾场选址的全部条件，值为0则表示不满足选址条件。,5.2.3 空间要素属性叠加,栅格数据叠加分析,具体模型如下：将各个图层二值化（TRUE，FALSE）或（0，1）。本例中各层数据的布尔逻辑条件如下：Ca = 地表渗透性级别为低级；Cb = 距离城区边界的距离1km；Cc = 生态敏感性为不敏感级别；Cd = 土地利用类型为农业用地；Ce = 地表坡度 2；Cf = 不属于洪泛区范围。对于各输入数据层的布尔逻

23、辑条件变量进行逻辑与运算，在区域某位置点上如果所有数据层的条件变量都是所要求的值，则结果变量OUTPUT为“1”，其他情况下为“0”。OUTPUTCa AND Cb AND Cc AND Cd AND Ce AND Cf生成二值图。满足条件的位置就是二值图中值为“1”的地点。,5.2.3 空间要素属性叠加,栅格数据叠加分析,5.3 网络分析,5.3.5流分析,5.3.6动态分段技术,5.3.4资源分配,5.3.7地址匹配,5.3.1网络分析概述,5.3.3连通分析,5.3.2最佳路径分析,5.3.1 网络分析概述,网络分析 是通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络

24、结构及其资源等的优化问题进行研究的一种空间分析方法。网络分析的理论基础是图论和运筹学。在地理信息系统中，网络分析功能依据图论和运筹学原理，在计算机系统软硬件的支持下，将与网络有关的实际问题抽象化、模型化、可操作化，根据网络元素的拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连结、连通关系），通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算，从而为制定系统的优化途径和方案提供科学决策的依据，最终达到使系统运行最优的目标。,5.3.1 网络分析概述,在城市之间建立通讯网络，使其中任意两个城市之间都有直接或间接的通讯联系，假设已知每两个城市之间通讯线路的成本，要求

25、找出一个成本最低的通讯网络。,图论中的基本概念,5.3.1 网络分析概述,图论中的“图”是指由点集合V和V中点与点之间的连线的集合E构成的二元组（V, E）。V 中的元素称为结点，E 中的元素称为边。图论中所研究的图是由实际问题抽象出来的逻辑关系图，图中点和线的位置与曲直无关紧要，点的多少和每条线是连接哪些点才是关键。,图论中的基本概念,5.3.1 网络分析概述,图论中的基本概念,两个端点重合的边称为环。如果有两条边的端点是同一对顶点，则称这两条边为重边。既没有环也没有重边的图，称为简单图。如果图中的边是有向的，则称为有向图，其中的边叫做弧。在无向图中，首尾相接的一串边的集合叫做路。在有向图中

26、，顺向的首尾相接的一串边的集合叫做有向路。如果一个图中，任意两个结点之间都存在一个路，则称之为连通图。起点和终点为同一个结点的路称为回路（或圈）。如果一个连通图中不存在任何回路，则称为树。任意一个连通图，去掉一些边后形成的树叫做连通图的生成树。,5.3.1 网络分析概述,给定一个图，图中的每一条边赋以一个实数，称这种数为边的权数，称这种图为赋权图。赋以权数的有向图称为赋权有向图，也可称之为网络。根据需要赋权有向图中的一条边，必要时可以赋以多个权值，另外也可以给结点赋权，称为点权网络，相对于点权网络，给边赋权的网络称为边权网络。在机器实现中，邻接矩阵表示法、关联矩阵表示法、邻接表表示法是用来描述

27、图与网络常用的方法。,图论中的基本概念,5.3.1 网络分析概述,邻接矩阵 用来表示图中任意两点间的邻接关系及其权值。如果两点间有一条弧，则邻接矩阵中对应的元素为 1；否则为 0（也可用表示两点间无任何连接关系），邻接矩阵为对称矩阵。对于加权图的邻接矩阵表示，一条弧所对应的元素不再是1，而是相应的权值。,图论中的基本概念,5.3.1 网络分析概述,关联矩阵 中，每行对应图的一个节点，每列对应图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。,图论中的基本概念,5.3

28、.1 网络分析概述,图的邻接表 是图中所有节点邻接表的集合。,图论中的基本概念,5.3.1 网络分析概述,网络数据模型是现实世界网络系统（如交通网、通讯网、自来水管网、煤气管网等 ）的抽象表示。按照几何形态，空间实体被抽象为点、线、面目标，构成网络的最基本元素是线性实体以及这些实体的连接交汇点。前者称为网线或链（Link），后者称为结点（Node）。链（Link） 链是构成网络的骨架，是现实世界中各种线路的抽象和资源传输或通信联络的通道，可以代表公路、铁路、街道、航线、水管、煤气管、输电线、河流等。链包括图形信息和属性信息，链的属性信息包括阻碍强度和资源需求量，链的阻碍强度是指在通过一条链时所

29、需要花费的时间或者费用等，如资源流动的时间、速度。链是有方向的，当资源沿着网络中的不同方向流动时所受到的阻碍强度可能相同，也可能不同。,网络数据模型,5.3.1 网络分析概述,结点（Node）结点是网线的端点，又是网线的汇合点，可以表示交叉路口、中转站、河流汇合点等，其状态属性除了包括阻碍强度和资源需求量等，还有下面几种特殊的类型。 障碍（Barrier）：禁止资源在网络中的链上流动的点。 拐点（Turn）：出现在网络链中的分割结点上，状态属性有阻碍强度，如拐弯的时间和限制（例如在8：00到18：00不允许左拐等）。在地理网络中，拐点对资源的流动有很大影响，资源沿着某一条链流动到有关结点后，既

30、可以原路返回，也可以流向与该结点相连的任意一条链，如果阻碍强度值为负数，则表示资源禁止流向特定的弧段。,网络数据模型,5.3.1 网络分析概述,结点（Node） 中心（Center）：网络中具有一定的容量，能够接受或分配资源的结点所在的位置。如水库商业中心、电站、学校等，其状态属性包括资源容量（如总量）阻碍强度（如中心到链的最大距离或时间限制）。资源容量决定了为中心服务的弧段的数量，中心的阻碍强度是指沿某一路径到达中心所经历的弧段总阻碍强度的最大值。 站点（Stop）：在路径选择中资源增减的结点，如库房车站等，其状态属性有两种，一种是站的阻碍强度，它代表与站有关的费用、时间等，如在某个库房装卸

31、货物所用时间等；一种是站的资源需求量，如产品数量、学生数、乘客数等。站的需求量为正值时，表示在该站上增加资源；若为负值，则表示在该站上减少资源。,网络数据模型,5.3.1 网络分析概述,网络分析功能路径分析路径分析是GIS中最基本的功能，其核心是对最佳路径的求解。从网络模型的角度看，最佳路径的求解是在指定网络的两个结点之间找一条阻碍强度最小的路径。另一种路径分析功能是求解最佳游历方案，又分为弧段最佳游历方案求解和结点最佳游历方案求解两种。连通分析现实中常需要知道从某一结点或边出发能够到达的全部结点或边，这一类问题称为连通分量求解；另一类连通分析问题是求解最少费用连通方案，即在耗费最小的情况下使

32、全部结点相互连通。,网络分析功能,5.3.1 网络分析概述,网络分析功能资源分配资源分配也称定位与分配问题，包括目标选址和将需求按最近（这里远近是按加权距离来确定的）原则寻找供应中心（资源发散或汇集地）两个问题。流分析 流是资源在结点间的传输。流分析问题主要是按照某种优化标准（时间最少、费用最低、路程最短或运送量最大等）设计的运送方案，网络流理论是其基础理论。,网络分析功能,5.3.1 网络分析概述,网络分析功能动态分段动态分段技术是GIS网络分析中一种基于网络线的动态分析、显示和绘图技术。通过建立一种比“弧段结点”数据模型高级的“动态段动态结点”模型，来实现根据不同的属性按照某种度量标准对线

33、性要素进行相对位置的划分。 地址匹配地址匹配实质是对地理位置的查询，涉及到地址的编码。地址匹配与其他网络分析功能结合起来，可以满足实际工作中复杂的分析要求。,网络分析功能,5.3.2 最佳路径分析,最佳路径分析也称最优路径分析，以最短路径分析为主。这里“最佳”包含很多含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无论判断标准和实际问题中的约束条件如何变化，其核心实现方法都是最短路径算法。 最短路径问题从算法研究

34、的角度考虑最短路径问题通常可归纳为两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。,5.3.2 最佳路径分析,Dijkstra算法基本思想其基本思路是：假设每个点都有一对标号（dj, pj），其中dj是从起源点 s 到点 j 的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj 则是从s到 j 的最短路径中 j 点的前一点。 初始化。起源点设置为ds = 0，ps为空，并标记起源点s，记k = s，其他所有点设为未标记点。 检验从所有已标记的点 k 到其直接连接的未标记的点j的距离，并设置dj = mindj, dk+lkj，其中，lkj为

35、从点k到j的直接连接距离。 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i，di = mindj, 所有未标记的点 j ，点i就被选为最短路径中的一点，并设为已标记的点。 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，记为i = j* 标记点i。如果所有点已标记，则算法完全推出，否则记k = i，重复步骤。,最短路径算法,5.3.2 最佳路径分析,左图为某一带权有向图，若对其施行Dijkstra算法，则所得从V0到其余各顶点的最短路径以及运算过程中距离的变化情况如右表所示。,最短路径算法,5.3.2 最佳路径分析,弗洛伊德算法其基本思想是：假设求从顶点

36、Vi 到 Vj 的最短路径。若从Vi 到 Vj 有弧，则从Vi 到 Vj 存在一条长度为 dij 的路径，该路径不一定是最短路径，需要进行 n 次试探。首先判别弧（Vi, V1）和弧（V1, Vj）是否存在。如果存在，则比较（Vi, Vj）和（Vi, V1, Vj）的路径长度，较短者为从Vi 到 Vj 的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点V2，若路径（Vi, , V2）和路径（V2 , , Vj）分别是当前找到的中间顶点的序号不大于1的最短路径，那么后来的路径（Vi, , V2 , , Vj）就有可能是从Vi 到 Vj 的中间顶点的序号不大于 2 的最短路径。将它和已

37、经得到的从Vi 到 Vj 的中间顶点的序号不大于 1 的最短路径相比较，从中选出中间顶点的序号不大于 2 的最短路径之后，再增加一个顶点 V3，继续进行试探。依次类推，在经过 n 次比较之后，最后求得的必是从Vi 到 Vj 的最短路径。,最短路径算法,5.3.2 最佳路径分析,矩阵算法该算法是利用矩阵来求出图的最短距离矩阵。算法步骤可表示为：,最短路径算法,5.3.2 最佳路径分析,最佳路径分析在汽车导航系统和各种应急系统（如110报警、119火警以及医疗救护系统等）中应用非常广泛，系统应用需求决定了最佳路径分析应是高效率的，比如一般要求计算出到出事地点的最佳路径的时间必须是在13s内，且在行

38、车过程中需要实时计算出车辆前方的行驶路线。但前面介绍的三种算法在时间复杂度上都不尽如人意，很难满足不断发展的各种系统的要求，从而促使人们考虑从各个角度解决其实现的效率问题。针对不同的网络特征、应用需求及具体的软硬件环境，各种最短路径算法不断涌现，在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。,最短路径算法的优化,5.3.2 最佳路径分析,以路径分析应用最广泛的交通道路网络为例，提供一个解决实际问题的基本模式。假定某地区交通管理部门接到举报在该区域内某一地点发生交通事故，需要有关人员立刻赶到现场，选择一条路途最短的行进路线到达指定地点。在解决问题之前要了解交通网络数据的基本特征。首

39、先，对于一定区域范围内庞大的交通网络要考虑它的存储结构，既要有利于网络分析算法的实现，又能够在节约存储空间的前提下根据需要扩充数据，对交通网络进行综合分析。然后是网络搜索，主要依据求解单源点间最短路径的戴克斯徒拉算法思想，同样也可以对其进行优化改进以提高效率。根据实际应用的需要，首先将网络边的权值设为两结点间的距离，并定义沿着起点到终点的方向为空间有效方向，相反的方向为无效方向；然后赋给网络边、结点相应的字段值，并定义站点、拐点、桥梁等特殊地物的属性，最后通过具体的程序设计来实现搜索过程。,路径分析的实现,5.3.3 连通分析,在地理网络中从某一点出发能够到达的全部结点或边有哪些，如何选择对于

40、用户来说成本最小的线路，即连通分析所要解决的问题。连通分析的求解过程实质上是对应的图的生成树的求解过程，其中研究最多的是最小生成树问题。,基本概念,5.3.3 连通分析,连通性是图论的一个重要概念。在无向图G = (V, E)中，如果从顶点Vs到顶点Vt有路径，则称Vs和Vt是连通的。如果对于图G中的任意两个顶点Vi,VjV，Vi和Vj都是连通的，则称G为连通图。,基本概念,5.3.3 连通分析,一个连通图的生成树是含有该连通图的全部顶点的一个极小连通子图，包含三个条件： 它是连通的； 它包含原有连通图的全部结点； 它不含任何回路。依据连通图的生成树的定义可知，若连通图G的顶点个数为n，则G的

41、生成树的边数为n-1；树无回路，但不相邻顶点连成一边，就会得到一个回路；树是连通的，但去掉任意一条边，就会变为不连通的。,基本概念,5.3.3 连通分析,从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次，这一过程叫做图的遍历。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。,基本思想是：从图中的某个顶点出发，然后访问任意一个该点的邻接点，并以该点的邻接点为新的出发点继续访问下一层级的邻接点，从而使整个搜索过程向纵深方向发展，直到图中的所有顶点都被访问过为止。,从图中的某个顶点出发，访问该顶点之后依次访问它的所有邻接点，然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至

42、所有顶点都被访问到为止。,基本概念,5.3.3 连通分析,图（a）是一个具有8个结点的网络图，对其分别进行深度优先搜索和广度优先搜索，其搜索过程如图（b）和（c）。,基本概念,5.3.3 连通分析,克罗斯克尔（Kruskal）算法是1956年提出的，俗称“避圈法”。设图G是由m个结点构成的连通赋权图，则构造最小生成树的步骤如下：,最小生成树算法,5.3.3 连通分析,构造最小生成树的另一个著名算法Prim算法的基本思想是：假设N = (V, E)是连通网，生成的最小生成树为T = (V, TE)，求T的步骤如下：,最小生成树算法,5.3.3 连通分析,图1中带权图最小生成树求算过程如图2所示。

43、,最小生成树算法,5.3.4 资源分配,在多数的应用中，需要解决在网络中选定几个供应中心，并将网络的各边和点分配给某一中心，使各中心所覆盖范围内每一点到中心的总的加权距离最小，实际上包括定位与分配两个问题。定位是指已知需求源的分布，确定在哪里布设供应点最合适的问题；分配指的是已知供应点，确定其为哪些需求源提供服务的问题。,5.3.4 资源分配,选址功能涉及在某一指定区域内选择服务性设施的位置，如确定市郊商店区消防站工厂飞机场仓库等的最佳位置。 选址问题的数学模型取决于可供选择的范围，以及所选位置的质量判断标准这两个条件。在一个地理网络中，能够从网络的结点和边上找到一些特定的点使它们满足某种优化

44、条件，这些点可用于较简单的定位问题。,选址问题（定位问题）,5.3.4 资源分配,给定一个地理网络D =（V, E），其中V表示地理网络结点的集合，E表示地理网络边的集合。令 d(p, q)表示从顶点 p 到顶点 q 之间的距离；令R表示矩阵，矩阵的第 p、q 个元素是 d(p, q)，矩阵R的元素称为顶点顶点距离（Vertex-vertex Distance，VVD）； 表示从网络边（vi, vj）上的f_点到结点 q 之间的距离，这个长度称为点顶点距离（Point-vertex Distance，PVD）；表示从顶点到网络边（vi, vj）的最大距离，此长度称为顶点弧距离（Vertex-a

45、rc Distance）。,选址问题（定位问题）,5.3.4 资源分配,从顶点p到任一顶点的最大距离从顶点p到所有顶点的总距离从顶点p到所有弧的最大距离从顶点p到所有弧的总距离 从网络边（vi, vj）上的f_点到任一结点的最大距离 从网络边（vi, vj）上的f_点到所有各结点的总距离,选址问题（定位问题）,5.3.4 资源分配,基于以上变量的定义，给出有关中心点和中位点的概念。使最大距离达到最小的位置称为网络的中心点，使最大距离总和达到最小的位置称为网络的中位点。一个地理网络的中心点主要有中心、一般中心、绝对中心和一般绝对中心等；一个地理网络的中位点主要有中位点、一般中位点、绝对中位点和一

46、般绝对中位点等。,选址问题（定位问题）,5.3.4 资源分配,地理网络的中心点是网络中距最远结点最近的一个结点vx，即地理网络的一般中心是距最远点最近的一个结点vx，即地理网络的绝对中心是距最远结点最近的任意一点vx，即地理网络的一般绝对中心是距最远点最近的任意一点vx，即,选址问题（定位问题）,5.3.4 资源分配,地理网络的中位点是从该点到其他各结点有最小总距离的一个结点vx，即地理网络的一般中位点是从该点到其他各结点有最小总距离的一个结点vx，即地理网络的绝对中位点是从该点到所有各结点有最小总距离的任意一点，即地理网络的一般绝对中位点是从该点到所有各条网络边有最小的总距离的任意一点，即,

47、选址问题（定位问题）,5.3.4 资源分配,实例分析现有一指定邮区，需在该邮区范围内的5个城市中选择一个城市作为中心局所在地。将城市用图的顶点表示，各顶点之间的连线表示各城市间邮件的进、出和转口的关系，连线的权值则设为两城市间运送邮件所耗费的成本，邮件的运送成本包含诸如路程长短、邮运工具、业务量的大小、邮件的流向及经转次数等因素。,选址问题（定位问题）,5.3.4 资源分配,首先先求出 R 矩阵。可利用 Floyd 算法或 Dantzig 算法求出 R 矩阵。,R 矩阵,选址问题（定位问题）,5.3.4 资源分配,如果选择以中心点法为标准，得到的顶点指的是该顶点所代表的城市与其他城市间的邮件往

48、来的最大成本为最小。可以先求出从城市1到其他各个城市的运送邮件的最大成本，然后依次求出城市2、3、4、5到其他各个城市运送邮件的最大成本，计算过程如下：,选址问题（定位问题）,从顶点4到其他顶点的最大距离为3，即从城市4向其他城市运送邮件的最大成本为最小，可知邮区中心局地址设置在该城市，可保证从邮区中心局到该邮区的其他收投点的邮件的最大运送成本为最小。,5.3.4 资源分配,如果选择以中位点法为标准，则求出的中位点的实际意义表示从该点向其他城市运送邮件的总成本为最小。根据中位点的数学表达式要先求出SVV（i）：,选址问题（定位问题）,由此得即顶点4是该邮区的中位点，从城市4向其他各城市运送邮件

49、的总成本为最小。,5.3.4 资源分配,分配问题 在现实生活中体现为设施的服务范围及其资源的分配范围的确定等一类问题，资源的分配能为城市中的每一条街道上的学生确定最近的学校，为水库提供其供水区等。资源分配是模拟资源如何在中心（学校、消防站、水库等）和周围的网线（街道、水路等）、结点（交叉路口、汽车中转站等）间流动的。,分配问题,5.3.4 资源分配,实际生活中，许多行业和部门都涉及到利用服务设施提供相关服务的问题，常见的服务范围有：到服务设施或中心的最短距离不超过一定范围的覆盖区域，如一个供水站50公里以内的区域，构成该供水站的供水区；到服务设施或中心的最短时间不超过一定限制的覆盖区域，如一个

50、消防站10分钟所能到达的范围是该消防站在10分钟的服务范围。中心服务范围分析作为基本网络分析功能，是指一个服务中心在给定的时间或范围内能够到达的区域，它为评价服务中心的位置及其通达性提供了有利工具。,分配问题,5.3.4 资源分配,确定中心服务范围的基本思想是依次求出服务费用不超过中心阻值的路径，组成这些路径的网络结点和边的集合构成了该中心的服务范围。主要步骤为：,分配问题,5.3.4 资源分配,具体求解中心资源的分配范围时与服务范围的搜索方法类似，设D =（V, E, c）为一给定的带中心的地理网络， P为满足资源分配范围条件的网络边和网络结点的集合。算法的主要步骤如下： 将中心所在的结点作