gis与空间分析.ppt

求最佳路径的步骤： 先找出起始结点并在路径中加入； 从剩余的结点中找距起始结点最近的顶点并加入路径； 重复步骤②，直至目的结点。 方法 ——最佳路径分析 方法 ——连通性分析 连通分析主要包括两方面的问题： 连通分量求解问题——分析从某一结点出发能够到达的全部结点或边； 最少耗费连通求解问题——即在耗费最小的情况下使全部结点相互连通。 方法 ——连通性分析 连通分析的求解——网络的遍历算法： 深度优先搜索（DFS）：假定图中某个顶点v1为出发点，首先访问出发点v1，然后任选一个v1的未访问过的邻接点v2，以v2为新的出发点继续前面的步骤，直至图中所有顶点被访问过。图的深度优先搜索是一个递归过程，类似于树的前序遍历，它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜索。  方法 ——连通性分析 ②广度优先搜索（BFS）：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其它顶点，直至所有顶点都被访问到。它类似于树的按层次遍历，其特点是尽可能优先对横向搜索，故称之为广度优先搜索。 方法 ——连通性分析 如下连通图的两种搜索方法： 方法 ——连通性分析 深度优先搜索 广度优先搜索 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往存在两种关系：①先后关系，即必须在一项目完成之后，才能开始实施另一个子项目；②子项目间无关系，即两个子项目可以同时进行，互不影响。 项目的实施可以构成一个有向图，现在要从这个有向图上找出一个施工流程图，以便顺利进行施工，解决这个问题可以采用拓扑排序的方法。 方法 ——拓扑排序 设G=（V，E）是一个具有n个顶点的有向图，V中顶点的序列V1，V2，Vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若在有向图G中，从顶点Vi到Vj有一条路径，则在序列中顶点Vi必须排在顶点Vj之前。 找一个有向图的一个拓扑序列的过程称为拓扑排序。  方法 ——拓扑排序 有向图拓扑排序算法的基本步骤：①从图中选择一个入度为0的顶点，输出该顶点；②从图中删除该顶点及其相关联的弧；③重复执行①、②直到所有顶点均被输出。可以证明，任何一个无环有向图，其全部顶点都可以排成一个拓扑序列。而且其拓扑序列不一定是唯一的。 方法 ——拓扑排序 以右图为例： 某施工工序的有 向图，对其进行 拓扑排序。 方法 ——拓扑排序 结果：对这个有向图进行拓扑排序可得到一个拓扑序列：C1，C2，C7，C6，C3，C4，C5。也可得到另一个拓扑序列C1，C7，C2，C3，C6，C4，C5。 资源分配就是为网络中的网线和结点寻找最近(这里的远近是按阻碍强度的大小来确定的)的中心(资源发散或汇集地)。 资源分配是模拟资源如何在中心(学校、消防站、水库等)和它周围的网线(街道、水路等)、结点(交叉路口、汽车中转站等)间流动的。根据中心容量以及网线和结点的需求将网线和结点分配给中心，分配是沿最佳路径进行的。 方法 ——资源分配 最佳路径分析： 各种应急系统（如110报警、119报警、122报警等）中的路径选择问题； 汽车导航系统中的应用； …… 应用 连通性分析： 判断某个城市的交通网、管道网、河流网等是否连通； 如何在最低消耗成本的条件下，将某城市的某种网络（如通信网、电网等）连通起来；…… 应用 拓扑排序： 为某工程的施工建立施工流程； 大学生的选课流程；…… 应用 资源分配： 某城市车站或机场的选址问题； 确定某商业中心或学校的服务范围；…… 应用 缓冲区分析可以对一组或一类地图要素按设定的距离，围绕这些要素形成具有一定范围的多边形实体，从而实现数据在二维空间扩展的信息分析。 小结 小结 网络分析在现实生活中应用非常广泛。它主要用来解决两大类问题：一类是研究由线状实体以及连接线状实体的点状实体组成的地理网络，其中涉及优化路径的求解、连同分量求解和拓扑排序等；一类是研究资源在网络系统中的分配与流动，主要包括资源分配范围或服务范围的确定等问题。 什么是缓冲区分析？其分类如何？ 什么是网络分析，其基础是什么？ 网络分析的功能有哪些？ 网络分析的主要方法有哪些？每种方法的求解是如何实现的？ 思考题 * * 第四章 GIS空间分析的一般方法 授课人:吴彩燕 2008年10月6日 §4.2 缓冲区分析 缓冲区分析的概念 缓冲区分析的分类 缓冲区分析的应用及实例 缓冲区分析（Buffer Analysis）是确定地物近邻影响的一种空间分析方法，是GIS 的基本空间操作的重要功能之一。 缓冲区是给定空间对象或集合后获得的它们的邻域，R为邻域的半径。 概念 缓冲区分析是指根据分析对象的点、线、面实体，自动