第5章空间几何关系分析

1、第第5章章 空间几何关系分析空间几何关系分析 5.1 邻近度分析邻近度分析5.2 叠加分析叠加分析5.3 网络分析网络分析5.1 邻近度分析 邻近度（Proximity）是定性描述空间目标距离关系的重要物理量之一，表示地理空间中两个目标地物距离相近的程度。 泰森多边形分析泰森多边形分析 5.1.15.1.2缓冲区分析缓冲区分析 5.1.1 缓冲区分析缓冲区分析 缓冲区缓冲区 是指为了识别某一地理实体或空间物体对其周围地物的影响度而在其周围建立的具有一定宽度的带状区域。缓冲区分析缓冲区分析 则是对一组或一类地物按缓冲的距离条件，建立缓冲区多边形，然后将这一图层与需要进行缓冲区分析的图层进行叠加分

2、析，得到所需结果的一种空间分析方法。 缓冲区分析适用于点、线或面对象，如点状的居民点、线状的河流和面状的作物区等。基本原理基本原理5.1.1 缓冲区分析缓冲区分析道路中心线道路中心线基本原理基本原理5.1.1 缓冲区分析缓冲区分析 从数学的角度看，缓冲区分析的基本思想是给定一个空间对象或集合，确定其邻域，邻域的大小由邻域半径R决定，因此对象Oi的缓冲区定义为：Bi = x | d (x, Oi) R，即半径为R的对象Oi的缓冲区，Bi为距Oi的距离小于等于R的全部点的集合，d一般指最小欧氏距离，但也可以为其他定义的距离，如网络距离，即空间物体间的路径距离。对于对象集合 O = Oi | i=1

3、, 2, , n，其半径为R的缓冲区是各个对象缓冲区的并集，即 ：niiBB1基本原理基本原理5.1.1 缓冲区分析缓冲区分析（a） 不同宽度缓冲区干流支流 邻域半径R即缓冲距离（宽度），是缓冲区分析的主要数量指标，可以是常数或变量。 空间对象还可以生成多个缓冲带。基本原理基本原理（b）环状缓冲区5.1.1 缓冲区分析缓冲区分析具有不同特性的缓冲区（a）静态缓冲区a = b （b）动态缓冲区a b abaaba 根据研究对象影响力的特点，缓冲区可以分为均质与非均质两种。 基本原理基本原理5.1.1 缓冲区分析缓冲区分析 矢量数据缓冲区的建立方法 缓冲区建立方法缓冲区建立方法（a）单点形成的缓冲

4、区 （b）点群形成的缓冲区 （c）分级点形成的缓冲区点形成的缓冲区形式 点要素的缓冲区5.1.1 缓冲区分析缓冲区分析 矢量数据缓冲区的建立方法 线要素的缓冲区线形成的缓冲区形式（a）单线形成的缓冲区 （b）多线形成的缓冲区 （c）分级线形成的缓冲区缓冲区建立方法缓冲区建立方法5.1.1 缓冲区分析缓冲区分析 矢量数据缓冲区的建立方法 面要素的缓冲区面形成的缓冲区形式（a）单一面形成的缓冲区 （b）多个面形成的缓冲区 （c）分级面形成的缓冲区缓冲区建立方法缓冲区建立方法5.1.1 缓冲区分析缓冲区分析 栅格数据缓冲区的建立方法 缓冲区建立方法缓冲区建立方法栅格数据的缓冲区分析通常称为推移或扩散

5、（Spread），推移或扩散实际上是模拟主体对邻近对象的作用过程，物体在主体的作用下沿着一定的阻力表面移动或扩散，距离主体越远所受到的作用力越弱。 5.1.1 缓冲区分析缓冲区分析缓冲区建立方法缓冲区建立方法5.1.1 缓冲区分析缓冲区分析 动态缓冲区缓冲区建立方法缓冲区建立方法现实世界中很多空间对象或过程对于周围的影响并不是随着距离的变化而固定不变的，需要建立动态缓冲区，根据空间物体对周围空间影响度的变化性质，可以采用不同的分析模型。 当缓冲区内各处随着距离变化，其影响度变化速度相等时，采用线性模型； 当距离空间物体近的地方比距离空间物体远的地方影响度变化快时，采用二次模型； 当距离空间物体

6、近的地方比距离空间物体远的地方影响度变化更快时，采用指数模型。5.1.1 缓冲区分析缓冲区分析 缓冲区实现有两种基本算法：矢量方法和栅格方法。缓冲区实现的基本算法缓冲区实现的基本算法矢量方法使用较广，产生时间较长，相对比较成熟，具体的几何算法是中心线扩张法，又称加宽线法或图形加粗法，通过以中心轴线为核心做平行曲线，生成缓冲区边线，再对生成边线求交、合并，最终生成缓冲区边界。栅格方法以数学形态学扩张算法为代表，采用由实体栅格和八方向位移L得到的n方向栅格像元与原图作布尔运算来完成，由于栅格数据量很大，特别是上述算法运算量级很大，当L较大时实施有一定困难，且距离精度也尚待提高。5.1.1 缓冲区分

7、析缓冲区分析 角分线法 缓冲区实现的基本算法缓冲区实现的基本算法RdB角分线法 角分线法简单易行，但算法存在不足： 难以最大限度地保证缓冲区左右边线的等宽性；校正过程复杂；算法模型欠结构化。5.1.1 缓冲区分析缓冲区分析缓冲区实现的基本算法缓冲区实现的基本算法 凸角圆弧法 凸角圆弧法对于凸部的圆弧处理使其能最大限度地保证左右平行曲线的等宽性，避免了角分线法所带来的异常情况。 凸角圆弧法原理5.1.1 缓冲区分析缓冲区分析 凸角圆弧法的算法实施步骤为 缓冲区实现的基本算法缓冲区实现的基本算法 直线性判断直线性判断为简化计算过程，凸角圆弧法的第一步是进行相邻三点的直线性判断。当相邻三点处于近似共

8、线状态时，用直线代替。常用的直线性判断方法是点到直线距离法，即直接利用解析几何中的距离公式 其中，Ax+By+C = 0为过首末点的直线方程，x、y为相邻三点中相对中间点的坐标，d为该中间点到直线Ax+By+C = 0的距离，当d小于某一给定值时，相邻三点可视为直线，简化计算过程。)(/22BACByAxd5.1.1 缓冲区分析缓冲区分析缓冲区实现的基本算法缓冲区实现的基本算法 凸角圆弧法的算法实施步骤为 折点凸凹性的判断折点凸凹性的判断凸角圆弧法的关键在于对凸凹部分的不同处理，因此折线顶点处的凸凹特性的判断是非常重要的步骤，它能确定何处需要用圆弧连接而何处需要用直线求交。这个问题可转化为两个

9、矢量的叉积：把相邻两个线段看成两个矢量，其方向取为坐标点序方向。若前一个矢量以最小的角度扫向第二个矢量时呈逆时针，则为凸顶点，反之，为凹顶点。 凸顶点圆弧的嵌入凸顶点圆弧的嵌入设圆弧的始边与终边分别为 、 ，其坐标形式分别为： ， ，为弦弧逼近误差（如图所示）。其中， ， ， ， 。 AB),(yxaaA),(yxbbB 21XXax21YYay23XXbx23YYbyABA213uv凸顶点圆弧的嵌入5.1.1 缓冲区分析缓冲区分析 凸角圆弧法的算法实施步骤为 缓冲区实现的基本算法缓冲区实现的基本算法 边线关系的判别和处理边线关系的判别和处理当轴线的弯曲空间不能容许左右平行曲线无压盖地通过时，

10、就产生边线自相交问题，形成若干个自相交多边形，如图所示。自相交多边形分为两种情况：岛屿多边形与重叠区多边形。 边线多边形的形成5.1.1 缓冲区分析缓冲区分析缓冲区实现的基本算法缓冲区实现的基本算法岛屿多边形&重叠区多边形及其自动识别：矢量数据格式表示的曲线具有方向性，取曲线坐标串的方向为曲线前进的方向。当中心轴线被取定方向后，其两侧的平行曲线也就自然地获得了左右属性，称左边线和右边线。对于左边线，岛屿多边形呈逆时针方向；对于右边线，岛屿多边形呈顺时针方向。对于重叠区多边形左边线呈顺时针方向；右边线呈逆时针方向 岛屿多边形与重叠区多边形（a）左边线的岛屿多边形与重叠区多边形 （b）右边

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

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

13、的一种非常有效的手段。 缓冲区分析应用缓冲区分析应用为了能根据离散分布的气象站降雨量数据来计算某地平均的降雨量，荷兰气候学家A.H.Thiessen提出了一种新的计算方法，即将所有相邻气象站连成三角形，作三角形各边的垂直平分线，每个气象站周围的若干垂直平分线便围成一个多边形，用这个多边形内所包含的惟一一个气象站的降雨强度来表示这个多边形区域内的降雨强度，该多边形称为泰森多边形（Thiessen Polygons或Thiessen Tesselations，又称Voronoi或Dirichlet多边形）。5.1.2 泰森多边形分析泰森多边形及其特性泰森多边形及其特性 ABCD泰森多边形u其几何定

14、义为：设平面上的一个离散点集P = P1, P2, , Pn ，其中任意两个点都不共位，即Pi Pj（i j, i1, 2, , n, j1, 2, , n），且任意四点不共圆，则任意离散点Pi 的泰森多边形的定义为在泰森多边形 Ti 中，任意一个内点到该泰森多边形的发生点 Pi 的距离都小于该点到其他任何发生点 Pj 的距离。这些发生点 Pi（i1, 2, , n）也称为泰森多边形的控制点或质心（Centroid）。 5.1.2 泰森多边形分析泰森多边形及其特性泰森多边形及其特性 为欧氏距离：dPPPPPPxdPxdxTjijijii,| ),(),(u 泰森多边形因其生成过程的特殊性，具有

15、以下一些特性：5.1.2 泰森多边形分析泰森多边形及其特性泰森多边形及其特性 1 1每个泰森多边形内仅含有一个控制点数据；3位于泰森多边形边上的点到其两边控制点的距离相等；2泰森多边形内的点到相应控制点的距离最近；4在判断一个控制点与其他哪些控制点相邻时，可直接根据泰森多边形得出结论，即若泰森多边形是n边形，则与n个离散点相邻。 Delaunay三角网是由与相邻泰森多边形共享一条边的相关点连接而成的三角网，它与泰森多边形是对偶关系。5.1.2 泰森多边形分析Delaunay三角网的构建三角网的构建 泰森多边形及其对偶Delaunay三角网5.1.2 泰森多边形分析uDelaunay三角网具有以

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

17、.1.2 泰森多边形分析Delaunay三角网的构建三角网的构建 凸包的生成123456789图 1 凸包生成凸包三角剖分图 2 环切边界法构成若干Delaunay三角形123456789离散点内插图 3 离散点内插入三角剖分形成新的三角剖分123456789泰森多边形建立过程：建立Delaunay三角网，对离散点和形成的三角形进行编号，并记录每个三角形是由哪三个离散点构成的；找出与每个离散点相邻的所有三角形的编号，并记录下来； 将与每个离散点相邻的所有三角形按顺时针或逆时针方向进行排序；计算出每个三角形的外接圆圆心，并记录下来；连接相邻三角形的外接圆圆心，即可得到泰森多边形。对于三角网边缘的

18、泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。5.1.2 泰森多边形分析泰森多边形的建立泰森多边形的建立 泰森多边形的栅格算法实现过程 一种栅格算法是先将图形栅格化为数字图像，然后对该数字图像进行欧氏距离变换，得到灰度图像，而泰森多边形的边一定处于该灰度图像的脊线上；再通过相应的图像运算，提取灰度图像的这些脊线，就得到最终的泰森多边形。另外还可采用以发生点为中心点，同时向周围相邻八方向做栅格扩张运算（一种距离变换），两个相邻发生点扩张运算的交线即为泰森多边形的邻接边，三个相邻发生点扩张运算的交点即为泰森多边形的顶点。泰森多边形的建立泰森多边形的建立用栅格方法得到的泰森多边形5

19、.1.2 泰森多边形分析5.2 叠加分析 叠加分析概述叠加分析概述5.2.1空间要素图形叠加空间要素图形叠加5.2.2空间要素属性叠加空间要素属性叠加5.2.35.2.1 叠加分析概述叠加分析是指将同一地区、同一比例尺、同一数学基础，不同信息表达的两组或多组专题要素的图形或数据文件进行叠加，根据各类要素与多边形边界的交点或多边形属性建立具有多重属性组合的新图层，并对那些在结构和属性上既相互重叠，又相互联系的多种现象要素进行综合分析和评价；或者对反映不同时期同一地理现象的多边形图形进行多时相系列分析，从而深入揭示各种现象要素的内在联系及其发展规律的一种空间分析方法。 a2结果图层abc1234a

20、1c2c4b3c1c3b2+=输入图层叠加图层叠加分析的基本概念5.2.1 叠加分析概述 地理空间数据的处理与分析目的是获得空间潜在信息，叠加分析是非常有效的提取隐含信息的工具之一。例如，将全国水文监测站分布图与政区图叠加，得到一个新的图层，既保留了水文监测站的点状图形及属性，同时附加了行政分区的属性信息，据此可以查询水文站点属于哪个省区，或者查询某省区内共有多少个水文站点；又如将某区域的土地利用类型图与土壤pH值状态图、地下水埋深图、植被覆盖图等专题地图叠加，生成新的图层后按照湿地的定义形成属性判别标准，从而判断该区域是否为湿地。将一个点层作为输入图层叠加到一个多边形图层上，即通过计算点与多

21、边形线段的相对位置，来判断这个点是否在多边形内，从而确定是否进行属性信息的叠加。5.2.2 空间要素图形叠加 点与多边形的叠加点与多边形的叠加点与多边形叠加分析将一个线图层作为输入图层叠加到一个多边形图层上，要进行线段与多边形的空间关系判别，主要是比较线上坐标与多边形的坐标，判断线段是否落在多边形内。5.2.2 空间要素图形叠加 线与多边形的叠加线与多边形的叠加线与多边形叠加分析5.2.2 空间要素图形叠加 多边形与多边形的叠合是指将两个不同图层的多边形要素相叠合，产生输出层的新多边形要素，用以解决地理变量的多准则分析、区域多重属性的模拟分析、地理特征的动态变化分析，以及图幅要素更新、相邻图幅

22、拼接、区域信息提取等。多边形与多边形的叠加多边形与多边形的叠加层1属性：地貌层2属性：土壤结果层属性：地貌、土壤5.2.2 空间要素图形叠加 多边形与多边形的叠加多边形与多边形的叠加根据叠加结果要保留不同的空间特征，常用的GIS软件通常提供了三种类型的多边形叠加分析操作，即并、叠和、交。输入图层叠加图层结果图层+=+=+=多边形的不同叠加方式并叠和交 矢量数据属性叠加处理更多地使用逻辑叠加运算，即布尔逻辑运算中的包含、交、并、差等。5.2.3 空间要素属性叠加 矢量数据叠加分析矢量数据叠加分析12345A123456A线与多边形的叠加属性逻辑运算LineID 1 2 3 4 5 6 Old I

23、D 1 2 3 4 5 1Poly A A A 0 0 0LineID 1 2 3 Old ID 1 2 3 Poly A A A LineID 4 5 6 Old ID 4 5 1Poly 0 0 0（a）逻辑并 （b）逻辑交 （c）逻辑差 栅格数据中对于同一区域、同一比例尺、同一数学基础的不同信息表达的要素来说，其栅格编号不会发生变化，即对于任意栅格单元用作标识的行列号I0、J0是不变的，进行叠加的时候只是增加了属性表的长度，下表表示进行多重叠加后的栅格多边形的数据结构：栅格数据叠加分析栅格数据叠加分析栅格编号属性1属性2属性nI0J0R1R2Rn5.2.3 空间要素属性叠加 栅格数据来源

24、复杂，叠加分析操作的前提是要将其转换为统一的栅格数据格式，如BMP、GRID等，且各个叠加层必须具有统一的地理空间，即具有统一的空间参考（包括地图投影、椭球体、基准面等），统一的比例尺以及具有统一的分辨率（即像元大小）。 栅格数据的叠加分析操作主要通过栅格之间的各种运算来实现。可以对单层数据进行各种数学运算如加、减、乘、除、指数、对数等，也可通过数学关系式建立多个数据层之间的关系模型。 5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析基于不同的运算方式和叠加形式：5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析基于像元与像元之间一一对应的运算，每一个像元都是基于它自

25、身的运算，不考虑其他的与之相邻的像元；局部变换将具有相同属性值的像元作为整体进行分析运算；分带变换基于研究区内所有像元的运算，输出栅格的每一个像元值是基于全区的栅格运算，这里像元是具有或没有属性值的网格（栅格）。全局变换以某一像元为中心，将周围像元的值作为算子，进行简单求和、求平均值、最大值、最小值等；邻域变换栅格叠加变换类型：局部变换每一个像元经过局部变换后的输出值与这个像元本身有关系，而不考虑围绕该像元的其他像元值。 3 输入栅格 输出栅格 输入栅格 乘数栅格 输出栅格（a）单层局部变换 （b）多层局部变换局部变换2 0 1 12 3 0 23 2 31 1 26 0 3 36 9 0 6

26、9 6 93 3 62 0 1 12 3 0 23 2 31 1 21 1 2 21 2 2 22 2 3 32 3 3 42 0 2 22 6 0 46 6 92 3 85.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析邻域变换如果要计算某一像元的值，就将该像元看作一个中心点，一定范围内围绕它的格网可以看作它的辐射范围，这个中心点的值取决于采用何种计算方法将周围格网的值赋给中心点，其中的辐射范围可自定义。邻域变换2 0 1 12 3 0 23 0 2 31 1 0 2邻域求和7 8 7 410 13 12 910 12 13 95 7 8 7输入栅格 输出栅格5.2.3 空间要素

27、属性叠加 栅格数据叠加分析栅格数据叠加分析分带变换将同一区域内具有相同像元值的格网看作一个整体进行分析运算，称为分带变换。 分带变换2 0 112 3 02 0 21 1 02输入栅格 分带栅格 输出栅格1 2 345 6 781 2 345 5 558 7 558 6 78 7 85 5 785.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析全局变换全局变换是基于区域内全部栅格的运算，一般指在同一网格内进行像元与像元之间距离的量测。欧几里德距离欧几里德距离运算 111 22.0 1.0 0.0 0.01.4 1.0 1.0 0.01.0 0.0 1.0 1.01.4 1.0 1.

28、4 2.0输入栅格 输出栅格5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析 在距离量测中像元间距离考虑全部的源数据，且要求像元间距离最短，但没有考虑其他因素如运费等。成本距离量测运算比空间距离量测运算要复杂得多，需要另一个格网来定义经过每个像元的成本或阻抗。交通费用计算5.0 3.0 0.0 0.03.5 2.5 2.8 0.01.5 0.0 2.5 2.02.1 3.0 2.8 4.0输入栅格 成本栅格 输出栅格 111a 2b c2 2 444 4 332 1 412 5 335.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析栅格逻辑叠加栅格数据中的像元值有时无

29、法用数值型字符来表示，不同专题要素用统一的量化系统表示也比较困难，故使用逻辑叠加更容易实现各个栅格层之间的运算。图层之间的布尔逻辑运算包括：与（AND）、或（OR）、非（NOT）、异或（OR）等。A B A AND B A OR B A NOT B A OR B 0 0 0 0 0 01 0 0 1 1 10 1 0 1 0 11 1 1 1 0 0布尔逻辑运算示例5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析假设某市政府要在辖区范围内选择理想地点建立一个垃圾场，有关垃圾场的选址条件如下所述：区域地表物质应具有低渗透率，以阻止可溶性物质快速渗入地下水中；区域与现有市政区域范围保

30、持一定距离；区域不属于环境敏感区；区域应属于农业区，而非市政区或工业区；区域的地表平均坡度平稳，并小于某个极限值；区域不发生洪水。5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析二值逻辑叠加模型：根据垃圾场选址条件组织有关图件资料，包括表土渗透性图、城区范围图、生态敏感度分布图、城乡区划图、地表坡度图和洪泛区分布图等。建立垃圾场选址的模型。该模型将以上图层结合起来进行布尔逻辑运算，结果生成二值图，其中值为1的地点表示满足上述垃圾场选址的全部条件，值为0则表示不满足选址条件。5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠加分析具体模型如下：将各个图层二值化（TRUE，FA

31、LSE）或（0，1）。本例中各层数据的布尔逻辑条件如下：Ca = 地表渗透性级别为低级；Cb = 距离城区边界的距离1km；Cc = 生态敏感性为不敏感级别；Cd = 土地利用类型为农业用地；Ce = 地表坡度 2；Cf = 不属于洪泛区范围。对于各输入数据层的布尔逻辑条件变量进行逻辑与运算，在区域某位置点上如果所有数据层的条件变量都是所要求的值，则结果变量OUTPUT为“1”，其他情况下为“0”。OUTPUTCa AND Cb AND Cc AND Cd AND Ce AND Cf生成二值图。满足条件的位置就是二值图中值为“1”的地点。5.2.3 空间要素属性叠加 栅格数据叠加分析栅格数据叠

32、加分析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 网络分析概述 网络分析网络分析 是通过研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及其资源等的优化问题进行研究的一种空间分析方法。网络分析的理论基础是图论和运筹学。在地理信息系统中，网络分析功能依据图论和运筹学原理，在计算机系统软硬件的支持下，将与网络有关的实际问题抽象化、模型化、可操作化，根据网络元素的拓扑关系（线性实体之间、线性实体与

33、结点之间、结点与结点之间的连结、连通关系），通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算，从而为制定系统的优化途径和方案提供科学决策的依据，最终达到使系统运行最优的目标。 5.3.1 网络分析概述 在城市之间建立通讯网络，使其中任意两个城市之间都有直接或间接的通讯联系，假设已知每两个城市之间通讯线路的成本，要求找出一个成本最低的通讯网络。图论中的基本概念图论中的基本概念31城市1城市2679城市3城市4城市576548（a）通讯网络问题中的数据（b）一个最小成本通讯网络用图形描述通讯网络问题31城市1城市26城市3城市4城市545.3.1 网络分析概述 图论中的“图”

34、是指由点集合V和V中点与点之间的连线的集合E构成的二元组（V, E）。V 中的元素称为结点，E 中的元素称为边。 图论中所研究的图是由实际问题抽象出来的逻辑关系图，图中点和线的位置与曲直无关紧要，点的多少和每条线是连接哪些点才是关键。图论中的基本概念图论中的基本概念图的结构ABCDe3e4e5e1e2e6e75.3.1 网络分析概述图论中的基本概念图论中的基本概念有向图V1V2V3V4e1e2e3e4e5e6树V1V2V3V4V5V6V7V8V10V9两个端点重合的边称为环。如果有两条边的端点是同一对顶点，则称这两条边为重边。既没有环也没有重边的图，称为简单图。如果图中的边是有向的，则称为有向

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

36、。在机器实现中，邻接矩阵表示法、关联矩阵表示法、邻接表表示法是用来描述图与网络常用的方法。图论中的基本概念图论中的基本概念V2V0V1100V3V5V46020301010505带权的有向图5.3.1 网络分析概述邻接矩阵邻接矩阵 用来表示图中任意两点间的邻接关系及其权值。如果两点间有一条弧，则邻接矩阵中对应的元素为 1；否则为 0（也可用表示两点间无任何连接关系），邻接矩阵为对称矩阵。对于加权图的邻接矩阵表示，一条弧所对应的元素不再是1，而是相应的权值。 图论中的基本概念图论中的基本概念24（a）有向图153（b）邻接矩阵0 1 1 0 00 0 0 1 00 1 0 0 00 0 1 0

37、10 0 1 1 0有向图及其邻接矩阵5.3.1 网络分析概述关联矩阵关联矩阵 中，每行对应图的一个节点，每列对应图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。图论中的基本概念图论中的基本概念24（a）有向图153有向图及其关联矩阵1-100010-100010-100-110000-1100001-100-101000-11（b）关联矩阵5.3.1 网络分析概述 图的邻接表邻接表 是图中所有节点邻接表的集合。图论中的基本概念图论中的基本概念24（a）有向图15

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

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

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

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

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

43、点”数据模型高级的“动态段动态结点”模型，来实现根据不同的属性按照某种度量标准对线性要素进行相对位置的划分。 地址匹配地址匹配地址匹配实质是对地理位置的查询，涉及到地址的编码。地址匹配与其他网络分析功能结合起来，可以满足实际工作中复杂的分析要求。网络分析功能网络分析功能5.3.2 最佳路径分析 最佳路径分析也称最优路径分析，以最短路径分析为主。这里“最佳”包含很多含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无

44、论判断标准和实际问题中的约束条件如何变化，其核心实现方法都是最短路径算法。 最短路径问题从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。5.3.2 最佳路径分析 Dijkstra算法基本思想其基本思路是：假设每个点都有一对标号（dj, pj），其中dj是从起源点 s 到点 j 的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj 则是从s到 j 的最短路径中 j 点的前一点。 初始化。起源点设置为ds = 0，ps为空，并标记起源点s，记k = s，其他所有点设为未标记点。 检验从所有已标记的点

45、k 到其直接连接的未标记的点j的距离，并设置dj = mindj, dk+lkj，其中，lkj为从点k到j的直接连接距离。 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i，di = mindj, 所有未标记的点 j ，点i就被选为最短路径中的一点，并设为已标记的点。 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，记为i = j* 标记点i。如果所有点已标记，则算法完全推出，否则记k = i，重复步骤。 最短路径算法最短路径算法5.3.2 最佳路径分析左图为某一带权有向图，若对其施行Dijkstra算法，则所得从V0到其余各顶点的最短路径以及运算过程中距离

46、的变化情况如右表所示。 V2V0V1100V3V5V46020301010505带权的有向图终点从源点V0到各终点的距离值和最短路径的求解过程i = 1i = 2i = 3i = 4i = 5V1V210（V0, V2）V360（V0, V2, V 3）50（V0, V4, V3）V430（V 0, V 4）30（V0, V 4）V5100（V0, V5）100（V0, V5）90（V0, V4, V5）60（V0, V4, V3, V5）VjV2V4V3V5SV0, V2V0, V2, V3V0, V2, V3, V4V0, V2, V3, V4, V5最短路径算法最短路径算法5.3.2 最

47、佳路径分析 弗洛伊德算法其基本思想是：假设求从顶点 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 到 V

48、j 的中间顶点的序号不大于 2 的最短路径。将它和已经得到的从Vi 到 Vj 的中间顶点的序号不大于 1 的最短路径相比较，从中选出中间顶点的序号不大于 2 的最短路径之后，再增加一个顶点 V3，继续进行试探。依次类推，在经过 n 次比较之后，最后求得的必是从Vi 到 Vj 的最短路径。 最短路径算法最短路径算法5.3.2 最佳路径分析 矩阵算法 该算法是利用矩阵来求出图的最短距离矩阵。算法步骤可表示为：最短路径算法最短路径算法 D = AA2A3 An-2 = (di,j)nn。 求出A, A2, A3 , , An-2 ； 已知图的邻接矩阵A；5.3.2 最佳路径分析最佳路径分析在汽车导航

49、系统和各种应急系统（如110报警、119火警以及医疗救护系统等）中应用非常广泛，系统应用需求决定了最佳路径分析应是高效率的，比如一般要求计算出到出事地点的最佳路径的时间必须是在13s内，且在行车过程中需要实时计算出车辆前方的行驶路线。但前面介绍的三种算法在时间复杂度上都不尽如人意，很难满足不断发展的各种系统的要求，从而促使人们考虑从各个角度解决其实现的效率问题。针对不同的网络特征、应用需求及具体的软硬件环境，各种最短路径算法不断涌现，在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。 最短路径算法的优化最短路径算法的优化5.3.2 最佳路径分析 以路径分析应用最广泛的交通道路网络为例

50、，提供一个解决实际问题的基本模式。 假定某地区交通管理部门接到举报在该区域内某一地点发生交通事故，需要有关人员立刻赶到现场，选择一条路途最短的行进路线到达指定地点。在解决问题之前要了解交通网络数据的基本特征。首先，对于一定区域范围内庞大的交通网络要考虑它的存储结构，既要有利于网络分析算法的实现，又能够在节约存储空间的前提下根据需要扩充数据，对交通网络进行综合分析。然后是网络搜索，主要依据求解单源点间最短路径的戴克斯徒拉算法思想，同样也可以对其进行优化改进以提高效率。根据实际应用的需要，首先将网络边的权值设为两结点间的距离，并定义沿着起点到终点的方向为空间有效方向，相反的方向为无效方向；然后赋给

51、网络边、结点相应的字段值，并定义站点、拐点、桥梁等特殊地物的属性，最后通过具体的程序设计来实现搜索过程。路径分析的实现路径分析的实现5.3.3 连通分析 在地理网络中从某一点出发能够到达的全部结点或边有哪些，如何选择对于用户来说成本最小的线路，即连通分析所要解决的问题。连通分析的求解过程实质上是对应的图的生成树的求解过程，其中研究最多的是最小生成树问题。基本概念基本概念V1V2V4V3无向图（连通图）5.3.3 连通分析 连通性是图论的一个重要概念。在无向图G = (V, E)中，如果从顶点Vs到顶点Vt有路径，则称Vs和Vt是连通的。如果对于图G中的任意两个顶点Vi,VjV，Vi和Vj都是连

52、通的，则称G为连通图。无向图及其连通分量（a）无向图GV9V2V1V8V3V5V6V7V4V9V8V2V1V3V5V6V7V4（b）G的三个连通分量基本概念基本概念5.3.3 连通分析 一个连通图的生成树是含有该连通图的全部顶点的一个极小连通子图，包含三个条件： 它是连通的； 它包含原有连通图的全部结点； 它不含任何回路。 依据连通图的生成树的定义可知，若连通图G的顶点个数为n，则G的生成树的边数为n-1；树无回路，但不相邻顶点连成一边，就会得到一个回路；树是连通的，但去掉任意一条边，就会变为不连通的。 基本概念基本概念5.3.3 连通分析 从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被

53、访问一次，这一过程叫做图的遍历。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。基本思想是：从图中的某个顶点出发，然后访问任意一个该点的邻接点，并以该点的邻接点为新的出发点继续访问下一层级的邻接点，从而使整个搜索过程向纵深方向发展，直到图中的所有顶点都被访问过为止。从图中的某个顶点出发，访问该顶点之后依次访问它的所有邻接点，然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被访问到为止。基本概念基本概念5.3.3 连通分析 图（a）是一个具有8个结点的网络图，对其分别进行深度优先搜索和广度优先搜索，其搜索过程如图（b）和（c）。（a）网络图V1V2V3V4V5V8V6V

54、7基本概念基本概念V1V2V3V4V5V8V6V71234567（b）广度优先搜索过程V1V2V3V4V5V8V6V71524673（c）深度优先搜索过程5.3.3 连通分析 克罗斯克尔（Kruskal）算法是1956年提出的，俗称“避圈法”。设图G是由m个结点构成的连通赋权图，则构造最小生成树的步骤如下：最小生成树算法最小生成树算法1先把图G中的各边按权数从小到大重新排列，并取权数最小的一条边为生成树T中的边；2在剩下的边中，按顺序取下一条边，若该边与生成树中已有的边构成回路，则舍去该边，否则选择进入生成树中；3重复步骤2，直到有m-1条边被选进T中，这m-1条边就是图G的最小生成树。5.3

55、.3 连通分析 构造最小生成树的另一个著名算法Prim算法的基本思想是：假设N = (V, E)是连通网，生成的最小生成树为T = (V, TE)，求T的步骤如下： 最小生成树算法最小生成树算法1初始化：U =u0，TE =；2在所有 uU，vV-U 的边（u, v）E中，找一条权最小的边（u0, v0），TE+（u0, v0）TE，v0+UU；3如果U = V，则算法结束，否则重复步骤2；4最后得到最小生成树T = ，其中TE为最小生成树的边集。5.3.3 连通分析 图1中带权图最小生成树求算过程如图2所示。1243566536264551图 1 带权图1243562124356241243

56、56241124356245112435632451图 2 求带权图最小生成树的过程（a） （b） （c） （d） （e）最小生成树算法最小生成树算法5.3.4 资源分配 在多数的应用中，需要解决在网络中选定几个供应中心，并将网络的各边和点分配给某一中心，使各中心所覆盖范围内每一点到中心的总的加权距离最小，实际上包括定位与分配两个问题。 定位是指已知需求源的分布，确定在哪里布设供应点最合适的问题； 分配指的是已知供应点，确定其为哪些需求源提供服务的问题。 5.3.4 资源分配 选址功能涉及在某一指定区域内选择服务性设施的位置，如确定市郊商店区消防站工厂飞机场仓库等的最佳位置。 选址问题的数学模

57、型取决于可供选择的范围，以及所选位置的质量判断标准这两个条件。在一个地理网络中，能够从网络的结点和边上找到一些特定的点使它们满足某种优化条件，这些点可用于较简单的定位问题。 选址问题（定位问题）选址问题（定位问题） 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 之间的距离，这个长

58、度称为点顶点距离（Point-vertex Distance，PVD）；表示从顶点到网络边（vi, vj）的最大距离，此长度称为顶点弧距离（Vertex-arc Distance）。 选址问题（定位问题）选址问题（定位问题） 5.3.4 资源分配从顶点p到任一顶点的最大距离从顶点p到所有顶点的总距离从顶点p到所有弧的最大距离从顶点p到所有弧的总距离 从网络边（vi, vj）上的f_点到任一结点的最大距离 从网络边（vi, vj）上的f_点到所有各结点的总距离),(max)(qpdpMVVqqqpdpSVV),()(),( ,(max)(),(jipdpMVAji),(),( ,()(jijip

59、dpSVAqjifdjifMPVq),_(max),_(qqjifdjifSPV),_(),_(选址问题（定位问题）选址问题（定位问题） 5.3.4 资源分配 基于以上变量的定义，给出有关中心点和中位点的概念。使最大距离达到最小的位置称为网络的中心点，使最大距离总和达到最小的位置称为网络的中位点。一个地理网络的中心点主要有中心、一般中心、绝对中心和一般绝对中心等；一个地理网络的中位点主要有中位点、一般中位点、绝对中位点和一般绝对中位点等。 选址问题（定位问题）选址问题（定位问题） 5.3.4 资源分配地理网络的中心点是网络中距最远结点最近的一个结点vx，即地理网络的一般中心是距最远点最近的一个

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