空间几何关系分析

关于空间几何关系分析第1页，共138页，2022年，5月20日，17点56分，星期五5.1邻近度分析邻近度（Proximity）是定性描述空间目标距离关系的重要物理量之一，表示地理空间中两个目标地物距离相近的程度。泰森多边形分析

5.1.15.1.2缓冲区分析

第2页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析

缓冲区是指为了识别某一地理实体或空间物体对其周围地物的影响度而在其周围建立的具有一定宽度的带状区域。缓冲区分析则是对一组或一类地物按缓冲的距离条件，建立缓冲区多边形，然后将这一图层与需要进行缓冲区分析的图层进行叠加分析，得到所需结果的一种空间分析方法。缓冲区分析适用于点、线或面对象，如点状的居民点、线状的河流和面状的作物区等。基本原理第3页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析道路中心线按道路中心线100米生成缓冲区基本原理第4页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析从数学的角度看，缓冲区分析的基本思想是给定一个空间对象或集合，确定其邻域，邻域的大小由邻域半径R决定，因此对象Oi的缓冲区定义为：Bi

={x|d(x,Oi)≤R}，即半径为R的对象Oi的缓冲区，Bi为距Oi的距离小于等于R的全部点的集合，d一般指最小欧氏距离，但也可以为其他定义的距离，如网络距离，即空间物体间的路径距离。对于对象集合O={Oi

|i=1,2,…,n}，其半径为R的缓冲区是各个对象缓冲区的并集，即：基本原理第5页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析（a）不同宽度缓冲区干流支流邻域半径R即缓冲距离（宽度），是缓冲区分析的主要数量指标，可以是常数或变量。空间对象还可以生成多个缓冲带。基本原理（b）环状缓冲区第6页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析具有不同特性的缓冲区（a）静态缓冲区a=b

（b）动态缓冲区a

≠b

abaaba根据研究对象影响力的特点，缓冲区可以分为均质与非均质两种。基本原理第7页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析矢量数据缓冲区的建立方法缓冲区建立方法（a）单点形成的缓冲区（b）点群形成的缓冲区（c）分级点形成的缓冲区点形成的缓冲区形式①点要素的缓冲区第8页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析矢量数据缓冲区的建立方法②线要素的缓冲区线形成的缓冲区形式（a）单线形成的缓冲区（b）多线形成的缓冲区（c）分级线形成的缓冲区缓冲区建立方法第9页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析矢量数据缓冲区的建立方法③面要素的缓冲区面形成的缓冲区形式（a）单一面形成的缓冲区（b）多个面形成的缓冲区（c）分级面形成的缓冲区缓冲区建立方法第10页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析栅格数据缓冲区的建立方法缓冲区建立方法栅格数据的缓冲区分析通常称为推移或扩散（Spread），推移或扩散实际上是模拟主体对邻近对象的作用过程，物体在主体的作用下沿着一定的阻力表面移动或扩散，距离主体越远所受到的作用力越弱。第11页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区建立方法第12页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析动态缓冲区缓冲区建立方法现实世界中很多空间对象或过程对于周围的影响并不是随着距离的变化而固定不变的，需要建立动态缓冲区，根据空间物体对周围空间影响度的变化性质，可以采用不同的分析模型。①当缓冲区内各处随着距离变化，其影响度变化速度相等时，采用线性模型；②当距离空间物体近的地方比距离空间物体远的地方影响度变化快时，采用二次模型；③当距离空间物体近的地方比距离空间物体远的地方影响度变化更快时，采用指数模型。第13页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区实现有两种基本算法：矢量方法和栅格方法。缓冲区实现的基本算法矢量方法使用较广，产生时间较长，相对比较成熟，具体的几何算法是中心线扩张法，又称加宽线法或图形加粗法，通过以中心轴线为核心做平行曲线，生成缓冲区边线，再对生成边线求交、合并，最终生成缓冲区边界。栅格方法以数学形态学扩张算法为代表，采用由实体栅格和八方向位移L得到的n方向栅格像元与原图作布尔运算来完成，由于栅格数据量很大，特别是上述算法运算量级很大，当L较大时实施有一定困难，且距离精度也尚待提高。第14页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析角分线法缓冲区实现的基本算法RdB角分线法基本思想是：首先在中心轴线两端点处作轴线的垂线，按缓冲区半径R截去超出部分，获得左右边线的起讫点；然后在中心轴线的其他各转折点处，用以偏移量为R的左右平行线的交点来确定该转折点处左右平行边线的对应顶点；最终由端点、转折点和左右平行线形成的多边形就构成了所需要的缓冲区多边形

第15页，共138页，2022年，5月20日，17点56分，星期五角分线法简单易行，但算法存在不足：难以最大限度地保证缓冲区左右边线的等宽性；校正过程复杂；算法模型欠结构化。RdB角分线法第16页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区实现的基本算法凸角圆弧法凸角圆弧法的算法思想是：在中心轴线两端点处作轴线的垂线，按缓冲区半径R截去超出部分，获得左右边线的起讫点；在中心轴线的其他各转折点处，首先判断该点的凸凹性，在凸侧用圆弧弥合，在凹侧用与该转折点前后相继的轴线的偏移量为R的左右平行线的交点来确定对应顶点凸角圆弧法对于凸部的圆弧处理使其能最大限度地保证左右平行曲线的等宽性，避免了角分线法所带来的异常情况。凸角圆弧法原理第17页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析凸角圆弧法的算法实施步骤为缓冲区实现的基本算法①直线性判断为简化计算过程，凸角圆弧法的第一步是进行相邻三点的直线性判断。当相邻三点处于近似共线状态时，用直线代替。常用的直线性判断方法是点到直线距离法，即直接利用解析几何中的距离公式

其中，Ax+By+C=0为过首末点的直线方程，x、y为相邻三点中相对中间点的坐标，d为该中间点到直线Ax+By+C=0的距离，当d小于某一给定值时，相邻三点可视为直线，简化计算过程。第18页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区实现的基本算法凸角圆弧法的算法实施步骤为

②折点凸凹性的判断凸角圆弧法的关键在于对凸凹部分的不同处理，因此折线顶点处的凸凹特性的判断是非常重要的步骤，它能确定何处需要用圆弧连接而何处需要用直线求交。这个问题可转化为两个矢量的叉积：把相邻两个线段看成两个矢量，其方向取为坐标点序方向。若前一个矢量以最小的角度扫向第二个矢量时呈逆时针，则为凹顶点，反之，为凸顶点。③凸顶点圆弧的嵌入设圆弧的始边与终边分别为、，其坐标形式分别为：，，δ为弦弧逼近误差（如图所示）。其中，，，，。A213uv凸顶点圆弧的嵌入第19页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析凸角圆弧法的算法实施步骤为缓冲区实现的基本算法④边线关系的判别和处理当轴线的弯曲空间不能容许左右平行曲线无压盖地通过时，就产生边线自相交问题，形成若干个自相交多边形，如图所示。自相交多边形分为两种情况：岛屿多边形与重叠区多边形。边线多边形的形成第20页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区实现的基本算法岛屿多边形&重叠区多边形及其自动识别：矢量数据格式表示的曲线具有方向性，取曲线坐标串的方向为曲线前进的方向。当中心轴线被取定方向后，其两侧的平行曲线也就自然地获得了左右属性，称左边线和右边线。对于左边线，岛屿多边形呈逆时针方向；对于右边线，岛屿多边形呈顺时针方向。对于重叠区多边形左边线呈顺时针方向；右边线呈逆时针方向岛屿多边形与重叠区多边形（a）左边线的岛屿多边形与重叠区多边形（b）右边线的岛屿多边形与重叠区多边形第21页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区实现的基本算法凸角圆弧法的算法实施步骤为⑤缓冲区边界的最终形成将重叠区进行合并绘制出最外围边线，同时绘出岛屿轮廓，就形成了最终的缓冲区边界。要注意的是，利用缓冲区进行检索的时候，按最外围边线所形成的圆头或方头缓冲区检索之后，要扣除按所有岛屿进行检索的结果。第22页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析对于矢量数据对于栅格数据①②③缓冲区多边形的重叠合并数学运算法矢量—栅格转换法矢量—栅格混合法对缓冲区内的栅格赋上一个与其影响度惟一对应的值，如果发生重叠的区域具有相同的影响度，则取任一值；如果发生重叠的区域具有不同影响度等级，则影响度小的服从于影响度大的。缓冲区实现的基本算法第23页，共138页，2022年，5月20日，17点56分，星期五5.1.1缓冲区分析缓冲区作为一个独立的数据层可以参与叠加分析，常应用到道路、河流、居民点、工厂（污染源）等生产生活设施的空间分析，为不同工作需要（如道路修整、河道改建、居民区拆迁、污染范围确定等）提供科学依据。结合不同的专业模型，缓冲区分析能够在景观生态、规划、军事应用等领域发挥更大的作用。例如，利用缓冲区分析和相邻缓冲区的景观结构总体变异系数方法对自然保护区进行自然景观和人为影响景观的分割研究。在虚拟军事演练系统中，缓冲区分析方法是对雷达群的合成探测范围和干扰效果进行研究的一种非常有效的手段。缓冲区分析应用第24页，共138页，2022年，5月20日，17点56分，星期五为了能根据离散分布的气象站降雨量数据来计算某地平均的降雨量，荷兰气候学家A.H.Thiessen提出了一种新的计算方法，即将所有相邻气象站连成三角形，作三角形各边的垂直平分线，每个气象站周围的若干垂直平分线便围成一个多边形，用这个多边形内所包含的惟一一个气象站的降雨强度来表示这个多边形区域内的降雨强度，该多边形称为泰森多边形（ThiessenPolygons或ThiessenTesselations，又称Voronoi或Dirichlet多边形）。5.1.2泰森多边形分析泰森多边形及其特性

ABCD泰森多边形第25页，共138页，2022年，5月20日，17点56分，星期五其几何定义为：设平面上的一个离散点集P={P1,P2,…,Pn

}，其中任意两个点都不共位，即Pi

≠Pj（i≠j,i∈[1,2,…,n],j∈[1,2,…,n]），且任意四点不共圆，则任意离散点Pi

的泰森多边形的定义为在泰森多边形Ti中，任意一个内点到该泰森多边形的发生点Pi的距离都小于该点到其他任何发生点Pj的距离。这些发生点Pi（i∈[1,2,…,n]）也称为泰森多边形的控制点或质心（Centroid）。5.1.2泰森多边形分析泰森多边形及其特性

第26页，共138页，2022年，5月20日，17点56分，星期五泰森多边形因其生成过程的特殊性，具有以下一些特性：5.1.2泰森多边形分析泰森多边形及其特性

1每个泰森多边形内仅含有一个控制点数据；3位于泰森多边形边上的点到其两边控制点的距离相等；2泰森多边形内的点到相应控制点的距离最近；4在判断一个控制点与其他哪些控制点相邻时，可直接根据泰森多边形得出结论，即若泰森多边形是n边形，则与n个离散点相邻。第27页，共138页，2022年，5月20日，17点56分，星期五Delaunay三角网是由与相邻泰森多边形共享一条边的相关点连接而成的三角网，它与泰森多边形是对偶关系。5.1.2泰森多边形分析Delaunay三角网的构建

泰森多边形及其对偶Delaunay三角网第28页，共138页，2022年，5月20日，17点56分，星期五5.1.2泰森多边形分析Delaunay三角网具有以下特征：Delaunay三角网是惟一的；三角网的外边界构成了给定点集的凸多边形“外壳”；没有任何点在三角形的外接圆内部，反之，如果一个三角网满足此条件，那么它就是Delaunay三角网（如图）。如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大，从这个意义上讲，Delaunay三角网是“最接近于规则化”的三角网。

Delaunay三角网的构建

Delaunay三角网构建1234567821345678构建三角网第29页，共138页，2022年，5月20日，17点56分，星期五凸包插值算法凸包插值算法是Tsai在1993年提出的在n维欧拉空间中构造Delaunay三角网的一种通用算法，包括三个主要步骤：5.1.2泰森多边形分析Delaunay三角网的构建

①凸包的生成123456789图1

凸包生成②凸包三角剖分图2

环切边界法构成若干Delaunay三角形123456789③离散点内插图3离散点内插入三角剖分形成新的三角剖分123456789第30页，共138页，2022年，5月20日，17点56分，星期五泰森多边形建立过程：建立Delaunay三角网，对离散点和形成的三角形进行编号，并记录每个三角形是由哪三个离散点构成的；找出与每个离散点相邻的所有三角形的编号，并记录下来；将与每个离散点相邻的所有三角形按顺时针或逆时针方向进行排序；计算出每个三角形的外接圆圆心，并记录下来；连接相邻三角形的外接圆圆心，即可得到泰森多边形。对于三角网边缘的泰森多边形，可作垂直平分线与图廓相交，与图廓一起构成泰森多边形。5.1.2泰森多边形分析泰森多边形的建立第31页，共138页，2022年，5月20日，17点56分，星期五泰森多边形的栅格算法实现过程一种栅格算法是先将图形栅格化为数字图像，然后对该数字图像进行欧氏距离变换，得到灰度图像，而泰森多边形的边一定处于该灰度图像的脊线上；再通过相应的图像运算，提取灰度图像的这些脊线，就得到最终的泰森多边形。另外还可采用以发生点为中心点，同时向周围相邻八方向做栅格扩张运算（一种距离变换），两个相邻发生点扩张运算的交线即为泰森多边形的邻接边，三个相邻发生点扩张运算的交点即为泰森多边形的顶点。泰森多边形的建立用栅格方法得到的泰森多边形5.1.2泰森多边形分析第32页，共138页，2022年，5月20日，17点56分，星期五5.2叠加分析叠加分析概述5.2.1空间要素图形叠加5.2.2空间要素属性叠加5.2.3第33页，共138页，2022年，5月20日，17点56分，星期五5.2.1叠加分析概述叠加分析是指将同一地区、同一比例尺、同一数学基础，不同信息表达的两组或多组专题要素的图形或数据文件进行叠加，根据各类要素与多边形边界的交点或多边形属性建立具有多重属性组合的新图层，并对那些在结构和属性上既相互重叠，又相互联系的多种现象要素进行综合分析和评价；或者对反映不同时期同一地理现象的多边形图形进行多时相系列分析，从而深入揭示各种现象要素的内在联系及其发展规律的一种空间分析方法。a2结果图层abc1234a1c2c4b3c1c3b3+=输入图层叠加图层叠加分析的基本概念第34页，共138页，2022年，5月20日，17点56分，星期五5.2.1叠加分析概述地理空间数据的处理与分析目的是获得空间潜在信息，叠加分析是非常有效的提取隐含信息的工具之一。例如，将全国水文监测站分布图与政区图叠加，得到一个新的图层，既保留了水文监测站的点状图形及属性，同时附加了行政分区的属性信息，据此可以查询水文站点属于哪个省区，或者查询某省区内共有多少个水文站点；又如将某区域的土地利用类型图与土壤pH值状态图、地下水埋深图、植被覆盖图等专题地图叠加，生成新的图层后按照湿地的定义形成属性判别标准，从而判断该区域是否为湿地。第35页，共138页，2022年，5月20日，17点56分，星期五将一个点层作为输入图层叠加到一个多边形图层上，即通过计算点与多边形线段的相对位置，来判断这个点是否在多边形内，从而确定是否进行属性信息的叠加。5.2.2空间要素图形叠加点与多边形的叠加点与多边形叠加分析第36页，共138页，2022年，5月20日，17点56分，星期五将一个线图层作为输入图层叠加到一个多边形图层上，要进行线段与多边形的空间关系判别，主要是比较线上坐标与多边形的坐标，判断线段是否落在多边形内。5.2.2空间要素图形叠加线与多边形的叠加线与多边形叠加分析第37页，共138页，2022年，5月20日，17点56分，星期五5.2.2空间要素图形叠加多边形与多边形的叠合是指将两个不同图层的多边形要素相叠合，产生输出层的新多边形要素，用以解决地理变量的多准则分析、区域多重属性的模拟分析、地理特征的动态变化分析，以及图幅要素更新、相邻图幅拼接、区域信息提取等。多边形与多边形的叠加层1属性：地貌层2属性：土壤结果层属性：地貌、土壤第38页，共138页，2022年，5月20日，17点56分，星期五5.2.2空间要素图形叠加多边形与多边形的叠加根据叠加结果要保留不同的空间特征，常用的GIS软件通常提供了三种类型的多边形叠加分析操作，即并、叠和、交。输入图层叠加图层结果图层+=+=+=多边形的不同叠加方式并叠和交第39页，共138页，2022年，5月20日，17点56分，星期五矢量数据属性叠加处理更多地使用逻辑叠加运算，即布尔逻辑运算中的包含、交、并、差等。5.2.3空间要素属性叠加矢量数据叠加分析12345A123456

A线与多边形的叠加属性逻辑运算LineID123456OldID123451PolyAAA000LineID123OldID123PolyAAALineID456OldID451Poly000（a）逻辑并（b）逻辑交（c）逻辑差第40页，共138页，2022年，5月20日，17点56分，星期五栅格数据中对于同一区域、同一比例尺、同一数学基础的不同信息表达的要素来说，其栅格编号不会发生变化，即对于任意栅格单元用作标识的行列号I0、J0是不变的，进行叠加的时候只是增加了属性表的长度，下表表示进行多重叠加后的栅格多边形的数据结构：栅格数据叠加分析栅格编号属性1属性2…属性nI0J0R1R2…Rn5.2.3空间要素属性叠加第41页，共138页，2022年，5月20日，17点56分，星期五栅格数据来源复杂，叠加分析操作的前提是要将其转换为统一的栅格数据格式，如BMP、GRID等，且各个叠加层必须具有统一的地理空间，即具有统一的空间参考（包括地图投影、椭球体、基准面等），统一的比例尺以及具有统一的分辨率（即像元大小）。栅格数据的叠加分析操作主要通过栅格之间的各种运算来实现。可以对单层数据进行各种数学运算如加、减、乘、除、指数、对数等，也可通过数学关系式建立多个数据层之间的关系模型。5.2.3空间要素属性叠加栅格数据叠加分析第42页，共138页，2022年，5月20日，17点56分，星期五基于不同的运算方式和叠加形式：5.2.3空间要素属性叠加栅格数据叠加分析基于像元与像元之间一一对应的运算，每一个像元都是基于它自身的运算，不考虑其他的与之相邻的像元；局部变换将具有相同属性值的像元作为整体进行分析运算；分带变换基于研究区内所有像元的运算，输出栅格的每一个像元值是基于全区的栅格运算，这里像元是具有或没有属性值的网格（栅格）。全局变换以某一像元为中心，将周围像元的值作为算子，进行简单求和、求平均值、最大值、最小值等；邻域变换栅格叠加变换类型：第43页，共138页，2022年，5月20日，17点56分，星期五局部变换每一个像元经过局部变换后的输出值与这个像元本身有关系，而不考虑围绕该像元的其他像元值。×3＝×＝

输入栅格输出栅格输入栅格乘数栅格输出栅格（a）单层局部变换（b）多层局部变换局部变换2011230232311260336906969336201123023231121122122222332334202226046692385.2.3空间要素属性叠加栅格数据叠加分析第44页，共138页，2022年，5月20日，17点56分，星期五邻域变换如果要计算某一像元的值，就将该像元看作一个中心点，一定范围内围绕它的格网可以看作它的辐射范围，这个中心点的值取决于采用何种计算方法将周围格网的值赋给中心点，其中的辐射范围可自定义。邻域变换2011230230231102＝邻域求和787410131291012139578 7输入栅格输出栅格5.2.3空间要素属性叠加栅格数据叠加分析第45页，共138页，2022年，5月20日，17点56分，星期五分带变换将同一区域内具有相同像元值的格网看作一个整体进行分析运算，称为分带变换。＝

分带变换201 1230 202 110 2输入栅格分带栅格输出栅格123 4567 8123 4555 5875 5867 878 557 85.2.3空间要素属性叠加栅格数据叠加分析第46页，共138页，2022年，5月20日，17点56分，星期五全局变换全局变换是基于区域内全部栅格的运算，一般指在同一网格内进行像元与像元之间距离的量测。欧几里德距离＝欧几里德距离运算1 1 12 2.01.0 0.00.01.41.0 1.00.01.00.0 1.01.01.41.0 1.42.0输入栅格输出栅格5.2.3空间要素属性叠加栅格数据叠加分析第47页，共138页，2022年，5月20日，17点56分，星期五在距离量测中像元间距离考虑全部的源数据，且要求像元间距离最短，但没有考虑其他因素如运费等。成本距离量测运算比空间距离量测运算要复杂得多，需要另一个格网来定义经过每个像元的成本或阻抗。交通费用计算5.03.0 0.00.03.52.5 2.80.01.50.0 2.52.02.13.0 2.84.0输入栅格成本栅格输出栅格

1 1 1a2 bc224 4443 3214 1253 35.2.3空间要素属性叠加栅格数据叠加分析第48页，共138页，2022年，5月20日，17点56分，星期五栅格逻辑叠加栅格数据中的像元值有时无法用数值型字符来表示，不同专题要素用统一的量化系统表示也比较困难，故使用逻辑叠加更容易实现各个栅格层之间的运算。图层之间的布尔逻辑运算包括：与（AND）、或（OR）、非（NOT）、异或（×OR）等。ABAANDBAORBANOTBA×ORB000000100111010101111100布尔逻辑运算示例5.2.3空间要素属性叠加栅格数据叠加分析不同为1,相同为0第49页，共138页，2022年，5月20日，17点56分，星期五假设某市政府要在辖区范围内选择理想地点建立一个垃圾场，有关垃圾场的选址条件如下所述：区域地表物质应具有低渗透率，以阻止可溶性物质快速渗入地下水中；区域与现有市政区域范围保持一定距离；区域不属于环境敏感区；区域应属于农业区，而非市政区或工业区；区域的地表平均坡度平稳，并小于某个极限值；区域不发生洪水。5.2.3空间要素属性叠加栅格数据叠加分析第50页，共138页，2022年，5月20日，17点56分，星期五二值逻辑叠加模型：根据垃圾场选址条件组织有关图件资料，包括表土渗透性图、城区范围图、生态敏感度分布图、城乡区划图、地表坡度图和洪泛区分布图等。建立垃圾场选址的模型。该模型将以上图层结合起来进行布尔逻辑运算，结果生成二值图，其中值为1的地点表示满足上述垃圾场选址的全部条件，值为0则表示不满足选址条件。5.2.3空间要素属性叠加栅格数据叠加分析第51页，共138页，2022年，5月20日，17点56分，星期五具体模型如下：将各个图层二值化（TRUE，FALSE）或（0，1）。本例中各层数据的布尔逻辑条件如下：Ca=地表渗透性级别为低级；Cb=距离城区边界的距离>1km；Cc=生态敏感性为不敏感级别；Cd=土地利用类型为农业用地；Ce=地表坡度<2°；Cf=不属于洪泛区范围。对于各输入数据层的布尔逻辑条件变量进行逻辑与运算，在区域某位置点上如果所有数据层的条件变量都是所要求的值，则结果变量OUTPUT为“1”，其他情况下为“0”。OUTPUT＝CaANDCbANDCcANDCdANDCeANDCf生成二值图。满足条件的位置就是二值图中值为“1”的地点。5.2.3空间要素属性叠加栅格数据叠加分析第52页，共138页，2022年，5月20日，17点56分，星期五5.3网络分析5.3.5流分析5.3.6动态分段技术5.3.4资源分配5.3.7地址匹配5.3.1网络分析概述5.3.3连通分析5.3.2最佳路径分析第53页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述网络分析是通过研究资源等的优化问题进行研究网络的状态以及模拟和分析资源在网络上的流动和分配情况，对网络结构及其的一种空间分析方法。网络分析的理论基础是图论和运筹学。在地理信息系统中，网络分析功能依据图论和运筹学原理，在计算机系统软硬件的支持下，将与网络有关的实际问题抽象化、模型化、可操作化，根据网络元素的拓扑关系（线性实体之间、线性实体与结点之间、结点与结点之间的连结、连通关系），通过考察网络元素的空间、属性数据，对网络的性能特征进行多方面的分析计算，从而为制定系统的优化途径和方案提供科学决策的依据，最终达到使系统运行最优的目标。第54页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述在城市之间建立通讯网络，使其中任意两个城市之间都有直接或间接的通讯联系，假设已知每两个城市之间通讯线路的成本，要求找出一个成本最低的通讯网络。图论中的基本概念31城市1城市2679城市3城市4城市576548（a）通讯网络问题中的数据（b）一个最小成本通讯网络用图形描述通讯网络问题31城市1城市26城市3城市4城市54第55页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述图论中的“图”是指由点集合V和V中点与点之间的连线的集合E构成的二元组（V,E）。V中的元素称为结点，E中的元素称为边。图论中所研究的图是由实际问题抽象出来的逻辑关系图，图中点和线的位置与曲直无关紧要，点的多少和每条线是连接哪些点才是关键。图论中的基本概念图的结构ABCDe3e4e5e1e2e6e7第56页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述图论中的基本概念有向图V1V2V3V4e1e2e3e4e5e6树V1V2V3V4V5V6V7V8V10V9两个端点重合的边称为环。如果有两条边的端点是同一对顶点，则称这两条边为重边。既没有环也没有重边的图，称为简单图。如果图中的边是有向的，则称为有向图，其中的边叫做弧。在无向图中，首尾相接的一串边的集合叫做路。在有向图中，顺向的首尾相接的一串边的集合叫做有向路。如果一个图中，任意两个结点之间都存在一个路，则称之为连通图。起点和终点为同一个结点的路称为回路（或圈）。如果一个连通图中不存在任何回路，则称为树。任意一个连通图，去掉一些边后形成的树叫做连通图的生成树。第57页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述给定一个图，图中的每一条边赋以一个实数，称这种数为边的权数，称这种图为赋权图。赋以权数的有向图称为赋权有向图，也可称之为网络。根据需要赋权有向图中的一条边，必要时可以赋以多个权值，另外也可以给结点赋权，称为点权网络，相对于点权网络，给边赋权的网络称为边权网络。在机器实现中，邻接矩阵表示法、关联矩阵表示法、邻接表表示法是用来描述图与网络常用的方法。图论中的基本概念V2V0V1100V3V5V46020301010505带权的有向图第58页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述邻接矩阵用来表示图中任意两点间的邻接关系及其权值。如果两点间有一条弧，则邻接矩阵中对应的元素为1；否则为0（也可用∞表示两点间无任何连接关系），邻接矩阵为对称矩阵。对于加权图的邻接矩阵表示，一条弧所对应的元素不再是1，而是相应的权值。图论中的基本概念24（a）有向图153（b）邻接矩阵0110000010010000010100110有向图及其邻接矩阵第59页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述关联矩阵中，每行对应图的一个节点，每列对应图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为–1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。图论中的基本概念24（a）有向图153有向图及其关联矩阵1-100010-100010-100-110000-1100001-100-101000-11（b）关联矩阵第60页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述图的邻接表是图中所有节点邻接表的集合。对每个节点，它的邻接表就是它的所有出弧图论中的基本概念24（a）有向图153有向图及其邻接表04212345860426303093035074（b）邻接表第61页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述网络数据模型是现实世界网络系统（如交通网、通讯网、自来水管网、煤气管网等）的抽象表示。按照几何形态，空间实体被抽象为点、线、面目标，构成网络的最基本元素是线性实体以及这些实体的连接交汇点。前者称为网线或链（Link），后者称为结点（Node）。链（Link）链是构成网络的骨架，是现实世界中各种线路的抽象和资源传输或通信联络的通道，可以代表公路、铁路、街道、航线、水管、煤气管、输电线、河流等。链包括图形信息和属性信息，链的属性信息包括阻碍强度和资源需求量，链的阻碍强度是指在通过一条链时所需要花费的时间或者费用等，如资源流动的时间、速度。链是有方向的，当资源沿着网络中的不同方向流动时所受到的阻碍强度可能相同，也可能不同。网络数据模型第62页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述结点（Node）结点是网线的端点，又是网线的汇合点，可以表示交叉路口、中转站、河流汇合点等，其状态属性除了包括阻碍强度和资源需求量等，还有下面几种特殊的类型。①障碍（Barrier）：禁止资源在网络中的链上流动的点。②拐点（Turn）：出现在网络链中的分割结点上，状态属性有阻碍强度，如拐弯的时间和限制（例如在8：00到18：00不允许左拐等）。在地理网络中，拐点对资源的流动有很大影响，资源沿着某一条链流动到有关结点后，既可以原路返回，也可以流向与该结点相连的任意一条链，如果阻碍强度值为负数，则表示资源禁止流向特定的弧段。网络数据模型第63页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述结点（Node）③中心（Center）：网络中具有一定的容量，能够接受或分配资源的结点所在的位置。如水库﹑商业中心、电站、学校等，其状态属性包括资源容量（如总量）﹑阻碍强度（如中心到链的最大距离或时间限制）。资源容量决定了为中心服务的弧段的数量，中心的阻碍强度是指沿某一路径到达中心所经历的弧段总阻碍强度的最大值。④站点（Stop）：在路径选择中资源增减的结点，如库房﹑车站等，其状态属性有两种，一种是站的阻碍强度，它代表与站有关的费用、时间等，如在某个库房装卸货物所用时间等；一种是站的资源需求量，如产品数量、学生数、乘客数等。站的需求量为正值时，表示在该站上增加资源；若为负值，则表示在该站上减少资源。网络数据模型第64页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述网络分析功能路径分析路径分析是GIS中最基本的功能，其核心是对最佳路径的求解。从网络模型的角度看，最佳路径的求解是在指定网络的两个结点之间找一条阻碍强度最小的路径。另一种路径分析功能是求解最佳游历方案，又分为弧段最佳游历方案求解和结点最佳游历方案求解两种。连通分析现实中常需要知道从某一结点或边出发能够到达的全部结点或边，这一类问题称为连通分量求解；另一类连通分析问题是求解最少费用连通方案，即在耗费最小的情况下使全部结点相互连通。网络分析功能第65页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述网络分析功能资源分配资源分配也称定位与分配问题，包括目标选址和将需求按最近（这里远近是按加权距离来确定的）原则寻找供应中心（资源发散或汇集地）两个问题。流分析

流是资源在结点间的传输。流分析问题主要是按照某种优化标准（时间最少、费用最低、路程最短或运送量最大等）设计的运送方案，网络流理论是其基础理论。网络分析功能第66页，共138页，2022年，5月20日，17点56分，星期五5.3.1网络分析概述网络分析功能动态分段动态分段技术是GIS网络分析中一种基于网络线的动态分析、显示和绘图技术。通过建立一种比“弧段－结点”数据模型高级的“动态段－动态结点”模型，来实现根据不同的属性按照某种度量标准对线性要素进行相对位置的划分。地址匹配地址匹配实质是对地理位置的查询，涉及到地址的编码。地址匹配与其他网络分析功能结合起来，可以满足实际工作中复杂的分析要求。网络分析功能第67页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析最佳路径分析也称最优路径分析，以最短路径分析为主。这里“最佳”包含很多含义，不仅指一般地理意义上的距离最短，还可以是成本最少、耗费时间最短、资源流量（容量）最大、线路利用率最高等标准。很多网络相关问题，如最可靠路径问题、最大容量路径问题、易达性评价问题和各种路径分配问题均可纳入最佳路径问题的范畴之中。无论判断标准和实际问题中的约束条件如何变化，其核心实现方法都是最短路径算法。最短路径问题从算法研究的角度考虑最短路径问题通常可归纳为两大类：一类是所有点对之间的最短路径，另一类是单源点间的最短路径问题。第68页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析Dijkstra算法基本思想其基本思路是：假设每个点都有一对标号（dj,pj），其中dj是从起源点s到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；pj则是从s到j的最短路径中j点的前一点。①初始化。起源点设置为ds

=0，ps为空，并标记起源点s，记k=s，其他所有点设为未标记点。②检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置dj=min［dj,dk+lkj］，其中，lkj为从点k到j的直接连接距离。③选取下一个点。从所有未标记的结点中，选取dj中最小的一个i，di=min［dj,所有未标记的点j］，点i就被选为最短路径中的一点，并设为已标记的点。④找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，记为i=j*⑤标记点i。如果所有点已标记，则算法完全推出，否则记k=i，重复步骤②③④。最短路径算法第69页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析左图为某一带权有向图，若对其施行Dijkstra算法，则所得从V0到其余各顶点的最短路径以及运算过程中距离的变化情况如右表所示。V2V0V1100V3V5V46020301010505带权的有向图终点从源点V0到各终点的距离值和最短路径的求解过程i=1i=2i=3i=4i=5V1∞∞∞∞∞V210（V0,V2）V3∞60（V0,V2,V3）50（V0,V4,V3）V430（V0,V4）30（V0,V

4）V5100（V0,V5）100（V0,V5）90（V0,V4,V5）60（V0,V4,V3,V5）VjV2V4V3V5S﹛V0,V2﹜﹛V0,V2,V4﹜﹛V0,V2,V3,V4﹜﹛V0,V2,V3,V4,V5﹜最短路径算法第70页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析弗洛伊德算法其基本思想是：假设求从顶点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的最短路径。将它和已经得到的从Vi到Vj的中间顶点的序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点V3，继续进行试探。依次类推，在经过n次比较之后，最后求得的必是从Vi到Vj的最短路径。最短路径算法第71页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析矩阵算法该算法是利用矩阵来求出图的最短距离矩阵。算法步骤可表示为：最短路径算法③D=AA[2]A[3]…A[n-2]=(di,j)n×n。②求出A,A[2],A[3],…,A[n-2]

；①已知图的邻接矩阵A；第72页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析最佳路径分析在汽车导航系统和各种应急系统（如110报警、119火警以及医疗救护系统等）中应用非常广泛，系统应用需求决定了最佳路径分析应是高效率的，比如一般要求计算出到出事地点的最佳路径的时间必须是在1～3s内，且在行车过程中需要实时计算出车辆前方的行驶路线。但前面介绍的三种算法在时间复杂度上都不尽如人意，很难满足不断发展的各种系统的要求，从而促使人们考虑从各个角度解决其实现的效率问题。针对不同的网络特征、应用需求及具体的软硬件环境，各种最短路径算法不断涌现，在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。最短路径算法的优化第73页，共138页，2022年，5月20日，17点56分，星期五5.3.2最佳路径分析以路径分析应用最广泛的交通道路网络为例，提供一个解决实际问题的基本模式。假定某地区交通管理部门接到举报在该区域内某一地点发生交通事故，需要有关人员立刻赶到现场，选择一条路途最短的行进路线到达指定地点。在解决问题之前要了解交通网络数据的基本特征。首先，对于一定区域范围内庞大的交通网络要考虑它的存储结构，既要有利于网络分析算法的实现，又能够在节约存储空间的前提下根据需要扩充数据，对交通网络进行综合分析。然后是网络搜索，主要依据求解单源点间最短路径的的需要，首先将网络边的权值设为两结点间的戴克斯徒拉算法思想，同样也可以对其进行优化改进以提高效率。根据实际应用距离，并定义沿着起点到终点的方向为空间有效方向，相反的方向为无效方向；然后赋给网络边、结点相应的字段值，并定义站点、拐点、桥梁等特殊地物的属性，最后通过具体的程序设计来实现搜索过程。路径分析的实现第74页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析在地理网络中从某一点出发能够到达的全部结点或边有哪些，如何选择对于用户来说成本最小的线路，即连通分析所要解决的问题。连通分析的求解过程实质上是对应的图的生成树的求解过程，其中研究最多的是最小生成树问题。基本概念V1V2V4V3无向图（连通图）第75页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析连通性是图论的一个重要概念。在无向图G=(V,E)中，如果从顶点Vs到顶点Vt有路径，则称Vs和Vt是连通的。如果对于图G中的任意两个顶点Vi,Vj∈V，Vi和Vj都是连通的，则称G为连通图。无向图及其连通分量（a）无向图GV9V2V1V8V3V5V6V7V4V9V8V2V1V3V5V6V7V4（b）G的三个连通分量基本概念第76页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析一个连通图的生成树是含有该连通图的全部顶点的一个极小连通子图，包含三个条件：①它是连通的；②它包含原有连通图的全部结点；③它不含任何回路。依据连通图的生成树的定义可知，若连通图G的顶点个数为n，则G的生成树的边数为n-1；树无回路，但不相邻顶点连成一边，就会得到一个回路；树是连通的，但去掉任意一条边，就会变为不连通的。基本概念第77页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次，这一过程叫做图的遍历。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。基本思想是：从图中的某个顶点出发，然后访问任意一个该点的邻接点，并以该点的邻接点为新的出发点继续访问下一层级的邻接点，从而使整个搜索过程向纵深方向发展，直到图中的所有顶点都被访问过为止。从图中的某个顶点出发，访问该顶点之后依次访问它的所有邻接点，然后分别从这些邻接点出发按深度优先搜索遍历图的其他顶点，直至所有顶点都被访问到为止。基本概念第78页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析图（a）是一个具有8个结点的网络图，对其分别进行深度优先搜索和广度优先搜索，其搜索过程如图（b）和（c）。（a）网络图V1V2V3V4V5V8V6V7基本概念V1V2V3V4V5V8V6V71234567（b）广度优先搜索过程V1V2V3V4V5V8V6V71524673（c）深度优先搜索过程第79页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析克罗斯克尔（Kruskal）算法是1956年提出的，俗称“避圈法”。设图G是由m个结点构成的连通赋权图，则构造最小生成树的步骤如下：最小生成树算法1先把图G中的各边按权数从小到大重新排列，并取权数最小的一条边为生成树T中的边；2在剩下的边中，按顺序取下一条边，若该边与生成树中已有的边构成回路，则舍去该边，否则选择进入生成树中；3重复步骤2，直到有m-1条边被选进T中，这m-1条边就是图G的最小生成树。第80页，共138页，2022年，5月20日，17点56分，星期五(2)最小生成数之一

(3)最小生成树之二第81页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析构造最小生成树的另一个著名算法Prim算法的基本思想是：假设N=(V,E)是连通网，生成的最小生成树为T=(V,TE)，求T的步骤如下：最小生成树算法1初始化：U={u0}，TE={φ}；2在所有u∈U，v∈V-U的边（u,v）∈E中，找一条权最小的边（u0,v0），TE+{（u0,v0）}→TE，{v0}+U→U；3如果U=V，则算法结束，否则重复步骤2；4最后得到最小生成树T=<V,TE>，其中TE为最小生成树的边集。第82页，共138页，2022年，5月20日，17点56分，星期五5.3.3连通分析图1中带权图最小生成树求算过程如图2所示。1243566536264551图1带权图124356212435624124356241124356245112435632451图2求带权图最小生成树的过程（a）（b）（c）（d）（e）最小生成树算法第83页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配在多数的应用中，需要解决在网络中选定几个供应中心，并将网络的各边和点分配给某一中心，使各中心所覆盖范围内每一点到中心的总的加权距离最小，实际上包括定位与分配两个问题。定位是指已知需求源的分布，确定在哪里布设供应点最合适的问题；分配指的是已知供应点，确定其为哪些需求源提供服务的问题。第84页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配选址功能涉及在某一指定区域内选择服务性设施的位置，如确定市郊商店区﹑消防站﹑工厂﹑飞机场﹑仓库等的最佳位置。选址问题的数学模型取决于可供选择的范围，以及所选位置的质量判断标准这两个条件。在一个地理网络中，能够从网络的结点和边上找到一些特定的点使它们满足某种优化条件，这些点可用于较简单的定位问题。

选址问题（定位问题）

第85页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配给定一个地理网络D=（V,E），其中V表示地理网络结点的集合，E表示地理网络边的集合。令d(p,q)表示从顶点p到顶点q之间的距离；令R表示矩阵，矩阵的第p、q个元素是d(p,q)，矩阵R的元素称为顶点—顶点距离（Vertex-vertexDistance，VVD）；表示从网络边（vi,vj）上的f_点到结点q之间的距离，这个长度称为点—顶点距离（Point-vertexDistance，PVD）；表示从顶点到网络边（vi,vj）的最大距离，此长度称为顶点—弧距离（Vertex-arcDistance）。选址问题（定位问题）

第86页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配从顶点p到任一顶点的最大距离从顶点p到所有顶点的总距离从顶点p到所有弧的最大距离从顶点p到所有弧的总距离从网络边（vi,vj）上的f_点到任一结点的最大距离从网络边（vi,vj）上的f_点到所有各结点的总距离选址问题（定位问题）

第87页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配基于以上变量的定义，给出有关中心点和中位点的概念。使最大距离达到最小的位置称为网络的中心点，使最大距离总和达到最小的位置称为网络的中位点。一个地理网络的中心点主要有中心、一般中心、绝对中心和一般绝对中心等；一个地理网络的中位点主要有中位点、一般中位点、绝对中位点和一般绝对中位点等。选址问题（定位问题）

第88页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配地理网络的中心点是网络中距最远结点最近的一个结点vx，即地理网络的一般中心是距最远点最近的一个结点vx，即地理网络的绝对中心是距最远结点最近的任意一点vx，即地理网络的一般绝对中心是距最远点最近的任意一点vx，即选址问题（定位问题）

第89页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配地理网络的中位点是从该点到其他各结点有最小总距离的一个结点vx，即地理网络的一般中位点是从该点到其他各结点有最小总距离的一个结点vx，即地理网络的绝对中位点是从该点到所有各结点有最小总距离的任意一点，即地理网络的一般绝对中位点是从该点到所有各条网络边有最小的总距离的任意一点，即选址问题（定位问题）

第90页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配实例分析现有一指定邮区，需在该邮区范围内的5个城市中选择一个城市作为中心局所在地。将城市用图的顶点表示，各顶点之间的连线表示各城市间邮件的进、出和转口的关系，连线的权值则设为两城市间运送邮件所耗费的成本，邮件的运送成本包含诸如路程长短、邮运工具、业务量的大小、邮件的流向及经转次数等因素。邮区城市示意图51342312572341选址问题（定位问题）

第91页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配首先先求出R矩阵。可利用Floyd算法或Dantzig算法求出R矩阵。邮区城市示意图51342312572341R矩阵选址问题（定位问题）

第92页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配如果选择以中心点法为标准，得到的顶点指的是该顶点所代表的城市与其他城市间的邮件往来的最大成本为最小。可以先求出从城市1到其他各个城市的运送邮件的最大成本，然后依次求出城市2、3、4、5到其他各个城市运送邮件的最大成本，计算过程如下：

选址问题（定位问题）

从顶点4到其他顶点的最大距离为3，即从城市4向其他城市运送邮件的最大成本为最小，可知邮区中心局地址设置在该城市，可保证从邮区中心局到该邮区的其他收投点的邮件的最大运送成本为最小。第93页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配如果选择以中位点法为标准，则求出的中位点的实际意义表示从该点向其他城市运送邮件的总成本为最小。根据中位点的数学表达式要先求出SVV（i）：选址问题（定位问题）

由此得即顶点4是该邮区的中位点，从城市4向其他各城市运送邮件的总成本为最小。第94页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配分配问题在现实生活中体现为设施的服务范围及其资源的分配范围的确定等一类问题，资源的分配能为城市中的每一条街道上的学生确定最近的学校，为水库提供其供水区等。资源分配是模拟资源如何在中心（学校、消防站、水库等）和周围的网线（街道、水路等）、结点（交叉路口、汽车中转站等）间流动的。分配问题第95页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配实际生活中，许多行业和部门都涉及到利用服务设施提供相关服务的问题，常见的服务范围有：①到服务设施或中心的最短距离不超过一定范围的覆盖区域，如一个供水站50公里以内的区域，构成该供水站的供水区；②到服务设施或中心的最短时间不超过一定限制的覆盖区域，如一个消防站10分钟所能到达的范围是该消防站在10分钟的服务范围。中心服务范围分析作为基本网络分析功能，是指一个服务中心在给定的时间或范围内能够到达的区域，它为评价服务中心的位置及其通达性提供了有利工具。分配问题第96页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配确定中心服务范围的基本思想是依次求出服务费用不超过中心阻值的路径，组成这些路径的网络结点和边的集合构成了该中心的服务范围。主要步骤为：根据拓扑关系，计算地理网络的最大邻接结点数。1构造邻接结点矩阵和初始判断矩阵描述地理网络结构。2应用广度优先搜索算法确定地理网络中心的服务范围。3分配问题第97页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配具体求解中心资源的分配范围时与服务范围的搜索方法类似，设D=（V,E,c）为一给定的带中心的地理网络，P为满足资源分配范围条件的网络边和网络结点的集合。算法的主要步骤如下：①将中心所在的结点作为V0，放入已标记结点集S中，并初始化有关变量；②如果整个网络都已被分配，则停止；否则，执行步骤④；③如果总货源量都已被分配，则停止；否则，执行步骤④；④在尚未分配的结点集中，寻找距离中心V0路径最短的结点Vn，假设Vn的前一点是Vm，将（Vm,Vn）作为当前处理的边；分配问题⑤⑥⑦⑧+⑨⑩第98页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配⑤判断网络流在边（Vm,Vn）上的运行情况：

⑥如果（Vm,Vn）边流向Vn点的流量为0，则该边停止运输；如果（Vm,Vn）边流向Vn点的流量小于该边的需求量，则将该边的一部分分配给中心后，停止运输；如果（Vm,Vn）边流向Vn点的流量大于该边的需求量，则考察网络流在Vn点上的接受量PRn、消耗量PFn和发出量POn；⑦判断网络流在结点上的运行情况，与网络流在边上的运行情况类似；⑧如果POn≤0，则该点停止运输；如果POn

＞0，则考察与结点Vn相邻的边；分配问题⑨⑩第99页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配⑨如果存在与Vn点相邻的边（Vn,Vr），该边尚未分配而该边的点Vn已经分配，则给该边分配它所需要的量LDnr，此时，从Vn点流向其他相邻的、且另一端点尚未分配的边的流量为POn

=POn－LDnr；⑩记录已分配的结点Vm、边（Vm,Vn）或边（Vn,Vr），并从未分配的点、边集合和中减去这些元素，将点Vn作为当前结点。最后，计算全网络点或边的总消耗量LET、PET，点或边的分配数LNT、PNT以及总的消耗量TF。分配问题END第100页，共138页，2022年，5月20日，17点56分，星期五5.3.4资源分配许多资源分配问题的供应点布设要求满足多种组合条件，比如在选择供应点时不仅要求使总的加权距离最小，有时还要使总服务范围最大，有时又限定服务范围最大距离不能超过一定的限值等，这些问题都可以分解为多个单目标问题，利用单目标方程即最小目标值法来求解。所谓目标方程是用数学方式表达