叠置分析3多边形与多边形叠加课件

,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,地 理 信 息 系 统,胡 嘉 骢,*,GIS,基本空间分析,2008-11,BNUEP,地理信息系统,GIS,基本空间分析,不 动 产 学 院,主讲教师：胡嘉骢,空 间 分 析 类 型,基本的空间分析包括：,空间查询,空间量算,缓冲区分析,叠置分析,网络分析,空间统计分析,空间插值,地形分析,空间分析模型,简单的空间分析,复杂的空间分析,面向应用的空间分析,2,2008-11,叠 置 分 析,叠置分析,是将,同一地区,的,两组,或,两组以上,的要素（地图）进行,叠置,，产生,新的特征,（新的,空间图形,或空间位置上的,新属性,的过程）的,分析方法,。,参加叠置分析的空间要素必须具有,相同的尺度,及,统一的空间参照系统，,叠加的结果将会使,几,何形状和属性都发生改变。,叠置分析的类型包括：,视觉信息的叠加：,将多个图层内容放在一起进行显示,矢量要素类型叠加,点与多边形的叠加,线与多边形的叠加,多边形叠加,最常用的叠加分析。,栅格图层叠加：,利用某种计算模型对不同栅格图层中相同位置像元的值进行计算，得到新的栅格图层。,叠置分析,3,2008-11,叠 置 分 析,1,、点与多边形叠加,实际上是计算,多边形对点的包含关系。,它通过点是否在多边形内的判别来完成。在完成点与多边形的几何关系计算之后，还要进行,属性信息的处理。,最简单的方式是将多边形属性信息叠加到其中的点上（或将点的属性叠加到多边形上，用于标识该多边形）。,通过叠加可以计算出每个多边形类型里有多少个点，以及这些点的属性信息。,A,B,1,2,1A,2B,+,=,输出地图包含输入地图相同的点要素，但点的属性已为其落入的多边形的属性,4,2008-11,叠 置 分 析,1,、点与多边形叠加,点号,名称,编码,功能,所属辖区,1,A,2,C,3,C,4,B,5,B,6,B,叠加结果：改变点属性内容,1,2,3,4,5,6,A,B,C,A,B,C,1,2,3,4,5,6,+,5,2008-11,叠 置 分 析,2,、线与多边形叠加,实际上是比较线上坐标与多边形坐标的关系，,判断线是否落在多边形内。,通常是计算线与多边,形的交点，只要相交就产生一个结点，将原线打断成一条条弧段，并,将原线和多边形的属性信,息一起赋给新弧段。,叠加的结果产生一个新的数据层面：每条线被它穿过的多边形打断成,新弧段图层,，同时，产生,一个,相应的属性数据表,记录原线和多边形的属性信息,。,输出地图包含新的弧段层，且产生新的属性数据表,A,B,1,1A,1B,+,=,6,2008-11,叠 置 分 析,2,、线与多边形叠加,线号,原线号,名称,等级,所属辖区,1,1,B,2,2,C,3,3,C,4,3,A,5,1,C,A,B,C,A,B,C,1,2,3,1,5,2,3,4,+,叠加结果：产生新弧段,改变线属性内容,7,2008-11,叠 置 分 析,3,、多边形与多边形叠加,实际上多边形与多边形的叠加是指将两个不同图层的多边形要素叠合，,根据两组多边形边界的交,点来,建立具有多重属性的多边形（合成叠置）,或,进行多边形范围内的属性特性的统计分析（统计,叠置），,以解决地理变量的多准则分析、区域多重属性的模拟分析、地理特征的动态变化分析、,区域信息提取等问题。,叠合后产生输出新图层的属性信息与原多边性的继承关系，,要根据叠合的不同方式而定。,合成叠置,需要进行,属性合并,。,方法可用,加、减、乘、除,，也可取,平均值、最大最小值,，或,取逻辑,运算的结果,等。,统计叠置,是确定一个多边形中含有其它多边形的属性类型的面积等，即把其它图上的多边形的属,性信息,提取到,本多边形中来。,8,2008-11,叠 置 分 析,3,、多边形与多边形叠加,逻辑叠加方法包括：,布尔计算（,Boolean,）：交集、并集、补集和分割,注意：,Clip,与,Intersect,的区别,9,2008-11,叠 置 分 析,3,、多边形与多边形叠加,+,=,(,输入地图,) AND (,叠加地图,) OR (,输入地图,),层的叠加（补集）,10,2008-11,叠 置 分 析,操作步骤：,a,）对原始数据（多边形）形成,拓扑关系。,b),多层多边形数据的,空间叠置,，形成新层。,c,）对新层中的多边形,重建拓扑。,d,）,删除多余多边形,（或处理意义多边形）提取感兴趣的部分。,操作难点：,a,）叠置后会产生,大量,对用户,无关,的多边形，在用户做提取前仍需建拓扑，工作量大。且新层的多边形数目不仅与原多边形数目有关，还与其复杂程度有关，越复杂，多边形数目越多。,b,）由于叠置的多边形往往是不同类型或不同比例尺的地图，在叠置时就会产生一系列无意义的多边形，即产生多边形叠置的,位置误差，,需要进行处理。,c,）建新多边形拓扑和多边形与新属性的,连接,，工作量大。,3,、多边形与多边形叠加,11,2008-11,叠 置 分 析,基于栅格数据的叠置分析,一、多层栅格数据的叠置,实际上是对图层之间的,对应单元数值进行数学运算,，叠合之后的图层中单元的数值是对应单元,数值进行数学运算的结果，原理上比较简单（相对矢量的叠合）。,A,，,B,，,C,等表示各层上的属性值，,f,函数取决于叠置的要求。,+,.,U,f(A,B,C,),栅格地图计算器,12,2008-11,叠 置 分 析,距离,得分,0500,米,0,（不必建设）,5001000,米,1,10001500,米,2,1500,米,3,（必须建设）,人口密度,得分,0 - 50,0,（无需建设）,50 - 100,1,100 - 200,2,200 - 300,3,（需要建设）,基于栅格数据的叠置分析,R_school,使用性质,得分,工业或绿地,0,（不能建设）,商业,1,居住,2,（可以建设）,R_popu,R_land,中学的选址结果,R_land R_popu R_school,乘法运算,需要进行哪种运算？,13,2008-11,叠 置 分 析,基于栅格数据的叠置分析,为什么用权重 ？,为什么要数值标准化？,14,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数,据的空间变换,类型：,局部运算（点运算）,邻域运算,掩模格网,即把栅格数据分析局限于不含,无数据单元（,No Data,）,的一种格网范围,数据查询和再分类,可实现掩模格网,Map Query:,排除分析之外的单元,=,特定值,Reclassify,：,No Data =,特定值,无数据不是零,，零是有效数据，无数据区域是指格网单元缺乏数据。,15,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,局部运算（点运算）,定义：,只将单个对应栅格单元的属性作某种运算得到新图层属性，而,不受其邻近单元,的影响，,不涉及位置运算,。,算术运算,三角函数,对数,幂,U=,f,(A, B,),A,A,B,C,U,U,16,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,局部运算（点运算）,应用举例：通用土壤流失方程,A,=,R K L S C P,，其中，,A,：平均土壤流失量；,R,：降雨强度；,K,：土壤可蚀性；,L,：坡长,S,：坡度；,C,：耕作因子；,P,：水土保持措施因素,17,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,邻域运算,定义：,计算新图层属性时，不仅考虑原始图上对应栅格本身的值，还需考虑,该图元邻域关联的其他图元值的影响。,邻域运算一般在单个图层上进行,通过所确定的邻域类型扫描整个格网。,邻域运算要素,中心点,邻域大小与类型,邻域运算函数,18,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,邻域运算,统计：,最大值、最小值,平均值、标准差,值域、总和、模、,测度：,多数、少数、种类、,19,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,邻域运算,低通滤波,平均值,高通滤波,原图,-,低通滤波,邻域运算的运用,滤波,20,2008-11,叠 置 分 析,基于栅格数据的叠置分析,二、栅格数据的空间变换,邻域运算,邻域运算的运用,地形分析,21,2008-11,叠 置 分 析,基于栅格数据的叠置分析,三、栅格数据的距离量算,定义：,计算与源单元（制定格网单元）的距离。,同层格网,全局运算，,扩展邻域运算,距离种类：,自然距离,成本距离,1.414 X Grid Cell,Grid Cell,22,2008-11,叠 置 分 析,基于栅格数据的叠置分析,自然距离量算：,单位：格网单元,类型：,连续距离对源单元建立缓冲，形成距离带,对格网中每个单元确定于最近源单元的自然距离,ArcView,实现,连续：,Find Distance,最近：,Assign proximity,23,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离量算：,定义：,移经每个单元的,成本或阻抗,作为距离单位的距离量测分析方法，在成本距离中，直线距,离不一定是最佳的通道。,类型：,最小成本表面,最小成本路径,24,2008-11,叠 置 分 析,基于栅格数据的叠置分析,自然距离与成本距离的对比：,25,2008-11,2,1,2,4,1,5,3,6,7,3,3,6,5.7,4.5,4.9,3.5,4.2,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,源单元矩阵、成本矩阵、连接成本矩阵,成本矩阵构成：,不同成本之和,例：选址 源地到目的地的距离,+,地形（坡度等级）,+,地质,+,河流,+,用低成本,+,居住中心距离,连接成本矩阵计算,横向：平均值,对角线：平均值,X1.414,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,26,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,目标：最小累计成本路径,方法：循环迭代,最小累计成本计算,示例：,源点格网矩阵,成本格网矩阵,连接格网矩阵,指派格网矩阵,输出格网矩阵,B,A,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,源点矩阵,成本矩阵,27,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,3,1,2,1,2,1,4,1,5,2,6,7,1,3,4,4,2.8,3,4.9,2.5,5,3.5,5.7,2.8,连接矩阵,28,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,1.5,B,4.2,1,1.5,2.8,A,2,1,1.5,1.5,2.0,2.8,4.2,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,29,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,1.5,B,4.2,1,1.5,2.8,6.7,4.5,A,2,4,1,1.5,1.5,2.0,2.8,4.2,1.5,1.5,2.0,2.8,4.0,6.7,4.5,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,30,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,3.5,1.5,B,3,5.7,4.0,1,1.5,2.8,6.7,4.5,A,2,1.5,1.5,2.0,2.8,4.0,4.5,6.7,2.0,2.8,4.0,5.7,4.5,6.7,3.0,3.5,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,31,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,3.5,1.5,B,3,5.7,4.0,1,1.5,2.8,6.7,4.5,A,2,5.5,2.8,4.0,5.7,4.5,6.7,3.0,3.5,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,2.0,2.8,4.0,5.7,4.5,6.7,3.0,3.5,5.5,32,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,3.5,1.5,B,3,5.7,4.0,1,1.5,2.8,6.7,4.5,A,2,5.5,2.8,4.0,5.7,4.5,6.7,3.0,3.5,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,5.5,4.0,5.7,4.5,6.7,3.0,3.5,5.5,33,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,4,3.5,1.5,B,3,5.7,4.0,1,1.5,2.8,6.7,4.5,A,2,5.5,1,2,1,2,1,4,1,5,2,3,6,7,1,3,4,4,4.0,5.7,4.5,6.7,3.0,3.5,5.5,4.0,5.5,4.5,6.7,3.5,5.5,5.5,34,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,4,3.5,1.5,B,3,5.7,4.0,1,1.5,2.8,6.7,4.5,A,2,5.5,9.5,3,1,1,B,3,5,1,7,3,4,8,7,A,5,5,7,1,2,3,4,5,6,7,8,最小累计成本矩阵,单元指派矩阵,35,2008-11,叠 置 分 析,基于栅格数据的叠置分析,成本距离的计算：,ArcView,中最小累计成本实现,CostDistance:,aGrid.CostDistance,(costGrid,DirectionFN, allocationFN, maxDistance),CostPath,aGrid.CostPath,(distanceGrid, directionGrid, ByZone),36,2008-11,37,2008-11,缓 冲 区 分 析,定义：缓冲区,是地理空间目标的一种,影响范围,或,服务范围,，具体指在点、线、面实体的周围，自动建立的,一定宽度,的,多边形。,缓冲把地图分为两个区域，一个区域在所选地图要素制定距离之内，另一个在制定距离之外。在指定距离之内的区域称为缓冲区。,数学表达为：,其中,R,为,缓冲宽度,，或,缓冲半径。,作用：,缓冲区分析是,GIS,的基本空间操作功能之一，一般应用于求地理实体的影响范围，即,邻近度问题。,如,道路噪声,影响范围就是沿道路建一定宽度的缓冲区，车流量决定缓冲区半径。如某地区有,危险品仓库,，要分析一旦仓库爆炸所涉及的范围，这就需要进行点缓冲区分析等等。,38,2008-11,缓 冲 区 分 析,基本缓冲区类型：,点：圆形缓冲区,线：长条缓冲区,面：向内、外的缓冲带,39,2008-11,缓 冲 区 分 析,缓冲区变形：,缓冲距离不一定为常数：主流用,200,米，支流用,100,米,可形成缓冲环：核电站：,5km, 10km, 20km, 50km,单侧缓冲区,单个缓冲区与完整缓冲区,40,2008-11,缓 冲 区 分 析,矢量缓冲区建立：,多个实体的缓冲区，各实体缓冲区的并，半径可以不同,1,、线的重采样，对线进行化简，以加快缓冲区建立的速度。,-,线的矢量数据压缩算法。,2,、建立线缓冲区，在线的两边按一定的距离（缓冲距）绘平行线，并在线的端点处绘半圆，连成缓冲区多边形。,3,、重叠处理：对缓冲区边界求交，并判断每个交点是出点还是入点，以决定交点之间的线段保留或删除。这样就可得到岛状的缓冲区。,以线状地物为例,41,2008-11,缓 冲 区 分 析,栅格缓冲区建立：,算法比较简单，核心问题是,距离变换,。,栅格数据,距离变换,提取一定宽度的多边形,缓冲区,42,2008-11,43,2008-11,网 络 分 析,什么是网络分析？,很多自然界及人类的社会、经济活动都是以网络形式运作，网络的形式、容量和效率与我们的生,活息息相关，例如铁路、公路、电力网、电讯网、煤气管网、各种服务网络、航空网络和街道网,络等。,我们需要知道：,从甲地道乙地的最短路径是什么？,如何设定一个服务中心？,特定位置的服务中心是的服务范围？,从一个位置到另一个位置的通行程度如何？,从出发地到目的地，有多少条可行路线？,如何在街道图上定位一个发生的事件？,44,2008-11,网 络 分 析,数学定义：,以,图论和运筹学,为基础，通过研究网络的状态以及模拟和分析资源在网络上的,流动和分配,情况，对网络结构及资源等的,优化,问题进行研究,GIS,定义：,依据,网络拓扑关系,，通过考察网络元素的空间与属性数据，以数学理论模型为基础，对网络的性能特征进行多方面的,分析计算技术,网络分析的定义,45,2008-11,网 络 分 析,网络类型：,平面网络,：除节点外，网络链不相交，如公路网；,非平面网络：,网络链可相交，如航空网络,网络层次：,精细尺度网络：,如街道网络,中尺度网络：,如交通规划,粗尺度网络：,如高速公路网,46,2008-11,网 络 分 析,网络的组成：,1,、网络：,是一系列,联结的弧段,，是形式,物质、信息,流通的通道。,2,、网络基本要素：,结点,网络中分布的中间点、交点等，弧段交点,链,连接节点并具有运输能力的线段（弧段）,47,2008-11,网 络 分 析,3,人,10,人,5,人,学校,8,路,公共汽车起点站,8,路,公共汽车终点站,6,人,路径,站点,中心,拐点,障碍点,段,地理网络的特殊要素,48,2008-11,结点,站点,网 络 分 析,站点：,网络中资源的,上下,结点，但不一定在网络结点上。,如公交路线的汽车站、邮政网络的邮筒等。,中心：,网络中具有集中或分散资源的,结点,。,如公交系统的汽车总站、水系中的水库、街道网络中的学校等,障碍点：,网络中限制资源流通的点，如河流的闸门,拐点：,网络中资源,方向发生改变,的点，有,方向控制,功能,段：,弧或弧的一部分，由起点和终点，可通过百分比形式衡量,路径：具有属性的有序弧段的集合，,表示一线型特征，如公交系统中北师大到中山大学路段,路径系统：路径和段的集合,，常用来管理具有相同属性的多个线形特征。如城市公交系统中的行,车路线。路径系统要使用统一的度量标准,地理网络的特殊要素,49,2008-11,网 络 分 析,阻抗,：,资源在网络中,运行的,阻力,大小，用时间、成本等衡量。它,与链的长度、方向、属性、结点,类型有关,，,不同类型的阻抗要具有统一的量纲,。,适用对象,：,链（弧段、段）,、,结点（拐点）,资源需求量：,网络链或结点能收集的或可提供给某一中心的资源量。如水网中水管的供水量、沿,街道学生分布等。,适用对象：,弧段、结点、,站点资源需求量（上、下）,网络要素的属性,3,人,10,人,5,人,学校,50,2008-11,网 络 分 析,资源容量,：,中心,为满足各弧段要求而能提供的,资源总量,，或从一中心流向（接收）另一中心的资,源总量，如水库容量、学校最大学生数等,适用范围：,中心点,最大容量、服务范围、服务延迟数等,事件：路径系统,中某一路径的,分段属性,，其属性由用户定义，用路径的度量表示,其类型包括：,点事件：与一个位置对应，一个度量,线事件：区段，两个度量,连续事件,网络要素的属性,51,2008-11,网 络 分 析,1,、网络的数据结构,具有图的结构,结点,/,结点集：图中任意两条线段交点,边,/,边集：图中的任意一条边（弧段）,图：有限结点和边的集合,网络：有向图,具有一般地理数据的内容,拓扑关系,空间数据,属性数据,网络要素的表达,52,2008-11,网 络 分 析,2,、链弧,网络要素的表达,链弧号,起结点,终结点,长度,(km),正方向阻强,(km/h),反方向阻强,(km/h),资源需求量,20,2,4,145.3,35,55,（,-1:,表示不通，单行道）,2,55,35,4,3,、转弯：,M,条弧相连共有转弯个数,结点号,从弧段,至弧段,角度,时间阻强,(s),34,L2,L1,90,60,34,L1,L1,180,30,34,L2,L3,-90,-1(,不允许拐弯）,34,L1,L3,0,0(,无阻强,),34,L1,L2,L3,停靠点,53,2008-11,网 络 分 析,网络要素的表达,4,、停靠点、中心,停靠点：,直接在相应的结点上附上需求量属性，,负为下卸，正值为装载。,中心：,资源最大容量、服务范围和服务延迟数（在其它中心达到某个数量时才提供服务）。,结点号,需求量,45,35,46,-20,结点号,资源最大容量,服务范围,服务延迟数,24,1000,200,0,中心：学校,停靠点,54,2008-11,网 络 分 析,一、路径分析,二、资源分配与定位,三、连通分析,四、流分析,五、爆管分析,网络分析的应用,55,2008-11,网 络 分 析,路径分析,1,、最短（最佳）路径分析含义：,在网络中从起点经一系列特定的结点至终点的资源运移的最佳路线，即,阻力最小,的路径。,2,、路径分析包括：,1,）静态求最佳路径：,在给定每条链上的属性后，求最佳路径。,一般分析从,p1,到,p2,共有,n,条路径，计算各路径上的权数之和，取最小者为最佳路径。,2,）,N,条最佳路径,给定起点、终点，求代价最小的,N,条路径，事实上，理论上只有一条，实际上需选择,N,条近似最佳路径。,3,）最短路径或最低耗费路径,确定起点、终点和要经过的中间点、链，求最短或耗费最小路径。,4,）动态最佳路径分析,实际中权数可能是变化的，可能会临时产生一些障碍点，要动态计算最佳路径。,3,、核心算法：,求两点间的权数最小路径，常用的算法是,Dijkstra,算法。,56,2008-11,网 络 分 析,最佳路径的数学模型：,最佳路径求解的依据：,1,、最佳矩阵计算：,最佳含义要求,两点之间直接相连，不直接相连着为不通,2,、简单路径，即互不相交,3,、整体最优则局部最优：,即若两点,S,和,T,之间有一条最佳路径，则该路径上任何点到,S,的路径都是最佳的。,路径分析,直接求解比较困难，目前主要采用,戴克斯徒拉,在,1959,年提出的算法。,57,2008-11,网 络 分 析,Dijkstra,算法步骤：,寻找从,1,点到其他点的最短路径,路径分析,58,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,0,1,2,3,4,5,0,1,2,3,4,5,0,10,30,100,0,5,0,50,0,10,20,0,60,0,4,3,0,1,5,2,100,60,20,30,10,50,5,10,59,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,第一步：初始化相关数组,X = 0,Y = 1,2,3,4,5,D = 0, , 10, 30, 100,P = 0, 0, 0, 0, 0, 0,第二步：在,Y,中寻找到,0,的最佳路径,X = X + 2 = 0, 2,Y = Y 2 = 1, 3, 4, 5,D =0, ,10,60, 30, 100,P = 0, 0, 0, 2, 0, 0,4,3,0,1,5,2,100,60,20,30,10,50,5,10,60,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,第三步：在,Y,中寻找从,0,到其余点的最佳路径,X = X + 4 = 0, 2, 4,Y = Y 4 = 1, 3, 5,D =0, , 10,50,30,90,P = 0, 0 ,0,4, 0,4,4,3,0,1,5,2,100,60,20,30,10,50,5,10,61,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,第四步：在,Y,中寻找从,0,经由,4,到其余点的最佳路径,X = X + 3 = 0, 2, 4, 3,Y = Y 3 = 1, 5,D =0, , 10,50, 30, 90,P = 0, 0, 0, 4, 0, 4,4,3,0,1,5,2,100,60,20,30,10,50,5,10,62,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,第五步：在,Y,中寻找从,0,经由,3,到其余点的最佳路径,X = X + 5 = 0, 2, 4, 3, 5,Y = Y 5 = 1,D =0, , 10, 50, 30,60,P = 0, 0, 0, 4, 0,3,4,3,0,1,5,2,100,60,20,30,10,50,5,10,63,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,第六步：在,Y,中寻找从,0,经由,5,到其余点的最佳路径,由于,1,中的值为，故退出,4,3,0,1,5,2,100,60,20,30,10,50,5,10,64,2008-11,网 络 分 析,路径分析,Dijkstra,算法例解：,寻找从,0,点到其他点的最短路径,开始点,到结点,最佳路经,最佳值,0,1,无,无,0,2,0,，,2,10,0,3,P(3)=4,P(4)=0,0,4,3,50,0,4,0,4,30,0,5,P(5)=3,P(3)=4,P(4)=0,0,4,3,5,60,4,3,0,1,5,2,100,60,20,30,10,50,5,10,65,2008-11,网 络 分 析,最佳路径算法评价：,对每个点重复,Drikstra,步骤,运算复杂，速度较慢,算法复杂度,O(n3),Floyd,算法,邻接矩阵计算,继续加强新算法的设计,大规模数据的处理能力,路径分析,66,2008-11,网 络 分 析,资源定位与分配模型,是通过网络模拟，根据需求点的空间分布，在一些候选点中选择给定数量的,供应点以使预定的目标方程达到最佳结果。,最佳分配中心，最优配置。,定位问题,是指已知需求源的分布，确定在哪里布设供应点最合适的问题；,分配问题,是确定这些需求源分别受哪个供应点服务的问题。,一般用于规划重要的公共设施：,普通设施,医院、教育、养老院等,应急设施,消防队、急救站等,资源分配与定位,67,2008-11,网 络 分 析,资源分配与定位,图书馆设在哪儿合适呢？,居民分布点,公共设施,划分服务区的问题,68,2008-11,网 络 分 析,资源分配与定位,1,和,2,那个去合适呢？,1,2,居民分布点,服务点,寻找最佳设施的问题,69,2008-11,网 络 分 析,在运筹学的理论中，定位与分配模型常可用,线性规划,求得全局性的最佳结果。由于其计算量以及,内存需求巨大，所以在实际应用中常用一些,启发式算法,来逼近或求得最佳结果。,常用模型包括：,最小距离法（,P,中值定位模型）：,在,m,个候选点中选择,P,个供应点为,n,个需求点服务，使得为这几,个需求点服务的总距离,(,或时间或费用,),为最少。常用于,图书馆、食物配送、健康设施、垃圾站设,置等。,最大覆盖模型：,指定时间或距离到达需求的覆盖面最大，常用于,紧急救护、消防服务等。,最大最小距离模型：,保证行程最小的情况下确保需求点在指定的最大距离范围内。,等分配模型：,服务点的服务在数量上相等,阀值限制模型：,服务对象尽可能超过指定的量,容量限制模型：,满足最大容量情况下的最大服务范围,资源分配与定位模型,70,2008-11,网 络 分 析,设施分析,案例：某人要去医院看病，现在为他设计一条从他家到医院的最短路线。,具体的操作如下：,把相关主题添加进视图目录表中。,71,2008-11,网 络 分 析,路径分析,激活,Customer.shp,，选择起始点（如某人的家，黄色的点表示选中的点）。,2,72,2008-11,网 络 分 析,路径分析,激活,S_fran.shp,（路径主题），主题突出显示,从,【Network】,菜单选择,【Find Closest Facility】,命令,3,4,73,2008-11,网 络 分 析,路径分析,4,、选择,Hospital.shp,。,5,、选择目的地个数。,6,、输入距离（到达费用，可以是距离或者时间）。,7,、载入事件。,4,5,6,7,11,最短路径生成,10,9,8,8,、选择,Customer.shp,。,9,、点击,ok,。,10,、选择事件（刚才选中的起始点）。,11,、点击路径生成按钮。,74,2008-11,网 络 分 析,连通分析,最小生成树,1,、含义：,连通图：,如果一个图中，任意两个节点之间都存在一条路。,树：,若一个连通图中不存在任何回路，则称为树。,最小生成树：,生成树是图的极小连通子图。,生成树,T,的权数：,设,T,为图,G,的一个生成树，若把,T,中各边的权数相加，则这个和数称为生成树,T,的权数。在,G,的所有生成树中，权数最小的生成树称为,G,的最小生成树。,2,、应用：,类似在,n,个城市间建立通信线路这样的连通分析问题。图的,顶点,表示,城市，边,表示两城市间的,线路，边,上所赋的,权值,表示,代价,。对,n,个顶点的图可以建立许多生成树，,每一棵树,可以是一个,通信网,。若要使通信网的,造价最低，,就需要构造图的,最小生成树。,1,2,6,5,4,3,16,11,18,6,5,6,75,2008-11,网 络 分 析,连通分析,最小生成树,3,、构造最小生成树的依据有两条,4,、算法,（,Kruskal,，克罗斯克尔算法，也叫“避圈”法）,设图,G,是由,m,个节点构成的连通赋权图，则构造最小生成树的,步骤,如下：,1,）先把图,G,中的各边按权数从小到大重新排列，并取权数最小的一条边为,T,中的边。,2,）在剩下的边中，按顺序取下一条边。若该边与,T,中已有的边构成回路，则舍去该边，否则选进,T,中。,3,）重复,2,），直到有,m-1,条边被选进,T,中，这,m-1,条边就是,G,的。,1,）在网中选择,n,1,条边连接网的,n,个顶点；,2,）尽可能选取权值为最小的边。,1,2,6,5,4,3,16,19,33,21,11,14,18,6,5,6,1,2,6,5,4,3,16,11,18,6,5,6,1,2,6,5,4,3,16,11,18,5,6,赋权图,最小生成树之一,最小生成树之二,76,2008-11,网 络 分 析,流分析,1,、概念：,1,）流：,资源在结点间的传输。,2,）流分析：,按照某种优化标准（时间最少、费用最低、路程最短或运送量最大等）设计资源的运送方案。,3,）最小费用最大流量：,不仅要考虑使网络上的流量最大，而且要使运送流的费用或代价最小。,2,、为了实施流分析，就要根据最优化标准的不同扩充网络模型。,例如：把结点分为,发货中心,和,收货中心,，分别代表资源运送的起始点和目标点。这时发货中心的容量代表,待运送资源量,，收货中心的容量代表它所,需要的资源量,。弧段的相关数据也要扩充，如果最优化标准是,运送量最大,，需要设定边的,传输能力,；若是,费用最低,，则要设定边的,传输费用,等。,3,、计算：网络流理论,是它的计算基础。,77,2008-11,网 络 分 析,爆管分析,定义：,水、油、气等物质网络上管道或点设备（阀门、仪表等）发生故障,的分析问题。,目的：,对该点断流，即检索出全部与该点直接相连的各种断流设备。,算法：,基于矢量数据的爆管算法,基于栅格数据的爆管算法,78,2008-11,79,2008-11,80,2008-11,谢谢！,请课后复习！,81,2008-11,