1、第四章 矢量数据的空间分析方法余洋 1矢量数据模型矢量数据的包含分析矢量数据的缓冲区分析矢量数据的叠置分析矢量数据的网络分析ArcGIS的矢量数据空间分析工具主要内容234565.1 矢量数据模型 查看地图可得知地图要素及其空间相互关系；地图通过符号和文字向人们传递信息。我们容易获知地图要素及其空间关系，如何才能使计算机懂得这些要素和空间关系？矢量数据 矢量数据对有确定位置与形状的离散要素是理想的表示方法。在GIS空间分析中基于矢量数据的分析方法是重点研究内容之一。n矢量数据空间分析：一般不存在模式化的分析处理方法表现为处理方法的多样性和复杂性n矢量数据空间分析的基础 矢量数据模型5.1 矢量
2、数据模型5 矢量数据模型是把GIS数据组织成点、线、面几何对象的形式，是基于对象实体模型的计算机实现。用构建矢量数据模型步骤：简单的几何对象（点、线和面）来表示空间要素明确地表达空间要素之间的相互关系（空间关系）建立恰当的数据文件逻辑结构陆地表面数据、重叠的空间要素和路网适用于简单几何对象的组合来表示5.1 矢量数据模型6空间要素可以表示为点、线或面几何对象。点对象：表示零维的、只有位置性质的空间要素 节点或折点线对象：一维的，有长度特性的空间要素。轮廓(edge)、链路(link)或链(chain)面对象：二维的且有面积和边界性质的空间要素。多边形(polygon)、区域(region)或地
3、带(zone)几何对象5.1 矢量数据模型7 矢量数据模型的基本单元是点及点的坐标。线要素由点构成，包括两个端点和端点之间标记线形态的一组点，可以是平滑曲线或折线。线对象几何对象5.1 矢量数据模型8 面要素通过线要素定义，通过边界把面要素区域分为内部区域和外部区域。单独的面要素：只有一个特征点，既是边界的起点又是边界的终点。相连的面要素：两个相互邻接的面。几何对象5.1 矢量数据模型面要素可相互重叠产生重叠区域几何对象5.1 矢量数据模型面要素可在其他面要素内形成岛。几何对象5.1 矢量数据模型 中文名称起源于希腊语“”的音译，当时主要研究的是出于数学分析的需要而产生的一些几何问题。拓扑拓扑
4、是指通过图论图论这一数学分支，用图表或图形研究几何对象排列及其相互关系。柯尼斯堡七桥拓扑关系5.1 矢量数据模型拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量。矢量空间分析中的拓扑主要研究几何对象在弯曲或拉伸等变换下仍保持不变的性质。拓扑关系拓扑关系用来表达空间要素之间的空间关系。ABAB拓扑关系5.1 矢量数据模型13n 拓扑数据结构拓扑数据结构 带拓扑关系的矢量数据模型在计算机中表现为数据文件结构和文件之间的关系。点要素直接用标识码和x,y坐标对进行编码。点的清单 点要素(0,0)拓扑关系5.1 矢量数据模型14 线要素的数据结构：表示弧段-节点之间的关系。显示了组成弧段的x,y坐标
5、。线要素拓扑关系5.1 矢量数据模型15 面要素的数据结构：多边形/弧段清单表示多边形和弧段之间的关系。左/右多边形清单显示弧段的左多边形和右多边形的关系。拓扑关系5.1 矢量数据模型16拓扑矢量数据格式 基于拓扑关系的数据结构有利于数据文件组织、减少数据冗余。ARC/INFO标准拓扑矢量数据格式（Coverage），以点、线和面对图层归类，支持3种基本拓扑关系：连接性：弧段间通过节点彼此连接面定义：由一系列相连接的弧段定义面邻接性：弧段有方向性，且有左多边形和右多边形5.1 矢量数据模型17非拓扑矢量数据格式 20年前，GIS开发者为了把GIS从CAD（计算机辅助设计）中分离出来而引进了拓扑
6、关系，AutoCAD用来转换数据文件的一种数据格式叫做DXF（数据交换格式）。DXF以分开的图层来保持数据，并允许用户使用不同的线符号、颜色和文字来绘制每个图层，但是不支持拓扑关系。使用非拓扑矢量数据的主要优点是能比拓扑数据更快速地在计算机屏幕上显示出来。5.1 矢量数据模型18非拓扑矢量数据格式ARCGIS中采用的标准的非拓扑数据格式 Shapefile每个shapefile，都至少有这三个文件组成，其中：*.shp 存储的是几何要素的的空间信息*.shx 存储的是有关*.shp存储的索引信息*.dbf 存储地理数据的属性信息的dBase表此外：*.prj、*.shp.xml、*.sbn、*
7、.sbx5.1 矢量数据模型19 一些空间要素，如陆地表面数据、重叠的空间要素、路网等适合用简单几何对象的组合来表示。（1）不规则三角网陆地表面数据可用TIN表示；TIN模型把地表近似描述成一组互不重叠的三角面的集合。高级对象5.1 矢量数据模型高级对象5.1 矢量数据模型21（2）区域数据模型：在简单的线和面上建立起来的区域数据模型由区域层和区域组成，其特征如下：区域层可以重叠或涵盖相同的范围一个区域可以有分离或者隔开的部分高级对象5.1 矢量数据模型区域号区域号多边形号多边形号10110111111011011212102102121210210213131021021414区域-多边形清
8、单区域号区域号圈号圈号弧段号弧段号1011011 11 11011011 12 21021021 13 31021021 14 41021022 25 5区域-弧段清单区域与弧段关系的文件区域与多边形关系的文件高级对象5.1 矢量数据模型 矢量数据格式能很好地表现具有静态特征的地物,如宗地、湖泊、土壤等。以上采用的数据格式都是基于多维空间参考系统的，对于变化较快的动态特征，还能想到其他的矢量数据格式吗？（3）线性参考和动态分段：在高速公路、铁路、河流、管线等,需要能够表现出呈线性分布的地物上的相对分布应用中,故交通行业提出了一种一维量测系统,如道路沿线上的里程碑。高级对象5.1 矢量数据模型2
9、4 GIS的空间查询如鼠标点击查询、图形查询、开窗查询等涉及包含分析。包含分析是一些空间分析功能的重要组成部分。如确定某个矿井属于哪个行政区，先对矿井、行政区等相关图层进行叠置运算，再通过点在多边形的包含分析确定具体关系。缓冲区分析中，缓冲区域确定后通常需要通过包含分析确定缓冲内所包含地物要素的情况。5.2 矢量数据的包含分析鼠标点击GPS轨迹匹配27点线面点线面 用于确定空间要素（点、线、面）之间在空间位置上的联系。5.2 矢量数据的包含分析28点线面点线面n 点和点之间的包含关系计算两点之间的距离，如距离(d)为零或者小于某个阈值D，则两点之间有包含关系。dd D5.2 矢量数据的包含分析
10、29点线面点线面n 点和线之间的包含关系（点落在线上）计算点到线之间的距离，如距离(d)为零或者小于某个阈值D，则两点之间有包含关系。d D5.2 矢量数据的包含分析30点线面点线面n 点和面之间的包含关系（点完全落在面内）判断点是位于面域范围之内还是之外，用多边形表示面状物体时，即为著名的“点在多边形内”的识别问题。5.2 矢量数据的包含分析31点线面点线面n 线和线之间的包含关系一条线完全或部分包含另一条线。5.2 矢量数据的包含分析32点线面点线面n 线和面之间的包含关系（线完全落在面内）判断组成该线的所有节点是否都包含在某个面之内。可转化为计算多个点与面之间的包含关系问题。5.2 矢量
11、数据的包含分析33点线面点线面n 面和面之间的包含关系（面完全被另一个面包含）判断组成一个面的所有节点是否都包含在另外一个面的区域范围之内。可转化为判断多个点与面之间的包含问题。5.2 矢量数据的包含分析34n 点在多边形内的判别方法5.2 矢量数据的包含分析 在矢量数据的包含分析中，点与面的包含、线与面的包含、面与面的包含分析都可以归结为点在多边形内的判断问题。实现算法有：计算通过点的垂直线与多边形相交的交点的分布情况。计算点与多边形顶点连线的方向角之和。35（1）用过点的垂直线与多边形交点分布的奇偶性 两侧交点个数均为奇数点位于多边形内 两侧交点个数均为偶数点位于多边形外。特点：计算简单，
12、能识别点在多边形边界上的情况，但若过点的垂直线与多边形的边重合时则需要进行附加判断。P436（2）角度计算 若点与多边形顶点连线形成的方向角之和为 360度点位于多边形内。否则(等于0度)点位于多边形外。特点：角度计算比交点计算稍嫌复杂，对于点在多边形边界上的情况则不便识别。P37 缓冲：基于近邻的概念把空间分为两个区域:位于所选空间要素的指定距离之内(缓冲区)位于所选空间要素的指定距离之外 空间要素可以是点、线、面或复杂要素。应用：u公共设施的选址，确定服务半径等点缓冲问题u河流两侧灌溉区域的确定线缓冲问题u公园向周围扩展面缓冲问题5.3 矢量数据的缓冲区分析森林禁伐带道路扩建禁飞区41 数
13、学观点的分析：缓冲区分析是基于空间目标拓扑关系的距离分析。基本思想：给定一个空间目标，确定它们的某邻域，邻域的大小由邻域半径决定。n空间目标Oi 的缓冲区定义为：iniBB1),(:ROxdxBiin空间目标集合的半径为R的缓冲区是单个物体的缓冲区的并，即：即对象Oi的半径为R的缓冲区是全部距Oi的距离d小于等于R的点的集合。d一般指最小欧氏距离。5.3 矢量数据的缓冲区分析42 点目标的缓冲：形成围绕点的半径为缓冲距的圆形缓冲区；线目标的缓冲：形成围绕线目标两侧距离不超过缓冲距的一系列长条形缓冲带；面要素缓冲：形成围绕多边形边界线内侧或外侧距离不超过缓冲距的面状区域；复杂目标的缓冲：形成由组
14、成复杂目标的单个目标的缓冲区的并组成的区域。425.3 矢量数据的缓冲区分析43 缓冲区分析包括两个部分：缓冲区域的生成 在缓冲区域内进行的各种统计分析或查询分析 缓冲区分析算法的关键：缓冲区的生成 多个缓冲区的合并5.3 矢量数据的缓冲区分析44 对选定的目标点设定缓冲距，生成圆形缓冲区。有两种常用方法：（1）直接绘圆法：以点目标为中心，以缓冲区距离为半径直接绘圆。点缓冲区直接生成5.3 矢量数据的缓冲区分析点要素45（2）圆弧步进拟合法：将圆心角等分为若干等分，用等长的弦来代替圆弧，用直线代替曲线，用已知半径为R(缓冲距)的圆弧上n个等间距的离散点来逼近缓冲圆。圆弧步进拟合法5.3 矢量数
15、据的缓冲区分析点要素46 特殊情况下点状目标缓冲区 对点状目标，还可以生成三角形、矩形、圆形等特殊形态的点缓冲区；对于相邻多个点目标的缓冲区分析，根据实际应用需要进行缓冲区的合并，消除重叠区域。缓冲带的边界可以融合也可以保留。5.3 矢量数据的缓冲区分析点要素 线缓冲区的生成：以线状目标为参考轴线，以轴线为中心向两侧沿法线方向平移一定距离，并在线端点处以光滑曲线连接，所得到的点组成的封闭区域。实质：对线状目标上的坐标点逐点求得其缓冲点的过程。线缓冲区生成关键算法：缓冲区边界点的生成 多个缓冲区的合并475.3 矢量数据的缓冲区分析线要素48（1）角平分线法 基本思想：在转折点处根据角平分线确定
16、缓冲线的形状。基本步骤：1）确定线状目标左右侧的缓冲距离dl，dr。2）提取线状目标的坐标序列。3）沿线状目标轴线的前进方向，依次计算轴线上各点的角平分线，起点和终点的角平分线为起始线段或终止线段的垂线。5.3 矢量数据的缓冲区分析线要素494）在各点角平分线的延长线上用左右侧缓冲距离dl和dr确定各点的左右缓冲点位置。5）左右缓冲点顺序相连，构成左右缓冲边界的基本部分。6）在起点和终点处，以(dl+dr)为直径、以角平分线(垂线)为直径向外作外接半圆。7）将外接半圆与左右缓冲边界的基本部分相连，即为线状目标的缓冲区。50 角平分线的缺点：难以保证双线的等宽性，轴线转角尖锐的转折点将随缓冲距的
17、增大迅速远离轴线5.3 矢量数据的缓冲区分析线要素51（2）凸角圆弧法-基本思想：在轴线的两端用半径为缓冲距的圆弧拟合；在轴线转折点，判断该点的凹凸性，在凸侧用半径为缓冲距的圆弧拟合，在凹侧用与该点关联的两缓冲线的交点为对应缓冲点。5.3 矢量数据的缓冲区分析线要素52 优点：凸侧的缓冲线与轴线等宽，而凹侧的对应缓冲点位于凹角的角平分线上，因而最大限度地保证缓冲区边界与轴线的等宽关系。5.3 矢量数据的缓冲区分析线要素ArcGIS Online 上的线状缓冲区生成算法5.3 矢量数据的缓冲区分析线要素545.3 矢量数据的缓冲区分析特殊情况的缓冲区：指定不同线状目标的不同的缓冲区宽度；同一线状
18、目标两侧的缓冲区宽度也可以不一样；同一线状目标不同段的缓冲区宽度也可以不一样；线要素5.3 矢量数据的缓冲区分析线要素56 面目标可视为由边界线目标围绕而成。面目标缓冲区生成的基本思路与线目标缓冲器生成算法基本相同。面目标缓冲区：内侧缓冲区和外侧缓冲区 面状目标的缓冲区宽度可不一样，甚至同一面状目标内外侧的缓冲区宽度也可不一样。5.3 矢量数据的缓冲区分析面要素ArcGIS Online 上的面状缓冲区生成算法5.3 矢量数据的缓冲区分析面要素58 缓冲线生成过程中的特殊情况：缓冲线失真缓冲线自相交缓冲区重叠等5.3 矢量数据的缓冲区分析特殊缓冲区59 缓冲区失真问题 当轴线转角太大时，转角处
19、的缓冲线交点随缓冲距的增大容易出现失真问题。角平分线法造成的缓冲区失真角平分线法造成的缓冲区失真 按角平分线法得到的大转角处的缓冲线会出现缓冲区失真。由于B点的右转角太大，按照该算法得到的B点的左右缓冲点Bl和Br点均远离B点，使缓冲区宽度发生变异，这是不合理的。5.3 矢量数据的缓冲区分析特殊缓冲区采用凸角圆弧法,下面线状要素的缓冲区会失真吗？dd5.3 矢量数据的缓冲区分析特殊缓冲区61 缓冲线自相交问题 当轴线的弯曲空间不能容许缓冲区边界自身无压覆地通过时，缓冲线将产生自相交现象，并形成多个自相交多边形：岛屿多边形保留 重叠多边形删除 识别是岛屿多边形还是重叠多边形是缓冲线自相交处理的关
20、键。5.3 矢量数据的缓冲区分析特殊缓冲区62（3）缓冲区重叠问题 指不同目标的缓冲区之间的重叠 对于这种重叠，首先通过拓扑分析方法自动识别出重叠的线段，然后删除，最后得到处理后的相互连通的缓冲区。5.3 矢量数据的缓冲区分析特殊缓冲区63u河网缓冲区的例子：河网不同部位的缓冲区相互重叠，缓冲区不能以简单多边形表示。必须计算出所有的重叠，通过一系列判断产生一个复杂多边(含洞)形或多边形集合表示的缓冲区。5.3 矢量数据的缓冲区分析特殊缓冲区64n 动态目标缓冲区 静态缓冲区：空间目标对邻近对象的影响呈现单一的距离关系。动态缓冲区：空间目标对邻近对象的影响呈现不同强度的扩散或衰减关系。如污染对周
21、围环境的影响呈现梯度变化。5.3 矢量数据的缓冲区分析特殊缓冲区65 动态缓冲区生成：不能简单地设定距离参数，需要根据空间目标的特点和要求选择合适的方法。动态缓冲区的生成针对两类特殊情况：流域问题 污染问题 5.3 矢量数据的缓冲区分析特殊缓冲区66 流域问题中的动态缓冲区生成问题：流域从上游的某一点出发沿流域下溯，河流的影响半径或流域辐射范围逐渐扩大；流域从下游的某一点出发沿流域上溯，河流的影响半径或流域辐射范围逐渐缩小。类似问题还有参数动态变化的运动目标的影响范围分析等。5.3 矢量数据的缓冲区分析特殊缓冲区67基于线目标的缓冲区生成算法：用分段处理的办法分别生成各流域分段的缓冲区，然后按
22、某种规则将各分段缓冲区光滑连接基于点目标的缓冲区生成算法：用逐点处理的办法分别生成沿线各点的缓冲圆，然后求出缓冲圆序列的两两外切线，所有外切线相连。流域问题中的动态缓冲区生成问题：5.3 矢量数据的缓冲区分析特殊缓冲区68 污染问题中的动态缓冲区生成 污染源对邻近对象的影响程度随距离的增大而逐渐缩小。可根据物体对周围空间影响度变化的性质，引入一个影响度参数来确定缓冲区半径的动态变化。生成动态缓冲区的类似问题：城市辐射影响分析、矿山开采影响分析等。5.3 矢量数据的缓冲区分析特殊缓冲区5.3 矢量数据的缓冲区分析特殊缓冲区5.3 矢量数据的缓冲区分析特殊缓冲区思考题：生成动态缓冲区常用的分析模型
23、有哪些？5.4 矢量数据的叠置分析 在统一的空间坐标系下，将同一地区的两个或两个以上的地理要素图层进行叠置，产生空间区域的多种属性特征的分析方法。大部分GIS软件是以分层的方式组织地理景观，将地理景观按主题分层存取。123AB1A2B3B栅格数据的叠置分析矢量数据的叠置分析点线面点线面矢量数据的叠置分析包括以下6种类型：75n点与点的叠置 含义：把一个图层上的点与另一个图层上的点进行叠置，为图层内的点建立新的属性，同时对点的属性进行统计分析。实现：通过不同图层间的点的位置和属性关系完成，得到一张新属性表，属性表示点之间的关系。76 城市中网吧与学校的叠置及相应的属性表，从中可判断网吧与学校的距
24、离。77n 点与线的叠置 含义：一个图层上的点目标与另一图层上的线目标进行叠置，为图层内的点和线建立新的属性。应用：叠置分析的结果可用于点和线的关系分析，如计算点与线的最近距离。78 城市与高速公路叠置分析 可以分析城市与高速公路之间的关系、高速公路的分布情况等。79n 点与多边形的叠置 含义：实际上是计算多边形对点的包含关系。将一个含有点的图层叠加到另一个含有多边形的图层上，以确定每个点落在哪个多边形内。80 实现：通过点在多边形内的判别完成，通常得到一张新属性表，包含：原属性 落在那个多边形的目标标识 还可以从多边形属性表中提取一些附加属性 应用：如油井与行政区划叠置：可以得到油井本身的属
25、性如井位、井深、出油量，还可以得到行政区划的属性，如目标标识、行政区名称、行政区首长姓名等。81n 线与线的叠置 含义：一个图层上的线与另一图层的线叠置，分析线之间的关系，为图层中的线建立新的属性关系。应用：如河流与公路的叠置分析结果，可以分析水陆交通运输的分布情况。82n 线与多边形的叠置 含义：将线的图层叠置在多边形的图层上，以确定一条线落在哪一个多边形内。实现：比较线上坐标与多边形坐标的关系，判断线是否落在多边形内。83 线目标跨越多个多边形：先进行线与多边形边界的求交，将线目标进行切割，对线段重新编号，形成新的空间目标的结果集，同时产生一个相应的属性数据表记录原线和多边形的属性信息。根
26、据叠置的结果可以确定每条弧段落在哪个多边形内，查询指定多边形内指定线穿过的长度。84 应用：公路线图层与县城图层进行叠加分析 可以回答每个县所包含的公路里程等问题。若线状图层为河流，叠置的结果是多边形将穿过它的所有河流分割成弧段。查询多边形内的河流长度，进而计算河流密度。85n 多边形与多边形的叠置 含义：指同一地区、同一比例尺的两组或两组以上的多边形要素进行叠置。参加叠置分析的图层都是矢量数据。多层叠置：两两叠置后再与第三层叠置，依次类推。被叠置的多边形为本底多边形；用来叠置的多边形为上覆多边形；叠置后产生具有多重属性的新多边形。86 实现：将两层多边形的边界全部进行边界求交运算和切割；然后
27、根据切割的弧段重建拓扑关系；最后判断新叠置的多边形分别落在原始多边形层的哪个多边形内，建立叠置多边形与原多边形的关系，如果必要再抽取属性。87 基本处理方法：根据两组多边形边界的交点来建立具有多重属性的多边形地图内容的合成叠置。进行多边形范围内的属性特性的统计分析地图内容的统计叠置。88 合成叠置的目的：通过区域多重属性的模拟，寻找和确定同时具有几种地理属性的分布区域。或者按照确定的地理目标，对叠置后产生的具有不同属性多边形进行重新分类或分级，叠置的结果为新的多边形数据文件。89统计叠置的目的：准确地计算一种要素(如土地利用)在另一种要素(如行政区域)的某个区域多边形范围内的分布状况和数量特征
28、(包括拥有的类型数、各类型的面积以及所占总面积的百分比等)，或提取某个区域范围内某种专题内容的数据。5.4 矢量数据的叠置分析图层擦除（Erase）识别叠加（Identity）交集操作（Intersect）对称差值（Symmetrical difference）图层合并（Union）修正更新（Update）叠置分析的基本方法 图层擦除（Erase）是指输入图层根据擦除图层的范围大小，将擦除参照图层所覆盖的输入图层内的要素去除，最后得到剩余的输入图层的结果。从数学的空间逻辑运算的角度来说，即 （即 且 ，A为输入图层，B为擦除层）AABxAxB图层擦除5.4 矢量数据的叠置分析多边形与多边形点与
29、多边形线与多边形图层擦除5.4 矢量数据的叠置分析 识别叠加（Identity）是指输入图层和另外一个图层进行识别叠加，在图形交迭的区域，识别图层的属性将赋给输入图层在该区域内的地图要素，同时也有部分的图形的变化在其中。识别叠加5.4 矢量数据的叠置分析多边形与多边形点与多边形线与多边形交集操作5.4 矢量数据的叠置分析 交集操作（Intersect）是得到两个图层的交集部分，并且原图层的所有属性将同时在得到的新的图层上显示出来。在数学运算上表现如:（A,B分别是进行交集的两个图层）xAB点与多边形点与点点与线线与线交集操作5.4 矢量数据的叠置分析对称差值5.4 矢量数据的叠置分析在矢量的叠
30、置分析中也有为了获得两个图层去掉它们之间的公共部分，而只需要剩下的部分，同时对原有图层的空间上的分布也进行一定区域内的调整，新生成的图层的属性也是综合两者的属性而产生的。利用数学的空间逻辑运算的方式表示就是：（A,B分别是进行交集的两个图层）()xABAB修正更新5.4 矢量数据的叠置分析修正更新是指首先对输入的图层和修正图层进行几何相交的计算，然后输入的图层被修正图层（一般为多边形）覆盖的那一部分的属性将被修正图层而代替。而且如果两个图层均是多边形要素的话，那么两者将进行合并，并且重叠部分将被修正图层所代替，而输入图层的那一部分将被擦去。修正更新5.4 矢量数据的叠置分析点与多边形线与多边形
31、多边形与多边形5.4 矢量数据的网络分析问题的引入问题1：从武汉大学到武昌火车站有很多条路线，那条线路的所需要的时间最短？问题2：城市绿地（公园）一般离住宅小区的距离不超过15分钟的路程以内，如何建设可以在达到成本最小的同时满足全市小区的需求？问题3：武汉大学信息学部在什么地方？5.5 矢量数据的网络分析 网络分析网络分析是通过模拟、分析网络状态以及资源在网络上的流动和分配等，研究网络结构、流动效率及网络资源等的优化问题。网络分析网络分析是对地理网络和城市基础设施网络等网状事物以及它们的相互关系和内在联系进行地理分析。人类活动总是趋向于按一定目标选择达到最佳效果的空间位置。101n GIS中的
32、网络具有图论中网络的边、节点、拓扑等特征。还具有空间定位上的地理意义、目标复合上的层次意义和地理属性意义。如交通网络中除道路网络外，还涉及车站、路况、通行能力等。102n GIS中网络的组成1）线状要素 链、弧段 有形的：街道、河流、水管、电缆线 无形的：无线通讯网络2）点状要素 结点（障碍点、拐角点）、中心、站点结点：网络的交汇点。可能属性：阻抗强度、资源需求量。中心：接受或分配资源的位置。可能属性：阻抗强度、资源容量。站点：资源的增减点。可能属性：阻抗强度、资源需求量。n GIS中网络的组成1）几何属性2）拓扑关系（结点弧段拓扑关系）3）特殊属性（阻抗强度、资源容量、资源需求量）网络流量：
33、网络上从起点到终点的某个函数，如运输价格、运输时间等。104n 网络分析的主要目的选择最佳路径选择最佳布局中心位置n 网络分析中的距离n 网络分析的常见问题地址匹配资源分配路径分析地址匹配 对地理位置的查询，涉及到地址的编码。地址匹配与其它网络分析功能结合起来，可以满足实际工作中非常复杂的分析要求。最短路径静态最佳路径N条最佳路径动态最佳路径路径分析 资源分配模型由中心点(分配中心)及其状态属性和网络组成。分配方式包括：由分配中心向四周输出 由四周向中心集中资源分配选址功能是指在一定约束条件下、在某一指定区域内选择设施的最佳位置，它本质上是资源分配分析的延伸。最佳选址n路径分析问题 网络：网络
34、的每一条弧段都有一个权值，表示弧段连接的两结点间阻抗值。权值：正值 负值GIS中的一般最短路径问题都不涉及负回路的情况，因此以下所有的讨论中假定弧的权都为非负值。n 最短路径 路径分析是网络分析的核心问题，是对最佳路径的求解，即在指定网络的两个节点之间找一条阻抗强度最小的路径。最短路径算法是路径分析问题的基础，其表述如下：若的权wij表示节点vi和vj间的长度，在vi和vj之间的所有路径中，寻求长度最小的路径，称为从vi到vj的最短路径。*长度 时间、费用、路线、距离、流量等等 在欧氏空间En中，设x,y,z为任意三点，令d(x,y)为xy的距离，则有：),(),(),(yzdzxdyxd当且
35、仅当z在x、y的连线上时等式成立。n 最短路径问题的数学表达 类似的，令dk为节点vk到vj的最短距离，wij为vi到vj的权值，对于 的结点对，令 ，显然：Evvji),(ijwpkj wdddjkjk,.,3,2,01当且仅当(vj,vk)在v1到vk的最短路径上时，等式成立。dk是从v1到vk的最短路径，设该路径的最后一段弧为(vj,vk)，wjk为vj到vk的权值，由局部与整体的关系，该路径的前一段，即v1到vj的路径也必须为从v1到vj的最短路径。用公式可表达为：jkpkjwdddjkjk;,.,),min(3201 这就是最短路径方程，然而直接求解此方程比较困难。目前几乎所有的最短
36、路径的算法都是如何解这个方程的问题。n 最短路径问题的数学表达广度优先（BFS）n 最短路径问题的求解深度优先（DFS）n广度优先算法n 最短路径问题的求解Dijkstra算法Floyd-Warshall算法Bellman-Ford算法A*算法SPFA算法边无负权值可以处理负权nDijkstra算法 Dijkstra算法是E.W.Dijkstra于1959年提出的，是一种按路径长度递增的次序产生最短路径的算法。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示在城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。此算法被公认为是
37、解决此类最短路径问题最经典、也是比较有效的算法。假设每个点都有一对标号:(dj,pj)，dj是从源点s到该点j的最短路径的长度，pj是从s到j的最短路径中的j点的前一点。求解从源点s到各点j的最短路径算法的基本过程如下，这种方法也称标号法或染色法。(1)初始化：初始化：起源点：ds=0，ps为空；其它点 j：将起源点k标号，并加入标号点集合S，记S=k，而其它点尚未处理。nDijkstra算法nDijkstra算法(2)距离计算：距离计算：检验从所有标记的点k到其它直接连接的未标记的点j的距离，并设置：,minkjkjjldddlkj是从点k到j的直接连接距离。nDijkstra算法(4)找到
38、点找到点i的前一点的前一点 从已标记的点中找到直接连接到点i的点j*，将其作为前一点。(5)标记点标记点i 如果所有点已标记，则算法完全退出，否则记k=i，转到第2步再继续执行。(3)选取下一个点选取下一个点 从节点中选取dj最小的连接点i：di=min dj,所有未标记点j，点i为最短路径中的下一个点，并标记。nDijkstra算法示例V1V3V4V5V21006030102050105V0终点从V0到各终点的距离值和最短路径的求解过程i=1i=2i=3i=4V1V2V3V4V5VjS初始化：ds=0,ps=nullk=V0V2(V0,V2)V4(V0,V2,V4)V3(V0,V2,V3,V
39、4)V5(V0,V2,V3,V4,V5)(10,V0)（30,V0）（100,V0）（60,V2）（30,V0）（100,V0）（50,V4）（90,V4）（60,V3）nDijkstra算法示例V1V3V4V5V21006030102050105V0终点从V0到各终点的距离值和最短路径的求解过程i=1i=2i=3i=4V1V2V3V4V5(10,V0)（30,V0）（50,V4）（60,V3）1.function Dijkstra（G,w,s）2.for each vertex v in VG /初始化3.dv:=/将各点的已知最短距离先设置成无穷大 4.previousv:=null /各
40、点的已知最短路径上的前趋都未知 5.ds:=0 /因为出发点到出发点间不需移动任何距离，所以可以直接将s 到s的最小距离设为0 6.S :=empty set 7.Q:=set of all vertices 8.while Q is not an empty 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.previou
41、sv:=u /记录前一个顶点 如果求s到t的最短路径，则加入以下判断即可 if u=t breaknDijkstra算法Dijkstra算法的运行时间是 O(n2)。nA*算法 A*算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。在此算法中，g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离。因此，A*算法中的距离计算公式为：f(n)=g(n)+h(n)这个公式遵循以下特性：如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法如果h(n)=“n到目标的实际
42、距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低nA*算法（欧氏距离）n几种常用的空间距离计算方式1.41411.414111.41411.4142121121211111111Euclidean 距离Manhattan 距离Chebyshev 距离nA*算法（Manhattan距离）nA*算法（Chebyshev距离）n Floyd算法Dijkstra算法 Floyd-Warshall算法是一种多点对间最短路径的方法，该算法有效地利用了邻接矩阵。A*算法边无负权值，1-Nn Floyd算法基本思想是：递推地产生一个矩阵序列：M(0),M(1),M(2),M(n
43、)。其中，M(0)就是邻接矩阵，M(0)i,j等于从Vi到Vj的边的权值，即从Vi到Vj的路径上不经过任何中间顶点；M(k)i,j等于从顶点Vi到顶点Vj的路径上中间顶点序号不大于k的最短路径长度值(k=1,2,n)。n Floyd算法基本思想是：由于在具有n个顶点的有向网络中，任何一对顶点之间的最短路径上都不可能出现序号大于n的中间点。因此，矩阵元素M(n)i,j就等于从Vi到Vj的最短路径长度值。递推地产生M(0),M(1),M(2),M(n)的过程就是逐步允许越来越多的顶点作为路径上的中间顶点，直到所有顶点都允许作为中间顶点。n Floyd算法假设已求得矩阵M(k-1)，如何由它求M(k
44、)呢？从Vi到Vj的路径上中间点数不大于k的最短路径只有以下两种可能的情况：中间不经过顶点Vk。在这种情况下：M(k)i,j M(k-1)i,j在这种情况下，在最短路径中并没有增加节点。n Floyd算法中间经过顶点Vk。在这种情况下，M(k)i,jM(k-1)i,j 这条由Vi经Vk到达Vj的最短路径由两段组成：u一段是从Vi到Vk中间序号不大于k-1的最短路径，其长度为M(k-1)i,k；u另一段是从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,jn Floyd算法P
45、1P2P3P4P5P1146P24127P317P4341P5321邻接矩阵：n Floyd算法算法描述：Floyd 算法的运行时间是 O(n3)。n Floyd算法 在如图所示的有向网络中，M(k)1,2表示由节点1到节点2经过节点序号不大于k的最短路径。M(1)1,2,M(2)1,2,M(3)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)
46、1,5+M(4)5,2=min15,15,15,12=12。因此，从V1到V2的最短路径长度值为12。n次最短路径求解算法 在某些情况下，除了需要求出两个给点之间的最短路径之外，还可能需要求出这两点之间的次最短路径、第3短路径，第k短路径。可以在求出第1最短路径P1之后，用枚举法求出与P1有尽可能多公共边的次最短路径P2。算法的基本思路是：假定第1最短路径P1包含了n条有向弧，每次删除其中的一条弧，即得到n个与原来只有一弧之差的新的网络。按原最短路径算法分别求解这n个新网络的最短路径，然后比较这n条最短路径，其中最短的那条即为所求的次最短路径。依此进行，可以分别求出第3短路径，第k短路径。n最
47、佳路径算法 最佳路径是指网络两结点之间阻抗最小的路径。阻抗最小”有多种理解，如基于单因素考虑的时间最短、费用最低、风景最好、路况最佳、过桥最少、收费站最少、经过乡村最多等；n最佳路径算法最大可靠性路径 利用最短路径算法也可以求解最大可靠路径。具体方法是：定义网络D(V,A)中的每条弧aij(Vi,Vj)的权为：wij=lnpij因 ，所以 。从而可以用前述Dijkstra算法求出关于权wij的最短路径(Vi,Vj)。由于 ，所以，关于权的最短路径就是(Vi,Vj)的最大可靠路径，其完好概率为 。10ijp0ijW)ln(ijijpw)exp(ijwn最佳路径算法最大容量路径 设网络D(V,E,
48、W)中任意一条路径P的容量定义为该路径中所有弧的容量cij的最小值，即：则网络D(V,A)中所有(Vi,Vj)路径中的容量最大的路径即为(Vi,Vj)的最大容量路径。)(min)()(ijPEecPcij143 最优路径的求解有多种形式，如两点间最优路径、多点间指定顺序的最优路径、多点间最优顺序最优路径、经指定点回到起点的最优路径等。5.6 ArcGIS的矢量数据空间分析工具n 缓冲区分析 在ArcGIS中建立缓冲区的方法是基于生成多边形来实现的。ArcGIS根据给定的缓冲区距离，对点状、线状和面状要素的周围形成缓冲区多边形图层。ArcGIS提供三种缓冲区的建立方法，分别是普通缓冲区、属性权值
49、缓冲区和分级缓冲区。n 缓冲区分析普通缓冲区属性权值缓冲区分级缓冲区n 叠置分析 按照一定的数学模型对要素进行计算分析得出新属性，计算中通常涉及到逻辑交、逻辑并、逻辑差等运算。根据操作形式的不同，叠置分析可分为图层擦除、识别叠加、交集操作、对称区别、图层合并和修正更新等。图层擦除：在输入图层中擦除参考图层与输入图层相交的部分。识别叠加：输入图层与识别图层叠加，识别图层将其属性赋予两层相交的区域。交集操作：通过叠置处理得到两个图层的交集部分，并且原图层的所有属性将同时在得到的新图层上显示出来。对称区别：输入图层与参考图层叠加后去掉其公共区域。图层合并：指通过把两个图层的区域范围联合起来而保持来自
50、输入地图和叠加地图的所有地图要素。修正更新：输入图层与修正图层叠加，其公共部分被修正图层代替，输入图层的这部分被擦除。n 网络分析 ArcGIS的网络分析包括传输网络分析(Network Analyst)和效用网络分析(Utility Network Analyst)。传输网络分析常用于道路、地铁等交通网络的分析。传输网络是无向网络，具有主观选择方向的能力。用户可以自由定义网络中前进的方向、速度以及终点。例如：一个卡车司机可以决定在哪条道路上开始行进，在什么地方停止，采用什么方向。并且还可以给网络设置限定性规则，例如是单行线还是禁行。在ArcGIS中，传输网络通过网络数据集(Network D
