1、第8章 GIS空间分析F最短路径分析最短路径分析 在最短路径选择中,两点之间的距离可以定义为在最短路径选择中,两点之间的距离可以定义为实实际的距离际的距离,也可定义为,也可定义为两点间的时间、运费、流量两点间的时间、运费、流量等等,可定义为,可定义为使用这条边所需付出的代价使用这条边所需付出的代价。因此,。因此,可以对不同的专题内容进行最短路径分析可以对不同的专题内容进行最短路径分析FDijkstra 算法算法基本思想:把图的顶点分为基本思想:把图的顶点分为S,T两类两类,若起始点若起始点u到某到某顶点顶点x的最短通路己求出的最短通路己求出,则将则将x归入归入S,其余归入其余归入T,开开始时始
2、时S中只有中只有u,随着程序运行随着程序运行,T的元素逐个转入的元素逐个转入S,直直到目标顶点到目标顶点v转入后结束转入后结束 一个道路网络中的城市间的链一个道路网络中的城市间的链路阻抗路阻抗六个节点间的阻抗矩阵六个节点间的阻抗矩阵 13 19 (6)13 13 (5)13 25 58(4)19 25 3953(3)39 20(2)585320(1)(6)(5)(4)(3)(2)(1)节点节点1到其他点的最短路径到其他点的最短路径72p13+p366171p14+p455158p144153p133120p1221最小累计阻抗最小累计阻抗最短路径最短路径终节点终节点始节点始节点0-5 1000
3、4 300-2 100-5 1000-4 300-2-3 10+50=600-5 1000-4-5 30+60=900-4-3 30+20=500-2-3 10+50=600-5 1000-4-5 30+60=900-4-3-5 30+20+10=600543218.3 路径分析和网络应用F两者都涉及两者都涉及运动和线运动和线要素要素F路径分析路径分析是基于是基于栅格栅格数据数据F网络应用网络应用是基于是基于矢量矢量并建立并建立拓扑拓扑关系的数据关系的数据F共用相同的术语和概念,但是共用相同的术语和概念,但是数据格式和数据分析数据格式和数据分析环境环境不同不同8.3.1 路径分析F需要一个需
4、要一个源栅格源栅格、一个、一个费用栅格费用栅格,耗费距离量测耗费距离量测、和生成最小累计耗费路径的和生成最小累计耗费路径的算法算法1.1 源栅格F定义源栅格单元定义源栅格单元F只有源位置只有源位置有单元值有单元值,其他单元格没有数值,其他单元格没有数值F源位置单元可以是源位置单元可以是起点起点也可以作为也可以作为目标目标F路径分析获得到源栅格单元路径分析获得到源栅格单元最小耗费路径最小耗费路径1.2 耗费栅格F定义移动通过每个栅格的定义移动通过每个栅格的耗费或阻抗耗费或阻抗两大特征两大特征:1 每个单元格的耗费为每个单元格的耗费为不同耗费的总和不同耗费的总和2 花费可以表示真花费可以表示真实或
5、相对花费实或相对花费耗费栅格生成耗费栅格生成1.从列出从列出耗费变量耗费变量开始开始2.然后对然后对每个每个变量确定栅格单元的数据变量确定栅格单元的数据3.使用使用局部运算局部运算将单独的耗费栅格加起来将单独的耗费栅格加起来4.局部总和是经过每个栅格单元的耗费局部总和是经过每个栅格单元的耗费1.3 直线距离和耗费距离F直线距离为测量每一个像元到最近源的直线距离;直线距离为测量每一个像元到最近源的直线距离;多用在经过路线多用在经过路线没有障碍或等同耗费没有障碍或等同耗费的情况下的情况下例如,在救援飞机飞往最近的医院的实例中,直线距离栅格例如,在救援飞机飞往最近的医院的实例中,直线距离栅格就可以确
6、定从救援飞机所在地点到周围各医院的距离;就可以确定从救援飞机所在地点到周围各医院的距离;然而然而,当救援汽车开往最近医院的实例中,因为地表有各种,当救援汽车开往最近医院的实例中,因为地表有各种类型的障碍物,采用不同的路线的耗费不尽相同类型的障碍物,采用不同的路线的耗费不尽相同F耗费距离是根据通过每个像元的耗费距离是根据通过每个像元的某个或某几个属性因子的某个或某几个属性因子的加权加权得到的实际到达源所需的耗费值得到的实际到达源所需的耗费值例如,翻越一座山例如,翻越一座山直线路程耗费较小,但时间耗费比绕行的时间耗费要多。直线路程耗费较小,但时间耗费比绕行的时间耗费要多。实际的地表覆盖类型多样,通
7、过直线距离来到达源是不可能实际的地表覆盖类型多样,通过直线距离来到达源是不可能的,必须要绕道以避开如河流,高山等的障碍物的,必须要绕道以避开如河流,高山等的障碍物F耗费距离是对直线距离的扩展和延伸。耗费距离是对直线距离的扩展和延伸。成本距离的计算原理 accum_cost =a1+(cost_a+cost_b)/2)*Daccum_cost:某一单元:某一单元b的累计通行成本的累计通行成本 a1:上一个相邻单元:上一个相邻单元a的累计通行成本的累计通行成本 cost_a:单元:单元a的成本的成本 cost_b:单元:单元b的成本的成本横向链接的成本距离:横向链接的成本距离:(1+2)/2=1.
8、5对角链接的成本距离:对角链接的成本距离:1.4142 x(1+5)/2=4.21.3耗费距离量测1.3 耗费距离量测 F在生成距离栅格的同时,还可以生成在生成距离栅格的同时,还可以生成服务区栅格和服务区栅格和方向栅格方向栅格。服务区栅格:每一个单元格的值表示其被分配到的服务区栅格:每一个单元格的值表示其被分配到的最近的地物。最近的地物。方向栅格:每一个单元格的值表示其到最近地物的方向栅格:每一个单元格的值表示其到最近地物的方向。方向。1.4 生成最小累计耗费路径F很容易去计算两个单元间的累计耗费很容易去计算两个单元间的累计耗费连接两个单元格的每条链路的成本求和连接两个单元格的每条链路的成本求
9、和F但是要但是要找到最小累计耗费路径就有点困难找到最小累计耗费路径就有点困难F路径要复杂的多。许多不同的路径都可以连接不相路径要复杂的多。许多不同的路径都可以连接不相邻的两个单元邻的两个单元F找到最小累计耗费路径是一个找到最小累计耗费路径是一个迭代过程迭代过程The cost distance for each link(c)and the least accumulative cost distance from each cell(d)are derived using the source cells(a)and the cost raster(b).See Box 18.2 for t
10、he derivation.1.5 耗费距离量测的改进F现有的量测现有的量测假定为一个同向性的表面假定为一个同向性的表面(属性单一、属性单一、直线距离),直线距离),实际上耗费表面不一致,因为地表在实际上耗费表面不一致,因为地表在坡度、高程、坡向坡度、高程、坡向均有变化均有变化F现实的分析还需考虑现实的分析还需考虑由高程栅格计算由高程栅格计算表面距离表面距离(测量真实地面距离)(测量真实地面距离)垂直和水平因子垂直和水平因子F 在计算距离栅格时,除了直接计算直线距离外,还在计算距离栅格时,除了直接计算直线距离外,还可以考虑耗费权重,比如坡度、土地利用类型等,可以考虑耗费权重,比如坡度、土地利用
11、类型等,计算耗费距离栅格。计算耗费距离栅格。1.6 路径分析的应用F规划道路、管线、沟渠、传输线路规划道路、管线、沟渠、传输线路F提取线性要素提取线性要素8.3.2 网络应用 F网络分析网络分析是是运筹学运筹学模型中的一个模型中的一个基本模型基本模型,它的根,它的根本目的是研究、筹划一项网络工程如何安排,并使本目的是研究、筹划一项网络工程如何安排,并使其运行效果最好其运行效果最好如如一定资源的最佳分配,从一地到另一地的运输费一定资源的最佳分配,从一地到另一地的运输费用最低等。用最低等。F其其基本思想基本思想则在于人类活动总是趋于按一定目标选则在于人类活动总是趋于按一定目标选择达到择达到最佳效果
12、的空间位置最佳效果的空间位置。FGIS网络分析的网络分析的主要目的:主要目的:对对地理网络地理网络(如交通网(如交通网络)、络)、城市基础设施网络城市基础设施网络(如各种网线、电力线、(如各种网线、电力线、电话线、供排水管线等)进行电话线、供排水管线等)进行地理分析和模型化地理分析和模型化。网络分析(Network Analysis)F矢量矢量数据特有的空间分析方法。数据特有的空间分析方法。F网络网络是由一组互相关联的是由一组互相关联的弧段、结点弧段、结点和它们的属性和它们的属性所组成的模型,用于表达现实世界中的所组成的模型,用于表达现实世界中的道路、管线道路、管线等事物。等事物。除此之外还要
13、定义一些要素以模拟现实中的供给、除此之外还要定义一些要素以模拟现实中的供给、需求、中心点等事物。需求、中心点等事物。F网络分析的基础:网络分析的基础:线线点拓扑关系点拓扑关系。F依据依据网络拓扑关系网络拓扑关系,根据网络的,根据网络的空间数据、属性数空间数据、属性数据据,对网络的,对网络的特征、性能特征、性能进行分析。进行分析。2.1网络组成 F网络中的基本组成部分和属性:网络中的基本组成部分和属性:链链(Link):网络中流动的管线,如街道、河流、水管等,):网络中流动的管线,如街道、河流、水管等,其其状态属性状态属性包括阻力和需求。包括阻力和需求。结点结点(Node):网络中链的结点,如港
14、口、车站、电站等,):网络中链的结点,如港口、车站、电站等,其其状态属性状态属性包括阻力和需求等。包括阻力和需求等。结点中又有下面几种结点中又有下面几种特殊的类型特殊的类型。障碍障碍(Barrier),禁止网络中链上流动的点。),禁止网络中链上流动的点。拐点拐点(Turn),出现在网络链中的分割结点上,状态属性有),出现在网络链中的分割结点上,状态属性有阻力,如拐弯的时间和限制阻力,如拐弯的时间和限制(如不允许左拐如不允许左拐)。中心中心(Center),是接受或分配资源的位置,如水库、商业),是接受或分配资源的位置,如水库、商业中心、电站等。其状态属性包括资源容量,如总的资源量;中心、电站等
15、其状态属性包括资源容量,如总的资源量;阻力限额,如中心与链之间的最大距离或时间限制。阻力限额,如中心与链之间的最大距离或时间限制。站点站点(Stop),在路径选择中资源增减的结点,如库房、汽),在路径选择中资源增减的结点,如库房、汽车站等,其状态属性有要被运输的资源需求,如产品数。车站等,其状态属性有要被运输的资源需求,如产品数。2.2网络要素的表示 1)链弧)链弧2)转弯:转弯:M条弧相连共有转弯个数条弧相连共有转弯个数N:4 42 255553535链弧链弧号号起结起结点点终结终结点点长度长度(km)正方向阻正方向阻强强(km/h)反方向阻强反方向阻强(km/h)资源需资源需求量求量20
16、24145.33555(-1:表示不表示不通,单行道)通,单行道)结点号 从弧段 至弧段 角度 时间阻强(s)34L2L1906034L1L11803034L2L3-90-1(不允许拐不允许拐弯)弯)34L1L300(无阻强无阻强)34L1L1L2L2L3L3停靠点停靠点3)停靠点、中心的属性F停靠点:直接在相应的结点上附上需求量属性,负停靠点:直接在相应的结点上附上需求量属性,负为下卸,正值为装载,为下卸,正值为装载,F中心:资源最大容量、服务范围和服务延迟数(在中心:资源最大容量、服务范围和服务延迟数(在其它中心达到某个数量时才提供服务)。其它中心达到某个数量时才提供服务)。结点号结点号
17、需求量需求量453546-20结点号结点号资源最大容量服务范围服务延迟数24100020002.3网络分析应用F网络分析的主要用途是:网络分析的主要用途是:1选择最佳路径选择最佳路径,包括路径的查找和通达度测定;,包括路径的查找和通达度测定;2选择最佳布局中心的位置选择最佳布局中心的位置,包括配置问题和城市交通,包括配置问题和城市交通规划模型。规划模型。F网络分析的基本方法:网络分析的基本方法:1.路径分析路径分析2.最近设施最近设施 3.服务区分析服务区分析4.资源分配资源分配5.选址分析选址分析2.3.1 最佳路径分析1、在网络中从起点经一系列特定的结点至终点的资、在网络中从起点经一系列特
18、定的结点至终点的资源运移的最佳路线,即阻力最小的路径。在网络的源运移的最佳路线,即阻力最小的路径。在网络的节点中寻找节点中寻找累计阻抗最小的路径累计阻抗最小的路径。由两个节点连成,也可在两点间有一些特定的站点由两个节点连成,也可在两点间有一些特定的站点可以帮助运输人员建立多个站点的时间表可以帮助运输人员建立多个站点的时间表紧急响应紧急响应-最短时间到达事故现场最短时间到达事故现场2、所谓最佳路经,是求解网络中两点之间阻抗最小、所谓最佳路经,是求解网络中两点之间阻抗最小的路经,必须按照结点的选择顺序访问网络中的结的路经,必须按照结点的选择顺序访问网络中的结点。点。F最短路径分析最短路径分析 在最
19、短路径选择中,两点之间的距离可以定义为在最短路径选择中,两点之间的距离可以定义为实实际的距离际的距离,也可定义为,也可定义为两点间的时间、运费、流量两点间的时间、运费、流量等等,可定义为,可定义为使用这条边所需付出的代价使用这条边所需付出的代价。因此,。因此,可以对不同的专题内容进行最短路径分析可以对不同的专题内容进行最短路径分析FDijkstra 算法算法基本思想:把图的顶点分为基本思想:把图的顶点分为S,T两类两类,若起始点若起始点u到某到某顶点顶点x的最短通路己求出的最短通路己求出,则将则将x归入归入S,其余归入其余归入T,开开始时始时S中只有中只有u,随着程序运行随着程序运行,T的元素
20、逐个转入的元素逐个转入S,直直到目标顶点到目标顶点v转入后结束转入后结束 旅行推销员问题F在最短路径分析中添加两个约束在最短路径分析中添加两个约束1.推销员必须仅访问选择的各站点一次推销员必须仅访问选择的各站点一次2.推销员可以从任一站点出发,但必须回到出发点推销员可以从任一站点出发,但必须回到出发点F旅行商分析是无序的路径分析。旅行商可以自己决定访问旅行商分析是无序的路径分析。旅行商可以自己决定访问结点的顺序,目标是旅行路线阻抗总和最小(或接近最小)结点的顺序,目标是旅行路线阻抗总和最小(或接近最小)。1-3-2-4-5-101-3-10-9-5-6-8-7-4-2-112345678109
21、13245678109132456781092.3.2 最近设施分析F指在网络上给定一个事件点和一组设施点,为事件指在网络上给定一个事件点和一组设施点,为事件点查找以最小耗费能到达的一个或几个设施点。还点查找以最小耗费能到达的一个或几个设施点。还可以设置查找的阈值,即搜索范围,超过该范围将可以设置查找的阈值,即搜索范围,超过该范围将不再进行查找。不再进行查找。首先计算选定地点到所有候选设施的最短路径首先计算选定地点到所有候选设施的最短路径然后从候选设施中选择最近的设施然后从候选设施中选择最近的设施可以应用于基于定位的服务,如自动柜员机可以应用于基于定位的服务,如自动柜员机方形标志显示为从所方形
22、标志显示为从所选地址到最近的消防选地址到最近的消防站点的最短路径站点的最短路径2.3.3 服务区分析F服务站点服务站点即即服务中心点服务中心点,就是提供某种特定服务的位置,就是提供某种特定服务的位置,如某一派出所、邮局、社区医院、社区公园等。如某一派出所、邮局、社区医院、社区公园等。F服务区服务区:是以指定点为中心,在一定阻力范围内,包含所:是以指定点为中心,在一定阻力范围内,包含所有可通达边的一个有可通达边的一个区域区域。如某一社区派出所按行政区划所管辖的社区。如某一社区派出所按行政区划所管辖的社区。F服务区分析服务区分析就是指在满足某种条件的前提下,查找网络上就是指在满足某种条件的前提下,
23、查找网络上指定的服务站点能够提供服务的区域范围。指定的服务站点能够提供服务的区域范围。也可以理解为不考虑中心资源供给量和需求量,而只考虑供也可以理解为不考虑中心资源供给量和需求量,而只考虑供给方与需求方之间网络弧段阻力的给方与需求方之间网络弧段阻力的资源分配资源分配。可用于评估分析在某一位置邮局、医院、超市等公共设施一可用于评估分析在某一位置邮局、医院、超市等公共设施一般的服务范围,从而为选择公共设施的最佳位置提供参考。般的服务范围,从而为选择公共设施的最佳位置提供参考。2.3.4(配置)资源分配F通过网络来研究通过网络来研究资源的空间分布资源的空间分布例如学校、银行、消防站的选址例如学校、银
24、行、消防站的选址而资源的分布决定服务的范围而资源的分布决定服务的范围响应时间响应时间F资源分配网络模型由资源分配网络模型由中心点中心点(分配中心或收集中心)(分配中心或收集中心)及其及其属性和网络属性和网络组成。组成。F分配有分配有两种形式两种形式,一种是由分配中心向四周分配,一种是由分配中心向四周分配,另一种是由四周向收集中心分配。另一种是由四周向收集中心分配。F资源分配的应用资源分配的应用包括包括消防站点分布和求援区划分、消防站点分布和求援区划分、学校选址、垃圾收集站点分布,停水停电对区域的学校选址、垃圾收集站点分布,停水停电对区域的社会、经济影响估计等社会、经济影响估计等2分钟响应时分钟
25、响应时间内两所消间内两所消防站点的服防站点的服务区域务区域5分钟响应时间分钟响应时间内两所消防站点内两所消防站点的服务区域的服务区域2.3.5 定位-配置(选址分析)F供给、需求和距离的匹配问题供给、需求和距离的匹配问题供给供给由设施或点为中心组成由设施或点为中心组成需求需求由点、线或多边形组成由点、线或多边形组成供给和需求之间的供给和需求之间的距离距离大小常以距离矩阵或距离列大小常以距离矩阵或距离列表表示表表示F定位与分配模型定位与分配模型是根据需求点的空间分布,在一些是根据需求点的空间分布,在一些候选点中选择给定数量的供应点以使预定的目标方候选点中选择给定数量的供应点以使预定的目标方程达到
26、最佳结果。程达到最佳结果。-最佳分配中心,最优配置。最佳分配中心,最优配置。定位问题定位问题是指已知需求源的分布,确定在哪里布设是指已知需求源的分布,确定在哪里布设供应点最合适的问题;供应点最合适的问题;分配问题分配问题是确定这些需求源分别受哪个供应点服务是确定这些需求源分别受哪个供应点服务的问题。的问题。定位/配置模型F最小距离最小距离模型模型要求所有需求点到最近的供给点的总行程最小要求所有需求点到最近的供给点的总行程最小F最大覆盖最大覆盖模型模型在指定的时间或距离内达到需求覆盖最大化在指定的时间或距离内达到需求覆盖最大化公共图书馆选址公共图书馆选址问题中的需求点问题中的需求点应用最大覆盖模
27、型应用最大覆盖模型选出的三个备选点选出的三个备选点以及备选点所服务以及备选点所服务的需求点的需求点应用最小距离模型应用最小距离模型选出的三个备选点选出的三个备选点以及备选点所服务以及备选点所服务的需求点的需求点.一点固定应用最小距一点固定应用最小距离模型且距离不超过离模型且距离不超过10英里选出的另外两英里选出的另外两个备选点;个备选点;固定点为最西边的点固定点为最西边的点网络分析有广泛的应用F借助借助GIS可以分析车速,单向行驶,交叉口延误,可以分析车速,单向行驶,交叉口延误,还可以分析公共交通换乘。还可以分析公共交通换乘。F在公用事业领域,可分析供水、排水、燃气、电力、在公用事业领域,可分析供水、排水、燃气、电力、通信管理的故障、维护,设施规划。该领域历史上通信管理的故障、维护,设施规划。该领域历史上曾经称曾经称AM/FM。作业GIS空间分析在空间分析在中的应用中的应用