第五章-矢量数据的空间分析方法.ppt

1、,第五章 矢量数据的空间分析方法,遥感信息工程学院 余洋 ,1,矢量数据,矢量数据的包含分析,矢量数据的缓冲区分析,矢量数据的叠置分析,矢量数据的网络分析,ArcGIS的矢量数据空间分析工具,主要内容,2,3,4,5,6,矢量数据模型把GIS数据组织成点、线、面几何对象的形式，是基于对象实体模型的计算机实现， 对有确定位置与形状的离散要素是理想的表示方法。 矢量数据空间分析： 一般不存在模式化的分析处理方法 表现为处理方法的多样性和复杂性 在GIS空间分析中基于矢量数据的分析方法是重点研究内容之一。,4,矢量数据模型 用坐标点构建空间要素，把空间看作是由不连续的几何对象组成的。 构建矢量数据模

2、型：,5.1 矢量数据,用简单的几何对象(点、线、面)表示空间要素； 空间要素之间的相互关系； 数据文件的逻辑结构必须恰当，使计算机能够处理空间要素及其相互关系； 复杂的空间要素适于用简单几何对象的组合来表示 。,5,几何对象 空间要素可以表示为点、线或面几何对象。 点对象：表示零维的、只有位置性质的空间要素 节点或折点 线对象：一维的，有长度特性的空间要素。 轮廓(edge)、链路(link)或链(chain) 面对象：二维的且有面积和边界性质的空间要素。 多边形(polygon)、区域(region)或地带(zone),6,矢量数据模型的基本单元是点及点的坐标。 线要素由点构成，包括两个端

3、点和端点之间标记线形态的一组点，可以是平滑曲线或折线。,线对象,7,面要素通过线要素定义，通过边界把面要素区域分为内部区域和外部区域。 单独的面要素：只有一个特征点，既是边界的起点又是边界的终点。 相连的面要素：两个相互邻接的面。,面要素可相互重叠产生重叠区域,面要素可在其他面要素内形成岛,10,拓扑关系,拓扑,中文名称起源于希腊语“”的音译。Topology原意为地貌，于19世纪中期由科学家引入，当时主要研究的是出于数学分析的需要而产生的一些几何问题。 拓扑是指通过图论这一数学分支，用图表或图形研究几何对象排列及其相互关系。,柯尼斯堡七桥,拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量

4、。 矢量空间分析中的拓扑主要研究几何对象在弯曲或拉伸等变换下仍保持不变的性质。 拓扑关系用来表达空间要素之间的空间关系。,12,拓扑数据结构 带拓扑关系的矢量数据模型在计算机中表现为数据文件结构和文件之间的关系。 点要素直接用标识码和x, y坐标对进行编码。,点的清单,点要素,(0,0),13,线要素的数据结构：,表示弧段-节点之间的关系。,显示了组成弧段的x, y坐标。,线要素,14,面要素的数据结构：,多边形/弧段清单表示多 边形和弧段之间的关系。,左/右多边形清单显示弧段的左多边形和右多边形的关系。,15,简单对象的组合,一些空间要素，如陆地表面数据、重叠的空间要素、路网等适合用简单几何

5、对象的组合来表示。 陆地表面数据： 可用TIN表示； TIN模型把地表近似描述成一组互不重叠的三角面的集合。,构建TIN,18,重叠空间要素： 用区域数据模型表示，包含两个特征：区域层和区域。 区域层：属性相同的区域。 区域层可以重叠或涵盖相同的范围，如不同历史年代的区域范围可能重叠。 不同区域层覆盖相同区域时，区域之间形成一种等级区域结构，一个区域层嵌套在另一个区域层中。,区域-多边形清单,区域-弧段清单,区域与弧段关系的文件 区域与多边形关系的文件,区域数据结构,20,GIS的空间查询如鼠标点击查询、图形查询、开窗查询等涉及包含分析。 包含分析是一些空间分析功能的重要组成部分。 如确定某个

6、矿井属于哪个行政区，先对矿井、行政区等相关图层进行叠置运算，再通过点在多边形的包含分析确定具体关系。 缓冲区分析中，缓冲区域确定后通常需要通过包含分析确定缓冲内所包含地物要素的情况。,5.2 矢量数据的包含分析,鼠标点击,GPS轨迹匹配,23,用于确定空间要素（点、线、面）之间在空间位置上的联系。,24,点和点之间的包含关系 计算两点之间的距离，如距离(d )为零或者小于某个阈值D，则两点之间有包含关系。,d,d D,d = 0,d,d D,25,点和线之间的包含关系（点落在线上） 计算点到线之间的距离，如距离(d )为零或者小于某个阈值D，则两点之间有包含关系。,d D,d = 0,d D,

7、26,点和面之间的包含关系（点完全落在面内） 判断点是位于面域范围之内还是之外，用多边形表示面状物体时，即为著名的“点在多边形内”的识别问题。,27,线和线之间的包含关系 一条线完全或部分包含另一条线。,28,线和面之间的包含关系（线完全落在面内） 判断组成该线的所有节点是否都包含在某个面之内。 可转化为计算多个点与面之间的包含关系问题。,29,面和面之间的包含关系（面完全被另一个面包含） 判断组成一个面的所有节点是否都包含在另外一个面的区域范围之内。 可转化为判断多个点与面之间的包含问题。,30,在矢量数据的包含分析中，点与面的包含、线与面的包含、面与面的包含分析都可以归结为点在多边形内的判

8、断问题。实现算法有： 计算通过点的垂直线与多边形相交的交点的分布情况。 计算点与多边形顶点连线的方向角之和。,点在多边形内的判别方法,31,（1）用过点的垂直线与多边形交点分布的奇偶性 两侧交点个数均为奇数点位于多边形内 两侧交点个数均为偶数点位于多边形外。 特点：计算简单，能识别点在多边形边界上的情况，但若过点的垂直线与多边形的边重合时则需要进行附加判断。,P4,32,（2）角度计算 若点与多边形顶点连线形成的方向角之和为 360度点位于多边形内。 否则(等于0度) 点位于多边形外。 特点：角度计算比交点计算稍嫌复杂，对于点在多边形边界上的情况则不便识别。,33,缓冲：基于近邻的概念把空间分

9、为两个区域: 位于所选空间要素的指定距离之内(缓冲区) 位于所选空间要素的指定距离之外 空间要素可以是点、线、面或复杂要素。 应用： 公共设施的选址，确定服务半径等点缓冲问题 河流两侧灌溉区域的确定线缓冲问题 公园向周围扩展面缓冲问题,5.3 矢量数据的缓冲区分析,森林禁伐带,道路扩建,禁飞区,37,数学观点的分析： 缓冲区分析是基于空间目标拓扑关系的距离分析。 基本思想：给定一个空间目标，确定它们的某邻域，邻域的大小由邻域半径决定。 空间目标Oi 的缓冲区定义为：,空间目标集合的半径为R的缓冲区是单个物体的缓冲区的并，即：,即对象Oi的半径为R的缓冲区是全部距Oi的距离d小于等于R的点的集合

10、。d一般指最小欧氏距离。,38,点目标的缓冲：形成围绕点的半径为缓冲距的圆形缓冲区； 线目标的缓冲：形成围绕线目标两侧距离不超过缓冲距的一系列长条形缓冲带； 面要素缓冲：形成围绕多边形边界线内侧或外侧距离不超过缓冲距的面状区域； 复杂目标的缓冲：形成由组成复杂目标的单个目标的缓冲区的并组成的区域。,38,39,缓冲区分析包括两个部分： 缓冲区域的生成 在缓冲区域内进行的各种统计分析或查询分析 缓冲区分析算法的关键： 缓冲区的生成 多个缓冲区的合并,40,点状要素的缓冲区生成,对选定的目标点设定缓冲距，生成圆形缓冲区。有两种常用方法： （1）直接绘圆法： 以点目标为中心，以缓冲区距离为半径直接绘

11、圆。,点缓冲区直接生成,41,（2）圆弧步进拟合法： 将圆心角等分为若干等分，用等长的弦来代替圆弧，用直线代替曲线，用已知半径为R(缓冲距)的圆弧上n个等间距的离散点来逼近缓冲圆。,圆弧步进拟合法,42,特殊情况下点状目标缓冲区 对点状目标，还可以生成三角形、矩形、圆形等特殊形态的点缓冲区； 对于相邻多个点目标的缓冲区分析，根据实际应用需要进行缓冲区的合并，消除重叠区域。缓冲带的边界可以融合也可以保留。,线缓冲区的生成：以线状目标为参考轴线，以轴线为中心向两侧沿法线方向平移一定距离，并在线端点处以光滑曲线连接，所得到的点组成的封闭区域。 实质：对线状目标上的坐标点逐点求得其缓冲点的过程。 线缓

12、冲区生成关键算法： 缓冲区边界点的生成 多个缓冲区的合并,43,线状要素的缓冲区生成,44,（1）角平分线法 基本思想：在转折点处根据角平分线确定缓冲线的形状。 基本步骤： 1）确定线状目标左右侧的缓冲距离dl，dr。 2）提取线状目标的坐标序列。 3）沿线状目标轴线的前进方向，依次计算轴线上各点的角平分线，起点和终点的角平分线为起始线段或终止线段的垂线。,线状缓冲区的生成算法：,45,4）在各点角平分线的延长线上用左右侧缓冲距离dl和dr确定各点的左右缓冲点位置。 5）左右缓冲点顺序相连，构成左右缓冲边界的基本部分。 6）在起点和终点处，以(dl+dr)为直径、以角平分线(垂线)为直径向外作

13、外接半圆。 7）将外接半圆与左右缓冲边界的基本部分相连，即为线状目标的缓冲区。,46,角平分线的缺点： 难以保证双线的等宽性，轴线转角尖锐的转折点将随缓冲距的增大迅速远离轴线,47,（2）凸角圆弧法 基本思想： 在轴线的两端用半径为缓冲距的圆弧拟合； 在轴线转折点，判断该点的凹凸性，在凸侧用半径为缓冲距的圆弧拟合，在凹侧用与该点关联的两缓冲线的交点为对应缓冲点。,48,优点： 凸侧的缓冲线与轴线等宽，而凹侧的对应缓冲点位于凹角的角平分线上，因而最大限度地保证缓冲区边界与轴线的等宽关系。,ArcGIS Online 上的线状缓冲区生成算法,50,特殊情况的缓冲区： 指定不同线状目标的不同的缓冲区

14、宽度； 同一线状目标两侧的缓冲区宽度也可以不一样； 同一线状目标不同段的缓冲区宽度也可以不一样；,52,面状要素的缓冲区生成,面目标可视为由边界线目标围绕而成。 面目标缓冲区生成的基本思路与线目标缓冲器生成算法基本相同。 面目标缓冲区：内侧缓冲区和外侧缓冲区 面状目标的缓冲区宽度可不一样，甚至同一面状目标内外侧的缓冲区宽度也可不一样。,ArcGIS Online 上的面状缓冲区生成算法,54,特殊缓冲区情况,缓冲线生成过程中的特殊情况： 缓冲线失真 缓冲线自相交 缓冲区重叠等,55,缓冲区失真问题 当轴线转角太大时，转角处的缓冲线交点随缓冲距的增大容易出现失真问题。,角平分线法造成的缓冲区失真

15、,按角平分线法得到的大转角处的缓冲线会出现缓冲区失真。由于B点的右转角太大，按照该算法得到的B点的左右缓冲点Bl和Br点均远离B点，使缓冲区宽度发生变异，这是不合理的。,采用凸角圆弧法,下面线状要素的缓冲区会失真吗？,d,d,57,缓冲线自相交问题 当轴线的弯曲空间不能容许缓冲区边界自身无压覆地通过时，缓冲线将产生自相交现象，并形成多个自相交多边形： 岛屿多边形保留 重叠多边形删除 识别是岛屿多边形还是重叠多边形是缓冲线自相交处理的关键。,58,（3）缓冲区重叠问题 指不同目标的缓冲区之间的重叠 对于这种重叠，首先通过拓扑分析方法自动识别出重叠的线段，然后删除，最后得到处理后的相互连通的缓冲区

16、。,59,河网缓冲区的例子： 河网不同部位的缓冲区相互重叠，缓冲区不能以简单多边形表示。 必须计算出所有的重叠，通过一系列判断产生一个复杂多边(含洞)形或多边形集合表示的缓冲区。,60,动态目标缓冲区,静态缓冲区： 空间目标对邻近对象的影响呈现单一的距离关系。 动态缓冲区： 空间目标对邻近对象的影响呈现不同强度的扩散或衰减关系。 如污染对周围环境的影响呈现梯度变化。,61,动态缓冲区生成： 不能简单地设定距离参数，需要根据空间目标的特点和要求选择合适的方法。 动态缓冲区的生成针对两类特殊情况： 流域问题 污染问题,62,流域问题中的动态缓冲区生成问题： 流域从上游的某一点出发沿流域下溯，河流的

17、影响半径或流域辐射范围逐渐扩大； 流域从下游的某一点出发沿流域上溯，河流的影响半径或流域辐射范围逐渐缩小。 类似问题还有参数动态变化的运动目标的影响范围分析等。,63,基于线目标的缓冲区生成算法： 用分段处理的办法分别生成各流域分段的缓冲区，然后按某种规则将各分段缓冲区光滑连接 基于点目标的缓冲区生成算法： 用逐点处理的办法分别生成沿线各点的缓冲圆，然后求出缓冲圆序列的两两外切线，所有外切线相连。,流域问题中的动态缓冲区生成问题：,64,污染问题中的动态缓冲区生成 污染源对邻近对象的影响程度随距离的增大而逐渐缩小。 可根据物体对周围空间影响度变化的性质，引入一个影响度参数来确定缓冲区半径的动态

18、变化。 生成动态缓冲区的类似问题：城市辐射影响分析、矿山开采影响分析等。,火山灰扩散,辐射尘扩散,思考题： 生成动态缓冲区常用的分析模型有哪些？,5.4 矢量数据的叠置分析,在统一的空间坐标系下，将同一地区的两个或两个以上的地理要素图层进行叠置，产生空间区域的多种属性特征的分析方法。,大部分GIS软件是以分层的方式组织地理景观，将地理景观按主题分层存取。,栅格数据的叠置分析,矢量数据的叠置分析,矢量数据的叠置分析包括以下6种类型：,71,点与点的叠置,含义： 把一个图层上的点与另一个图层上的点进行叠置，为图层内的点建立新的属性，同时对点的属性进行统计分析。 实现： 通过不同图层间的点的位置和属

19、性关系完成，得到一张新属性表，属性表示点之间的关系。,72,城市中网吧与学校的叠置及相应的属性表，从中可判断网吧与学校的距离。,73,点与线的叠置,含义： 一个图层上的点目标与另一图层上的线目标进行叠置，为图层内的点和线建立新的属性。 应用： 叠置分析的结果可用于点和线的关系分析，如计算点与线的最近距离。,74,城市与高速公路叠置分析 可以分析城市与高速公路之间的关系、高速公路的分布情况等。,75,点与多边形的叠置,含义： 实际上是计算多边形对点的包含关系。将一个含有点的图层叠加到另一个含有多边形的图层上，以确定每个点落在哪个多边形内。,76,实现： 通过点在多边形内的判别完成，通常得到一张新

20、属性表，包含： 原属性 落在那个多边形的目标标识 还可以从多边形属性表中提取一些附加属性 应用： 如油井与行政区划叠置：可以得到油井本身的属性如井位、井深、出油量，还可以得到行政区划的属性，如目标标识、行政区名称、行政区首长姓名等。,77,线与线的叠置,含义： 一个图层上的线与另一图层的线叠置，分析线之间的关系，为图层中的线建立新的属性关系。 应用： 如河流与公路的叠置分析结果，可以分析水陆交通运输的分布情况。,78,线与多边形的叠置,含义： 将线的图层叠置在多边形的图层上，以确定一条线落在哪一个多边形内。 实现： 比较线上坐标与多边形坐标的关系，判断线是否落在多边形内。,79,线目标跨越多个

21、多边形： 先进行线与多边形边界的求交，将线目标进行切割，对线段重新编号，形成新的空间目标的结果集，同时产生一个相应的属性数据表记录原线和多边形的属性信息。,根据叠置的结果可以确定每条弧段落在哪个多边形内，查询指定多边形内指定线穿过的长度。,80,应用： 公路线图层与县城图层进行叠加分析 可以回答每个县所包含的公路里程等问题。 若线状图层为河流，叠置的结果是多边形将穿过它的所有河流分割成弧段。 查询多边形内的河流长度，进而计算河流密度。,81,多边形与多边形的叠置,含义： 指同一地区、同一比例尺的两组或两组以上的多边形要素进行叠置。 参加叠置分析的图层都是矢量数据。 多层叠置：两两叠置后再与第三

22、层叠置，依次类推。 被叠置的多边形为本底多边形； 用来叠置的多边形为上覆多边形； 叠置后产生具有多重属性的新多边形。,82,实现： 将两层多边形的边界全部进行边界求交运算和切割； 然后根据切割的弧段重建拓扑关系； 最后判断新叠置的多边形分别落在原始多边形层的哪个多边形内，建立叠置多边形与原多边形的关系，如果必要再抽取属性。,83,基本处理方法： 根据两组多边形边界的交点来建立具有多重属性的多边形地图内容的合成叠置。 进行多边形范围内的属性特性的统计分析地图内容的统计叠置。,84,合成叠置的目的： 通过区域多重属性的模拟，寻找和确定同时具有几种地理属性的分布区域。或者按照确定的地理目标，对叠置后

23、产生的具有不同属性多边形进行重新分类或分级，叠置的结果为新的多边形数据文件。,85,统计叠置的目的： 准确地计算一种要素(如土地利用)在另一种要素(如行政区域)的某个区域多边形范围内的分布状况和数量特征(包括拥有的类型数、各类型的面积以及所占总面积的百分比等)，或提取某个区域范围内某种专题内容的数据。,5.4 矢量数据的网络分析,网络分析是通过模拟、分析网络状态以及资源在网络上的流动和分配等，研究网络结构、流动效率及网络资源等的优化问题。 网络分析是对地理网络和城市基础设施网络等网状事物以及它们的相互关系和内在联系进行地理分析。,人类活动总是趋向于按一定目标选择达到最佳效果的空间位置。,87,

24、GIS中的网络,具有图论中网络的边、节点、拓扑等特征。 还具有空间定位上的地理意义、目标复合上的层次意义和地理属性意义。如交通网络中除道路网络外，还涉及车站、路况、通行能力等。,88,GIS中网络的组成,1）线状要素 链、弧段 有形的：街道、河流、水管、电缆线 无形的：无线通讯网络,2）点状要素 障碍点、拐角点、结点、中心、站点,GIS中网络的组成,1）几何属性 2）拓扑关系（结点弧段拓扑关系） 3）特殊属性 （阻抗强度、资源容量、资源需求量）,网络流量：网络上从起点到终点的某个函数，如运输价格、运输时间等。,90,网络分析的主要目的,选择最佳路径,选择最佳布局中心位置,网络分析中的距离,网络

25、分析的常见问题,地址匹配,资源分配,路径分析,地址匹配,对地理位置的查询，涉及到地址的编码。地址匹配与其它网络分析功能结合起来，可以满足实际工作中非常复杂的分析要求。,路径分析,资源分配模型由中心点(分配中心)及其状态属性和网络组成。分配方式包括： 由分配中心向四周输出 由四周向中心集中,资源分配,选址功能是指在一定约束条件下、在某一指定区域内选择设施的最佳位置，它本质上是资源分配分析的延伸。,最佳选址,路径分析问题,网络：网络的每一条弧段都有一个权值，表示弧段连接的两结点间阻抗值。 权值： 正值 负值 GIS中的一般最短路径问题都不涉及负回路的情况，因此以下所有的讨论中假定弧的权都为非负值。

26、,最短路径,路径分析是网络分析的核心问题，是对最佳路径的求解，即在指定网络的两个节点之间找一条阻抗强度最小的路径。,最短路径算法是路径分析问题的基础，其表述如下： 若一条弧段的权wij表示节点vi和vj间的长度，在vi和vj之间的所有路径中，寻求长度最小的路径，称为从vi到vj的最短路径。 *长度 时间、费用、路线、距离、流量等等,在欧氏空间En中，设x, y, z为任意三点，令d(x,y)为xy的距离，则有：,当且仅当z在x、y的连线上时等式成立。,最短路径问题的数学表达,类似的，令dk为节点vk到vj的最短距离，wij为vi到vj的权值，对于 的结点对，令 ，显然：,当且仅当(vj, vk

27、)在v1到vk的最短路径上时，等式成立。,dk是从v1到vk的最短路径，设该路径的最后一段弧为(vj,vk)， wjk为vj到vk的权值，由局部与整体的关系，该路径的前一段，即v1到vj的路径也必须为从v1到vj的最短路径。用公式可表达为：,这就是最短路径方程，然而直接求解此方程比较困难。目前几乎所有的最短路径的算法都是如何解这个方程的问题。,最短路径问题的数学表达,广度优先（BFS）,最短路径问题的求解,深度优先（DFS）,广度优先算法,最短路径问题的求解,Dijkstra算法,Floyd-Warshall算法,Bellman-Ford算法,A*算法,SPFA算法,边无负权值,可以处理负权,

28、Dijkstra算法,Dijkstra算法是E.W.Dijkstra于1959年提出的，是一种按路径长度递增的次序产生最短路径的算法。 算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示在城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。 此算法被公认为是解决此类最短路径问题最经典、也是比较有效的算法。,假设每个点都有一对标号:(dj, pj)，dj是从源点s到该点j的最短路径的长度，pj是从s到j的最短路径中的j点的前一点。求解从源点s到各点j的最短路径算法的基本过程如下，这种方法也称标号法或染色法。,(1)初始化： 起源点

29、：ds=0，ps为空； 其它点 j ：将起源点k标号，并加入标号点集合S，记S=k，而其它点尚未处理。,Dijkstra算法,Dijkstra算法,(2)距离计算： 检验从所有标记的点k到其它直接连接的未标记的点j的距离，并设置：,lkj是从点k到j的直接连接距离。,Dijkstra算法,(4)找到点i的前一点 从已标记的点中找到直接连接到点i的点j*，将其作为前一点。 (5)标记点i 如果所有点已标记，则算法完全退出，否则记k=i，转到第2步再继续执行。,(3)选取下一个点 从节点中选取dj最小的连接点i：di=min dj, 所有未标记点j，点i为最短路径中的下一个点，并标记。,Dijks

30、tra算法示例,初始化：ds=0, ps = null k = V0,Dijkstra算法示例,function Dijkstra（G, w, s） 2. for each vertex v in VG / 初始化 3. dv := / 将各点的已知最短距离先设置成无穷大 4. previousv := null / 各点的已知最短路径上的前趋都未知 ds := 0 / 因为出发点到出发点间不需移动任何距离， 所以可以直接将s 到s的最小距离设为0 6. S := empty set 7. Q := set of all vertices 8. while Q is not an empty

31、set / Dijkstra算法主体 9. u := Extract_Min(Q) 10. S.append(u) 11. for each edge outgoing from u as (u,v) 12. if dv du + w(u,v) / w(u,v)为从u到v的路径长度。 13. dv := du + w(u,v) / 更新路径长度到更小的那个和值。 14. previousv := u / 记录前一个顶点,如果求s到t的最短路径，则加入以下判断即可 if u= t break,Dijkstra算法,Dijkstra算法的运行时间是 O(n2)。,A*算法,A*算法像Dijkstr

32、a算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。在此算法中，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。 因此，A*算法中的距离计算公式为： f(n)=g(n)+h(n) 这个公式遵循以下特性： 如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法 如果h(n)=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低,A*算法（欧氏距离）,几种常用的空间距离计算方式,Euclidean 距离,Manhattan 距离,Cheb

33、yshev 距离,A*算法（Manhattan距离）,A*算法（ Chebyshev距离）,Floyd算法,Dijkstra算法,Floyd-Warshall算法是一种多点对间最短路径的方法，该算法有效地利用了邻接矩阵。,A*算法,边无负权值，1 - N,Floyd算法,基本思想是： 递推地产生一个矩阵序列：M(0), M(1), M(2), , M(n)。其中，M(0)就是邻接矩阵，M(0)i,j等于从Vi到Vj的边的权值，即从Vi到Vj的路径上不经过任何中间顶点； M(k)i,j等于从顶点Vi到顶点Vj的路径上中间顶点序号不大于k的最短路径长度值(k=1,2,n)。,Floyd算法,基本思

34、想是： 由于在具有n个顶点的有向网络中，任何一对顶点之间的最短路径上都不可能出现序号大于n的中间点。因此，矩阵元素M(n)i,j就等于从Vi到Vj的最短路径长度值。 递推地产生M(0), M(1), M(2), , M(n)的过程就是逐步允许越来越多的顶点作为路径上的中间顶点，直到所有顶点都允许作为中间顶点。,Floyd算法,假设已求得矩阵M(k-1)，如何由它求M(k)呢？ 从Vi到Vj的路径上中间点数不大于k的最短路径只有以 下两种可能的情况： 中间不经过顶点Vk。在这种情况下： M(k)i,j M(k-1)i,j 在这种情况下，在最短路径中并没有增加节点。,Floyd算法,中间经过顶点V

35、k 。在这种情况下， M(k)i,jM(k-1)i,j 这条由Vi经Vk到达Vj的最短路径由两段组成： 一段是从Vi到Vk中间序号不大于k-1的最短路径，其长度为M(k-1)i,k； 另一段是从Vk到Vj的中间序号不大于k-1的最短路径，其长度为M(k-1)k,j。因此，可得到递推公式： M(k)i, jminM(k-1)i,j, M(k-1)i,k+ M(k-1)k,j,Floyd算法,算法描述：,Floyd 算法的运行时间是 O(n3)。,Floyd算法,在如图所示的有向网络中，M(k)1,2表示由节点1到节点2经过节点序号不大于k的最短路径。,M(1)1,2, M(2)1,2, M(3)

36、1,2,M(4)1,2 和M(5)1,2的计算结果为： M(1)1,2=M(2)1,2=M(3)1,2= ； M(4)1,2=minM(3)1,2, M(3)1,4+ M(3)4,2 =min, 15=15；,M(5)1,2=minM(4)1,2, M(4)1,3 +M(4)3,2, M(4)1,4+M(4)4,2, M(4)1,5+M(4)5,2= min15,15,15,12=12。 因此，从V1到V2的最短路径长度值为12。,次最短路径求解算法 在某些情况下，除了需要求出两个给点之间的最短路径之外，还可能需要求出这两点之间的次最短路径、第3短路径，第k短路径。 可以在求出第1最短路径P1

37、之后，用枚举法求出与P1有尽可能多公共边的次最短路径P2。 算法的基本思路是： 假定第1最短路径P1包含了n条有向弧，每次删除其中的一条弧，即得到n个与原来只有一弧之差的新的网络。 按原最短路径算法分别求解这n个新网络的最短路径，然后比较这n条最短路径，其中最短的那条即为所求的次最短路径。 依此进行，可以分别求出第3短路径，第k短路径。,最佳路径算法 最佳路径是指网络两结点之间阻抗最小的路径。阻抗最小”有多种理解，如基于单因素考虑的时间最短、费用最低、风景最好、路况最佳、过桥最少、收费站最少、经过乡村最多等；,最佳路径算法 最大可靠性路径,利用最短路径算法也可以求解最大可靠路径。 具体方法是：

38、定义网络D(V, A)中的每条弧aij(Vi,Vj)的权为： wij=lnpij 因 ，所以 。从而可以用前述Dijkstra算法求出关于权wij的最短路径(Vi, Vj)。由于 ，所以，关于权的最短路径就是(Vi, Vj)的最大可靠路径，其完好概率为 。,最佳路径算法 最大容量路径,设网络D(V, E, W)中任意一条路径P的容量定义为该路径中所有弧的容量cij的最小值，即： 则网络D(V, A)中所有(Vi, Vj)路径中的容量最大的路径即为(Vi, Vj)的最大容量路径。,128,最优路径的求解有多种形式，如两点间最优路径、多点间指定顺序的最优路径、多点间最优顺序最优路径、经指定点回到起

39、点的最优路径等。,5.5 ArcGIS的矢量数据空间分析工具,缓冲区分析 叠置分析 网络分析,5.5 ArcGIS的矢量数据空间分析工具,缓冲区分析,在ArcGIS中建立缓冲区的方法是基于生成多边形来实现的。ArcGIS根据给定的缓冲区距离，对点状、线状和面状要素的周围形成缓冲区多边形图层。 ArcGIS提供三种缓冲区的建立方法，分别是普通缓冲区、属性权值缓冲区和分级缓冲区。,缓冲区分析,普通缓冲区,属性权值缓冲区,分级缓冲区,叠置分析,按照一定的数学模型对要素进行计算分析得出新属性，计算中通常涉及到逻辑交、逻辑并、逻辑差等运算。根据操作形式的不同，叠置分析可分为图层擦除、识别叠加、交集操作、对称区别、图层合并和修正更新等。 图层擦除：在输入图层中擦除参考图层与输入图层相交的部分。 识别叠加：输入图层与识别图层叠加，识别图层将其属性赋予两层相交的区域。 交集操作：通过叠置处理得到两个图层的交集部分，并且原图层的所有属性将同时在得到的新图层上显示出来。 对称区别：输入图层与参考图层叠加后去掉其公共区域。 图层合并：指通过把两个图层的区域范围联合起来而保持来自输入地图和叠加地图的所有地图要素。 修正更新：输入图层与修正图层叠加，其公共部分